Researcher solves nearly 60-year-old game theory dilemma

To understand how driverless vehicles can navigate the complexity of the road, researchers often use game theory – mathematical models that represent how rational agents behave strategically to achieve their goals.

Dejan Milutinovic, a 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, that involves moving players. One such game is called the Wall Chase Game, a relatively simple model for a situation where a fast pursuer’s goal is to catch a slower dodger who is constrained to moving along a wall.

Ever since this game was first described almost 60 years ago, there has been a dilemma within the game – a series of positions where it was felt that there was no optimal solution to the game. But now Milutinovic and his colleagues have proved it in a new article published in the journal IEEE transactions for automatic control that this long-standing dilemma does not really exist, and introduced a new analysis method that proves that there is always a deterministic solution to the wall chase game. This discovery opens the door to solving other similar challenges that exist in the field of differential backlash and allows better reasoning about autonomous systems such as driverless vehicles.

Game theory is used to think about behavior in a variety of fields such as economics, political science, computer science, and engineering. Within game theory, the Nash equilibrium is one of the most widely recognized concepts. Introduced by mathematician John Nash, the concept defines game-optimal strategies for all players in the game to end the game with the fewest regrets. Any player who decides not to play their optimal playing strategy will end up with more regrets, 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 the two players, the pursuer and the dodger, describing their best strategy in almost all of their positions. However, there are a number of positions between the pursuer and the dodger for which the classical analysis does not provide optimal game strategies and ends with the existence of the dilemma. This series of positions is known as the singular surface – and for years the research community has accepted the dilemma as fact.

But Milutinovic and his co-authors did not want to accept that.

“That bothered us because we thought that if the scammer knows that there is a singular surface, there is a risk that the scammer can go to the singular surface and abuse it,” Milutinovic said. “The outlier can force you to go to the unique surface where you don’t know how to behave optimally – and then we just don’t know what impact that would have on much more complicated 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 Chase game was originally conceived. By using the viscosity solution of the Hamilton-Jacobi-Isaacs equation and introducing loss rate analysis to solve the singular surface, they were able to determine that a game-optimal solution can be determined under all circumstances of the game, 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 reasoning to solve the Hamilton-Jacobi-Isaacs equation. It is now well known that the concept is relevant to considerations of optimal control and game theory problems.

Using viscosity solutions, which are functions, to solve game theoretic problems involves using calculus to find the derivatives of these functions. It is relatively easy to find game-optimal solutions if the viscosity solution associated with a game has well-defined derivatives. This is not the case with the Wall Pursuit game, and this lack of well-defined derivations creates the dilemma.

When faced with a dilemma, a practical approach is usually for players to randomly select one of the possible actions and accept losses resulting from those choices. But here’s the catch: when there’s a loss, any rational player will want to minimize it.

So, to find out how players could 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 loss rate analysis over these individual surface states of the equation. They found that when each actor minimizes its loss rate, there are well-defined game strategies for their actions on the singular surface.

The authors found that this loss rate minimization not only defines the game-optimal actions for the singular surface, but also agrees with the game-optimal actions in every possible state where classical analysis can also find those actions.

“If we take loss rate analysis and apply it elsewhere, it doesn’t affect the game’s optimal actions from classical analysis,” Milutinovic said. “We take the classical theory and extend it with loss rate analysis so that a solution exists everywhere. This is an important result showing that augmentation is not just a fix to find a solution on the singular surface but a fundamental contribution to game theory.

Milutinovic and his co-authors are interested in investigating other game-theoretic problems with singular surfaces where their new method could be applied. The paper is also an open call for the research community to explore other dilemmas in a similar way.

“Now the question becomes, what kind of other dilemmas can we solve?” said Milutinovic.