# Difference between revisions of "Matrix game (LP for game theory)"

Line 29: | Line 29: | ||

=== Payoff Matrix === | === 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..m\}</math> and <math>j \in \{1..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>). | + | 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 ==== | ==== Example ==== | ||

Line 46: | Line 46: | ||

=== Formulation of LP === | === Formulation of LP === | ||

− | 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 | + | 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: | 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: | ||

Line 54: | Line 52: | ||

<math> | <math> | ||

\begin{align} | \begin{align} | ||

− | \text{min} & ~~ \sum_{i=1}^ | + | \text{min} & ~~ \sum_{i=1}^m {x^T}Py\\ |

− | \text{s.t.} & ~~ \sum_{i=1}^ | + | \text{s.t.} & ~~ \sum_{i=1}^m x_i = 1\\ |

− | & | + | & ~~ x \ge 0 \\ |

\end{align} | \end{align} | ||

</math> | </math> | ||

Line 67: | Line 65: | ||

=== Proof === | === 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, by symmetry the optimal solution for the first player 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> | ||

+ | |||

+ | By 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 prove the Minimax Theorem <math> \min_x {x^T}P{y^*} = \max_y {{x^*}^T}Py</math> | ||

== Example == | == Example == |

## Revision as of 19:57, 25 May 2014

Authors: Nick Dotzenrod and Matt Kweon (ChE 345 Spring 2014)

Steward: Dajun Yue, Fengqi You

Date Presented: Apr. 10, 2014

Linear programming (LP) is a simple yet powerful tool that can be used as an aid in decision making under certainty - that is, the objective, constraints, and any other relevant information about the problem are known. A highly practical application of LP lies in its use in game theory. This page specifically explores how LP can be used to solve a finite two-person zero-sum game, also known as the matrix game, which is one of the simplest form of decision making games.

## 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.

### 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**

## 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

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.

### Application of LP in Matrix Game

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, or even complicated games such as poker or a variation of rock-paper scissors. 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

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, there is an optimal payoff value for one player given the other player’s strategy, 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, by symmetry the optimal solution for the first player can be determined from

By 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 prove the Minimax Theorem

## Example

*example coming soon!*

## References

1. S. Tadelis, *Game Theory: an Introduction*, Princeton University Press, 2013.

2. R. J. Vanderbei, *Linear Programming: Foundations and Extensions*, Springer, 2008.

3. M. J. Osborne, *An Introduction to Game Theory*, Oxford University Press, 2004.