The Lemke-Howson algorithm - exercises

  1. Define the Lemke-Howson algorithm
  2. Draw the best response polytopes and use the Lemke-Howson algorithm (with all possible starting labels) for the following games:
    1. $ A = \begin{pmatrix} 3 & -1\\ 2 & 7\end{pmatrix} \qquad B = \begin{pmatrix} -3 & 1\\ 1 & -6\end{pmatrix} $
    2. $ A = \begin{pmatrix} 2 & -1\\ 1 & 3\end{pmatrix} \qquad B = \begin{pmatrix} -2 & 2\\ 1 & -2\end{pmatrix} $
  3. Use the tableaux representation to execute the Lemke-Howson algorithm (using starting label: 0) on the games of question 2.