{ "cells": [ { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "***********\n", "Game Theory\n", "***********" ] }, { "cell_type": "raw", "metadata": { "collapsed": true, "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 11.1\n", "=============\n", "\n", "Let :math:`y` and :math:`x` denote the strategy for players A and B\n", "respectively. The strategy consists of two choices :math:`\\{a, b\\}_{> 0}`.\n", "The corresponding payoff matrix is\n", "\n", ".. math::\n", "\n", " A = \\begin{bmatrix} -a & a\\\\ b & -b \\end{bmatrix}.\n", "\n", "Player B seeks a strategy :math:`x^*` that attains optimality in the following\n", "LP:\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " & \\mathcal{P} \\quad \\underset{x}{\\text{maximize}} &\n", " v &\\\\\n", " & \\text{subject to} &\n", " \\begin{bmatrix} -A & e\\\\ e^\\top & 0 \\end{bmatrix}\n", " \\begin{bmatrix} x\\\\ v \\end{bmatrix}\n", " &\\begin{matrix} \\leq\\\\ = \\end{matrix}\n", " \\begin{bmatrix} 0\\\\ 1 \\end{bmatrix}\\\\\n", " & & x &\\geq 0\n", " \\end{aligned}\n", " \\quad \\iff \\quad\n", " \\begin{aligned}\n", " & \\underset{x}{\\text{maximize}} &\n", " v &\\\\\n", " & \\text{subject to} &\n", " a x_1 - a x_2 + v &\\leq 0\\\\\n", " & & -b x_1 + b x_2 + v &\\leq 0\\\\\n", " & & x_1 + x_2 &= 1\\\\\n", " & & x_1, x_2 &\\geq 0.\n", " \\end{aligned}\n", "\n", "Converting to standard form yields\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " & \\underset{x}{\\text{maximize}} &\n", " v &\\\\\n", " & \\text{subject to} &\n", " 2a x_1 + v &\\leq a\\\\\n", " & & -2b x_1 + v &\\leq -b\\\\\n", " & & x_1 &\\leq 1\\\\\n", " & & x_1 &\\geq 0.\n", " \\end{aligned}\n", "\n", "The initial feasible dictionary is\n", "\n", ".. math::\n", "\n", " \\begin{array}{r c r c r c r}\n", " \\epsilon & = & & & & & v\\\\\n", " \\hline\n", " x_3 & = & a & - & 2 a x_1 & - & v\\\\\n", " x_4 & = & -b & + & 2 b x_1 & - & v\\\\\n", " x_2 & = & 1 & - & x_1.\n", " \\end{array}\n", "\n", "Since :math:`v` is a free variable, choose :math:`v` and :math:`x_4` as the\n", "entering and leaving variable respectively where\n", "\n", ".. math::\n", "\n", " v =\n", " \\min \\left\\{ x_3, x_4 \\right\\} =\n", " \\min \\left\\{ a, -b \\right\\}.\n", "\n", "Pivot dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{array}{r c r c r c r}\n", " \\epsilon & = & -b & + & 2 b x_1 & - & x_4\\\\\n", " \\hline\n", " x_3 & = & (a + b) & - & 2 (a + b) x_1 & + & x_4\\\\\n", " x_2 & = & 1 & - & x_1 & &\n", " \\end{array}\n", "\n", "where :math:`v = \\epsilon`.\n", "\n", "Choose :math:`x_1` and :math:`x_3` as the entering and leaving variable\n", "respectively where\n", "\n", ".. math::\n", "\n", " x_1 =\n", " \\min \\left\\{ x_3, x_2 \\right\\}_{\\geq 0} =\n", " \\min \\left\\{ \\frac{1}{2}, 1 \\right\\}_{\\geq 0}.\n", "\n", "Pivot dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{array}{r c r c r c r}\n", " \\epsilon & = & & - & \\frac{b}{a + b} x_3 & - & \\frac{a}{a + b} x_4\\\\\n", " \\hline\n", " x_1 & = & \\frac{1}{2} & - & \\frac{1}{2 (a + b)} x_3 & + &\n", " \\frac{1}{2 (a + b)} x_4\\\\\n", " x_2 & = & \\frac{1}{2} & + & \\frac{1}{2 (a + b)} x_3 & - &\n", " \\frac{1}{2 (a + b)} x_4.\n", " \\end{array}\n", "\n", "The optimal strategy for player B is a uniform random strategy. By the strong\n", "duality theorem, optimal strategy for player A is\n", ":math:`y_1^* = \\frac{b}{a + b}` and :math:`y_2^* = \\frac{a}{a + b}`.\n", "\n", "The value of the game is :math:`v^* = \\epsilon^* = 0`, which indicates that the\n", "game is fair for arbitrary denominations." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 11.2\n", "=============\n", "\n", "Let :math:`y` and :math:`x` denote the strategy for players A and B\n", "respectively. The corresponding payoff matrix is a skew-symmetric matrix\n", "\n", ".. math::\n", "\n", " A = L - L^\\top\n", " \\quad \\text{where} \\quad\n", " L =\n", " \\begin{bmatrix}\n", " 0\\\\\n", " -1 & 0 & & \\LARGE 0\\\\\n", " & \\ddots & \\ddots\\\\\n", " & \\LARGE 1 & \\ddots & 0\\\\\n", " & & & -1 & 0\n", " \\end{bmatrix}.\n", "\n", "Since :math:`-A^\\top = A`, the game is symmetric and hence fair. This means\n", "both players have the same set of pure strategies and the same optimal mixed\n", "strategies.\n", "\n", "Player B seeks a strategy :math:`x^*` that attains optimality in the following\n", "LP:\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " & \\underset{x}{\\text{maximize}} &\n", " v &\\\\\n", " & \\text{subject to} &\n", " v - \\sum_{i = 1}^{k - 2} x_i +\n", " \\mathop{\\sum_{k' = k - 1}^{k + 1}}_{1 \\leq k' \\leq n}\n", " (k - k') x_{k'} +\n", " \\sum_{j = k + 2}^n x_j &\\leq 0\n", " \\quad \\forall k = 1, \\ldots, n\\\\\n", " & & e^\\top x &= 1\\\\\n", " & & x_1, \\ldots, x_n &\\geq 0.\n", " \\end{aligned}\n", "\n", "Converting to standard form gives\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " & \\underset{x}{\\text{maximize}} &\n", " v &\\\\\n", " & \\text{subject to} &\n", " v - \\sum_{i = 1}^{k - 2} 2 x_i - x_k - 2 x_{k + 1} &\\leq -1\n", " \\quad \\forall k = 1, \\ldots, n - 2\\\\\n", " & & v + 2 x_{n - 2} + x_{n - 1} &\\leq 1\\\\\n", " & & v - \\sum_{i = 1}^{n - 2} x_i + x_{n - 1} &\\leq 0\\\\\n", " & & \\sum_{i = 1}^{n - 1} x_i &\\leq 1\\\\\n", " & & x_1, \\ldots, x_{n - 1} &\\geq 0.\n", " \\end{aligned}\n", "\n", "The initial feasible dictionary is\n", "\n", ".. math::\n", "\n", " \\begin{array}{r c r c}\n", " \\epsilon & = & v\\\\\n", " \\hline\n", " x_{n + k} & = & -1 + \\sum_{i = 1}^{k - 2} 2 x_i + x_k + 2 x_{k + 1} - v\n", " & k = 1, \\ldots n - 2\\\\\n", " x_{2n - 1} & = & 1 - 2 x_{n - 2} - x_{n - 1} - v\\\\\n", " x_{2n} & = & \\sum_{i = 1}^{n - 2} x_i - x_{n - 1} - v\\\\\n", " x_n & = & 1 - \\sum_{i = 1}^{n - 1} x_i.\n", " \\end{array}\n", "\n", ":math:`n = 1`\n", "-------------\n", "\n", "There is only one trivial strategy available.\n", "\n", ":math:`n = 2`\n", "-------------\n", "\n", "Choose :math:`v` and :math:`x_4` as the entering and leaving variable\n", "respectively where\n", "\n", ".. math::\n", "\n", " v = \\min \\{ x_3, x_4 \\} = \\min \\{ 1, 0 \\}.\n", "\n", "Pivot dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{array}{r c r c r c r}\n", " \\epsilon & = & & - & x_1 & - & x_4\\\\\n", " \\hline\n", " x_3 & = & 1 & & & + & x_4\\\\\n", " x_2 & = & 1 & - & x_1\n", " \\end{array}\n", "\n", "where :math:`v = \\epsilon`. The already optimal dictionary implies that the\n", "optimal strategy is :math:`x^* = (0, 1) = y^*`.\n", "\n", ":math:`n = 3`\n", "-------------\n", "\n", "Choose :math:`v` and :math:`x_4` as the entering and leaving variable\n", "respectively where\n", "\n", ".. math::\n", "\n", " v =\n", " \\min \\{ x_4, x_5, x_6 \\} =\n", " \\min \\{ -1, 1, 0 \\}.\n", "\n", "Pivot dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{array}{r c r c r c r c r}\n", " \\epsilon & = & -1 & + & x_1 & + & 2 x_2 & - & x_4\\\\\n", " \\hline\n", " x_5 & = & 2 & - & 3 x_1 & - & 3 x_2 & + & x_4\\\\\n", " x_6 & = & 1 & & & - & 3 x_2 & + & x_4\\\\\n", " x_3 & = & 1 & - & x_1 & - & x_2\n", " \\end{array}\n", "\n", "where :math:`v = \\epsilon`.\n", "\n", "The final dictionary\n", "\n", ".. math::\n", "\n", " \\begin{array}{r c r c r c r c r}\n", " 3 \\epsilon & = & & - & x_5 & - & x_6 & - & x_4\\\\\n", " \\hline\n", " 3 x_1 & = & 1 & - & x_5 & + & x_6 &\\\\\n", " 3 x_2 & = & 1 & & & - & x_6 & + & x_4\\\\\n", " 3 x_3 & = & 1 & + & x_5 & & & - & x_4\n", " \\end{array}\n", "\n", "implies that the optimal strategy is\n", ":math:`x^* = \\left( \\frac{1}{3}, \\frac{1}{3}, \\frac{1}{3} \\right) = y^*`.\n", "\n", ":math:`n \\geq 4`\n", "----------------\n", "\n", "Choose :math:`v` and :math:`x_5` as the entering and leaving variable\n", "respectively where\n", "\n", ".. math::\n", "\n", " v =\n", " \\min \\{ x_5, x_6, x_7, x_8 \\} =\n", " \\min \\{ -1, -1, 1, 0 \\}.\n", "\n", "Pivot dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{array}{r c r c r c r c r c r}\n", " \\epsilon & = & -1 & + & x_1 & + & 2 x_2 & & & - & x_5\\\\\n", " \\hline\n", " x_6 & = & & - & x_1 & - & x_2 & + & 2 x_3 & + & x_5\\\\\n", " x_7 & = & 2 & - & x_1 & - & 4 x_2 & - & x_3 & + & x_5\\\\\n", " x_8 & = & 1 & & & - & x_2 & - & x_3 & + & x_5\\\\\n", " x_4 & = & 1 & - & x_1 & - & x_2 & - & x_3\n", " \\end{array}\n", "\n", "where :math:`v = \\epsilon`.\n", "\n", "The final dictionary\n", "\n", ".. math::\n", "\n", " \\begin{array}{r c r c r c r c r c r}\n", " 3 \\epsilon & = & & - & x_4 & - & x_6 & - & x_7 & - & x_5\\\\\n", " \\hline\n", " 3 x_2 & = & 1 & + & x_4 & & & - & x_7 & + & x_5\\\\\n", " 3 x_3 & = & 1 & - & x_4 & + & x_6 & & & - & x_5\\\\\n", " 3 x_8 & = & 1 & & & - & x_6 & + & x_7 & + & x_5\\\\\n", " 3 x_1 & = & 1 & - & x_4 & - & x_6 & + & x_7\n", " \\end{array}\n", "\n", "implies that the optimal strategy is\n", ":math:`x^* = \\left( \\frac{1}{3}, \\frac{1}{3}, \\frac{1}{3}, 0 \\right) = y^*`.\n", "\n", "By induction, the optimal strategy for :math:`n > 4` is\n", "\n", ".. math::\n", "\n", " x^* =\n", " \\left( \\frac{1}{3}, \\frac{1}{3}, \\frac{1}{3}, 0, \\ldots, 0 \\right)\n", " = y^*\n", "\n", "because there is no incentive to choose a larger number." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 11.3\n", "=============\n", "\n", "Applying (a) and (b) to the payoff matrix gives\n", "\n", ".. math::\n", "\n", " \\begin{bmatrix}\n", " -6 & 2 & -4 & -7 & -5\\\\\n", " 0 & 4 & -2 & -9 & -1\\\\\n", " -7 & 3 & -3 & -8 & -2\\\\\n", " 2 & -3 & 6 & 0 & 3\n", " \\end{bmatrix}\n", " &\\implies \\begin{bmatrix}\n", " -6 & 2 & -4 & -5\\\\\n", " 0 & 4 & -2 & -1\\\\\n", " -7 & 3 & -3 & -2\\\\\n", " 2 & -3 & 6 & 3\n", " \\end{bmatrix}\n", " & \\quad & \\text{columns } \\{ 1, 3, 5 \\}\n", " \\text{ dominate column } 4\\\\\n", " &\\implies \\begin{bmatrix}\n", " -6 & 2 & -4 & -5\\\\\n", " -7 & 3 & -3 & -2\\\\\n", " 2 & -3 & 6 & 3\n", " \\end{bmatrix}\n", " & \\quad & \\text{row } 2\n", " \\text{ dominates rows } \\{ 1, 3 \\}\\\\\n", " &\\implies \\begin{bmatrix}\n", " 2 & -4 & -5\\\\\n", " 3 & -3 & -2\\\\\n", " -3 & 6 & 3\n", " \\end{bmatrix}\n", " & \\quad & \\text{columns } \\{ 3, 4 \\}\n", " \\text{ dominate column } 1\\\\\n", " &\\implies \\begin{bmatrix}\n", " 2 & -4 & -5\\\\\n", " -3 & 6 & 3\n", " \\end{bmatrix}\n", " & \\quad & \\text{row } 2\n", " \\text{ dominates row } 1\\\\\n", " &\\implies \\begin{bmatrix}\n", " 2 & -4\\\\\n", " -3 & 6\n", " \\end{bmatrix}\n", " & \\quad & \\text{column } 2\n", " \\text{ dominates column } 3.\n", "\n", "(a)\n", "---\n", "\n", "Suppose a new row :math:`r` is added to :math:`A` such that :math:`r` dominates\n", "row :math:`s` and :math:`y_r^* \\neq 0`. By inspection,\n", "\n", ".. math::\n", "\n", " a_{rj} &\\geq a_{sj}\n", " & \\quad & \\forall j = 1, \\ldots, n\\\\\n", " a_{rj} - \\delta_j &= a_{sj}\n", " & \\quad & \\delta_j = a_{rj} - a_{sj} \\geq 0\\\\\n", " \\sum_j a_{rj} x_j &= \\sum_j (a_{sj} + \\delta_j) x_j.\n", "\n", "Furthermore,\n", "\n", ".. math::\n", "\n", " \\min_y y^\\top A x^*\n", " &= \\min_i e_i^\\top A x^*\n", " & \\quad & \\text{minimax theorem}\\\\\n", " &= e_r^\\top A x^*\n", " & \\quad & y_r^* \\neq 0\\\\\n", " &= e_s^\\top A x^* + \\delta^\\top x^*\\\\\n", " &\\geq e_s^\\top A x^*\n", "\n", "contradicts the definition of a minimum. Therefore, :math:`y_r^* = 0` and\n", "dominate rows can be removed without affecting the value of the game.\n", "\n", "(b)\n", "---\n", "\n", "Suppose a new column :math:`c` is added to :math:`A` such that :math:`c`\n", "dominates column :math:`s` and :math:`x_s^* \\neq 0`. By inspection,\n", "\n", ".. math::\n", "\n", " a_{ic} &\\geq a_{is}\n", " & \\quad & \\forall i = 1, \\ldots, m\\\\\n", " a_{ic} - \\delta_i &= a_{is}\n", " & \\quad & \\delta_i = a_{ic} - a_{is} \\geq 0\\\\\n", " \\sum_i (a_{ic} - \\delta_i) y_i &= \\sum_i a_{is} y_i.\n", "\n", "Furthermore,\n", "\n", ".. math::\n", "\n", " \\max_x x^\\top A^\\top y^*\n", " &= \\max_j e_j^\\top A^\\top y^*\n", " & \\quad & \\text{minimax theorem}\\\\\n", " &= e_s^\\top A^\\top y^*\n", " & \\quad & x_s^* \\neq 0\\\\\n", " &= e_c^\\top A^\\top y^* - \\delta^\\top y^*\\\\\n", " &\\leq e_c^\\top A^\\top y^*\n", "\n", "contradicts the definition of a maximum. Therefore, :math:`x_s^* = 0` and\n", "dominated columns can be removed without affecting the value of the game." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 11.4\n", "=============" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "from enum import Enum\n", "\n", "class Action(Enum):\n", " BET = 1\n", " PASS = 0\n", "\n", "class StrategyA:\n", " def __init__(self, pure_strategies):\n", " lines = [\n", " StrategyA.__line1, StrategyA.__line2, StrategyA.__line3\n", " ]\n", " self.action_plans = []\n", " for ps in pure_strategies:\n", " self.action_plans.append(lines[ps - 1])\n", "\n", " def invoke(self, card_dealt):\n", " return self.action_plans[card_dealt - 1]()\n", "\n", " @staticmethod\n", " def __line1():\n", " return Action.PASS,\\\n", " lambda _: Action.PASS\n", "\n", " @staticmethod\n", " def __line2():\n", " return Action.PASS,\\\n", " lambda action: Action.BET if action == Action.BET else Action.PASS\n", "\n", " @staticmethod\n", " def __line3():\n", " return Action.BET,\\\n", " lambda _: Action.BET\n", "\n", "class StrategyB:\n", " def __init__(self, pure_strategies):\n", " lines = [\n", " StrategyB.__line1, StrategyB.__line2,\n", " StrategyB.__line3, StrategyB.__line4\n", " ]\n", " self.action_plans = []\n", " for ps in pure_strategies:\n", " self.action_plans.append(lines[ps - 1])\n", "\n", " def invoke(self, card_dealt, other_action):\n", " return self.action_plans[card_dealt - 1](other_action)\n", "\n", " @staticmethod\n", " def __line1(_):\n", " return Action.PASS\n", "\n", " @staticmethod\n", " def __line2(action):\n", " return Action.PASS if action == Action.PASS else Action.BET\n", "\n", " @staticmethod\n", " def __line3(action):\n", " return Action.BET if action == Action.PASS else Action.PASS\n", "\n", " @staticmethod\n", " def __line4(_):\n", " return Action.BET" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "import itertools\n", "import numpy\n", "\n", "def paymentA2B(pure_strategies_A, pure_strategies_B, ante=1, bet=1):\n", " A = StrategyA(pure_strategies_A)\n", " B = StrategyB(pure_strategies_B)\n", "\n", " total_payment = 0\n", " count = 0\n", " for cards_dealt in itertools.product([1, 2, 3], [1, 2, 3]):\n", " a, b = cards_dealt\n", " if a == b:\n", " #card game is without replacement\n", " continue\n", "\n", " A_action, A_response = A.invoke(a)\n", " B_action = B.invoke(b, A_action)\n", " end_turn = A_response(B_action)\n", "\n", " pot = 0\n", " if A_action == Action.PASS and B_action == Action.PASS:\n", " if a > b:\n", " pot = -ante\n", " elif a < b:\n", " pot = ante\n", " elif A_action == Action.PASS and B_action == Action.BET and end_turn == Action.PASS:\n", " pot = ante\n", " elif A_action == Action.PASS and B_action == Action.BET and end_turn == Action.BET:\n", " if a > b:\n", " pot = -ante - bet\n", " elif a < b:\n", " pot = ante + bet\n", " elif A_action == Action.BET and B_action == Action.PASS:\n", " pot = -ante\n", " elif A_action == Action.BET and B_action == Action.BET:\n", " if a > b:\n", " pot = -ante - bet\n", " elif a < b:\n", " pot = ante + bet\n", "\n", " count += 1\n", " total_payment += pot\n", "\n", " return total_payment / count\n", "\n", "a_strategies = [\n", " (1, 1, 2), (1, 1, 3), (1, 2, 2), (1, 2, 3),\n", " (3, 1, 2), (3, 1, 3), (3, 2, 2), (3, 2, 3)\n", "]\n", "b_strategies = [\n", " (1, 1, 4), (1, 2, 4), (3, 1, 4), (3, 2, 4)\n", "]\n", "\n", "payoff_matrix = []\n", "for psa in a_strategies:\n", " payoffs = []\n", " for psb in b_strategies:\n", " payoffs.append(paymentA2B(psa, psb, ante=2))\n", " payoff_matrix.append(payoffs)\n", "\n", "A = numpy.asarray(payoff_matrix)\n", "print(A)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "def solveDualMatrixGame(A):\n", " P = numpy.column_stack((-A.T, numpy.ones(A.T.shape[0])))\n", "\n", " n = A.T.shape[1] + 1\n", " c = numpy.zeros(n)\n", " c[-1] = 1\n", "\n", " from pymprog import model\n", "\n", " lp = model('LP')\n", "\n", " #lp.verbose(True)\n", " y = lp.var('y', n, bounds=(None, None))\n", " for j in range(n - 1):\n", " lp.st(y[j] >= 0)\n", "\n", " lp.minimize(sum(c[j] * y[j] for j in range(n)))\n", "\n", " for row in range(P.shape[0]):\n", " sum(P[row, col] * y[col] for col in range(n)) >= 0\n", "\n", " sum(y[j] for j in range(n - 1)) == 1\n", "\n", " lp.solve()\n", " lp.sensitivity()\n", "\n", " lp.end()\n", "\n", "solveDualMatrixGame(A)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "def solvePrimalMatrixGame(A):\n", " P = numpy.column_stack((-A, numpy.ones(A.shape[0])))\n", "\n", " n = A.shape[1] + 1\n", " c = numpy.zeros(n)\n", " c[-1] = 1\n", "\n", " from pymprog import model\n", "\n", " lp = model('LP')\n", "\n", " #lp.verbose(True)\n", " x = lp.var('x', n, bounds=(None, None))\n", " for i in range(n - 1):\n", " lp.st(x[i] >= 0)\n", "\n", " lp.maximize(sum(c[i] * x[i] for i in range(n)))\n", "\n", " for row in range(P.shape[0]):\n", " sum(P[row, col] * x[col] for col in range(n)) <= 0\n", "\n", " sum(x[i] for i in range(n - 1)) == 1\n", "\n", " lp.solve()\n", " lp.sensitivity()\n", "\n", " lp.end()\n", "\n", "solvePrimalMatrixGame(A)" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 11.5\n", "=============\n", "\n", "The simultaneously optimality of the :math:`r\\text{th}` pure strategy of the row\n", "and the :math:`s\\text{th}` pure strategy of the column player requires\n", ":math:`y^*, x^*` to be indicator vectors. This means :math:`r` is dominated by\n", "all the other rows and :math:`s` dominates all the other columns." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 11.6\n", "=============\n", "\n", "Suppose :math:`x^*` and :math:`y^*` are the optimal strategies. The Minimax\n", "Theorem guarantees that\n", "\n", ".. math::\n", "\n", " \\max_x {y^*}^\\top A x = \\min_y y^\\top A x^*.\n", "\n", "By the Strong Duality Theorem,\n", "\n", ".. math::\n", "\n", " {y^*}^\\top A x^* \\geq\n", " \\min_y y^\\top A x^* =\n", " \\max_x {y^*}^\\top A x \\geq\n", " {y^*}^\\top A x^*\n", "\n", "and\n", "\n", ".. math::\n", "\n", " {y^*}^\\top A x \\leq {y^*}^\\top A x^* \\leq y^\\top A x^*\n", "\n", "for all :math:`x, y`. Thus\n", "\n", ".. math::\n", "\n", " \\max_x \\min_y y^\\top A x = \\min_y \\max_x y^\\top A x." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 11.7\n", "=============\n", "\n", "Given a matrix :math:`M \\in \\mathbb{R}^{n \\times n}` and a vector\n", ":math:`q \\in \\mathbb{R}^n`, the linear complementarity problem (LCP) is to find\n", "vectors :math:`u, v \\in \\mathbb{R}^n` satisfying the relations\n", ":cite:`chandrasekaranbg`:\n", "\n", ".. math::\n", "\n", " u = Mv + q\\\\\n", " u \\geq 0; v \\geq 0\\\\\n", " u^\\top v = 0.\n", "\n", "The reason for the term \"complementarity\" in the name of the problem is due to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " u \\geq 0; v \\geq 0\\\\\n", " u^\\top v = 0\n", " \\end{aligned}\n", " \\iff\n", " \\begin{aligned}\n", " u_i v_i = 0 \\, \\forall \\, i.\n", " \\end{aligned}\n", "\n", "The stochastic vectors :math:`x^*` and :math:`y^*` form a Nash equilibrium pair\n", "if they satisfy\n", "\n", ".. math::\n", "\n", " {y^*}^\\top A x^* &\\leq y^\\top A x^* \\quad \\forall \\, y\\\\\n", " {y^*}^\\top B x^* &\\leq {y^*}^\\top B x \\quad \\forall \\, x\n", "\n", "where :math:`A, B \\in \\mathbb{R}^{m \\times n}` are loss matrices of the row and\n", "column players respectively. Since :math:`e^\\top x^* = \\sum_j x^*_j = 1` and\n", ":math:`e^\\top y^* = \\sum_i y^*_i = 1`, the preceding relations are equivalent to\n", "\n", ".. math::\n", "\n", " \\left( {y^*}^\\top A x^* \\right) e &\\leq A x^*\\\\\n", " \\left( {y^*}^\\top B x^* \\right) e &\\leq B^\\top y^*.\n", "\n", "The equivalent LCP formulation is\n", "\n", ".. math::\n", "\n", " w &= Ax - e\\\\\n", " z &= B^\\top y - e\\\\\n", " x &\\geq 0; y \\geq 0; w \\geq 0; z \\geq 0\\\\\n", " y^\\top w &= 0; x^\\top z = 0\n", "\n", "and\n", "\n", ".. math::\n", "\n", " M = \\begin{bmatrix} 0 & A\\\\ B^\\top & 0 \\end{bmatrix};\n", " q = \\begin{bmatrix} -e\\\\ -e \\end{bmatrix}\\\\\n", " u = \\begin{bmatrix} w\\\\ z \\end{bmatrix};\n", " v = \\begin{bmatrix} y\\\\ x \\end{bmatrix}.\n", "\n", "(a)\n", "---\n", "\n", "Let :math:`C = A + kJ` and :math:`D = B + kJ` where :math:`k` is the smallest\n", "scalar such that the all-ones matrix :math:`J` forces :math:`C` and :math:`D` to\n", "be positive matrices. Any equilibrium pair of strategies for :math:`(A, B)` is\n", "also an equilibrium pair of strategies for :math:`(C, D)`:\n", "\n", ".. math::\n", "\n", " {y^*}^\\top C x^*&\\leq y^\\top C x^*\\\\\n", " {y^*}^\\top A x^* + {y^*}^\\top kJ x^* &\\leq y^\\top A x^* + y^\\top kJ x^*\\\\\n", " {y^*}^\\top A x^* + {y^*}^\\top ke &\\leq y^\\top A x^* + y^\\top ke\n", " & \\quad & J x^* = e\\\\\n", " {y^*}^\\top A x^* + k &\\leq y^\\top A x^* + k\n", " & \\quad & y \\cdot e = 1\\\\\n", " {y^*}^\\top A x^* &\\leq y^\\top A x^*.\n", "\n", "The proof is the same for :math:`B` and :math:`D`.\n", "\n", "(b)\n", "---\n", "\n", "Suppose :math:`(x^*, y^*)` is a Nash equilibrium and :math:`A, B` are positive\n", "matrices such that\n", "\n", ".. math::\n", "\n", " \\left( {y^*}^\\top A x^* \\right) e &\\leq A x^*\\\\\n", " e &\\leq Ax'\n", " & \\quad & x' = \\frac{x^*}{{y^*}^\\top A x^*}\\\\\n", " 0 &\\leq w\n", "\n", "and\n", "\n", ".. math::\n", "\n", " \\left( {y^*}^\\top B^\\top x^* \\right) e &\\leq B^\\top y^*\\\\\n", " e &\\leq B^\\top y'\n", " & \\quad & y' = \\frac{y^*}{{y^*}^\\top B^\\top x^*}\\\\\n", " 0 &\\leq z.\n", "\n", "The remaining LCP relations are also satisfied because\n", "\n", ".. math::\n", "\n", " {y'}^\\top w\n", " &= {y'}^\\top A x' - {y'}^\\top e\\\\\n", " &= \\frac{{y^*}^\\top}{{y^*}^\\top B^\\top x^*}\n", " A \\frac{x^*}{{y^*}^\\top A x^*} -\n", " \\frac{{y^*}^\\top e}{{y^*}^\\top B^\\top x^*}\\\\\n", " &= \\frac{1}{{y^*}^\\top B^\\top x^*} -\n", " \\frac{1}{{y^*}^\\top B^\\top x^*}\\\\\n", " &= 0.\n", "\n", "The proof is the same for :math:`{x'}^\\top z`. Therefore,\n", ":math:`(x', y')` solves the LCP.\n", "\n", "(c)\n", "---\n", "\n", "Suppose :math:`(x', y')` solves the LCP such that\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " 0 &= {y'}^\\top w\\\\\n", " &= {y'}^\\top A x' - {y'}^\\top e\\\\\n", " e^\\top y' &= {y'}^\\top A x'\\\\\n", " 1 &= \\frac{{y'}^\\top A x'}{e^\\top y'}\n", " \\end{aligned}\n", " \\qquad \\text{and} \\qquad\n", " \\begin{aligned}\n", " 0 &= {x'}^\\top z\\\\\n", " &= {x'}^\\top B^\\top y' - {x'}^\\top e\\\\\n", " e^\\top x' &= {x'}^\\top B^\\top y'\\\\\n", " 1 &= \\frac{{x'}^\\top B^\\top y'}{e^\\top x'}.\n", " \\end{aligned}\n", "\n", "The conditions for :math:`(x^*, y^*)` to form a Nash equilibrium is satisfied\n", "because\n", "\n", ".. math::\n", "\n", " w &\\geq 0\\\\\n", " A x' &\\geq e\\\\\n", " A x^* &\\geq \\frac{e}{{x'}^\\top e}\n", " & \\quad & x^* = \\frac{x'}{e^\\top x'}\\\\\n", " &\\geq \\frac{{y'}^\\top A x'}{e^\\top y'} \\frac{e}{{x'}^\\top e}\\\\\n", " &\\geq \\left( {y^*}^\\top A x^* \\right) e.\n", "\n", "The proof is the same for :math:`z \\geq 0`. Therefore,\n", ":math:`(x^*, y^*)` is a Nash equilibrium." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 11.8\n", "=============\n", "\n", "Since players A and B can only throw out one or two fingers, the total sum\n", "of the outstretched fingers are:\n", "\n", "+------------+------------+------------+\n", "| | Player B 1 | Player B 2 |\n", "+------------+------------+------------+\n", "| Player A 1 | 2 | 3 |\n", "+------------+------------+------------+\n", "| Player A 2 | 3 | 4 |\n", "+------------+------------+------------+\n", "\n", "(a)\n", "---\n", "\n", "The players' pure strategies can be denoted by :math:`(g_1, g_2)` where\n", ":math:`g_i \\in \\{ 2, 3, 4 \\}` is the player's guess when throwing out\n", ":math:`i \\in \\{ 1, 2 \\}` fingers. Each player has a total of\n", ":math:`3 \\times 3 = 9` pure strategies. Thus there are :math:`9 \\times 9 = 81`\n", "pairs.\n", "\n", "(b)\n", "---\n", "\n", "The following observations reveal that certain strategies are nonsensical:\n", "\n", "- A player throwing out one finger should never guess four.\n", "- A player throwing out two fingers should never guess two.\n", "\n", "After eliminating these strategies from consideration, each player has\n", ":math:`2 \\times 2 = 4` pure strategies.\n", "\n", "(c)\n", "---\n", "\n", "The formulation is given by (11.4).\n", "\n", "(d)\n", "---\n", "\n", "This is a symmetric fair game; hence, the value of the game is zero.\n", "\n", "(e)\n", "---\n", "\n", "The optimal randomized strategy is to uniformly throw one or two finger while\n", "using the pure strategy :math:`(g_1 = 3, g_2 = 4)`." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "def paymentA2B(psa, psb):\n", " total_payment = 0\n", " count = 0\n", " for fingers_thrown in itertools.product([1, 2], [1, 2]):\n", " a_fingers, b_fingers = fingers_thrown\n", " total_fingers = a_fingers + b_fingers\n", "\n", " a_guess = psa[a_fingers - 1]\n", " b_guess = psb[b_fingers - 1]\n", "\n", " if a_guess == total_fingers and b_guess != total_fingers:\n", " total_payment -= total_fingers\n", " elif a_guess != total_fingers and b_guess == total_fingers:\n", " total_payment += total_fingers\n", "\n", " count += 1\n", " return total_payment / count\n", "\n", "a_strategies = [\n", " (2, 3), (2, 4), (3, 3), (3, 4)\n", "]\n", "b_strategies = [\n", " (2, 3), (2, 4), (3, 3), (3, 4)\n", "]\n", "\n", "payoff_matrix = []\n", "for psa in a_strategies:\n", " payoffs = []\n", " for psb in b_strategies:\n", " payoffs.append(paymentA2B(psa, psb))\n", " payoff_matrix.append(payoffs)\n", "\n", "A = numpy.asarray(payoff_matrix)\n", "print(A)\n", "\n", "solveDualMatrixGame(A)" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 11.9\n", "=============\n", "\n", "There are three possible betting scenarios:\n", "\n", "#. Player A leaves: $1 goes to player B.\n", "#. Player A stays and player B leaves: $1 goes to player A.\n", "#. Player A stays and player B stays: $2 goes to player A if the fair coin flip\n", " resulted in heads, otherwise $2 goes to player B.\n", "\n", "(a)\n", "---\n", "\n", "Player A's pure strategy can be denoted by :math:`(y_1, y_2)` where\n", ":math:`y_i \\in \\{ \\text{leave}, \\text{stay} \\}` is player A's action when the\n", "observed outcome is :math:`i \\in \\{ \\text{heads}, \\text{tails} \\}`.\n", "\n", "Player B's pure strategy :math:`(x_1)` is dependent on A's declared action.\n", ":math:`x_1 \\in \\{ \\text{leave}, \\text{stay} \\}` is player B's decision when\n", "player A decides to stay. Note that player B wins when player A leaves.\n", "\n", "Therefore there are :math:`(2 \\times 2) \\times (2) = 8` pairs.\n", "\n", "(b)\n", "---\n", "\n", "The accompanying code prints out the reduced payoff matrix.\n", "\n", "(c)\n", "---\n", "\n", "Player A should never leave the game when the outcome is heads.\n", "\n", "When the outcome is tails, leaving will guarantee a loss of $1, but staying will\n", "on average result in :math:`\\alpha (2) + (1 - \\alpha) (-1)` where :math:`\\alpha`\n", "is the probability of player B staying. This strategy should be ruled out when\n", "\n", ".. math::\n", "\n", " 1 &< \\alpha (2) + (1 - \\alpha) (-1)\\\\\n", " 2 &< 3 \\alpha\\\\\n", " \\frac{2}{3} &< \\alpha.\n", "\n", "(d)\n", "---\n", "\n", "The formulation is given by (11.4).\n", "\n", "(e)\n", "---\n", "\n", "Player A's optimal strategy is as follows:\n", "\n", "- When heads is observed, always stay.\n", "- When tails is observed, leave :math:`2/3` of the time and stay :math:`1/3` of\n", " the time.\n", "\n", "Player B's optimal strategy is to leave :math:`1/3` of the time and stay\n", ":math:`2/3` of the time.\n", "\n", "(f)\n", "---\n", "\n", "This game is neither symmetric nor fair, and it is in player A's favor. This\n", "game is interesting in the sense that there is no way to make the game fair." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "def paymentA2B(psa, psb):\n", " total_payment = 0\n", " count = 0\n", " for coin in range(2):\n", " a_action = psa[coin]\n", " b_action = psb\n", "\n", " if a_action == LEAVE:\n", " total_payment += 1\n", " else:\n", " if b_action == LEAVE:\n", " total_payment -= 1\n", " else:\n", " if coin == HEADS:\n", " total_payment -= 2\n", " else:\n", " total_payment += 2\n", "\n", " count += 1\n", " return total_payment / count\n", "\n", "LEAVE, STAY = range(2)\n", "HEADS, TAILS = range(2)\n", "a_strategies = [\n", " (STAY, LEAVE), (STAY, STAY)\n", "]\n", "b_strategies = [\n", " (LEAVE), (STAY)\n", "]\n", "\n", "payoff_matrix = []\n", "for psa in a_strategies:\n", " payoffs = []\n", " for psb in b_strategies:\n", " payoffs.append(paymentA2B(psa, psb))\n", " payoff_matrix.append(payoffs)\n", "\n", "A = numpy.asarray(payoff_matrix)\n", "print(A)\n", "\n", "solveDualMatrixGame(A)" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ ".. rubric:: References\n", "\n", ".. bibliography:: chapter-11.bib" ] } ], "metadata": { "anaconda-cloud": {}, "celltoolbar": "Raw Cell Format", "kernelspec": { "display_name": "Python [default]", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.5.2" } }, "nbformat": 4, "nbformat_minor": 1 }