Implement "vertex enumeration", using scipy.spatial.ConvexHull to compute convex hull, or facet enumeration, of the polars of the (translated) best response polytopes.

• This is faster than support_enumeration:

  ns = [10, 11, 12]
  seed = 1234
  for n in ns:
      g = gt.random_game((n, n), random_state=seed)
      %timeit gt.support_enumeration(g)
      %timeit gt.vertex_enumeration(g)

  • support_enumeration:

    • n=10: 124 ms
    • n=11: 528 ms
    • n=12: 2.17 s

  • vertex_enumeration:

    • n=10: 8.95 ms
    • n=11: 21.8 ms
    • n=12: 64.4 ms

• For some degenerate games, vertex_enumeration finds all the extreme equilibria, while support_enumeration fails:

  g = gt.NormalFormGame(
      [[(3, 3), (3, 3)],
       [(2, 2), (5, 6)],
       [(0, 3), (6, 1)]]
  )

  • support_enumeration:

    [(array([ 1.,  0.,  0.]), array([ 1.,  0.])),
     (array([ 0.        ,  0.33333333,  0.66666667]),
      array([ 0.33333333,  0.66666667]))]

  • vertex_enumeration:

    [(array([ 0.        ,  0.33333333,  0.66666667]),
      array([ 0.33333333,  0.66666667])),
     (array([ 1.,  0.,  0.]), array([ 1.,  0.])),
     (array([ 1.,  0.,  0.]), array([ 0.66666667,  0.33333333]))]

• For highly degenerate games where some action is weakly dominated or payoff equivalent to some other mixed action, vertex_enumeration may return fewer equilibria than support_enumeration:

  g = gt.NormalFormGame(np.zeros((2, 2)))

  • support_enumeration:

    [(array([ 1.,  0.]), array([ 1.,  0.])),
     (array([ 1.,  0.]), array([ 0.,  1.])),
     (array([ 0.,  1.]), array([ 1.,  0.])),
     (array([ 0.,  1.]), array([ 0.,  1.]))]

  • vertex_enumeration:

    [(array([ 1.,  0.]), array([ 1.,  0.]))]