#!/usr/bin/env python # coding: utf-8 # # Tools for Game Theory in QuantEcon.py # **Daisuke Oyama** # *Faculty of Economics, University of Tokyo* # This notebook demonstrates the functionalities of the [`game_theory`](http://quanteconpy.readthedocs.io/en/latest/game_theory.html) module # in [QuantEcon.py](https://github.com/QuantEcon/QuantEcon.py). # In[1]: import numpy as np import quantecon.game_theory as gt # ## Normal Form Games # An $N$-player *normal form game* is a triplet $g = (I, (A_i)_{i \in I}, (u_i)_{i \in I})$ where # # * $I = \{0, \ldots, N-1\}$ is the set of players, # * $A_i = \{0, \ldots, n_i-1\}$ is the set of actions of player $i \in I$, and # * $u_i \colon A_i \times A_{i+1} \times \cdots \times A_{i+N-1} \to \mathbb{R}$ # is the payoff function of player $i \in I$, # # where $i+j$ is understood modulo $N$. # # Note that we adopt the convention that the $0$-th argument of the payoff function $u_i$ is # player $i$'s own action # and the $j$-th argument, $j = 1, \ldots, N-1$, is player ($i+j$)'s action (modulo $N$). # In our module, # a normal form game and a player are represented by # the classes `NormalFormGame` and `Player`, respectively. # # A `Player` carries the player's payoff function and implements in particular # a method that returns the best response action(s) given an action of the opponent player, # or a profile of actions of the opponents if there are more than one. # # A `NormalFormGame` is in effect a container of `Player` instances. # ### Creating a `NormalFormGame` # There are several ways to create a `NormalFormGame` instance. # The first is to pass an array of payoffs for all the players, i.e., # an $(N+1)$-dimenstional array of shape $(n_0, \ldots, n_{N-1}, N)$ # whose $(a_0, \ldots, a_{N-1})$-entry contains an array of the $N$ payoff values # for the action profile $(a_0, \ldots, a_{N-1})$. # As an example, consider the following game ("**Matching Pennies**"): # # $ # \begin{bmatrix} # 1, -1 & -1, 1 \\ # -1, 1 & 1, -1 # \end{bmatrix} # $ # In[2]: matching_pennies_bimatrix = [[(1, -1), (-1, 1)], [(-1, 1), (1, -1)]] g_MP = gt.NormalFormGame(matching_pennies_bimatrix) # In[3]: print(g_MP) # In[4]: print(g_MP.players[0]) # Player instance for player 0 # In[5]: print(g_MP.players[1]) # Player instance for player 1 # In[6]: g_MP.players[0].payoff_array # Player 0's payoff array # In[7]: g_MP.players[1].payoff_array # Player 1's payoff array # In[8]: g_MP[0, 0] # payoff profile for action profile (0, 0) # If a square matrix (2-dimensional array) is given, # then it is considered to be a symmetric two-player game. # # Consider the following game (symmetric $2 \times 2$ "**Coordination Game**"): # # $ # \begin{bmatrix} # 4, 4 & 0, 3 \\ # 3, 0 & 2, 2 # \end{bmatrix} # $ # In[9]: coordination_game_matrix = [[4, 0], [3, 2]] # square matrix g_Coo = gt.NormalFormGame(coordination_game_matrix) # In[10]: print(g_Coo) # In[11]: g_Coo.players[0].payoff_array # Player 0's payoff array # In[12]: g_Coo.players[1].payoff_array # Player 1's payoff array # Another example ("**Rock-Paper-Scissors**"): # # $ # \begin{bmatrix} # 0, 0 & -1, 1 & 1, -1 \\ # 1, -1 & 0, 0 & -1, 1 \\ # -1, 1 & 1, -1 & 0, 0 # \end{bmatrix} # $ # In[13]: RPS_matrix = [[ 0, -1, 1], [ 1, 0, -1], [-1, 1, 0]] g_RPS = gt.NormalFormGame(RPS_matrix) # In[14]: print(g_RPS) # The second is to specify the sizes of the action sets of the players # to create a `NormalFormGame` instance filled with payoff zeros, # and then set the payoff values to each entry. # # Let us construct the following game ("**Prisoners' Dilemma**"): # # $ # \begin{bmatrix} # 1, 1 & -2, 3 \\ # 3, -2 & 0, 0 # \end{bmatrix} # $ # In[15]: g_PD = gt.NormalFormGame((2, 2)) # There are 2 players, each of whom has 2 actions g_PD[0, 0] = 1, 1 g_PD[0, 1] = -2, 3 g_PD[1, 0] = 3, -2 g_PD[1, 1] = 0, 0 # In[16]: print(g_PD) # Finally, a `NormalFormGame` instance can be constructed by giving an array of `Player` instances, # as explained in the next section. # ### Creating a `Player` # A `Player` instance is created by passing an array of dimension $N$ # that represents the player's payoff function ("payoff array"). # # Consider the following game (a variant of "**Battle of the Sexes**"): # # $ # \begin{bmatrix} # 3, 2 & 1, 1 \\ # 0, 0 & 2, 3 # \end{bmatrix} # $ # In[17]: player0 = gt.Player([[3, 1], [0, 2]]) player1 = gt.Player([[2, 0], [1, 3]]) # Beware that in `payoff_array[h, k]`, `h` refers to the player's own action, # while `k` refers to the opponent player's action. # In[18]: player0.payoff_array # In[19]: player1.payoff_array # Passing an array of Player instances is the third way to create a `NormalFormGame` instance: # In[20]: g_BoS = gt.NormalFormGame((player0, player1)) # In[21]: print(g_BoS) # ### More than two players # The `game_theory` module also supports games with more than two players. # Let us consider the following version of $N$-player **Cournot Game**. # # There are $N$ firms (players) which produce a homogeneous good # with common constant marginal cost $c \geq 0$. # Each firm $i$ simultaneously determines the quantity $q_i \geq 0$ (action) of the good to produce. # The inverse demand function is given by the linear function $P(Q) = a - Q$, $a > 0$, # where $Q = q_0 + \cdots + q_{N-1}$ is the aggregate supply. # Then the profit (payoff) for firm $i$ is given by # $$ # u_i(q_i, q_{i+1}, \ldots, q_{i+N-1}) # = P(Q) q_i - c q_i # = \left(a - c - \sum_{j \neq i} q_j - q_i\right) q_i. # $$ # Theoretically, the set of actions, i.e., available quantities, may be # the set of all nonnegative real numbers $\mathbb{R}_+$ # (or a bounded interval $[0, \bar{q}]$ with some upper bound $\bar{q}$), # but for computation on a computer we have to discretize the action space # and only allow for finitely many grid points. # # The following script creates a `NormalFormGame` instance of the Cournot game as described above, # assuming that the (common) grid of possible quantity values is stored in an array `q_grid`. # In[22]: from quantecon import cartesian def cournot(a, c, N, q_grid): """ Create a `NormalFormGame` instance for the symmetric N-player Cournot game with linear inverse demand a - Q and constant marginal cost c. Parameters ---------- a : scalar Intercept of the demand curve c : scalar Common constant marginal cost N : scalar(int) Number of firms q_grid : array_like(scalar) Array containing the set of possible quantities Returns ------- NormalFormGame NormalFormGame instance representing the Cournot game """ q_grid = np.asarray(q_grid) payoff_array = \ cartesian([q_grid]*N).sum(axis=-1).reshape([len(q_grid)]*N) * (-1) + \ (a - c) payoff_array *= q_grid.reshape([len(q_grid)] + [1]*(N-1)) payoff_array += 0 # To get rid of the minus sign of -0 player = gt.Player(payoff_array) return gt.NormalFormGame([player for i in range(N)]) # Here's a simple example with three firms, # marginal cost $20$, and inverse demand function $80 - Q$, # where the feasible quantity values are assumed to be $10$ and $15$. # In[23]: a, c = 80, 20 N = 3 q_grid = [10, 15] # [1/3 of Monopoly quantity, Nash equilibrium quantity] g_Cou = cournot(a, c, N, q_grid) # In[24]: print(g_Cou) # In[25]: print(g_Cou.players[0]) # In[26]: g_Cou.nums_actions # ## Nash Equilibrium # A *Nash equilibrium* of a normal form game is a profile of actions # where the action of each player is a best response to the others'. # The `Player` object has a method `best_response`. # # Consider the Matching Pennies game `g_MP` defined above. # For example, player 0's best response to the opponent's action 1 is: # In[27]: g_MP.players[0].best_response(1) # Player 0's best responses to the opponent's mixed action `[0.5, 0.5]` # (we know they are 0 and 1): # In[28]: # By default, returns the best response action with the smallest index g_MP.players[0].best_response([0.5, 0.5]) # In[29]: # With tie_breaking='random', returns randomly one of the best responses g_MP.players[0].best_response([0.5, 0.5], tie_breaking='random') # Try several times # In[30]: # With tie_breaking=False, returns an array of all the best responses g_MP.players[0].best_response([0.5, 0.5], tie_breaking=False) # For this game, we know that `([0.5, 0.5], [0.5, 0.5])` is a (unique) Nash equilibrium. # In[31]: g_MP.is_nash(([0.5, 0.5], [0.5, 0.5])) # In[32]: g_MP.is_nash((0, 0)) # In[33]: g_MP.is_nash((0, [0.5, 0.5])) # ### Finding Nash equilibria # There are several algorithms implemented to compute Nash equilibria: # # * Brute force # Find all pure-action Nash equilibria of an $N$-player game (if any). # * Sequential best response # Find one pure-action Nash equilibrium of an $N$-player game (if any). # * Support enumeration # Find all mixed-action Nash equilibria of a two-player nondegenerate game. # * Vertex enumeration # Find all mixed-action Nash equilibria of a two-player nondegenerate game. # * Lemke-Howson # Find one mixed-action Nash equilibrium of a two-player game. # * McLennan-Tourky # Find one mixed-action Nash equilibrium of an $N$-player game. # # For more variety of algorithms, one should look at [Gambit](http://www.gambit-project.org). # #### Brute force # For small games, we can find pure action Nash equilibria by brute force, # by calling the routine [`pure_nash_brute`](http://quanteconpy.readthedocs.io/en/latest/game_theory/pure_nash.html#quantecon.game_theory.pure_nash.pure_nash_brute). # It visits all the action profiles and check whether each is a Nash equilibrium # by the `is_nash` method. # In[34]: def print_pure_nash_brute(g): """ Print all pure Nash equilibria of a normal form game found by brute force. Parameters ---------- g : NormalFormGame """ NEs = gt.pure_nash_brute(g) num_NEs = len(NEs) if num_NEs == 0: msg = 'no pure Nash equilibrium' elif num_NEs == 1: msg = '1 pure Nash equilibrium:\n{0}'.format(NEs) else: msg = '{0} pure Nash equilibria:\n{1}'.format(num_NEs, NEs) print('The game has ' + msg) # Matching Pennies: # In[35]: print_pure_nash_brute(g_MP) # Coordination game: # In[36]: print_pure_nash_brute(g_Coo) # Rock-Paper-Scissors: # In[37]: print_pure_nash_brute(g_RPS) # Battle of the Sexes: # In[38]: print_pure_nash_brute(g_BoS) # Prisoners' Dillema: # In[39]: print_pure_nash_brute(g_PD) # Cournot game: # In[40]: print_pure_nash_brute(g_Cou) # #### Sequential best response # In some games, such as "supermodular games" and "potential games", # the process of sequential best responses converges to a Nash equilibrium. # Here's a script to find *one* pure Nash equilibrium by sequential best response, if it converges. # In[41]: def sequential_best_response(g, init_actions=None, tie_breaking='smallest', verbose=True): """ Find a pure Nash equilibrium of a normal form game by sequential best response. Parameters ---------- g : NormalFormGame init_actions : array_like(int), optional(default=[0, ..., 0]) The initial action profile. tie_breaking : {'smallest', 'random'}, optional(default='smallest') verbose: bool, optional(default=True) If True, print the intermediate process. """ N = g.N # Number of players a = np.empty(N, dtype=int) # Action profile if init_actions is None: init_actions = [0] * N a[:] = init_actions if verbose: print('init_actions: {0}'.format(a)) new_a = np.empty(N, dtype=int) max_iter = np.prod(g.nums_actions) for t in range(max_iter): new_a[:] = a for i, player in enumerate(g.players): if N == 2: a_except_i = new_a[1-i] else: a_except_i = new_a[np.arange(i+1, i+N) % N] new_a[i] = player.best_response(a_except_i, tie_breaking=tie_breaking) if verbose: print('player {0}: {1}'.format(i, new_a)) if np.array_equal(new_a, a): return a else: a[:] = new_a print('No pure Nash equilibrium found') return None # A Cournot game with linear demand is known to be a potential game, # for which sequential best response converges to a Nash equilibrium. # # Let us try a bigger instance: # In[42]: a, c = 80, 20 N = 3 q_grid = np.linspace(0, a-c, 13) # [0, 5, 10, ..., 60] g_Cou = cournot(a, c, N, q_grid) # In[43]: a_star = sequential_best_response(g_Cou) # By default, start with (0, 0, 0) print('Nash equilibrium indices: {0}'.format(a_star)) print('Nash equilibrium quantities: {0}'.format(q_grid[a_star])) # In[44]: # Start with the largest actions (12, 12, 12) sequential_best_response(g_Cou, init_actions=(12, 12, 12)) # The limit action profile is indeed a Nash equilibrium: # In[45]: g_Cou.is_nash(a_star) # In fact, the game has other Nash equilibria # (because of our choice of grid points and parameter values): # In[46]: print_pure_nash_brute(g_Cou) # Make it bigger: # In[47]: N = 4 q_grid = np.linspace(0, a-c, 61) # [0, 1, 2, ..., 60] g_Cou = cournot(a, c, N, q_grid) # In[48]: sequential_best_response(g_Cou) # In[49]: sequential_best_response(g_Cou, init_actions=(0, 0, 0, 30)) # Sequential best response does not converge in all games: # In[50]: print(g_MP) # Matching Pennies # In[51]: sequential_best_response(g_MP) # #### Support enumeration # The routine [`support_enumeration`](http://quanteconpy.readthedocs.io/en/latest/game_theory/support_enumeration.html#quantecon.game_theory.support_enumeration.support_enumeration), # which is for two-player games, # visits all equal-size support pairs and # checks whether each pair has a Nash equilibrium (in mixed actions) # by the indifference condition. # (This should thus be used only for small games.) # For nondegenerate games, this routine returns all the Nash equilibria. # Matching Pennies: # In[52]: gt.support_enumeration(g_MP) # The output list contains a pair of mixed actions as a tuple of two NumPy arrays, # which constitues the unique Nash equilibria of this game. # Coordination game: # In[53]: print(g_Coo) # In[54]: gt.support_enumeration(g_Coo) # The output contains three tuples of mixed actions, # where the first two correspond to the two pure action equilibria, # while the last to the unique totally mixed action equilibrium. # Rock-Paper-Scissors: # In[55]: print(g_RPS) # In[56]: gt.support_enumeration(g_RPS) # Consider the $6 \times 6$ game by # von Stengel (1997), page 12: # In[57]: player0 = gt.Player( [[ 9504, -660, 19976, -20526, 1776, -8976], [ -111771, 31680, -130944, 168124, -8514, 52764], [ 397584, -113850, 451176, -586476, 29216, -178761], [ 171204, -45936, 208626, -263076, 14124, -84436], [ 1303104, -453420, 1227336, -1718376, 72336, -461736], [ 737154, -227040, 774576, -1039236, 48081, -300036]] ) player1 = gt.Player( [[ 72336, -461736, 1227336, -1718376, 1303104, -453420], [ 48081, -300036, 774576, -1039236, 737154, -227040], [ 29216, -178761, 451176, -586476, 397584, -113850], [ 14124, -84436, 208626, -263076, 171204, -45936], [ 1776, -8976, 19976, -20526, 9504, -660], [ -8514, 52764, -130944, 168124, -111771, 31680]] ) g_vonStengel = gt.NormalFormGame((player0, player1)) # In[58]: len(gt.support_enumeration(g_vonStengel)) # Note that the $n \times n$ game where the payoff matrices are given by the identy matrix # has $2^n−1$ equilibria. # It had been conjectured that this is the maximum number of equilibria of # any nondegenerate $n \times n$ game. # The game above, the number of whose equilibria is $75 > 2^6 - 1 = 63$, # was presented as a counter-example to this conjecture. # Next, let us study the **All-Pay Acution**, # where, unlike standard auctions, # bidders pay their bids regardless of whether or not they win. # Situations modeled as all-pay auctions include # job promotion, R&D, and rent seeking competitions, among others. # # Here we consider a version of All-Pay Auction with complete information, # symmetric bidders, discrete bids, bid caps, and "full dissipation" # (where the prize is materialized if and only if # there is only one bidder who makes a highest bid). # Specifically, each of $N$ players simultaneously bids an integer from $\{0, 1, \ldots, c\}$, # where $c$ is the common (integer) bid cap. # If player $i$'s bid is higher than all the other players', # then he receives the prize, whose value is $r$, common to all players, # and pays his bid $b_i$. # Otherwise, he pays $b_i$ and receives nothing (zero value). # In particular, if there are more than one players who make the highest bid, # the prize gets *fully dissipated* and all the players receive nothing. # Thus, player $i$'s payoff function is # $$ # u_i(b_i, b_{i+1}, \ldots, b_{i+N-1}) = # \begin{cases} # r - b_i & \text{if $b_i > b_j$ for all $j \neq i$}, \\ - b_i & \text{otherwise}. # \end{cases} # $$ # The following is a script to construct a `NormalFormGame` instance # for the All-Pay Auction game, # where we use [Numba](https://lectures.quantecon.org/py/need_for_speed.html#numba) # to speed up the loops: # In[59]: from numba import jit def all_pay_auction(r, c, N, dissipation=True): """ Create a `NormalFormGame` instance for the symmetric N-player All-Pay Auction game with common reward `r` and common bid cap `e`. Parameters ---------- r : scalar(float) Common reward value. c : scalar(int) Common bid cap. N : scalar(int) Number of players. dissipation : bool, optional(default=True) If True, the prize fully dissipates in case of a tie. If False, the prize is equally split among the highest bidders (or given to one of the highest bidders with equal probabilities). Returns ------- NormalFormGame NormalFormGame instance representing the All-Pay Auction game. """ player = gt.Player(np.empty((c+1,)*N)) populate_APA_payoff_array(r, dissipation, player.payoff_array) return gt.NormalFormGame((player,)*N) @jit(nopython=True) def populate_APA_payoff_array(r, dissipation, out): """ Populate the payoff array for a player in an N-player All-Pay Auction game. Parameters ---------- r : scalar(float) Reward value. dissipation : bool, optional(default=True) If True, the prize fully dissipates in case of a tie. If False, the prize is equally split among the highest bidders (or given to one of the highest bidders with equal probabilities). out : ndarray(float, ndim=N) NumPy array to store the payoffs. Modified in place. Returns ------- out : ndarray(float, ndim=N) View of `out`. """ nums_actions = out.shape N = out.ndim for bids in np.ndindex(nums_actions): out[bids] = -bids[0] num_ties = 1 for j in range(1, N): if bids[j] > bids[0]: num_ties = 0 break elif bids[j] == bids[0]: if dissipation: num_ties = 0 break else: num_ties += 1 if num_ties > 0: out[bids] += r / num_ties return out # Consider the two-player case with the following parameter values: # In[60]: N = 2 c = 5 # odd r = 8 # In[61]: g_APA_odd = all_pay_auction(r, c, N) print(g_APA_odd) # Clearly, this game has no pure-action Nash equilibrium. # Indeed: # In[62]: gt.pure_nash_brute(g_APA_odd) # As pointed out by Dechenaux et al. (2006), # there are three Nash equilibria when the bid cap `c` is odd # (so that there are an even number of actions for each player): # In[63]: gt.support_enumeration(g_APA_odd) # In addition to a symmetric, totally mixed equilibrium (the third), # there are two asymmetric, "alternating" equilibria (the first and the second). # If `c` is even, there is a unique equilibrium, which is symmetric and totally mixed. # For example: # In[64]: c = 6 # even g_APA_even = all_pay_auction(r, c, N) gt.support_enumeration(g_APA_even) # #### Vertex enumeration # The routine [`vertex_enumeration`](http://quanteconpy.readthedocs.io/en/latest/game_theory/vertex_enumeration.html#quantecon.game_theory.vertex_enumeration.vertex_enumeration) # computes mixed-action Nash equilibria of a 2-player normal form game # by enumeration and matching of vertices of the best response polytopes. # For a non-degenerate game input, these are all the Nash equilibria. # # Internally, # [`scipy.spatial.ConvexHull`](https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.ConvexHull.html) # is used to compute vertex enumeration of the best response polytopes, # or equivalently, facet enumeration of their polar polytopes. # Then, for each vertex of the polytope for player 0, # vertices of the polytope for player 1 are searched to find a completely labeled pair. # In[65]: gt.vertex_enumeration(g_MP) # In[66]: len(gt.support_enumeration(g_vonStengel)) # In[67]: gt.vertex_enumeration(g_APA_odd) # In[68]: gt.vertex_enumeration(g_APA_even) # `support_enumeration` and `vertex_enumeration` the same functionality # (i.e., enumeration of Nash equilibria of a two-player game), # but the latter seems to run faster than the former. # #### Lemke-Howson # The routine [`lemke_howson`](http://quanteconpy.readthedocs.io/en/latest/game_theory/lemke_howson.html#quantecon.game_theory.lemke_howson.lemke_howson) # implements the Lemke-Howson algorithm (Lemke and Howson 1964), # which returns one Nash equilibrium of a two-player normal form game. # For the details of the algorithm, see, e.g., von Stengel (2007). # Matching Pennies: # In[69]: gt.lemke_howson(g_MP) # Coordination game: # In[70]: gt.lemke_howson(g_Coo) # The initial pivot can be specified by `init_pivot`, # which should be an integer $k$ such that $0 \leq k \leq n_1 + n_2 - 1$ (default to `0`), # where $0, \ldots, n_1-1$ correspond to player 0's actions, # while $n_1 \ldots, n_1+n_2-1$ to player 1's actions. # In[71]: gt.lemke_howson(g_Coo, init_pivot=1) # All-Pay Auction: # In[72]: gt.lemke_howson(g_APA_odd, init_pivot=0) # In[73]: gt.lemke_howson(g_APA_odd, init_pivot=1) # Additional information is returned if the option `full_output` is set `True`: # In[74]: NE, res = gt.lemke_howson(g_APA_odd, full_output=True) res # `lemke_howson` runs fast, # with a reasonable time amount for games with up to several hundreds actions. # (In fact, this is the only routine among the Nash equilibrium computation routines in the `game_theory` submodule # that scales to large-size games.) # For example: # In[75]: N = 2 c = 200 # 201 actions r = 500 g_APA200 = all_pay_auction(r, c, N) # In[76]: gt.lemke_howson(g_APA200) # #### McLennan-Tourky # The routine [`mclennan_tourky`](http://quanteconpy.readthedocs.io/en/latest/game_theory/mclennan_tourky.html#quantecon.game_theory.mclennan_tourky.mclennan_tourky) # computes one approximate Nash equilibrium of an $N$-player normal form game # by the fixed-point algorithm of McLennan and Tourky (2006) applied to the best response correspondence # Consider the symmetric All-Pay Auction with full dissipation as above, but this time with three players: # In[77]: N = 3 r = 16 c = 5 g_APA3 = all_pay_auction(r, c, N) # Run `mclennan_tourky`: # In[78]: NE = gt.mclennan_tourky(g_APA3) NE # This output is an $\varepsilon$-Nash equilibrium of the game, # which is a profile of mixed actions $(x^*_0, \ldots, x^*_{N-1})$ such that # for all $i$, $u_i(x^*_i, x^*_{-i}) \geq u_i(x_i, x^*_{-i}) - \varepsilon$ for all $x_i$, # where the value of $\varepsilon$ is specified by the option `epsilon` (default to `1e-3`). # In[79]: g_APA3.is_nash(NE, tol=1e-3) # In[80]: epsilon = 1e-4 NE = gt.mclennan_tourky(g_APA3, epsilon=epsilon) NE # In[81]: g_APA3.is_nash(NE, tol=epsilon) # Additional information is returned by setting the `full_output` option to `True`: # In[82]: NE, res = gt.mclennan_tourky(g_APA3, full_output=True) res # For this game, `mclennan_tourky` returned a symmetric, totally mixed action profile # (cf. Rapoport and Amaldoss 2004) # with the default initial condition `(0, 0, 0)` (profile of pure actions). # # Let's try a different initial condition: # In[83]: init = ( [1/2, 0, 0, 1/2, 0, 0], [0, 1/2, 0, 0, 1/2, 0], [0, 0, 0, 0, 0, 1] ) # profile of mixed actions gt.mclennan_tourky(g_APA3, init=init) # We obtained an asymetric "alternating" mixed action profile. # While this is just an approximate Nash equilibrium, # it suggests that there is an (exact) Nash equilibrium of the form # $((p_0, 0, p_2, 0, p_4, 0), (p_0, 0, p_2, 0, p_4, 0), (0, q_1, 0, q_3, 0, q_5))$. # In fact, a simple calculation shows that there is one such that # $$ # p_0 = \left(\frac{r-4}{r}\right)^{\frac{1}{2}}, # p_0 + p_2 = \left(\frac{r-2}{r}\right)^{\frac{1}{2}}, # p_4 = 1 - (p_0 + p_2), # $$ # and # $$ # q_1 = \frac{2}{r p_0}, # q_1 + q_3 = \frac{4}{r (p_0+p_2)}, # q_5 = 1 - (q_1 + q_3). # $$ # # To verify: # In[84]: p0 = ((r-4)/r)**(1/2) p02 = ((r-2)/r)**(1/2) p2 = p02 - p0 p4 = 1 - p02 q1 = (2/r)/p0 q13 = (4/r)/(p02) q3 = q13 - q1 q5 = 1 - q13 a = ([p0, 0, p2, 0, p4, 0], [p0, 0, p2, 0, p4, 0], [0, q1, 0, q3, 0, q5]) a # In[85]: g_APA3.is_nash(a) # ## References # # * E. Dechenaux, D. Kovenock, and V. Lugovskyy (2006), # "Caps on bidding in all-pay auctions: # Comments on the experiments of A. Rapoport and W. Amaldoss," # Journal of Economic Behavior and Organization 61, 276-283. # # * C. E. Lemke and J. T. Howson (1964), # "Equilibrium Points of Bimatrix Games," # Journal of the Society for Industrial and Applied Mathematics 12, 413-423. # # * A. McLennan and R. Tourky (2006), # "[From Imitation Games to Kakutani](http://cupid.economics.uq.edu.au/mclennan/Papers/kakutani60.pdf)." # # * A. Rapoport and W. Amaldoss (2004), # "Mixed-strategy play in single-stage first-price all-pay auctions with symmetric players," # Journal of Economic Behavior and Organization 54, 585-607. # # * B. von Stengel (1997), # "[New Lower Bounds for the Number of Equilibria in Bimatrix Games](http://www.maths.lse.ac.uk/personal/stengel/TEXTE/264.pdf)." # # * B. von Stengel (2007), # "[Equilibrium Computation for Two-Player Games in Strategic and Extensive Form](http://www.maths.lse.ac.uk/personal/stengel/TEXTE/agt-stengel.pdf)," # Chapter 3, N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani eds., Algorithmic Game Theory. # In[ ]: