Prev Next Top

 \newcommand{\P}{{\bf P}}
Zero Sum Matrix Games

Introduction
We are given two players  X and  Y and a matrix  A \in \R^{m \times n} If player  X makes choice  j \in \{ 1 , \ldots , n \} and player  Y makes choice  i \in \{ 1 , \ldots , m \} , player  X wins (player  Y looses)  A_{i,j} units.

Strategy
We use the notation  \P(n) to denote the set of probability measures on the indices  \{ 1 , \ldots , n \} ; i.e.,  \[
     \P ( n ) = \left\{ 
          x \in \R_+^n {\rm \; such \; that \;} \sum_{j=1}^n x_j = 1
     \right\}
\]  If player  X adopts a strategy  x \in \P(n) and player adopts a strategy  y \in \P(m) , the expected winnings for player  X (loosing for player  Y ) is  \[
     y^T A x = \sum_{i=1}^m \sum_{j=1}^n y_i A_{i,j} x_j
\] 

Lemma
For each  \hat{x} \in \R^n and  \hat{y} \in \R^m ,  \[
\begin{array}{rcl}
\inf_{y \in \P(m)} y^T A \hat{x} & = &
     \min_{i=1, \ldots , m} \; \sum_j^n A_{i,j} \hat{x}_j 
\\
\sup_{x \in \P(n)} \hat{y}^T A x & = &
     \max_{j=1, \ldots , n} \; \sum_i^m \hat{y}_i A_{i,j} 
\end{array}
\] 

Proof
Let  k \in \{ 1 , \ldots , m \} be an index such that  \[
\begin{array}{rcl}
\min_{i=1, \ldots , m} \; \sum_j^m A_{i,j} \hat{x}_j  & = &
     \sum_j^n A_{k,j} \hat{x}_j 
\end{array}
\]  Choosing  y \in \P (m) by  y_k = 1 and for  i \neq k ,  y_i = 0 , we conclude that  \[
\begin{array}{rcl}
\inf_{y \in \P(m)} y^T A \hat{x} & \leq &
     \sum_j^n A_{k,j} \hat{x}_j 
\\
& \leq &
     \min_{i=1, \ldots , m} \; \sum_j^n A_{i,j} \hat{x}_j 
\end{array}
\]  But it also follows that  \[
\begin{array}{rcl}
y^T A \hat{x} & = &
     \sum_{i=1}^m y_i \sum_{j=1}^n A_{i,j} \hat{x}_j
\\
& \geq &
     \sum_{i=1}^m y_i \sum_{j=1}^n A_{k,j} \hat{x}_j
\\
& \geq &
     \left( \sum_{j=1}^n A_{k,j} \hat{x}_j \right)
     \sum_{i=1}^m y_i 
\\
& \geq &
     \sum_{j=1}^n A_{k,j} \hat{x}_j 
\\
\inf_{y \in \P(m)} y^T A \hat{x} & \geq &
     \min_{i=1, \ldots , m} \; \sum_j^n A_{i,j} \hat{x}_j 
\end{array}
\]  The completes the proof of the first equation in the lemma. The proof of the second equation is similar.

Primal Problem
Suppose that player  X chooses her strategy first and then player  Y gets to choose his strategy. It follows that player  X should solve the problem the problem  \[
{\rm maximize} \;
      \left[ \min_{y \in \P(m)} \; y^T A x  \right]
     {\rm \; w.r.t. \;} x \in \P (n)
\]  This problem is equivalent to  \[
\begin{array}{cc}
{\rm maximize}      
     & z {\rm \; w.r.t. \;} z \in \R  \; , \; x \in \R_+^n 
\\
{\rm subject \; to} 
     & 1  = \sum_{j=1}^n x_j 
\\
     & z \leq \sum_{j=1}^n A_{i,j} x_j \; (i = 1, \ldots , m)
\end{array}
\]  We use the notation  0_{m \times n} (  1_{m \times n} ) to denote the  m \times n matrix of zeros (ones). The problem above can be written as  \[
\begin{array}{cc}
{\rm maximize}      
     & (1 , 0_{1 \times n} ) 
     \left( \begin{array}{c} z \\ x \end{array} \right)
     {\rm \; w.r.t. \;} z \in \R  \; , \; x \in \R_+^n 
\\
{\rm subject \; to} 
     & \left( \begin{array}{cc}
          0               & 1_{1 \times n} \\
          1_{m \times 1}  & - A 
     \end{array} \right) 
     \left( \begin{array}{c} 
          z \\ 
          x 
     \end{array} \right)
     \begin{array}{cc} 
          =    & 1 \\ 
          \leq & 0_{m \times 1} 
     \end{array} 
\end{array}
\] 

Dual Problem
This problem has the same form as the primal problem with equality and inequality constraints; i.e., DualEqIneq (or equation (9.1) of the text). The correspondence between the notation in DualEqIneq and the notation above is  \[
\left( \begin{array}{c} c_{\pm} \\ c_+ \end{array} \right)
=
\left( \begin{array}{c} 1  \\ 0_{n \times 1}   \end{array} \right)
\; , \; \;
\left( \begin{array}{c} x_{\pm} \\ x_+ \end{array} \right)
=
\left( \begin{array}{c} z    \\ x   \end{array} \right)
\; , \; \;
\left( \begin{array}{cc} 
     A_{=, \pm}    & A_{=, +} \\
     A_{\leq, \pm} & A_{\leq, +}
\end{array} \right)
=
\left( \begin{array}{cc}
          0               & 1_{1 \times n} \\
          1_{m \times 1}  & - A 
\end{array} \right) 
\; , \; \;
\left( \begin{array}{c} b_= \\ b_\leq \end{array} \right)
=
\left( \begin{array}{c} 1  \\ 0_{m \times 1}   \end{array} \right)
\]  Using this correspondence, and  y_= = w ,  y_\leq = y , the dual of the problem above is  \[
\begin{array}{cc}
{\rm minimize}      
     & (1 , 0_{1 \times m} ) 
     \left( \begin{array}{c} w \\ y \end{array} \right)
     {\rm \; w.r.t. \;} w \in \R  \; , \; y \in \R_+^m 
\\
{\rm subject \; to} 
     & \left( \begin{array}{cc}
          0               & 1_{1 \times m} \\
          1_{n \times 1}  & - A^T 
     \end{array} \right) 
     \left( \begin{array}{c} 
          w \\ 
          y 
     \end{array} \right)
     \begin{array}{cc} 
          =    & 1 \\ 
          \geq & 0_{n \times 1} 
     \end{array} 
\end{array}
\]  This problem is equivalent to  \[
\begin{array}{cc}
{\rm minimize}      
     & w {\rm \; w.r.t. \;} w \in \R  \; , \; y \in \R_+^m 
\\
{\rm subject \; to} 
     & 1  = \sum_{i=1}^m y_i 
\\
     & w \geq \sum_{i=1}^m y_i A_{i,j} \; (j = 1, \ldots , n)
\end{array}
\]  Which is also equivalent to  \[
{\rm minimize} \;
      \left[ \max_{x \in \P(n)} \; y^T A x  \right]
     {\rm \; w.r.t. \;} y \in \P (m)
\]  This is the problem that player  Y should solve if  Y chooses his strategy first and then player  X gets to choose here strategy.

Theorem
Duality theory leads us to the conclusion that if both players know linear programming, it does not matter which one goes first; i.e.,  \[
\min_{y \in \P (m)} \; 
     \left[ \max_{x \in \P(n)} \; y^T A x  \right]
=
\max_{x \in \P (n)} \; 
     \left[ \min_{y \in \P(m)} \; y^T A x  \right]
\] 

Examples
RockPaperScissor Rock Paper Scissor as a Zero Sum Matrix Game
Problem15_1 Problem 15.1 of the Text
Quiz0810 Math 407 Summer 06 Quiz 08-10
Input File: MatrixGame.omh