MSGID: 1:317/3 641149f7   
   PID: hpt/lnx 1.9.0-cur 2019-01-08   
   TID: hpt/lnx 1.9.0-cur 2019-01-08   
    Researcher solves nearly 60-year-old game theory dilemma    
      
     Date:   
         March 14, 2023   
     Source:   
         University of California - Santa Cruz   
     Summary:   
         A researcher has solved a nearly 60-year-old game theory dilemma   
         called the wall pursuit game, with implications for better reasoning   
         about autonomous systems such as driver-less vehicles.   
      
      
         Facebook Twitter Pinterest LinkedIN Email   
   FULL STORY   
   ==========================================================================   
   To understand how driverless vehicles can navigate the complexities   
   of the road, researchers often use game theory -- mathematical models   
   representing the way rational agents behave strategically to meet   
   their goals.   
      
      
   ==========================================================================   
   Dejan Milutinovic, professor of electrical and computer engineering at   
   UC Santa Cruz, has long worked with colleagues on the complex subset   
   of game theory called differential games, which have to do with game   
   players in motion. One of these games is called the wall pursuit game,   
   a relatively simple model for a situation in which a faster pursuer has   
   the goal to catch a slower evader who is confined to moving along a wall.   
      
   Since this game was first described nearly 60 years ago, there has been   
   a dilemma within the game -- a set of positions where it was thought that   
   no game optimal solution existed. But now, Milutinovic and his colleagues   
   have proved in a new paper published in the journalIEEE Transactions on   
   Automatic Controlthat this long-standing dilemma does not actually exist,   
   and introduced a new method of analysis that proves there is always a   
   deterministic solution to the wall pursuit game. This discovery opens the   
   door to resolving other similar challenges that exist within the field   
   of differential games, and enables better reasoning about autonomous   
   systems such as driverless vehicles.   
      
   Game theory is used to reason about behavior across a wide range of   
   fields, such as economics, political science, computer science and   
   engineering. Within game theory, the Nash equilibrium is one of the most   
   commonly recognized concepts. The concept was introduced by mathematician   
   John Nash and it defines game optimal strategies for all players in the   
   game to finish the game with the least regret. Any player who chooses   
   not to play their game optimal strategy will end up with more regret,   
   therefore, rational players are all motivated to play their equilibrium   
   strategy.   
      
   This concept applies to the wall pursuit game -- a classical Nash   
   equilibrium strategy pair for the two players, the pursuer and   
   evader, that describes their best strategy in almost all of their   
   positions. However, there are a set of positions between the pursuer and   
   evader for which the classical analysis fails to yield the game optimal   
   strategies and concludes with the existence of the dilemma. This set of   
   positions are known as a singular surface -- and for years, the research   
   community has accepted the dilemma as fact.   
      
   But Milutinovic and his co-authors were unwilling to accept this.   
      
   "This bothered us because we thought, if the evader knows there is a   
   singular surface, there is a threat that the evader can go to the singular   
   surface and misuse it," Milutinovic said. "The evader can force you to   
   go to the singular surface where you don't know how to act optimally --   
   and then we just don't know what the implication of that would be in much   
   more complicated games."  So Milutinovic and his coauthors came up with   
   a new way to approach the problem, using a mathematical concept that was   
   not in existence when the wall pursuit game was originally conceived. By   
   using the viscosity solution of the Hamilton-Jacobi-Isaacs equation and   
   introducing a rate of loss analysis for solving the singular surface   
   they were able to find that a game optimal solution can be determined   
   in all circumstances of the game and resolve the dilemma.   
      
   The viscosity solution of partial differential equations is a mathematical   
   concept that was non-existent until the 1980s and offers a unique line of   
   reasoning about the solution of the Hamilton-Jacobi-Isaacs equation. It is   
   now well known that the concept is relevant for reasoning about optimal   
   control and game theory problems.   
      
   Using viscosity solutions, which are functions, to solve game theory   
   problems involves using calculus to find the derivatives of these   
   functions. It is relatively easy to find game optimal solutions   
   when the viscosity solution associated with a game has well-defined   
   derivatives. This is not the case for the wall-pursuit game, and this   
   lack of well-defined derivatives creates the dilemma.   
      
   Typically when a dilemma exists, a practical approach is that players   
   randomly choose one of possible actions and accept losses resulting   
   from these decisions. But here lies the catch: if there is a loss,   
   each rational player will want to minimize it.   
      
   So to find how players might minimize their losses, the authors analyzed   
   the viscosity solution of the Hamilton-Jacobi-Isaacs equation around   
   the singular surface where the derivatives are not well-defined. Then,   
   they introduced a rate of loss analysis across these singular surface   
   states of the equation.   
      
   They found that when each actor minimizes its rate of losses, there are   
   well- defined game strategies for their actions on the singular surface.   
      
   The authors found that not only does this rate of loss minimization   
   define the game optimal actions for the singular surface, but it is also   
   in agreement with the game optimal actions in every possible state where   
   the classical analysis is also able to find these actions.   
      
   "When we take the rate of loss analysis and apply it elsewhere, the   
   game optimal actions from the classical analysis are not impacted ,"   
   Milutinovic said. "We take the classical theory and we augment it with   
   the rate of loss analysis, so a solution exists everywhere. This is an   
   important result showing that the augmentation is not just a fix to find   
   a solution on the singular surface, but a fundamental contribution to   
   game theory.   
      
   Milutinovic and his coauthors are interested in exploring other game   
   theory problems with singular surfaces where their new method could be   
   applied. The paper is also an open call to the research community to   
   similarly examine other dilemmas.   
      
   "Now the question is, what kind of other dilemmas can we   
   solve?" Milutinovic said.   
      
       * RELATED_TOPICS   
             o Matter_&_Energy   
                   # Albert_Einstein # Nature_of_Water #   
                   Automotive_and_Transportation # Engineering   
             o Computers_&_Math   
                   # Video_Games # Artificial_Intelligence #   
                   Educational_Technology # Mathematical_Modeling   
       * RELATED_TERMS   
             o Game_theory o Computer_and_video_games o   
             Massively_multiplayer_online_game o Full_motion_video o   
             Pac-Man o John_von_Neumann o Battery_electric_vehicle o   
             Constructal_theory   
      
   ==========================================================================   
   Story Source: Materials provided by   
   University_of_California_-_Santa_Cruz. Original written by Emily   
   Cerf. Note: Content may be edited for style and length.   
      
      
   ==========================================================================   
   Journal Reference:   
      1. Dejan Milutinovic, David W. Casbeer, Alexander Von Moll, Meir   
      Pachter,   
         Eloy Garcia. Rate of Loss Characterization That Resolves the   
         Dilemma of the Wall Pursuit Game Solution. IEEE Transactions on   
         Automatic Control, 2023; 68 (1): 242 DOI: 10.1109/TAC.2021.3137786   
   ==========================================================================   
      
   Link to news story:   
   https://www.sciencedaily.com/releases/2023/03/230314205331.htm   
      
   --- up 1 year, 2 weeks, 1 day, 10 hours, 50 minutes   
    * Origin: -=> Castle Rock BBS <=- Now Husky HPT Powered! (1:317/3)   
   SEEN-BY: 15/0 106/201 114/705 123/120 153/7715 226/30 227/114 229/110   
   SEEN-BY: 229/111 112 113 307 317 400 426 428 470 664 700 292/854 298/25   
   SEEN-BY: 305/3 317/3 320/219 396/45   
   PATH: 317/3 229/426