Source code for quantecon.game_theory.vertex_enumeration

"""
Compute all mixed Nash equilibria of a 2-player normal form game by
vertex enumeration.

References
----------
B. von Stengel, "Equilibrium Computation for Two-Player Games in
Strategic and Extensive Form," Chapter 3, N. Nisan, T. Roughgarden, E.
Tardos, and V. Vazirani eds., Algorithmic Game Theory, 2007.

"""
import numpy as np
import scipy.spatial
from numba import jit, guvectorize


[docs]def vertex_enumeration(g, qhull_options=None): """ Compute 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` 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. Parameters ---------- g : NormalFormGame NormalFormGame instance with 2 players. qhull_options : str, optional(default=None) Options to pass to `scipy.spatial.ConvexHull`. See the `Qhull manual <http://www.qhull.org>`_ for details. Returns ------- list(tuple(ndarray(float, ndim=1))) List containing tuples of Nash equilibrium mixed actions. """ return list(vertex_enumeration_gen(g, qhull_options=qhull_options))
[docs]def vertex_enumeration_gen(g, qhull_options=None): """ Generator version of `vertex_enumeration`. Parameters ---------- g : NormalFormGame NormalFormGame instance with 2 players. qhull_options : str, optional(default=None) Options to pass to `scipy.spatial.ConvexHull`. See the `Qhull manual <http://www.qhull.org>`_ for details. Yields ------- tuple(ndarray(float, ndim=1)) Tuple of Nash equilibrium mixed actions. """ try: N = g.N except AttributeError: raise TypeError('input must be a 2-player NormalFormGame') if N != 2: raise NotImplementedError('Implemented only for 2-player games') brps = [_BestResponsePolytope( g.players[1-i], idx=i, qhull_options=qhull_options ) for i in range(N)] labelings_bits_tup = \ tuple(_ints_arr_to_bits(brps[i].labelings) for i in range(N)) equations_tup = tuple(brps[i].equations for i in range(N)) trans_recips = tuple(brps[i].trans_recip for i in range(N)) return _vertex_enumeration_gen(labelings_bits_tup, equations_tup, trans_recips)
@jit(nopython=True) def _vertex_enumeration_gen(labelings_bits_tup, equations_tup, trans_recips): """ Main body of `vertex_enumeration_gen`. Parameters ---------- labelings_bits_tup : tuple(ndarray(np.uint64, ndim=1)) Tuple of ndarrays of integers representing labelings of the vertices of the best response polytopes. equations_tup : tuple(ndarray(float, ndim=2)) Tuple of ndarrays containing the hyperplane equations of the polar polytopes. trans_recips : tuple(scalar(float)) Tuple of the reciprocals of the translations. """ m, n = equations_tup[0].shape[1] - 1, equations_tup[1].shape[1] - 1 num_vertices0, num_vertices1 = \ equations_tup[0].shape[0], equations_tup[1].shape[0] ZERO_LABELING0_BITS = (np.uint64(1) << np.uint64(m)) - np.uint64(1) COMPLETE_LABELING_BITS = (np.uint64(1) << np.uint64(m+n)) - np.uint64(1) for i in range(num_vertices0): if labelings_bits_tup[0][i] == ZERO_LABELING0_BITS: continue for j in range(num_vertices1): xor = labelings_bits_tup[0][i] ^ labelings_bits_tup[1][j] if xor == COMPLETE_LABELING_BITS: yield _get_mixed_actions( labelings_bits_tup[0][i], (equations_tup[0][i], equations_tup[1][j]), trans_recips ) break class _BestResponsePolytope: """ Class that represents a best response polytope for a player in a two-player normal form game. Let :math:`A` and :math:`B` be the m x n and n x m payoff matrices of players 0 and 1, respectively, where the payoffs are assumed to have been shifted in such a way that :math:`A` and :math:`B` are nonnegative and have no zero column. In von Stegel (2007), the best response polytope for player 0 is defined by .. math:: P = \{x \in \mathbb{R}^m \mid x \geq 0,\ B x \leq 1\}, and that for player 1 by .. math:: Q = \{y \in \mathbb{R}^n \mid A y \leq 1,\ y \geq 0\}. Here, by translation we represent these in the form .. math:: \hat{P} = \{z \in \mathbb{R}^m \mid D z \leq 1\}, and .. math:: \hat{Q} = \{w \in \mathbb{R}^n \mid C w \leq 1\}, where :math:`D` and :math:`C` are (m+n) x m and (m+n) x n matrices, respectively. The 2d array of matrix :math:`D` for player 0 (or :math:`C` for player 1) is passed as its `points` argument to `scipy.spatial.ConvexHull`, which then computes, by the Qhull library, convex hull (or facet enumeration). By polar duality, this is equivalent to vertex enumeration of the polytope :math:`\hat{P}`, where its k-th vertex is obtained by `-equations[k, :-1]/ equations[k, -1]`, and the indices of the corresponding binding inequalities by `labelings[k]`, while the vertex of the original polytope :math:`P` can be obtained by `-equations[k, :-1]/ equations[k, -1] + 1/trans_recip`. Parameters ---------- opponent_player : Player Instance of Player with one opponent. idx : scalar(int), optional(default=0) Player index in the normal form game, either 0 or 1. qhull_options : str, optional(default=None) Options to pass to `scipy.spatial.ConvexHull`. See the `Qhull manual <http://www.qhull.org>`_ for details. Attributes ---------- ndim : scalar(int) Dimension of the polytope. hull : scipy.spatial.ConvexHull `ConvexHull` instance reprensenting the polar polytope. num_vertices : scalar(int) Number of the vertices identified by `ConvexHull`. equations : ndarray(float, ndim=2) Output of `ConvexHull.equations`. The k-th vertex is obtained by `-equations[k, :-1]/equations[k, -1]`. labelings : ndarray(int32, ndim=2) Output of `ConvexHull.simplices`. `labelings[k]` stores the indices of the binding inequalities for the k-th vertex. trans_recip : scalar(float) Reciprocal of the translation; the k-th vertex of the original polytope before translation can be computed by `-equations[k, :-1]/equations[k, -1] + 1/trans_recip`. """ def __init__(self, opponent_player, idx=0, qhull_options=None): try: num_opponents = opponent_player.num_opponents except AttributeError: raise TypeError('input must be a Player instance') if num_opponents != 1: raise NotImplementedError( 'Implemented only for Player in a 2-player game' ) B = opponent_player.payoff_array n, m = B.shape self.ndim = m D = np.empty((m+n, m)) nonneg_cond_start, payoff_cond_start = (0, m) if idx == 0 else (n, 0) # Shift the payoffs to be nonnegative and have no zero column col_mins = B.min(axis=0) col_maxs = B.max(axis=0) neg_cols = (col_mins < 0) nonpos_const_cols = (col_maxs == col_mins) * (col_mins <= 0) shifts = np.zeros(m) shifts[col_mins < 0] = -col_mins[col_mins < 0] shifts[nonpos_const_cols] += 1 D[payoff_cond_start:payoff_cond_start+n, :] = B + shifts # Construct matrix D for player 0 (or matrix C for player 1) # by translation z = x - 1/trans_recip row_sums = D[payoff_cond_start:payoff_cond_start+n, :].sum(axis=1) trans_recip = row_sums.max() * 2 D[payoff_cond_start:payoff_cond_start+n, :] *= trans_recip D[payoff_cond_start:payoff_cond_start+n, :] /= \ (trans_recip - row_sums).reshape(n, 1) D[nonneg_cond_start:nonneg_cond_start+m, :] = 0 np.fill_diagonal( D[nonneg_cond_start:nonneg_cond_start+m, :], -trans_recip ) # Create scipy.spatial.ConvexHull self.hull = scipy.spatial.ConvexHull(D, qhull_options=qhull_options) self.equations = self.hull.equations self.labelings = self.hull.simplices self.num_vertices = self.hull.equations.shape[0] self.trans_recip = trans_recip @guvectorize(['(i4[:], u8[:])'], '(m)->()', nopython=True, cache=True) def _ints_arr_to_bits(ints_arr, out): """ Convert an array of integers representing the set bits into the corresponding integer. Compiled as a ufunc by Numba's `@guvectorize`: if the input is a 2-dim array with shape[0]=K, the function returns a 1-dim array of K converted integers. Parameters ---------- ints_arr : ndarray(int32, ndim=1) Array of distinct integers from 0, ..., 63. Returns ------- np.uint64 Integer with set bits represented by the input integers. Examples -------- >>> ints_arr = np.array([0, 1, 2], dtype=np.int32) >>> _ints_arr_to_bits(ints_arr) 7 >>> ints_arr2d = np.array([[0, 1, 2], [3, 0, 1]], dtype=np.int32) >>> _ints_arr_to_bits(ints_arr2d) array([ 7, 11], dtype=uint64) """ m = ints_arr.shape[0] out[0] = 0 for i in range(m): out[0] |= np.uint64(1) << np.uint64(ints_arr[i]) @jit(nopython=True, cache=True) def _get_mixed_actions(labeling_bits, equation_tup, trans_recips): """ From a labeling for player 0, a tuple of hyperplane equations of the polar polytopes, and a tuple of the reciprocals of the translations, return a tuple of the corresponding, normalized mixed actions. Parameters ---------- labeling_bits : scalar(np.uint64) Integer with set bits representing a labeling of a mixed action of player 0. equation_tup : tuple(ndarray(float, ndim=1)) Tuple of hyperplane equations of the polar polytopes. trans_recips : tuple(scalar(float)) Tuple of the reciprocals of the translations. Returns ------- tuple(ndarray(float, ndim=1)) Tuple of mixed actions. """ m, n = equation_tup[0].shape[0] - 1, equation_tup[1].shape[0] - 1 out = np.empty(m+n) for pl, (start, stop, skip) in enumerate([(0, m, np.uint64(1)), (m, m+n, np.uint64(0))]): sum_ = 0. for i in range(start, stop): if (labeling_bits & np.uint64(1)) == skip: out[i] = 0 else: out[i] = equation_tup[pl][i-start] * trans_recips[pl] - \ equation_tup[pl][-1] sum_ += out[i] labeling_bits = labeling_bits >> np.uint64(1) if sum_ != 0: out[start:stop] /= sum_ return out[:m], out[m:]