Applying Optimization in Game Theory
Author: Leon Huang (Spring 2015)
Optimization and Game Theory have certain conceptual overlaps. It is even said that John von Neumann conjectured the Duality Theorem using information from his game theory.1 This article discusses two optimization applications to the game theory: a methodology for solving the Nash Equilibrium and a decentralized model in supply chain management.
In game theory, the Nash Equilibrium is "an action profile with the property that no single player can obtain a higher payoff by deviating unilaterally from this profile."2 An equilibrium is reached since every player will conform to the his or her decisions dictated by the profile. For example, in the classical game the Prisoners' Dilemma, two prisoners, A and B, are given the opportunities to snitch on each other. If neither snitches, both will get out in 1 year. If one of them snitches and the other one doesn't, the one who snitches get out immediately and the other will stay in the prison for 10 years. If they snitch on each other, they will both stay in the prison for 5 years. The Nash Equilibrium here is the action profile that both snitch and take 5 years of jailtime. Neither of them has the incentive to deviate from this profile because the prison who remains silent would be worse off. Formally, if is the strategy profile for player , is the strategy profiles for all the players except player , and is the player's payoff function, then a strategy profile that contains the strategies of all players is a Nash Equilibrium so long as
Nash Equilibrium can be found iteratively by mixed-integer linear programming. In the same example of the Prisoner's Dilemma, starting from Prisoner A's perspective, we shall first assume that Prisoner B will choose to remain silent. Using linear programming, the Prisoner A's best move can be found by maximizing his payoff under the condition that Prisoner B will remain silent. Obviously Prisoner A will snitch, a choice that reduces his sentence from 1 year to none. Then we take Prisoner A's choice as given and find Prisoner B's response by solving for the maximum of Prisoner B's payoff. If Prisoner B's response coincide with what we assumed when solving for Prisoner A's move, an equilibrium is found. If not, we shall take Prisoner B's updated response as given, and continue solving for Prisoner A's response until an equilibrium is reached. If all possible scenarios are consumed before an equilibrium is found, the game is said to have no equilibrium. In this case, Prisoner B's best response is to snitch too. Under this condition Prisoner A will still be better off to snitch. A Nash Equilibrium of (snitch, snitch) is then found. Simple iterations are used here to demonstrate the idea of Nash Equilibrium. A rigorous methodology for solving more complex games is further discussed in Matrix game (LP for game theory).
Supply Chain Management
In supply chain management, the optimizing solution not only depends on the manufacturer's own strategies, but also the strategies of the suppliers at the upstream and those of the customers at the downstream. Traditionally, the strategies of all participants are modeled in a centralized fashion that assumes the decision maker to have full control over the entire supply chain.3 However, in practice the problems with imperfect knowledge and conflicting interests demand a more flexible model to incorporate the nuances and uncertainties in supply chain management. Game theory is well equipped for this task, as it allows multiple players to act on their own knowledge base and to act toward their own self-centered interests.
For example, Dajun Yue and Fenqi You have proposed a multi-echelon supply chain model under the Stackleberg Game, in which the manufacturer is modeled as the single leader while the suppliers and the customers are modeled as the many followers.4 In this model, the manufacturer first optimizes manufacturing decisions such as the location and capacity of the manufacturing plant. The suppliers and the customers then follow suit to determine how to maximize their own profits. Formulating in the form of bi-level mixed integer nonlinear programming, the model was then solved by a novel branch-and-refine algorithm devised by Yue and You.
1. George Dantzig, "Foreword," Linear Programming and Related Problems, Evar D. Nering, and Albert William Tucker (Massachusetts: Academic Press, 1993).
2. Gamal Abdel Nasser, "Nash Equilibrium," International Encyclopedia of the Social Sciences, 2nd Edition, ed. William A. Darity, Jr. (Michigan: Gale, 2008).
3. Nilay Shah, "Process industry supply chains: Advances and challenges," Comp Chem Eng 29(2005): 1225-1235.
4. Dajun Yue and Fenqi You, "Game-Theoretic Modeling and Optimization of Multi-echelon Supply Chain Design and Operation under Stackelberg Game and Market Equilibrium," Computers & Chemical Engineering 71(2014): 347–361.