An iterative numerical approach to solving game theory problem expands its applications

Game theory is the mathematical study of decision-making. It can be applied to parlour games, as well as economics, military situations, and evolutionary biology.

Picture a highway at rush hour. Each driver aims to arrive at their destination safely and in the shortest time possible. There is a finite set of driving strategies that they can use to achieve their goals: changing lanes, accelerating, breaking, signaling, or passing cars, for example. The choice of a driver’s strategy may impact the strategies available to other drivers, as well as their overall goal. For example, a driver that chooses to pass another car may block the possibility of changing lanes for another driver. This scenario is a setup for a generalized Nash equilibrium, a mathematical model that Dr. Monica Cojocaru, a University of Guelph mathematics professor, is exploring deeply. 

The generalized Nash equilibrium

The generalized Nash equilibrium is used in game theory, a discipline that applies mathematical models to the study of social and economic situations among competing players. It has since been applied to a range of disciplines from biology to computer science. The example above is a case in point.

Along with postdoctoral researcher Tangi Migot, Cojocaru has set out to solve for the generalized Nash equilibrium, which will enable researchers to predict behavioural decisions and determine best response outcomes in complicated situations. In most games with a finite number of players where each player has a finite number of choices (or strategies), there is at least one strategy—a so-called equilibrium state—from which no single player can improve his or her well-being (payoff) by unilaterally changing to another strategy. Equilibrium states amount to finding strategies that are best responses for all players, but they are complex and mathematically difficult to compute. 

New Approaches, New Directions

Migot and Cojocaru applied an iterative mathematical modelling method called a decomposition method to solve for the generalized Nash equilibrium. They developed two algorithms and applied them to published examples. Their approach obtained a solution close to the generalized Nash equilibrium in every case.

“Our numerical method is easily implemented,” says Cojocaru. “From here, we can explore new avenues for research, tackling more sophisticated problems, and perhaps even extending our approach with more complex algorithms.”

Monica Cojocaru is a professor of mathematics in the Department of Mathematics and Statistics.

This work was supported by an NSERC Discovery Accelerator Supplement, Grant Number 401285.

Migot T, Cojocaru MG. A decomposition method for a class of convex generalized Nash equilibrium problems. Optim. Eng. 2020 Nov 12. doi: 10.1007/s11081-020-09578-9