Converting a Game to a Linear Programming Problem
| A\B | \[B_1\] | \[B_2\] |
| \[A_1\] | 2 | 4 |
| \[A_2\] | 6 | 1 |
\[A_1\]
he will win at least 2, and if he plays strategy 2 he will win at least 1, so his maximin strategy 1. If B plays strategy \[B_1\]
he will lose at most 6 and if he plays strategy \[B_2\]
he will lose at most 4, so B's minimax strategy is to play strategy \[B_2\]
. If A chooses strategies \[A_1, \: A_2\]
with probability \[p, \: 1-p\]
respectively, then if B plays \[B_1\]
the expected payoff to A is \[2p+6(1-p)=6-4p\]
, and if B plays strategy \[B_2\]
then the expected payoff to A will be \[4p+1-p=1+3p\]
.for any choice of
\[p\]
the expected payoff to A is greater than 0. Let \[M\]
be the minimum expected payoff for the row player, \[M=MIN(6-4p,1+3p)\]
, and let \[s=\frac{p}{M}, \: t=\frac{1-p}{M}, \: s, \: t ge 0\]
(1).Then
\[s+t=\frac{1}{M}\]
. The maximum value of \[M\]
leads to the minimum value of \[s+t\]
.Also
\[6-4p, \: 1+3p \ge M\]
(2)From (1),
\[p=sM, \:1-p=tM\]
and (2) can be written \[2sM+6tM, \: 4sM+tM \ge M \rightarrow 2s+6t, \: 4s+t \ge 1\]
A now has to minimise
\[s+t\]
subject to\[2s+6t \ge 1\]
\[4s+t \ge 1\]
\[s \ge 0, \: t \ge 0\]
Similarly B has to maximise
\[x+y\]
subject to\[2x+4y \le 1\]
\[6x+y \le 1\]
\[x \ge 0, \: y \ge 0\]
Note that A's and B's problems are dual to each other, so that if solutions exist the optimal values are the same. From game theory, the value of the game is the same for both players. Any game can be converted to a linear programming problem and vice versa.
