The Linear Programming Solver

Example 7.3 Two-Person Zero-Sum Game

Consider a two-person zero-sum game (where one person wins what the other person loses). The players make moves simultaneously, and each has a choice of actions. There is a payoff matrix that indicates the amount one player gives to the other under each combination of actions:

\[ \begin{array}{ccc}& & \mr{Player \ II \ plays}\, j \\ & & \begin{array}{rrrr}1 & 2 & 3 & 4 \end{array}\\ \mr{Player \ I \ plays}\, i & \begin{array}{c}1\\ 2\\ 3\end{array}& \left( \begin{array}{rlll} -5 & 3 & 1 & 8\\ 5 & 5 & 4 & 6 \\ -4 & 6 & 0 & 5 \end{array} \right) \end{array} \]

If player I makes move i and player II makes move j, then player I wins (and player II loses) $a_{ij}$. What is the best strategy for the two players to adopt? This example is simple enough to be analyzed from observation. Suppose player I plays 1 or 3; the best response of player II is to play 1. In both cases, player I loses and player II wins. So the best action for player I is to play 2. In this case, the best response for player II is to play 3, which minimizes the loss. In this case, (2, 3) is a pure-strategy Nash equilibrium in this game.

For illustration, consider the following mixed strategy case. Assume that player I selects i with probability $p_ i,\, i = 1, 2, 3$, and player II selects j with probability $q_ j,\, j = 1, 2, 3, 4$. Consider player II’s problem of minimizing the maximum expected payout:

\[ \displaystyle \mathop {\min }_{\mathbf{q}}\left\{ \displaystyle \mathop {\max }_{i} \sum _{j = 1}^4 a_{ij}q_ j \right\} \quad {\mathrm{ subject \ to}} \; \; \sum _{j = 1}^4 q_{ij} = 1, \quad \mathbf{q} \geq 0 \]

This is equivalent to

\[ \begin{array}{rcrccl} \displaystyle \mathop {\min }_{\mathbf{q}, v}\; v & {\mathrm{ subject \ to}} & \displaystyle \mathop \sum _{j = 1}^4 a_{ij}q_ j & \leq & v & \forall \, i \\ & & \displaystyle \mathop \sum _{j=1}^4 q_ j & = & 1 & \\ & & \mathbf{q} & \geq & 0 & \end{array} \]

The problem can be transformed into a more standard format by making a simple change of variables: $x_ j = q_ j / v$. The preceding LP formulation now becomes

\[ \begin{array}{rcrccl} \displaystyle \mathop {\min }_{\mathbf{x}, v}\; v & {\mathrm{ subject \ to}} & \displaystyle \mathop \sum _{j = 1}^4 a_{ij}x_ j & \leq & 1 & \forall \, i \\ & & \displaystyle \mathop \sum _{j=1}^4 x_ j & = & 1/v & \\ & & \mathbf{q} & \geq & 0 & \end{array} \]

which is equivalent to

\[ \displaystyle \mathop {\max }_{\mathbf{x}}\; \sum _{j = 1}^4 x_ j \quad {\mathrm{ subject \ to} }\; \; A\mathbf{x} \leq \mathbf{1}, \quad \mathbf{x} \geq 0 \]

where A is the payoff matrix and $\mathbf{1}$ is a vector of 1’s. It turns out that the corresponding optimization problem from player I’s perspective can be obtained by solving the dual problem, which can be written as

\[ \displaystyle \mathop {\min }_{\mathbf{y}}\; \sum _{i = 1}^3 y_ i \quad {\mathrm{ subject \ to}} \; \; A^\textrm {T}\mathbf{y} \geq \mathbf{1}, \quad \mathbf{y} \geq 0 \]

You can model the problem and solve it by using PROC OPTMODEL as follows: 

proc optmodel;
   num a{1..3, 1..4}=[-5 3 1 8
                       5 5 4 6
                      -4 6 0 5];
   var x{1..4} >= 0;
   max f = sum{i in 1..4}x[i];
   con c{i in 1..3}: sum{j in 1..4}a[i,j]*x[j] <= 1;
   solve with lp / algorithm = ps presolver = none logfreq = 1;
   print x;
   print c.dual;
quit;

The optimal solution is displayed in Output 7.3.1.

Output 7.3.1: Optimal Solutions to the Two-Person Zero-Sum Game

The OPTMODEL Procedure

Problem Summary
Objective Sense Maximization
Objective Function f
Objective Type Linear
   
Number of Variables 4
Bounded Above 0
Bounded Below 4
Bounded Below and Above 0
Free 0
Fixed 0
   
Number of Constraints 3
Linear LE (<=) 3
Linear EQ (=) 0
Linear GE (>=) 0
Linear Range 0
   
Constraint Coefficients 11

Performance Information
Execution Mode Single-Machine
Number of Threads 1

Solution Summary
Solver LP
Algorithm Primal Simplex
Objective Function f
Solution Status Optimal
Objective Value 0.25
   
Primal Infeasibility 0
Dual Infeasibility 0
Bound Infeasibility 0
   
Iterations 3
Presolve Time 0.00
Solution Time 0.00

[1] x
1 0.00
2 0.00
3 0.25
4 0.00

[1] c.DUAL
1 0.00
2 0.25
3 0.00 




            

            


            
The optimal solution $\mathbf{x}^* = (0, 0, 0.25, 0)$ with an optimal value of 0.25. Therefore the optimal strategy for player II is $\mathbf{q}^* = \mathbf{x}^*/0.25 = (0, 0, 1, 0)$. You can check the optimal solution of the dual problem by using the constraint suffix ".dual". So $\mathbf{y}^* = (0, 0.25, 0)$ and player I’s optimal strategy is (0, 1, 0). The solution is consistent with our intuition from observation.