Source files

Submodules module

A class for a normal form game


Bases: object

A class for a normal form game.

  • A, B (-) – non zero sum games.
  • A (-) – zero sum game.

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) –
Return type:A tuple.

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.

Return type:A generator
support_enumeration(non_degenerate=False, tol=1e-16)[source]

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.
Return type:A generator.

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
Return type:A generator.

Module contents