To understand how driverless cars might navigate the complexities of the road, researchers often use game theory — mathematical models that represent how rational agents act strategically to reach their goals.
Dejan Milutinovic, professor of electrical and computer engineering at UC Santa Cruz, has long worked with colleagues on a complex subset of game theory called differential games, which involve game players moving. One of these games is called the wall pursuit game, a relatively simple model for a situation where a faster pursuer has the goal of catching a slower evader who is confined in motion by a wall.
Since this game was first described nearly 60 years ago, there has been a dilemma within the game — a set of positions for which no game-optimal solution is thought to exist. But now, Milutinovic and his colleagues proved it in a new paper published in the journal IEEE Transactions on Automatic Control that this long-standing dilemma does not actually exist, and introduces a new analysis method that proves that there is always a deterministic solution to the wall pursuit game. This discovery opens the door to solving other similar challenges that exist in the field of differential games, and allows better reasoning about autonomous systems such as driverless cars.
Game theory is used to reason about behavior in 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 optimal game strategies for all players in the game to end the game with minimal regret. Any player who chooses not to play their optimal game strategy will lead to more regret, therefore, rational players are all motivated to play their equilibrium strategy.
This concept applies to the wall pursuit game — a classical pair of Nash equilibrium strategies for two players, the pursuer and the evader, describing their best strategy in almost all of their positions. However, there is a range of positions between pursuers and evaders where classical analysis fails to provide an optimal game strategy and ends up in a dilemma. This set of positions is known as a single surface — and for years, the research community accepted the dilemma as fact.
But Milutinovic and his co-authors weren’t willing to accept it.
“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 singular surfaces where you don’t know how to behave efficiently — and then we just don’t know what the implications of that are going to be in more complex games.”
So Milutinovic and his co-authors came up with a new way to approach the problem, using a mathematical concept that didn’t exist when the wall pursuit game was originally conceived. By using the viscosity solution of the Hamilton-Jacobi-Isaacs equation and introducing the rate of loss analysis for solving the singular surface, they found that a game optimal solution can be determined for all instances of the game and solve dilemma.
The viscosity solution of the partial differential equation is a mathematical concept that did not exist until the 1980s and offers a unique line of reasoning about the solution of the Hamilton-Jacobi-Isaacs equation. The concept is now known to be 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 optimal game 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 a dilemma.
Often when there is a dilemma, a practical strategy is for the players to randomly choose one of the possible actions and accept the losses resulting from these decisions. But here’s the catch: if there is a loss, every reasonable player wants to minimize it.
So to find out how players can minimize their losses, the authors analyzed the viscous solution of the Hamilton-Jacobi-Isaacs equation around a singular surface where the derivatives are not well defined. Then, they introduce a loss assessment rate in the singular states over the equation. They found that when each actor minimizes its loss rate, there are well-defined game strategies for their actions on the same surface.
The authors find that this loss minimization rate not only determines the game’s optimal action for the singular surface, but also agrees with the game’s optimal action in every possible state where classical analysis also finds these actions.
“When we take the analysis of the loss rate and apply it elsewhere, the optimal action in the game from the classical analysis will not be affected,” said Milutinovic. “We take the classical theory and we add it to the rate of loss analysis, so a solution exists everywhere. This is an important result that shows that scaling is not just a fix to find a solution on a singular surface, but a major contribution to game theory.
Milutinovic and his co-authors are interested in exploring other game theory problems with singular surfaces to which their new method can be applied. The paper is also an open call to the research community to examine other dilemmas as well.
“Now the question is, what kind of other dilemmas can we solve?” Milutinovic said.