View source for Matrix game (LP for game theory)

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.

== Game Theory ==
[[File:johnny.jpg|thumb|right|350px|]]
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 (<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}^{n \times m}</math>). 

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

:<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 such game, as can be seen in the payoff matrix. In other words, each player has an equal chance of winning where if vector <math>x</math> is the probability for the first player to choose among rock, paper, or scissors, the optimal solution <math>x^*</math> would be 

:<math>x^* = \begin{bmatrix} 1/3 \\ 1/3 \\ 1/3 \end{bmatrix}</math>. 

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

:<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. Solutions to these non-trivial matrix games can be obtained by solving the equivalent LPs based on the Minimax Theorem developed by John von Neumann.

== Minimax Theorem ==
''content coming soon!''

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