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)