Researcher solves nearly 60-year-old game theory dilemma

Researchers frequently use game theory—mathematical models that reflect the way logical actors conduct tactically to achieve their goals—to better understand how autonomous vehicles can negotiate the intricacies of the road.

Dejan Milutinovic, a professor of electrical and computer engineering at UC Santa Cruz, has long collaborated with others on differential games, a challenging branch of game theory that deals with moving participants. The wall chase game is one of these games, which is a fairly straightforward example for a scenario in which a faster pursuer seeks to capture a slower evader who is restricted to moving along a wall.

There has been a dilemma within the game ever since it was first defined nearly 60 years ago—a collection of situations where it was believed that there was no place for which there was an optimal game play. However, Milutinovic and his coworkers have now disproved this enduring conundrum in a new article released in the journal IEEE Transactions on Automatic Control and presented a new technique of analysis that demonstrates there is always a deterministic solution to the wall pursuit game. This finding makes it possible to solve additional problems of a similar nature in the study of differential games and improves our ability to think about automated systems like driverless cars.

Many different disciplines, including economics, political science, computer science, and engineering, use game theory to explain behavior. The Nash equilibrium is one of the most well-known ideas in game theory. Mathematician John Nash developed the idea, which outlines the best game-playing tactics for all participants to use in order to end the game with the least amount of remorse. Therefore, rational players are all driven to play their equilibrium strategy because any player who opts not to play their game-optimal strategy will lament it more in the end.

This idea is relevant to the wall chase game, where the pursuer and evader each have a best-case strategy pair that covers almost all of their possible situations. There are some situations between the pursuer and the evader, though, for which the traditional analysis is unable to produce the winning strategies and comes to the conclusion that the conundrum exists. The study community has long accepted the paradox as true because this collection of locations is known as a singular surface.

Milutinovic and his co-authors, however, did not agree to this.

This concerned Milutinovic and his team because they believed that if the evader knew there was a unique area, he or she might use it inappropriately. We simply don't know what the implications of that would be in games that are much more complex because the evader can compel you to go to the singular surface where you are unsure of how to behave best.

In order to solve the issue, Milutinovic and his co-authors developed a novel method that made use of a mathematical idea that had not yet been invented when the wall chase game was first imagined. They were able to discover that a game optimal solution can be found in all game conditions by using the viscosity solution of the Hamilton-Jacobi-Isaacs equation and adding a rate of loss analysis for solving the singular surface.

The Hamilton-Jacobi-Isaacs equation can be solved in a novel way thanks to the 1980s invention of the mathematical idea known as the viscous solution of partial differential equations. The idea's applicability to problem-solving in game theory and optimum management is now widely acknowledged.

Calculus is used to locate the derivatives of the viscous solutions, which are functions used to handle game theory issues. When a game's related viscosity solution has well-defined derivatives, it is comparatively simple to locate the game's optimal solutions. The wall-pursuit game is an exception to this, and the conundrum is brought on by the absence of clearly specified variants.

Usually, when faced with a choice, participants will take the least advantageous course of action and tolerate losses as a consequence of their choice. The problem is that each reasonable participant will try to limit any losses if there are any.

In order to determine how participants could reduce their loses, the writers examined the Hamilton-Jacobi-Isaacs equation's viscosity solution near the singular surface where the derivatives are ill-defined. Then they added a rate of loss study over these singular equation surface states. They discovered that there are clearly specified game tactics for their actions on the single surface when each player minimizes its rate of losses.

In addition to defining the game-optimal actions for the single surface, the authors discovered that this rate of loss reduction agrees with the game-optimal actions in every scenario in which the classical analysis is also capable of identifying these actions.

The game-optimal behaviors from the conventional analysis are unaffected when we implement the rate of loss analysis elsewhere, according to Milutinovic. There is an answer everywhere because we take the traditional theory and add the rate of loss analysis to it. This significant finding demonstrates that the enhancement is a fundamental advancement in game theory rather than merely a workaround to locate a solution on the solitary surface.

Milutinovic and his co-authors are eager to investigate additional single surface game theory issues that could benefit from the use of their novel methodology. The article serves as a free invitation to the study community to investigate other conundrums in a similar manner.

The next query is, "What other conundrums can we resolve?" said Milutinovic.