Using Game Theory to Navigate the Road
Researchers studying driverless vehicles often turn to game theory, a mathematical model that simulates how rational agents strategically achieve their goals. Dejan Milutinovic, a professor at UC Santa Cruz, specializes in a subset of game theory called differential games, which involve players in motion. One such game is the wall pursuit game, a simple model where a faster pursuer aims to catch a slower evader restricted to a wall.
For years, researchers believed that certain positions in the wall pursuit game had no optimal solutions. However, Milutinovic and his team recently published a paper in the journal “IEEE Transactions on Automatic Control,” disproving this longstanding dilemma. They introduced a novel method of analysis that demonstrates a deterministic solution always exists for the wall pursuit game. This breakthrough not only resolves similar challenges in differential games but also enhances our understanding of autonomous systems like driverless vehicles.
Game theory, commonly used across various fields like economics, political science, computer science, and engineering, relies on concepts such as the Nash equilibrium. This equilibrium provides optimal strategies for all players to minimize any potential regrets. Deviating from the equilibrium strategy results in more regret, motivating rational players to adhere to their optimal strategies.
The wall pursuit game also follows this concept, offering a classical Nash equilibrium strategy pair for both the pursuer and evader. However, classical analysis fails to provide optimal strategies for certain positions, leading to the existence of the dilemma. Known as a singular surface, this set of positions has puzzled researchers until now.
Milutinovic and his co-authors refused to accept this dilemma as an insurmountable obstacle. They devised a fresh approach utilizing a mathematical concept not available during the game’s inception. By employing the viscosity solution of the Hamilton-Jacobi-Isaacs equation and introducing rate of loss analysis, they established that a game optimal solution can be determined in all game scenarios, resolving the dilemma.
Viscosity solutions, which emerged in the 1980s, offer a unique way to reason about optimal control and game theory problems. Solving game theory problems using these functions involves calculating their derivatives through calculus. Normally, finding game optimal solutions is straightforward when the viscosity solution has well-defined derivatives. However, the wall pursuit game’s lack of well-defined derivatives complicates matters and creates the dilemma.
When faced with a dilemma, players often randomly choose actions and accept resulting losses. However, rational players strive to minimize their losses. To understand how players minimize their losses, the authors analyzed the viscosity solution around the singular surface, where derivatives are undefined. They introduced a rate of loss analysis for these singular surface states. Notably, they discovered that minimizing the rate of losses yields well-defined game strategies on the singular surface.
The authors also found that this rate of loss minimization aligns with game optimal actions in all other states where classical analysis successfully identifies optimal actions. The rate of loss analysis does not impact these actions, serving as an augmentation to the classical theory rather than a mere fix for the singular surface. This breakthrough contributes significantly to game theory.
Milutinovic and his co-authors hope to explore other game theory problems featuring singular surfaces. Their paper serves as a call to the research community to address similar dilemmas.
Next Steps in Game Theory Research
With the resolution of the wall pursuit game dilemma, Milutinovic and his team are eager to tackle other game theory problems using their innovative method. This breakthrough opens doors to solving more complex challenges and provides a foundation for further research in the field.
“What other dilemmas can we solve?” Milutinovic prompts the research community, inviting them to join in unraveling the mysteries of game theory.