Prev Next Top RockPaperScissor

 \newcommand{\P}{{\bf P}}
Rock Paper Scissor as a Zero Sum Matrix Game

The Game
We consider a game where players  X and  Y simultaneously (and repeatedly) choose one of the following options: Rock, Paper, or Scissor. The following table gives the payoff from player  Y to player  X for each of the possible cases
 X
Rock Paper Scissor
Rock 0 -1 1
 Y Paper 1 0 -1
Scissor -1 1 0
Each player tries to guess the others strategy and thereby improve their expected outcomes.

Mathematical Formulation
We define the matrix  \[
A = \left( \begin{array}{ccc}
 0 & -1 &  1  \\
 1 &  0 & -1 \\
-1 &  1 &  0
\end{array} \right)
\]  The optimal strategy for  X (if the strategy is discovered by  Y ) solves the following problem  \[
{\rm maximize} \left[ \min_{ y \in \P (3) } y^T A x \right] 
     {\rm \; w.r.t \; } x \in \P (3)
\]  The optimal strategy for  Y (if the strategy is discovered by  X ) solves the following problem  \[
{\rm minimize} \left[ \max_{ x \in \P (3) } y^T A x \right] 
     {\rm \; w.r.t \; } y \in \P (3)
\] 

Optimal Strategy
We guess that the optimal strategy for player  X and  Y are  \hat{x} = (1 , 1 , 1) / 3 and  \hat{y} = (1 , 1 , 1) / 3 . In this case we also think that the corresponding payoff value is zero; i.e.,  \[
     0 = \hat{y}^T A \hat{x}
\]  We can check this by checking that  \hat{x} is feasible for the corresponding primal problem,  \hat{y} is feasible for the corresponding dual problem, and the primal and dual have the same object value zero at these points.

Primal Problem
The matrix game primal problem is  \[
\begin{array}{ll}
{\rm maximize}      
     & (1 , 0 , 0 , 0 ) 
     \left( \begin{array}{c} z \\ x \end{array} \right)
     {\rm \; w.r.t. \;} z \in \R  \; , \; x \in \R_+^3 
\\
{\rm subject \; to} 
     & \left( \begin{array}{lllll}
          0  &  1 &  1 &  1   \\
          1  &  0 &  1 & -1   \\
          1  & -1 &  0 &  1  \\
          1  &  1 & -1 &  0
     \end{array} \right) 
     \left( \begin{array}{c} 
          z \\ 
          x_1 \\
          x_2 \\
          x_3 
     \end{array} \right)
     \begin{array}{cc} 
          =    & 1 \\ 
          \leq & 0 \\ 
          \leq & 0 \\ 
          \leq & 0 
     \end{array} 
\end{array}
\]  Using the argument value  ( \hat{z} , \hat{x}^T ) = (0, 1/3, 1/3, 1/3) , the corresponding primal objective is zero and the primal feasibility conditions check out because  \[
\begin{array}{ll}
     & \left( \begin{array}{lllll}
          0  &  1 &  1 &  1   \\
          1  &  0 &  1 & -1   \\
          1  & -1 &  0 &  1  \\
          1  &  1 & -1 &  0
     \end{array} \right) 
     \left( \begin{array}{c} 
          0 \\ 
          1/3 \\
          1/3 \\
          1/3 
     \end{array} \right)
     \begin{array}{cc} 
          =    & 1 \\ 
          \leq & 0 \\ 
          \leq & 0 \\ 
          \leq & 0 
     \end{array} 
\end{array}
\] 

Dual Problem
The matrix game dual problem is  \[
\begin{array}{ll}
{\rm minimize}      
     & (1 , 0 , 0 , 0 ) 
     \left( \begin{array}{c} w \\ y \end{array} \right)
     {\rm \; w.r.t. \;} w \in \R  \; , \; y \in \R_+^3 
\\
{\rm subject \; to} 
     & \left( \begin{array}{lllll}
          0  &  1 &  1 &  1   \\
          1  &  0 & -1 &  1   \\
          1  &  1 &  0 & -1  \\
          1  & -1 &  1 &  0
     \end{array} \right) 
     \left( \begin{array}{c} 
          w \\ 
          y_1 \\
          y_2 \\
          y_3 
     \end{array} \right)
     \begin{array}{cc} 
          =    & 1 \\ 
          \geq & 0 \\ 
          \geq & 0 \\ 
          \geq & 0 
     \end{array} 
\end{array}
\]  Using the argument value  ( \hat{w} , \hat{y}^T ) = (0, 1/3, 1/3, 1/3) , the corresponding dual objective is zero and the primal feasibility conditions check out because  \[
\begin{array}{ll}
     & \left( \begin{array}{lllll}
          0  &  1 &  1 &  1   \\
          1  &  0 & -1 &  1   \\
          1  &  1 &  0 & -1  \\
          1  & -1 &  1 &  0
     \end{array} \right) 
     \left( \begin{array}{c} 
          0 \\ 
          1/3 \\
          1/3 \\
          1/3 
     \end{array} \right)
     \begin{array}{cc} 
          =    & 1 \\ 
          \geq & 0 \\ 
          \geq & 0 \\ 
          \geq & 0 
     \end{array} 
\end{array}
\] 
Input File: RockPaperScissor.omh