Difference between revisions of "Matrix game (LP for game theory)"
(→Game Theory) |
|||
(65 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
Authors: Nick Dotzenrod and Matt Kweon (ChE 345 Spring 2014) | Authors: Nick Dotzenrod and Matt Kweon (ChE 345 Spring 2014) | ||
+ | == Game Theory == | ||
+ | [[File:johnny.jpg|thumb|right|350px|John von Neumann [1]]] | ||
+ | The objective of game theory is to analyze the relationship between decision-making situations in order to achieve a desirable outcome. The theory can be applied to a wide range of applications, including, but not limited to, economics, politics and even the biological sciences. In essence, game theory serves as means to create a model to represent certain scenarios that have a variety of variables and potential outcomes. With these models developed from game theory, one can determine if assumptions made for a certain scenario are valid or whether additional models should be created that could more accurately assess the current problem. Game theory can be broken into a variety of different "games," each analyzing different situations in which a decision is to be made by one player with other players potentially affecting the process. | ||
− | + | === History === | |
+ | Many mathematicians would agree that John von Neumann can be considered the Father of Game Theory. John was born in Hungary in 1903 and grew up having a love for math and the sciences. In college, he received degree a degree in chemical engineering and later, a Ph.D. in mathematics from the University of Budapest. In 1928, Neumann proved the minimax theorem, which describes how two players can minimize their losses against each other. In 1930, he then went on to be a professor at Princeton in the mathematics department and later in 1944, wrote ''Theory of Games and Economic Behavior.'' After this publication, game theory became a mainstream topic in mathematical discourse. Since its spawn in the 1940's, game theory has continued to be studied by mathematicians worldwide with many new discoveries being made. Starting as a way to model economics, game theory progressed to analyzing biological systems in the 1970's to later having a role in the development in computer science. Today, game theory has evolved into many type of "games," each describing various scenarios with players making decisions [2]. | ||
− | + | === Game Types === | |
− | + | As aforementioned, there are many types of "games" that have been developed due to game theory. These games model various scenarios and differ from each other depending on how the players in the game cooperate with each other. | |
− | + | * '''Strategic Games''' A strategic game that models a set of players, each with a set of actions with preferences for performing each of their corresponding actions. | |
− | '' | + | * '''Extensive Games''' A game that consists of players that choose a terminal history that results in a player function depending on the chosen terminal history. Much like the strategic game, players have preferences over their set of terminal histories. |
+ | * '''Coalitional Game''' A game that consists of a set of players, with each player being part of a group. These groups of players are called coalitions and have a set of actions that can be taken based on player preferences. | ||
− | + | == Matrix Game == | |
− | + | A matrix game, which is short for finite two-person zero-sum game, allows a game to be represented in matrix form as its name implies. This is a direct consequence of the fact that two opponents with exactly opposite interests play a game under a finite number of strategies, independently of his or her opponent’s action. Once both players each make an action, their decisions are disclosed. A payment is made from one player to the other based on the outcome, such that the gain of one player equals the loss of the other, resulting in a net payoff summing to zero. | |
+ | === Payoff Matrix === | ||
+ | From the definition of the finite two-person zero-sum game, all payments (<math>p_{ij}</math>) can be represented as a matrix <math>P = [p_{ij}]</math> where <math>i</math> is an action in the finite set of choices that one player makes and <math>j</math> is that of the other for all <math>i \in \{1,2,...,m\}</math> and <math>j \in \{1,2,...,n\}</math>. Here, matrix <math>P</math> is called the payoff matrix. Note that the payments are made in one direction; that is, <math>p_{ij}</math> represents payments made from the first player to the second so that the elements of <math>P</math> can positive, 0, or negative (i.e. <math>P \in \mathbb{R}^{m \times n}</math>). | ||
− | == | + | ==== Example 1 ==== |
+ | Consider the game rock-paper-scissors as a simple example. Let the choice of rock, paper, and scissors be denoted as 1, 2, and 3, respectively. This means that the first row of the payoff matrix indicates the first person playing a rock, while the columns represent the second player’s choices. Further, let a “win,” “draw,” and “loss” be respectively assigned the values +1, 0, and -1. Based on the definition of the payoff matrix, a game of rock-paper-scissors then has the payoff matrix | ||
+ | |||
+ | :<math>P = \begin{bmatrix} 0 & 1 & -1 \\ -1 & 0 & 1 \\ 1 & -1 & 0 \end{bmatrix}</math>. | ||
+ | |||
+ | It is well known a clear winning strategy does not exist for rock-paper-scissors, as can be seen in the payoff matrix. In other words, each player equally has a <math>\tfrac{1}{3}</math> chance of winning. | ||
+ | |||
+ | ==== Example 2 ==== | ||
+ | Now consider a non-trivial game of rock-paper-scissors where the payoff matrix is | ||
+ | |||
+ | :<math>P = \begin{bmatrix} 0 & 2 & -3 \\ -1 & 0 & 4 \\ 3 & -4 & 0 \end{bmatrix}</math>. | ||
+ | |||
+ | In this game, an equal chance of 1/3 is no longer optimal, and the first player has a total payoff of 9 while the second player has that of 8. It appears that the first player has an advantage, but this may not necessarily be true. For example, it may be possible for the second player to make a profit if for each game played, the second player were to make a payment to the first player that is less than the expected gain. | ||
+ | |||
+ | === Formulation of LP === | ||
+ | Formulating a matrix game as an LP problem allows for a player to determine the optimal winning strategy. This is true for simple zero-sum games such as Matching Pennies and rock-paper-scissors, or even complicated games such as poker and a variation of rock-paper scissors as seen in Example 2. In all cases, the solution to any matrix game can be obtained by solving the equivalent LP. It is assumed that players choose random strategies and the probability distributions that the players follow are known. | ||
+ | |||
+ | Let <math>x_i</math> be defined as a vector that consists of all probabilities that the first player follows, such that <math>x_i \ge 0</math> and <math> \sum x_i = 1 </math>. Similarly, a vector <math>y_j</math> can be defined as the probabilities that describe the second player’s actions. Then, the expected payoff from the first player to the second can be expressed as <math> \sum {x_i}{p_{ij}}{y_j} = {x^T}Py</math>. | ||
+ | |||
+ | Noting that this is a zero-sum game, the optimal strategy for the first player to employ is to minimize the payoff <math>{x^T}Py</math> to the second player. Therefore, a generalized optimal strategy for the first player can be represented as the following LP: | ||
+ | |||
+ | <math> | ||
+ | \begin{align} | ||
+ | \text{min} & ~~ \sum_{i=1}^m {x^T}Py\\ | ||
+ | \text{s.t.} & ~~ \sum_{i=1}^m x_i = 1\\ | ||
+ | & ~~ x \ge 0 \\ | ||
+ | \end{align} | ||
+ | </math> | ||
+ | |||
+ | Note that, on the other hand, the optimal strategy of the second player is to maximize the payoff from the first player. Given the objective of the first player, the objective of the second player can be expressed as <math> \max_y \min_x {x^T}Py </math>. Based on this LP formulation, an optimal strategy can be determined by solving the problem using the Minimax Theorem developed by John von Neumann. | ||
== Minimax Theorem == | == Minimax Theorem == | ||
− | + | As its name implies, the Minimax Theorem is used in a matrix game minimize the maximum payoff to the opposing player. The theorem states that for a zero-sum game, if the first and second player have optimal strategies <math>x^*</math> and <math>y^*</math> respectively, then | |
+ | <math> \max_y {{x^*}^T}Py = \min_x {x^T}P{y^*}</math>. In other words, for a finite two-person zero-sum game, given the other player’s strategy, there is an optimal payoff value <math>w</math> for one player for which the other player’s payoff value will be <math>-w</math>. This guarantees that the optimal strategies employed by both players are consistent with each other due to symmetry of the problem. | ||
− | == Example == | + | === Proof === |
− | '' | + | The Minimax Theorem can be proved within the context of the matrix game. Note that the optimal solution for the first player can be obtained from rewriting the objective as <math> \min_x {x^T}Py = \min_i {{a_i}^T}Py</math>, where <math>a_i</math> is a vector that consists of zeroes except at <math>i</math>, which holds the value 1. This equality holds true because deciding on an optimal probability distribution that would minimize the payoff is equivalent to selecting the minimal payoff to the other player. |
+ | |||
+ | Introducing a new variable <math>u</math> along with this substitution allows the original maximin LP problem (optimal strategy for the second player) to be reformulated as a simple maximization problem: | ||
+ | |||
+ | <math> | ||
+ | \begin{align} | ||
+ | \text{max} & ~~ u\\ | ||
+ | \text{s.t.} & ~~ u \le {{a_i}^T}Py,~~\forall~i \in \{1,2,...,m\} \\ | ||
+ | & ~~ \sum_{j=1}^n y_j = 1\\ | ||
+ | & ~~ y_j \ge 0,~~\forall~i \in \{1,2,...,m\} \\ | ||
+ | \end{align} | ||
+ | </math> | ||
+ | |||
+ | or in vector notation, | ||
+ | |||
+ | <math> | ||
+ | \begin{align} | ||
+ | \text{max} & ~~ u\\ | ||
+ | \text{s.t.} & ~~ ua - Py \le 0 \\ | ||
+ | & ~~ {a^T}y = 1\\ | ||
+ | & ~~ y \ge 0\\ | ||
+ | \end{align} | ||
+ | </math> | ||
+ | |||
+ | Since the problem is a finite two-person zero-sum game, the optimal solution for the first player, by symmetry, can be determined from | ||
+ | |||
+ | <math> | ||
+ | \begin{align} | ||
+ | \text{min} & ~~ v\\ | ||
+ | \text{s.t.} & ~~ va - {P^T}x \ge 0 \\ | ||
+ | & ~~ {a^T}x = 1\\ | ||
+ | & ~~ x \ge 0\\ | ||
+ | \end{align} | ||
+ | </math> | ||
+ | |||
+ | Based on the duality theorem, it is evident that the two LPs are primal-dual pairs, such that the strong duality suggests that <math>u^* = v^*</math>. | ||
+ | |||
+ | |||
+ | By definition, recall that <math> v = \min_i {{a_i}^T}Py</math> and <math>u = \max_j {{a_j}^T}{P^T}x</math>, | ||
+ | such that for optimal solutions <math>x^*</math> and <math>y^*</math>, | ||
+ | <math> v = \min_i {{a_i}^T}P{y^*} = \min_x {x^T}P{y^*}</math> and <math>u = \max_j {{a_j}^T}{P^T}{x^*} = \max_y {y^T}{P^T}{x^*}</math>. | ||
+ | Since <math>{y^T}{P^T}{x^*} = {{x^*}^T}Py</math> due to symmetry, <math>u = \max_y {y^T}{P^T}{x^*} = \max_y {{x^*}^T}Py</math>. | ||
+ | Based on strong duality, <math>u^* = v^*</math>, so this proves the Minimax Theorem <math> \min_x {x^T}P{y^*} = \max_y {{x^*}^T}Py</math> | ||
+ | |||
+ | === Example === | ||
+ | [[File:gametheory.jpg|thumb|right|400px|Poker Betting Results]] | ||
+ | Though there are a variety of applications for the minimax theorem, one example that is commonly used is poker game. Analyzing the game of poker as a whole would be incredibly complex, however, simply modeling the game techniques of bluffing (bidding when you have a weaker hand and would lose if opponent continues play) and underbidding (bidding less in order to try to convince your opponent to bid more and lose). Begin by assigning the variables: | ||
+ | |||
+ | '''A''' for Player 1 | ||
+ | |||
+ | '''B''' for Player 2 | ||
+ | |||
+ | Each player has two actions, pass or bet. There are a total of 5 scenarios as a result of player A and B deciding to either "bet" or "pass" these scenarios include: | ||
+ | [[File:gamematrix.jpg|thumb|right|400px|Payoff Matrix [3]]] | ||
+ | |||
+ | 1.'''A''' Bets then '''B''' Bets: Higher card wins all | ||
+ | |||
+ | 2.'''A''' Bets then '''B''' Bets: '''A''' wins back bet | ||
+ | |||
+ | 3.'''A''' Passes then '''B''' Bets then '''A''' Bets: Higher card wins all | ||
+ | |||
+ | 4.'''A''' Passes then '''B''' Bets then '''A''' Passes: '''B''' wins back bet | ||
+ | |||
+ | 5.'''A''' Passes then '''B''' Passes: Highest card wins | ||
+ | |||
+ | In order to simply the problem further, there will only be three cards being used valued '''1''', '''2''', and '''3'''. We can design a table that illustrates the possible outcomes for player '''A''', assuming they choose to always bet when dealt '''1''' and pass when dealt '''2''' or '''3'''. | ||
+ | |||
+ | If the column for '''Payment''' is averaged (et. (2+2+1+1-2-1)/6) a value of 0.5 is obtained. This calculation, however, is only one of thousands of average payment calculations that must be made in order to determine the optimal betting strategy. After in depth mathematical analysis, a finalized matrix can be created that outputs the potential payoffs. | ||
+ | |||
+ | == Conclusion == | ||
+ | Game theory, and more importantly, matrix game theory, have had a profound impact on the way mathematicians model certain scenarios and events. The advent of this problem solving method has revolutionized the way many different situation can be analyzed in many different areas including economics, biology and computer science. | ||
== References == | == References == | ||
− | 1. | + | 1. "John Von Neumann." John Von Neumann Biography. N.p., n.d. Web. 25 May 2014. |
+ | |||
+ | 2. M. J. Osborne, ''An Introduction to Game Theory'', Oxford University Press, 2004. | ||
− | + | 3. R. J. Vanderbei, ''Linear Programming: Foundations and Extensions'', Springer, 2008. | |
− | + | 4. S. Tadelis, ''Game Theory: an Introduction'', Princeton University Press, 2013. |
Latest revision as of 16:07, 8 June 2014
Authors: Nick Dotzenrod and Matt Kweon (ChE 345 Spring 2014)
Contents |
Game Theory
The objective of game theory is to analyze the relationship between decision-making situations in order to achieve a desirable outcome. The theory can be applied to a wide range of applications, including, but not limited to, economics, politics and even the biological sciences. In essence, game theory serves as means to create a model to represent certain scenarios that have a variety of variables and potential outcomes. With these models developed from game theory, one can determine if assumptions made for a certain scenario are valid or whether additional models should be created that could more accurately assess the current problem. Game theory can be broken into a variety of different "games," each analyzing different situations in which a decision is to be made by one player with other players potentially affecting the process.
History
Many mathematicians would agree that John von Neumann can be considered the Father of Game Theory. John was born in Hungary in 1903 and grew up having a love for math and the sciences. In college, he received degree a degree in chemical engineering and later, a Ph.D. in mathematics from the University of Budapest. In 1928, Neumann proved the minimax theorem, which describes how two players can minimize their losses against each other. In 1930, he then went on to be a professor at Princeton in the mathematics department and later in 1944, wrote Theory of Games and Economic Behavior. After this publication, game theory became a mainstream topic in mathematical discourse. Since its spawn in the 1940's, game theory has continued to be studied by mathematicians worldwide with many new discoveries being made. Starting as a way to model economics, game theory progressed to analyzing biological systems in the 1970's to later having a role in the development in computer science. Today, game theory has evolved into many type of "games," each describing various scenarios with players making decisions [2].
Game Types
As aforementioned, there are many types of "games" that have been developed due to game theory. These games model various scenarios and differ from each other depending on how the players in the game cooperate with each other.
- Strategic Games A strategic game that models a set of players, each with a set of actions with preferences for performing each of their corresponding actions.
- Extensive Games A game that consists of players that choose a terminal history that results in a player function depending on the chosen terminal history. Much like the strategic game, players have preferences over their set of terminal histories.
- Coalitional Game A game that consists of a set of players, with each player being part of a group. These groups of players are called coalitions and have a set of actions that can be taken based on player preferences.
Matrix Game
A matrix game, which is short for finite two-person zero-sum game, allows a game to be represented in matrix form as its name implies. This is a direct consequence of the fact that two opponents with exactly opposite interests play a game under a finite number of strategies, independently of his or her opponent’s action. Once both players each make an action, their decisions are disclosed. A payment is made from one player to the other based on the outcome, such that the gain of one player equals the loss of the other, resulting in a net payoff summing to zero.
Payoff Matrix
From the definition of the finite two-person zero-sum game, all payments () can be represented as a matrix where is an action in the finite set of choices that one player makes and is that of the other for all and . Here, matrix is called the payoff matrix. Note that the payments are made in one direction; that is, represents payments made from the first player to the second so that the elements of can positive, 0, or negative (i.e. ).
Example 1
Consider the game rock-paper-scissors as a simple example. Let the choice of rock, paper, and scissors be denoted as 1, 2, and 3, respectively. This means that the first row of the payoff matrix indicates the first person playing a rock, while the columns represent the second player’s choices. Further, let a “win,” “draw,” and “loss” be respectively assigned the values +1, 0, and -1. Based on the definition of the payoff matrix, a game of rock-paper-scissors then has the payoff matrix
- .
It is well known a clear winning strategy does not exist for rock-paper-scissors, as can be seen in the payoff matrix. In other words, each player equally has a chance of winning.
Example 2
Now consider a non-trivial game of rock-paper-scissors where the payoff matrix is
- .
In this game, an equal chance of 1/3 is no longer optimal, and the first player has a total payoff of 9 while the second player has that of 8. It appears that the first player has an advantage, but this may not necessarily be true. For example, it may be possible for the second player to make a profit if for each game played, the second player were to make a payment to the first player that is less than the expected gain.
Formulation of LP
Formulating a matrix game as an LP problem allows for a player to determine the optimal winning strategy. This is true for simple zero-sum games such as Matching Pennies and rock-paper-scissors, or even complicated games such as poker and a variation of rock-paper scissors as seen in Example 2. In all cases, the solution to any matrix game can be obtained by solving the equivalent LP. It is assumed that players choose random strategies and the probability distributions that the players follow are known.
Let be defined as a vector that consists of all probabilities that the first player follows, such that and . Similarly, a vector can be defined as the probabilities that describe the second player’s actions. Then, the expected payoff from the first player to the second can be expressed as .
Noting that this is a zero-sum game, the optimal strategy for the first player to employ is to minimize the payoff to the second player. Therefore, a generalized optimal strategy for the first player can be represented as the following LP:
Note that, on the other hand, the optimal strategy of the second player is to maximize the payoff from the first player. Given the objective of the first player, the objective of the second player can be expressed as . Based on this LP formulation, an optimal strategy can be determined by solving the problem using the Minimax Theorem developed by John von Neumann.
Minimax Theorem
As its name implies, the Minimax Theorem is used in a matrix game minimize the maximum payoff to the opposing player. The theorem states that for a zero-sum game, if the first and second player have optimal strategies and respectively, then . In other words, for a finite two-person zero-sum game, given the other player’s strategy, there is an optimal payoff value for one player for which the other player’s payoff value will be . This guarantees that the optimal strategies employed by both players are consistent with each other due to symmetry of the problem.
Proof
The Minimax Theorem can be proved within the context of the matrix game. Note that the optimal solution for the first player can be obtained from rewriting the objective as , where is a vector that consists of zeroes except at , which holds the value 1. This equality holds true because deciding on an optimal probability distribution that would minimize the payoff is equivalent to selecting the minimal payoff to the other player.
Introducing a new variable along with this substitution allows the original maximin LP problem (optimal strategy for the second player) to be reformulated as a simple maximization problem:
or in vector notation,
Since the problem is a finite two-person zero-sum game, the optimal solution for the first player, by symmetry, can be determined from
Based on the duality theorem, it is evident that the two LPs are primal-dual pairs, such that the strong duality suggests that .
By definition, recall that and ,
such that for optimal solutions and ,
and .
Since due to symmetry, .
Based on strong duality, , so this proves the Minimax Theorem
Example
Though there are a variety of applications for the minimax theorem, one example that is commonly used is poker game. Analyzing the game of poker as a whole would be incredibly complex, however, simply modeling the game techniques of bluffing (bidding when you have a weaker hand and would lose if opponent continues play) and underbidding (bidding less in order to try to convince your opponent to bid more and lose). Begin by assigning the variables:
A for Player 1
B for Player 2
Each player has two actions, pass or bet. There are a total of 5 scenarios as a result of player A and B deciding to either "bet" or "pass" these scenarios include:
1.A Bets then B Bets: Higher card wins all
2.A Bets then B Bets: A wins back bet
3.A Passes then B Bets then A Bets: Higher card wins all
4.A Passes then B Bets then A Passes: B wins back bet
5.A Passes then B Passes: Highest card wins
In order to simply the problem further, there will only be three cards being used valued 1, 2, and 3. We can design a table that illustrates the possible outcomes for player A, assuming they choose to always bet when dealt 1 and pass when dealt 2 or 3.
If the column for Payment is averaged (et. (2+2+1+1-2-1)/6) a value of 0.5 is obtained. This calculation, however, is only one of thousands of average payment calculations that must be made in order to determine the optimal betting strategy. After in depth mathematical analysis, a finalized matrix can be created that outputs the potential payoffs.
Conclusion
Game theory, and more importantly, matrix game theory, have had a profound impact on the way mathematicians model certain scenarios and events. The advent of this problem solving method has revolutionized the way many different situation can be analyzed in many different areas including economics, biology and computer science.
References
1. "John Von Neumann." John Von Neumann Biography. N.p., n.d. Web. 25 May 2014.
2. M. J. Osborne, An Introduction to Game Theory, Oxford University Press, 2004.
3. R. J. Vanderbei, Linear Programming: Foundations and Extensions, Springer, 2008.
4. S. Tadelis, Game Theory: an Introduction, Princeton University Press, 2013.