To understand how driverless cars navigate the complexities of the road, researchers often use game theory—mathematical models that represent the strategic behavior of rational agents to achieve their goals.
Dejan Milutinovic, a 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 that deal with players on the move. One of these games is called the wall chase game, a relatively simple model of a situation in which a faster chaser aims to catch a slower dodger who is constrained to move along a wall.
Since this game was first described nearly 60 years ago, there has been a dilemma in the game, a series of positions where it was believed that there was no optimal solution to the game. But now Milutinovic and his colleagues have proved it in a new paper published in the journal IEEE Transactions on Automatic Control that this long-term dilemma does not actually exist, and presented a new analysis method that proves that there is always a deterministic solution to the wall-chasing game. This discovery opens the door to solving other similar challenges in the field of differential gaming and enables better reasoning about autonomous systems such as driverless cars.
Game theory is used to reason about behavior in various fields, such as economics, political science, computer science, and engineering. Nash equilibrium is one of the most popular concepts in game theory. The concept was introduced by mathematician John Nash and it defines the optimal game strategy for all players in the game to complete the game with the least amount of regret. Any player who chooses not to play their optimal game strategy will regret more, so rational players are all motivated to play their equilibrium strategy.
This concept applies to the wall chase game, a classic Nash equilibrium strategy pair for two players, a chaser and an evader, that describes their best strategy in almost every position. However, there are a number of positions between pursuer and evader for which classical analysis fails to provide optimal game strategies and ends up in a dilemma. This set of positions is known as the unique surface, and for years the research community has accepted the dilemma as fact.
But Milutinovic and his co-authors didn’t want to admit it.
“This worried us because we thought that if the evader knows there is a unique surface, there is a risk that the evader could go to the unique surface and abuse it,” Milutinovic said. “A dodger can force you to go to a unique surface where you don’t know how to behave optimally, and then we just don’t know what that means in much 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-chasing game was originally created. Using the viscosity solution of the Hamilton-Jacobi-Isaacs equation and introducing loss rate analysis to solve the singular surface, they were able to find that the optimal game solution can be determined under all game circumstances and solve the dilemma.
The viscosity solution of partial differential equations is a mathematical concept that did not exist until the 1980s and offers a unique line of reasoning for solving the Hamilton–Jacobi–Isaacs equation. It is now well known that the concept is relevant to reasoning about problems in optimal control and game theory.
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 solutions to the game when the viscosity solution associated with the game has well-defined derivatives. This cannot be said for the wall chase game, and this lack of well-defined derivations creates a dilemma.
Usually, when faced with a dilemma, the practical approach is for the players to randomly choose one of the possible actions and accept the losses resulting from those decisions. But here’s the catch. if there is a loss, every rational player will want to minimize it.
Thus, to find out how players can minimize their losses, the authors analyzed the viscosity solution of the Hamilton-Jacobi-Isaacs equation around a singular surface where the derivatives are not well defined. They then presented an analysis of the loss rate at these unique surface states in Eq. They found that when each player minimizes their loss rate, there are well-defined playing strategies for their actions on a unique surface.
The authors found that not only does this rate of loss reduction define the game’s optimal actions for a unique surface, but it also coincides with the game’s optimal actions in every possible state where classical analysis can also find those actions.
“When we take the loss rate analysis and apply it elsewhere, the optimal actions of the game from the classical analysis are not affected,” Milutinovic said. “We take classical theory and add it to loss analysis, so the solution exists everywhere. This is an important result that shows that scaling is not just a solution to finding a solution on a singular surface, but a fundamental contribution. to game theory.
Milutinovic and his co-authors are interested in other game theory problems involving singular surfaces where their new method could be applied. The paper is also an open call to the research community to explore other similar dilemmas.
“Now the question is: what other dilemmas can we solve?” Milutinovich said.