Source code for nash.game

"""A class for a normal form game"""
import numpy as np
from .algorithms.lemke_howson import lemke_howson
from .algorithms.support_enumeration import support_enumeration
from .algorithms.vertex_enumeration import vertex_enumeration
from itertools import combinations


[docs]class Game: """ A class for a normal form game. Parameters ---------- - A, B: 2 dimensional list/arrays representing the payoff matrices for non zero sum games. - A: 2 dimensional list/array representing the payoff matrix for a zero sum game. """ def __init__(self, *args): if len(args) == 2: self.payoff_matrices = tuple([np.asarray(m) for m in args]) if len(args) == 1: self.payoff_matrices = np.asarray(args[0]), -np.asarray(args[0]) self.zero_sum = np.array_equal(self.payoff_matrices[0], -self.payoff_matrices[1]) def __repr__(self): if self.zero_sum: tpe = "Zero sum" else: tpe = "Bi matrix" return """{} game with payoff matrices: Row player: {} Column player: {}""".format(tpe, *self.payoff_matrices) def __getitem__(self, key): row_strategy, column_strategy = key return np.array([np.dot(row_strategy, np.dot(m, column_strategy)) for m in self.payoff_matrices])
[docs] def vertex_enumeration(self): """ Obtain the Nash equilibria using enumeration of the vertices of the best response polytopes. Algorithm implemented here is Algorithm 3.5 of [Nisan2007]_. 1. Build best responses polytopes of both players 2. For each vertex pair of both polytopes 3. Check if pair is fully labelled 4. Return the normalised pair Returns ------- equilibria: A generator. """ return vertex_enumeration(*self.payoff_matrices)
[docs] def support_enumeration(self): """ Obtain the Nash equilibria using support enumeration. Algorithm implemented here is Algorithm 3.4 of [Nisan2007]_. 1. For each k in 1...min(size of strategy sets) 2. For each I,J supports of size k 3. Solve indifference conditions 4. Check that have Nash Equilibrium. Returns ------- equilibria: A generator. """ return support_enumeration(*self.payoff_matrices)
[docs] def lemke_howson_enumeration(self): """ Obtain Nash equilibria for all possible starting dropped labels using the lemke howson algorithm. See `Game.lemke_howson` for more information. Note: this is not guaranteed to find all equilibria. Returns ------- equilibria: A generator """ for label in range(sum(self.payoff_matrices[0].shape)): yield self.lemke_howson(initial_dropped_label=label)
[docs] def lemke_howson(self, initial_dropped_label): """ Obtain the Nash equilibria using the Lemke Howson algorithm implemented using integer pivoting. Algorithm implemented here is Algorithm 3.6 of [Nisan2007]_. 1. Start at the artificial equilibrium (which is fully labeled) 2. Choose an initial label to drop and move in the polytope for which the vertex has that label to the edge that does not share that label. (This is implemented using integer pivoting) 3. A label will now be duplicated in the other polytope, drop it in a similar way. 4. Repeat steps 2 and 3 until have Nash Equilibrium. Parameters ---------- initial_dropped_label: int Returns ------- equilibria: A tuple. """ return lemke_howson(*self.payoff_matrices, initial_dropped_label=initial_dropped_label)