To understand how self-driving vehicles can navigate the complexities of the road, researchers often use game theory — mathematical models that represent the way rational agents act strategically 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, which relates to moving players. One such game is called the wall game, which is a relatively simple model of a situation in which a faster stalker has the goal of catching a slower evader who is limited to moving along the wall.
Since this game was first described nearly 60 years ago, there has been a dilemma within the game – a set of situations where it was thought that there was no perfect solution to the game. But now, Milutinovic and his colleagues prove it in a new research paper published in the journal IEEE Transactions on Automation Control that this longstanding dilemma does not actually exist, and provided a new method of analysis proving that there is always a definite solution to the wall chase game. This discovery opens the door to solving other similar challenges that exist in the field of differential games, and allows for better thinking about autonomous systems such as self-driving 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 popular concepts. This concept was introduced by mathematician John Nash and it identifies optimal game strategies for all players in the game to end the game with the least amount of regret. Any player who chooses not to play their optimal strategy will end up with more regret, and thus, all rational players have an incentive to play their balancing strategy.
This concept applies to the game Chasing the Wall – a classic Nash balance strategy for two players, the pursuer and the evader, which best describes their strategy in almost all of their positions. However, there is a set of situations between the pursuer and the evader that classical analysis fails to achieve optimal strategies for the game and ends up with the dilemma. This set of situations is known as the single surface—and for years, the research community accepted the dilemma as fact.
But Milutinović and his comrades were not ready to accept that.
“This bothered us because we thought that if the slacker knows there is a single deck, there is a threat that the slacker could go to the single deck and misuse it,” Milutinovic said. “A slacker can force you into the single deck where you don’t know how to act optimally – and then we don’t know what effect that has in more complex games.”
So Milutinovic and his colleagues came up with a new way to approach the problem, using a mathematical concept that didn’t exist when the wall chase game was originally designed. Using the viscosity solution of the Hamilton-Jacobi-Isaacs equation and providing a loss rate analysis for the single surface solution, they were able to find an optimal game solution that can be determined under all game conditions and solve the dilemma.
The viscoelastic solution of partial differential equations is a mathematical concept that did not exist until the 1980s and provides a unique line of thinking about the solution of the Hamilton-Jacobi-Isaac equation. It is now known that the concept is relevant for thinking about optimal control and game theory problems.
Using solutions of viscosity, 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 for the game when the viscosity solution associated with the game has well-defined derivatives. This is not the case for wall chase, and this lack of well-defined derivatives creates the dilemma.
Usually when a dilemma arises, the practical approach is for the players to randomly choose one of the possible actions and accept the losses that result from these decisions. But here’s the catch: If there is a loss, every rational player will want to minimize it.
To see how players can reduce their losses, the authors analyzed the viscoelastic solution of the Hamilton-Jacoby-Isaacs equation about the single surface where the derivatives are not well defined. Next, they introduced loss rate analysis across these single surface states of Eq. They find that when each actor minimizes their loss rate, there are well-defined play strategies for their actions on the individual surface.
The authors found that this loss reduction rate not only determined optimal game actions for the single deck, but was also consistent with optimal game actions in every possible case where classical analysis would also be able to find these actions.
“When we take the loss rate analysis and apply it elsewhere, the optimal actions of the game from classical analysis are not affected,” Milutinovic said. “We take classical theory and augment it with loss rate analysis, so there is a solution everywhere. This is an important result that shows that augmentation is not just a solution to finding a solution on the individual surface, but an essential contribution to game theory.
Milutinovic and colleagues are interested in exploring other game theory problems with single surfaces where their new method can be applied. The paper is also an open invitation to the research community to similarly examine other dilemmas.
The question now is, what kind of other dilemmas can we solve? Milutinovic said.
