Game Theory

Exercise 11.1

Let \(y\) and \(x\) denote the strategy for players A and B respectively. The strategy consists of two choices \(\{a, b\}_{> 0}\). The corresponding payoff matrix is

\[\begin{split}A = \begin{bmatrix} -a & a\\ b & -b \end{bmatrix}.\end{split}\]

Player B seeks a strategy \(x^*\) that attains optimality in the following LP:

\[\begin{split}\begin{aligned} & \mathcal{P} \quad \underset{x}{\text{maximize}} & v &\\ & \text{subject to} & \begin{bmatrix} -A & e\\ e^\top & 0 \end{bmatrix} \begin{bmatrix} x\\ v \end{bmatrix} &\begin{matrix} \leq\\ = \end{matrix} \begin{bmatrix} 0\\ 1 \end{bmatrix}\\ & & x &\geq 0 \end{aligned} \quad \iff \quad \begin{aligned} & \underset{x}{\text{maximize}} & v &\\ & \text{subject to} & a x_1 - a x_2 + v &\leq 0\\ & & -b x_1 + b x_2 + v &\leq 0\\ & & x_1 + x_2 &= 1\\ & & x_1, x_2 &\geq 0. \end{aligned}\end{split}\]

Converting to standard form yields

\[\begin{split}\begin{aligned} & \underset{x}{\text{maximize}} & v &\\ & \text{subject to} & 2a x_1 + v &\leq a\\ & & -2b x_1 + v &\leq -b\\ & & x_1 &\leq 1\\ & & x_1 &\geq 0. \end{aligned}\end{split}\]

The initial feasible dictionary is

\[\begin{split}\begin{array}{r c r c r c r} \epsilon & = & & & & & v\\ \hline x_3 & = & a & - & 2 a x_1 & - & v\\ x_4 & = & -b & + & 2 b x_1 & - & v\\ x_2 & = & 1 & - & x_1. \end{array}\end{split}\]

Since \(v\) is a free variable, choose \(v\) and \(x_4\) as the entering and leaving variable respectively where

\[v = \min \left\{ x_3, x_4 \right\} = \min \left\{ a, -b \right\}.\]

Pivot dictionary to

\[\begin{split}\begin{array}{r c r c r c r} \epsilon & = & -b & + & 2 b x_1 & - & x_4\\ \hline x_3 & = & (a + b) & - & 2 (a + b) x_1 & + & x_4\\ x_2 & = & 1 & - & x_1 & & \end{array}\end{split}\]

where \(v = \epsilon\).

Choose \(x_1\) and \(x_3\) as the entering and leaving variable respectively where

\[x_1 = \min \left\{ x_3, x_2 \right\}_{\geq 0} = \min \left\{ \frac{1}{2}, 1 \right\}_{\geq 0}.\]

Pivot dictionary to

\[\begin{split}\begin{array}{r c r c r c r} \epsilon & = & & - & \frac{b}{a + b} x_3 & - & \frac{a}{a + b} x_4\\ \hline x_1 & = & \frac{1}{2} & - & \frac{1}{2 (a + b)} x_3 & + & \frac{1}{2 (a + b)} x_4\\ x_2 & = & \frac{1}{2} & + & \frac{1}{2 (a + b)} x_3 & - & \frac{1}{2 (a + b)} x_4. \end{array}\end{split}\]

The optimal strategy for player B is a uniform random strategy. By the strong duality theorem, optimal strategy for player A is \(y_1^* = \frac{b}{a + b}\) and \(y_2^* = \frac{a}{a + b}\).

The value of the game is \(v^* = \epsilon^* = 0\), which indicates that the game is fair for arbitrary denominations.

Exercise 11.2

Let \(y\) and \(x\) denote the strategy for players A and B respectively. The corresponding payoff matrix is a skew-symmetric matrix

\[\begin{split}A = L - L^\top \quad \text{where} \quad L = \begin{bmatrix} 0\\ -1 & 0 & & \LARGE 0\\ & \ddots & \ddots\\ & \LARGE 1 & \ddots & 0\\ & & & -1 & 0 \end{bmatrix}.\end{split}\]

Since \(-A^\top = A\), the game is symmetric and hence fair. This means both players have the same set of pure strategies and the same optimal mixed strategies.

Player B seeks a strategy \(x^*\) that attains optimality in the following LP:

\[\begin{split}\begin{aligned} & \underset{x}{\text{maximize}} & v &\\ & \text{subject to} & v - \sum_{i = 1}^{k - 2} x_i + \mathop{\sum_{k' = k - 1}^{k + 1}}_{1 \leq k' \leq n} (k - k') x_{k'} + \sum_{j = k + 2}^n x_j &\leq 0 \quad \forall k = 1, \ldots, n\\ & & e^\top x &= 1\\ & & x_1, \ldots, x_n &\geq 0. \end{aligned}\end{split}\]

Converting to standard form gives

\[\begin{split}\begin{aligned} & \underset{x}{\text{maximize}} & v &\\ & \text{subject to} & v - \sum_{i = 1}^{k - 2} 2 x_i - x_k - 2 x_{k + 1} &\leq -1 \quad \forall k = 1, \ldots, n - 2\\ & & v + 2 x_{n - 2} + x_{n - 1} &\leq 1\\ & & v - \sum_{i = 1}^{n - 2} x_i + x_{n - 1} &\leq 0\\ & & \sum_{i = 1}^{n - 1} x_i &\leq 1\\ & & x_1, \ldots, x_{n - 1} &\geq 0. \end{aligned}\end{split}\]

The initial feasible dictionary is

\[\begin{split}\begin{array}{r c r c} \epsilon & = & v\\ \hline x_{n + k} & = & -1 + \sum_{i = 1}^{k - 2} 2 x_i + x_k + 2 x_{k + 1} - v & k = 1, \ldots n - 2\\ x_{2n - 1} & = & 1 - 2 x_{n - 2} - x_{n - 1} - v\\ x_{2n} & = & \sum_{i = 1}^{n - 2} x_i - x_{n - 1} - v\\ x_n & = & 1 - \sum_{i = 1}^{n - 1} x_i. \end{array}\end{split}\]

\(n = 1\)

There is only one trivial strategy available.

\(n = 2\)

Choose \(v\) and \(x_4\) as the entering and leaving variable respectively where

\[v = \min \{ x_3, x_4 \} = \min \{ 1, 0 \}.\]

Pivot dictionary to

\[\begin{split}\begin{array}{r c r c r c r} \epsilon & = & & - & x_1 & - & x_4\\ \hline x_3 & = & 1 & & & + & x_4\\ x_2 & = & 1 & - & x_1 \end{array}\end{split}\]

where \(v = \epsilon\). The already optimal dictionary implies that the optimal strategy is \(x^* = (0, 1) = y^*\).

\(n = 3\)

Choose \(v\) and \(x_4\) as the entering and leaving variable respectively where

\[v = \min \{ x_4, x_5, x_6 \} = \min \{ -1, 1, 0 \}.\]

Pivot dictionary to

\[\begin{split}\begin{array}{r c r c r c r c r} \epsilon & = & -1 & + & x_1 & + & 2 x_2 & - & x_4\\ \hline x_5 & = & 2 & - & 3 x_1 & - & 3 x_2 & + & x_4\\ x_6 & = & 1 & & & - & 3 x_2 & + & x_4\\ x_3 & = & 1 & - & x_1 & - & x_2 \end{array}\end{split}\]

where \(v = \epsilon\).

The final dictionary

\[\begin{split}\begin{array}{r c r c r c r c r} 3 \epsilon & = & & - & x_5 & - & x_6 & - & x_4\\ \hline 3 x_1 & = & 1 & - & x_5 & + & x_6 &\\ 3 x_2 & = & 1 & & & - & x_6 & + & x_4\\ 3 x_3 & = & 1 & + & x_5 & & & - & x_4 \end{array}\end{split}\]

implies that the optimal strategy is \(x^* = \left( \frac{1}{3}, \frac{1}{3}, \frac{1}{3} \right) = y^*\).

\(n \geq 4\)

Choose \(v\) and \(x_5\) as the entering and leaving variable respectively where

\[v = \min \{ x_5, x_6, x_7, x_8 \} = \min \{ -1, -1, 1, 0 \}.\]

Pivot dictionary to

\[\begin{split}\begin{array}{r c r c r c r c r c r} \epsilon & = & -1 & + & x_1 & + & 2 x_2 & & & - & x_5\\ \hline x_6 & = & & - & x_1 & - & x_2 & + & 2 x_3 & + & x_5\\ x_7 & = & 2 & - & x_1 & - & 4 x_2 & - & x_3 & + & x_5\\ x_8 & = & 1 & & & - & x_2 & - & x_3 & + & x_5\\ x_4 & = & 1 & - & x_1 & - & x_2 & - & x_3 \end{array}\end{split}\]

where \(v = \epsilon\).

The final dictionary

\[\begin{split}\begin{array}{r c r c r c r c r c r} 3 \epsilon & = & & - & x_4 & - & x_6 & - & x_7 & - & x_5\\ \hline 3 x_2 & = & 1 & + & x_4 & & & - & x_7 & + & x_5\\ 3 x_3 & = & 1 & - & x_4 & + & x_6 & & & - & x_5\\ 3 x_8 & = & 1 & & & - & x_6 & + & x_7 & + & x_5\\ 3 x_1 & = & 1 & - & x_4 & - & x_6 & + & x_7 \end{array}\end{split}\]

implies that the optimal strategy is \(x^* = \left( \frac{1}{3}, \frac{1}{3}, \frac{1}{3}, 0 \right) = y^*\).

By induction, the optimal strategy for \(n > 4\) is

\[x^* = \left( \frac{1}{3}, \frac{1}{3}, \frac{1}{3}, 0, \ldots, 0 \right) = y^*\]

because there is no incentive to choose a larger number.

Exercise 11.3

Applying (a) and (b) to the payoff matrix gives

\[\begin{split}\begin{bmatrix} -6 & 2 & -4 & -7 & -5\\ 0 & 4 & -2 & -9 & -1\\ -7 & 3 & -3 & -8 & -2\\ 2 & -3 & 6 & 0 & 3 \end{bmatrix} &\implies \begin{bmatrix} -6 & 2 & -4 & -5\\ 0 & 4 & -2 & -1\\ -7 & 3 & -3 & -2\\ 2 & -3 & 6 & 3 \end{bmatrix} & \quad & \text{columns } \{ 1, 3, 5 \} \text{ dominate column } 4\\ &\implies \begin{bmatrix} -6 & 2 & -4 & -5\\ -7 & 3 & -3 & -2\\ 2 & -3 & 6 & 3 \end{bmatrix} & \quad & \text{row } 2 \text{ dominates rows } \{ 1, 3 \}\\ &\implies \begin{bmatrix} 2 & -4 & -5\\ 3 & -3 & -2\\ -3 & 6 & 3 \end{bmatrix} & \quad & \text{columns } \{ 3, 4 \} \text{ dominate column } 1\\ &\implies \begin{bmatrix} 2 & -4 & -5\\ -3 & 6 & 3 \end{bmatrix} & \quad & \text{row } 2 \text{ dominates row } 1\\ &\implies \begin{bmatrix} 2 & -4\\ -3 & 6 \end{bmatrix} & \quad & \text{column } 2 \text{ dominates column } 3.\end{split}\]

(a)

Suppose a new row \(r\) is added to \(A\) such that \(r\) dominates row \(s\) and \(y_r^* \neq 0\). By inspection,

\[\begin{split}a_{rj} &\geq a_{sj} & \quad & \forall j = 1, \ldots, n\\ a_{rj} - \delta_j &= a_{sj} & \quad & \delta_j = a_{rj} - a_{sj} \geq 0\\ \sum_j a_{rj} x_j &= \sum_j (a_{sj} + \delta_j) x_j.\end{split}\]

Furthermore,

\[\begin{split}\min_y y^\top A x^* &= \min_i e_i^\top A x^* & \quad & \text{minimax theorem}\\ &= e_r^\top A x^* & \quad & y_r^* \neq 0\\ &= e_s^\top A x^* + \delta^\top x^*\\ &\geq e_s^\top A x^*\end{split}\]

contradicts the definition of a minimum. Therefore, \(y_r^* = 0\) and dominate rows can be removed without affecting the value of the game.

(b)

Suppose a new column \(c\) is added to \(A\) such that \(c\) dominates column \(s\) and \(x_s^* \neq 0\). By inspection,

\[\begin{split}a_{ic} &\geq a_{is} & \quad & \forall i = 1, \ldots, m\\ a_{ic} - \delta_i &= a_{is} & \quad & \delta_i = a_{ic} - a_{is} \geq 0\\ \sum_i (a_{ic} - \delta_i) y_i &= \sum_i a_{is} y_i.\end{split}\]

Furthermore,

\[\begin{split}\max_x x^\top A^\top y^* &= \max_j e_j^\top A^\top y^* & \quad & \text{minimax theorem}\\ &= e_s^\top A^\top y^* & \quad & x_s^* \neq 0\\ &= e_c^\top A^\top y^* - \delta^\top y^*\\ &\leq e_c^\top A^\top y^*\end{split}\]

contradicts the definition of a maximum. Therefore, \(x_s^* = 0\) and dominated columns can be removed without affecting the value of the game.

Exercise 11.4

from enum import Enum

class Action(Enum):
    BET = 1
    PASS = 0

class StrategyA:
    def __init__(self, pure_strategies):
        lines = [
            StrategyA.__line1, StrategyA.__line2, StrategyA.__line3
        ]
        self.action_plans = []
        for ps in pure_strategies:
            self.action_plans.append(lines[ps - 1])

    def invoke(self, card_dealt):
        return self.action_plans[card_dealt - 1]()

    @staticmethod
    def __line1():
        return Action.PASS,\
               lambda _: Action.PASS

    @staticmethod
    def __line2():
        return Action.PASS,\
               lambda action: Action.BET if action == Action.BET else Action.PASS

    @staticmethod
    def __line3():
        return Action.BET,\
               lambda _: Action.BET

class StrategyB:
    def __init__(self, pure_strategies):
        lines = [
            StrategyB.__line1, StrategyB.__line2,
            StrategyB.__line3, StrategyB.__line4
        ]
        self.action_plans = []
        for ps in pure_strategies:
            self.action_plans.append(lines[ps - 1])

    def invoke(self, card_dealt, other_action):
        return self.action_plans[card_dealt - 1](other_action)

    @staticmethod
    def __line1(_):
        return Action.PASS

    @staticmethod
    def __line2(action):
        return Action.PASS if action == Action.PASS else Action.BET

    @staticmethod
    def __line3(action):
        return Action.BET if action == Action.PASS else Action.PASS

    @staticmethod
    def __line4(_):
        return Action.BET

import itertools
import numpy

def paymentA2B(pure_strategies_A, pure_strategies_B, ante=1, bet=1):
    A = StrategyA(pure_strategies_A)
    B = StrategyB(pure_strategies_B)

    total_payment = 0
    count = 0
    for cards_dealt in itertools.product([1, 2, 3], [1, 2, 3]):
        a, b = cards_dealt
        if a == b:
            #card game is without replacement
            continue

        A_action, A_response = A.invoke(a)
        B_action = B.invoke(b, A_action)
        end_turn = A_response(B_action)

        pot = 0
        if A_action == Action.PASS and B_action == Action.PASS:
            if a > b:
                pot = -ante
            elif a < b:
                pot = ante
        elif A_action == Action.PASS and B_action == Action.BET and end_turn == Action.PASS:
            pot = ante
        elif A_action == Action.PASS and B_action == Action.BET and end_turn == Action.BET:
            if a > b:
                pot = -ante - bet
            elif a < b:
                pot = ante + bet
        elif A_action == Action.BET and B_action == Action.PASS:
            pot = -ante
        elif A_action == Action.BET and B_action == Action.BET:
            if a > b:
                pot = -ante - bet
            elif a < b:
                pot = ante + bet

        count += 1
        total_payment += pot

    return total_payment / count

a_strategies = [
    (1, 1, 2), (1, 1, 3), (1, 2, 2), (1, 2, 3),
    (3, 1, 2), (3, 1, 3), (3, 2, 2), (3, 2, 3)
]
b_strategies = [
    (1, 1, 4), (1, 2, 4), (3, 1, 4), (3, 2, 4)
]

payoff_matrix = []
for psa in a_strategies:
    payoffs = []
    for psb in b_strategies:
        payoffs.append(paymentA2B(psa, psb, ante=2))
    payoff_matrix.append(payoffs)

A = numpy.asarray(payoff_matrix)
print(A)

[[ 0.          0.          0.5         0.5       ]
 [ 0.         -0.16666667  0.66666667  0.5       ]
 [ 0.16666667  0.16666667 -0.16666667 -0.16666667]
 [ 0.16666667  0.          0.         -0.16666667]
 [-0.5         0.33333333  0.          0.83333333]
 [-0.5         0.16666667  0.16666667  0.83333333]
 [-0.33333333  0.5        -0.66666667  0.16666667]
 [-0.33333333  0.33333333 -0.5         0.16666667]]

def solveDualMatrixGame(A):
    P = numpy.column_stack((-A.T, numpy.ones(A.T.shape[0])))

    n = A.T.shape[1] + 1
    c = numpy.zeros(n)
    c[-1] = 1

    from pymprog import model

    lp = model('LP')

    #lp.verbose(True)
    y = lp.var('y', n, bounds=(None, None))
    for j in range(n - 1):
        lp.st(y[j] >= 0)

    lp.minimize(sum(c[j] * y[j] for j in range(n)))

    for row in range(P.shape[0]):
        sum(P[row, col] * y[col] for col in range(n)) >= 0

    sum(y[j] for j in range(n - 1)) == 1

    lp.solve()
    lp.sensitivity()

    lp.end()

solveDualMatrixGame(A)

PyMathProg 1.0 Sensitivity Report Created: 2020/04/05 Sun 03:20AM
================================================================================
Variable            Activity   Dual.Value     Obj.Coef   Range.From   Range.Till
--------------------------------------------------------------------------------
 y[0]                      0    0.0666667            0   -0.0666667          inf
*y[1]                    0.2            0            0    -0.333333            0
 y[2]                      0    0.0666667            0   -0.0666667          inf
*y[3]                    0.6            0            0            0    0.0666667
 y[4]                      0    0.0666667            0   -0.0666667          inf
 y[5]                      0            0            0            0          inf
 y[6]                      0    0.0666667            0   -0.0666667          inf
*y[7]                    0.2            0            0    -0.333333            0
*y[8]              0.0333333            0            1            0 1.79769e+308
================================================================================
================================================================================
Constraint       Activity Dual.Value  Lower.Bnd  Upper.Bnd RangeLower RangeUpper
--------------------------------------------------------------------------------
 R1                     0        0.4          0        inf          0        0.5
 R2                     0        0.4          0        inf  -0.166667          0
*R3                     0          0          0        inf          0          0
 R4                     0        0.2          0        inf          0   0.166667
 R5                     1  0.0333333          1          1          0 1.79769e+308
================================================================================

def solvePrimalMatrixGame(A):
    P = numpy.column_stack((-A, numpy.ones(A.shape[0])))

    n = A.shape[1] + 1
    c = numpy.zeros(n)
    c[-1] = 1

    from pymprog import model

    lp = model('LP')

    #lp.verbose(True)
    x = lp.var('x', n, bounds=(None, None))
    for i in range(n - 1):
        lp.st(x[i] >= 0)

    lp.maximize(sum(c[i] * x[i] for i in range(n)))

    for row in range(P.shape[0]):
        sum(P[row, col] * x[col] for col in range(n)) <= 0

    sum(x[i] for i in range(n - 1)) == 1

    lp.solve()
    lp.sensitivity()

    lp.end()

solvePrimalMatrixGame(A)

PyMathProg 1.0 Sensitivity Report Created: 2020/04/05 Sun 03:20AM
================================================================================
Variable            Activity   Dual.Value     Obj.Coef   Range.From   Range.Till
--------------------------------------------------------------------------------
*x[0]                    0.4            0            0            0            0
*x[1]                    0.4            0            0            0            0
 x[2]                      0            0            0         -inf            0
*x[3]                    0.2            0            0            0            0
*x[4]              0.0333333            0            1            0 1.79769e+308
================================================================================
================================================================================
Constraint       Activity Dual.Value  Lower.Bnd  Upper.Bnd RangeLower RangeUpper
--------------------------------------------------------------------------------
*R1            -0.0666667          0       -inf          0 -0.0666667 -0.0666667
 R2                     0          0       -inf          0          0   0.111111
*R3            -0.0666667          0       -inf          0 -0.0666667 -0.0666667
 R4                     0        0.8       -inf          0  -0.166667          0
*R5            -0.0666667          0       -inf          0 -0.0666667 -0.0666667
 R6                     0        0.2       -inf          0  -0.333333          0
*R7            -0.0666667          0       -inf          0 -0.0666667 -0.0666667
*R8                     0          0       -inf          0          0          0
 R9                     1  0.0333333          1          1          0 1.79769e+308
================================================================================

Exercise 11.5

The simultaneously optimality of the \(r\text{th}\) pure strategy of the row and the \(s\text{th}\) pure strategy of the column player requires \(y^*, x^*\) to be indicator vectors. This means \(r\) is dominated by all the other rows and \(s\) dominates all the other columns.

Exercise 11.6

Suppose \(x^*\) and \(y^*\) are the optimal strategies. The Minimax Theorem guarantees that

\[\max_x {y^*}^\top A x = \min_y y^\top A x^*.\]

By the Strong Duality Theorem,

\[{y^*}^\top A x^* \geq \min_y y^\top A x^* = \max_x {y^*}^\top A x \geq {y^*}^\top A x^*\]

and

\[{y^*}^\top A x \leq {y^*}^\top A x^* \leq y^\top A x^*\]

for all \(x, y\). Thus

\[\max_x \min_y y^\top A x = \min_y \max_x y^\top A x.\]

Exercise 11.7

Given a matrix \(M \in \mathbb{R}^{n \times n}\) and a vector \(q \in \mathbb{R}^n\), the linear complementarity problem (LCP) is to find vectors \(u, v \in \mathbb{R}^n\) satisfying the relations [Cha]:

\[\begin{split}u = Mv + q\\ u \geq 0; v \geq 0\\ u^\top v = 0.\end{split}\]

The reason for the term “complementarity” in the name of the problem is due to

\[\begin{split}\begin{aligned} u \geq 0; v \geq 0\\ u^\top v = 0 \end{aligned} \iff \begin{aligned} u_i v_i = 0 \, \forall \, i. \end{aligned}\end{split}\]

The stochastic vectors \(x^*\) and \(y^*\) form a Nash equilibrium pair if they satisfy

\[\begin{split}{y^*}^\top A x^* &\leq y^\top A x^* \quad \forall \, y\\ {y^*}^\top B x^* &\leq {y^*}^\top B x \quad \forall \, x\end{split}\]

where \(A, B \in \mathbb{R}^{m \times n}\) are loss matrices of the row and column players respectively. Since \(e^\top x^* = \sum_j x^*_j = 1\) and \(e^\top y^* = \sum_i y^*_i = 1\), the preceding relations are equivalent to

\[\begin{split}\left( {y^*}^\top A x^* \right) e &\leq A x^*\\ \left( {y^*}^\top B x^* \right) e &\leq B^\top y^*.\end{split}\]

The equivalent LCP formulation is

\[\begin{split}w &= Ax - e\\ z &= B^\top y - e\\ x &\geq 0; y \geq 0; w \geq 0; z \geq 0\\ y^\top w &= 0; x^\top z = 0\end{split}\]

and

\[\begin{split}M = \begin{bmatrix} 0 & A\\ B^\top & 0 \end{bmatrix}; q = \begin{bmatrix} -e\\ -e \end{bmatrix}\\ u = \begin{bmatrix} w\\ z \end{bmatrix}; v = \begin{bmatrix} y\\ x \end{bmatrix}.\end{split}\]

(a)

Let \(C = A + kJ\) and \(D = B + kJ\) where \(k\) is the smallest scalar such that the all-ones matrix \(J\) forces \(C\) and \(D\) to be positive matrices. Any equilibrium pair of strategies for \((A, B)\) is also an equilibrium pair of strategies for \((C, D)\):

\[\begin{split}{y^*}^\top C x^*&\leq y^\top C x^*\\ {y^*}^\top A x^* + {y^*}^\top kJ x^* &\leq y^\top A x^* + y^\top kJ x^*\\ {y^*}^\top A x^* + {y^*}^\top ke &\leq y^\top A x^* + y^\top ke & \quad & J x^* = e\\ {y^*}^\top A x^* + k &\leq y^\top A x^* + k & \quad & y \cdot e = 1\\ {y^*}^\top A x^* &\leq y^\top A x^*.\end{split}\]

The proof is the same for \(B\) and \(D\).

(b)

Suppose \((x^*, y^*)\) is a Nash equilibrium and \(A, B\) are positive matrices such that

\[\begin{split}\left( {y^*}^\top A x^* \right) e &\leq A x^*\\ e &\leq Ax' & \quad & x' = \frac{x^*}{{y^*}^\top A x^*}\\ 0 &\leq w\end{split}\]

and

\[\begin{split}\left( {y^*}^\top B^\top x^* \right) e &\leq B^\top y^*\\ e &\leq B^\top y' & \quad & y' = \frac{y^*}{{y^*}^\top B^\top x^*}\\ 0 &\leq z.\end{split}\]

The remaining LCP relations are also satisfied because

\[\begin{split}{y'}^\top w &= {y'}^\top A x' - {y'}^\top e\\ &= \frac{{y^*}^\top}{{y^*}^\top B^\top x^*} A \frac{x^*}{{y^*}^\top A x^*} - \frac{{y^*}^\top e}{{y^*}^\top B^\top x^*}\\ &= \frac{1}{{y^*}^\top B^\top x^*} - \frac{1}{{y^*}^\top B^\top x^*}\\ &= 0.\end{split}\]

The proof is the same for \({x'}^\top z\). Therefore, \((x', y')\) solves the LCP.

(c)

Suppose \((x', y')\) solves the LCP such that

\[\begin{split}\begin{aligned} 0 &= {y'}^\top w\\ &= {y'}^\top A x' - {y'}^\top e\\ e^\top y' &= {y'}^\top A x'\\ 1 &= \frac{{y'}^\top A x'}{e^\top y'} \end{aligned} \qquad \text{and} \qquad \begin{aligned} 0 &= {x'}^\top z\\ &= {x'}^\top B^\top y' - {x'}^\top e\\ e^\top x' &= {x'}^\top B^\top y'\\ 1 &= \frac{{x'}^\top B^\top y'}{e^\top x'}. \end{aligned}\end{split}\]

The conditions for \((x^*, y^*)\) to form a Nash equilibrium is satisfied because

\[\begin{split}w &\geq 0\\ A x' &\geq e\\ A x^* &\geq \frac{e}{{x'}^\top e} & \quad & x^* = \frac{x'}{e^\top x'}\\ &\geq \frac{{y'}^\top A x'}{e^\top y'} \frac{e}{{x'}^\top e}\\ &\geq \left( {y^*}^\top A x^* \right) e.\end{split}\]

The proof is the same for \(z \geq 0\). Therefore, \((x^*, y^*)\) is a Nash equilibrium.

Exercise 11.8

Since players A and B can only throw out one or two fingers, the total sum of the outstretched fingers are:

	Player B 1	Player B 2
Player A 1	2	3
Player A 2	3	4

(a)

The players’ pure strategies can be denoted by \((g_1, g_2)\) where \(g_i \in \{ 2, 3, 4 \}\) is the player’s guess when throwing out \(i \in \{ 1, 2 \}\) fingers. Each player has a total of \(3 \times 3 = 9\) pure strategies. Thus there are \(9 \times 9 = 81\) pairs.

(b)

The following observations reveal that certain strategies are nonsensical:

• A player throwing out one finger should never guess four.

• A player throwing out two fingers should never guess two.

After eliminating these strategies from consideration, each player has \(2 \times 2 = 4\) pure strategies.

(c)

The formulation is given by (11.4).

(d)

This is a symmetric fair game; hence, the value of the game is zero.

(e)

The optimal randomized strategy is to uniformly throw one or two finger while using the pure strategy \((g_1 = 3, g_2 = 4)\).

def paymentA2B(psa, psb):
    total_payment = 0
    count = 0
    for fingers_thrown in itertools.product([1, 2], [1, 2]):
        a_fingers, b_fingers = fingers_thrown
        total_fingers = a_fingers + b_fingers

        a_guess = psa[a_fingers - 1]
        b_guess = psb[b_fingers - 1]

        if a_guess == total_fingers and b_guess != total_fingers:
            total_payment -= total_fingers
        elif a_guess != total_fingers and b_guess == total_fingers:
            total_payment += total_fingers

        count += 1
    return total_payment / count

a_strategies = [
    (2, 3), (2, 4), (3, 3), (3, 4)
]
b_strategies = [
    (2, 3), (2, 4), (3, 3), (3, 4)
]

payoff_matrix = []
for psa in a_strategies:
    payoffs = []
    for psb in b_strategies:
        payoffs.append(paymentA2B(psa, psb))
    payoff_matrix.append(payoffs)

A = numpy.asarray(payoff_matrix)
print(A)

solveDualMatrixGame(A)

[[ 0.    0.25  0.25  0.5 ]
 [-0.25  0.    0.    0.25]
 [-0.25  0.    0.    0.25]
 [-0.5  -0.25 -0.25  0.  ]]

PyMathProg 1.0 Sensitivity Report Created: 2020/04/05 Sun 03:20AM
================================================================================
Variable            Activity   Dual.Value     Obj.Coef   Range.From   Range.Till
--------------------------------------------------------------------------------
 y[0]                      0          0.5            0         -0.5          inf
 y[1]                      0         0.25            0        -0.25          inf
 y[2]                      0         0.25            0        -0.25          inf
*y[3]                      1            0            0 -1.79769e+308         0.25
*y[4]                      0            0            1            0 1.79769e+308
================================================================================
================================================================================
Constraint       Activity Dual.Value  Lower.Bnd  Upper.Bnd RangeLower RangeUpper
--------------------------------------------------------------------------------
*R1                   0.5          0          0        inf        0.5        0.5
*R2                  0.25          0          0        inf       0.25       0.25
*R3                  0.25          0          0        inf       0.25       0.25
 R4                     0          1          0        inf      -0.25 1.79769e+308
 R5                     1          0          1          1          0 1.79769e+308
================================================================================

Exercise 11.9

There are three possible betting scenarios:

1. Player A leaves: $1 goes to player B.

2. Player A stays and player B leaves: $1 goes to player A.

3. Player A stays and player B stays: $2 goes to player A if the fair coin flip resulted in heads, otherwise $2 goes to player B.

(a)

Player A’s pure strategy can be denoted by \((y_1, y_2)\) where \(y_i \in \{ \text{leave}, \text{stay} \}\) is player A’s action when the observed outcome is \(i \in \{ \text{heads}, \text{tails} \}\).

Player B’s pure strategy \((x_1)\) is dependent on A’s declared action. \(x_1 \in \{ \text{leave}, \text{stay} \}\) is player B’s decision when player A decides to stay. Note that player B wins when player A leaves.

Therefore there are \((2 \times 2) \times (2) = 8\) pairs.

(b)

The accompanying code prints out the reduced payoff matrix.

(c)

Player A should never leave the game when the outcome is heads.

When the outcome is tails, leaving will guarantee a loss of $1, but staying will on average result in \(\alpha (2) + (1 - \alpha) (-1)\) where \(\alpha\) is the probability of player B staying. This strategy should be ruled out when

\[\begin{split}1 &< \alpha (2) + (1 - \alpha) (-1)\\ 2 &< 3 \alpha\\ \frac{2}{3} &< \alpha.\end{split}\]

(d)

The formulation is given by (11.4).

(e)

Player A’s optimal strategy is as follows:

• When heads is observed, always stay.

• When tails is observed, leave \(2/3\) of the time and stay \(1/3\) of the time.

Player B’s optimal strategy is to leave \(1/3\) of the time and stay \(2/3\) of the time.

(f)

This game is neither symmetric nor fair, and it is in player A’s favor. This game is interesting in the sense that there is no way to make the game fair.

def paymentA2B(psa, psb):
    total_payment = 0
    count = 0
    for coin in range(2):
        a_action = psa[coin]
        b_action = psb

        if a_action == LEAVE:
            total_payment += 1
        else:
            if b_action == LEAVE:
                total_payment -= 1
            else:
                if coin == HEADS:
                    total_payment -= 2
                else:
                    total_payment += 2

        count += 1
    return total_payment / count

LEAVE, STAY = range(2)
HEADS, TAILS = range(2)
a_strategies = [
    (STAY, LEAVE), (STAY, STAY)
]
b_strategies = [
    (LEAVE), (STAY)
]

payoff_matrix = []
for psa in a_strategies:
    payoffs = []
    for psb in b_strategies:
        payoffs.append(paymentA2B(psa, psb))
    payoff_matrix.append(payoffs)

A = numpy.asarray(payoff_matrix)
print(A)

solveDualMatrixGame(A)

[[ 0.  -0.5]
 [-1.   0. ]]

PyMathProg 1.0 Sensitivity Report Created: 2020/04/05 Sun 03:20AM
================================================================================
Variable            Activity   Dual.Value     Obj.Coef   Range.From   Range.Till
--------------------------------------------------------------------------------
*y[0]               0.666667            0            0           -1          0.5
*y[1]               0.333333            0            0         -0.5            1
*y[2]              -0.333333            0            1            0 1.79769e+308
================================================================================
================================================================================
Constraint       Activity Dual.Value  Lower.Bnd  Upper.Bnd RangeLower RangeUpper
--------------------------------------------------------------------------------
 R1                     0   0.333333          0        inf       -0.5          1
 R2                     0   0.666667          0        inf         -1        0.5
 R3                     1  -0.333333          1          1          0 1.79769e+308
================================================================================

References

Cha

R. Chandrasekaran. Bimatrix games. http://www.utdallas.edu/ chandra/documents/6311/bimatrix.pdf. Accessed on 2017-08-06.