Vertex enumeration

The vertex enumeration algorithm implemented in Nashpy is based on the one described in [Nisan2007].

The algorithm is as follows:

For a nondegenerate 2 player game \((A, B)\in{\mathbb{R}^{m\times n}}^2\) the following algorithm returns all nash equilibria:

  1. Obtain the best response Polytopes \(P\) and \(Q\).
  2. For all pairs of vertices of \(P\) and \(Q\).
  3. Check if the pair is fully labeled and return the normalised probability vectors.

Repeat steps 2 and 3 for all pairs of vertices.

Discussion

  1. Before creating the best response Polytope we need to consider the best response Polyhedron. For the row player, this corresponds to the set of all the mixed strategies available to the row player as well as an upper bound on the utilities to the column player. Analogously for the column player:

    \[ \begin{align}\begin{aligned}\bar P = \{(x, v) \in \mathbb{R}^m \times \mathbb{R}\;|\; x\geq 0, \mathbb{1}x=1, B^Tx\leq\mathbb{1}v\}\\\bar Q = \{(y, u) \in \mathbb{R}^n \times \mathbb{R}\;|\; y\geq 0, \mathbb{1}y=1, Ay\leq\mathbb{1}u\}\end{aligned}\end{align} \]

    Note that in both definitions above we have a total of \(m + n\) inequalities in the constraints.

    For \(P\), the first \(m\) of those constraints correspond to the elements of \(x\) being greater or equal to 0. For a given \(x\), if \(x_i=0\), we say that \(x\) has label :math`i`. This corresponds to strategy \(i\) not being in the support of \(x\).

    For the last \(n\) of these inequalities, when they are equalities they correspond to whether or not strategy \(1\leq j \leq n\) of the other player is a best response to \(x\). Similarly, if strategy \(j\) is a best response to \(x\) then we say that \(x\) has label \(m + j\).

    This all holds analogously for the column player. If the labels of a pair of elements of \(\bar P\) and \(\bar Q\) give the full set of integers from \(1\) to \(m + n\) then they represent strategies that are best responses to each other. Since, this would imply that either a pure stragey is not played or it is a best response to the other players strategy.

    The difficulty with using the best response Polyhedron is that the upper bound on the utilities of both players (\(u, v\)) is not known. Importantly, we do not need to know it. Thus, we assume that in both cases: \(u=v=1\) (this simply corresponds to a scaling of our strategy vectors).

    This allows us to define the best response Polytopes:

    \[ \begin{align}\begin{aligned}P = \{(x, v) \in \mathbb{R}^m \times \mathbb{R}\;|\; x\geq 0, B^Tx\leq 1\}\\Q = \{(y, u) \in \mathbb{R}^n \times \mathbb{R}\;|\; y\geq 0, Ay\leq 1\}\end{aligned}\end{align} \]
  2. Step 2: The vertices of these polytopes are the points that will have labels (they are the points that lie at the intersection of the underlying halfspaces [Ziegler2012]).

    To find these vertices, nashpy uses scipy which has a handy class for creating Polytopes using the inequality definitions and being able to return the vertices. Here is the wrapper written in nashpy that is used by the vertex enumeration algorithm to give the vertices and corresponding labels:

    >>> import nashpy as nash
    >>> import numpy as np
    >>> A = np.array([[3, 1], [1, 3]])
    >>> halfspaces = nash.polytope.build_halfspaces(A)
    >>> vertices = nash.polytope.non_trivial_vertices(halfspaces)
    >>> for vertex in vertices:
    ...     print(vertex)
    (array([ 0.333...,  0...]), {0, 3})
    (array([ 0...,  0.333...]), {1, 2})
    (array([ 0.25,  0.25]), {0, 1})
    
  3. Step 3, we iterate over all pairs of the vertices of both polytopes and pick out the ones that are fully labeled. Because of the scaling that took place to create the Polytope from the Polyhedron, we will need to return a normalisation of both vertices.