Vertex enumeration

[samwycherley]

Adds the vertex enumeration algorithm from B. von Stengel, Chapter 3 in Nisan et al (eds.) Algorithmic Game Theory (2007), using Polyhedra.jl. Still not quite as fast as support_enumeration (but close).

[oyamad]

@samwycherley Thank you for the PR!

First of all, will you add your test file to runtests.jl by

include("test_vertex_enumeration.jl")

[samwycherley]

@oyamad Sorry, should be fixed now

[oyamad]

Thanks. A few general comments first:

• For readability, could you reduce the length of each line? I limit to 80 characters per line myself, while it seems standard to be 92 characters in Julia?

• Could you delete the parts of the code that are commented out?

• Is possible to return NEs with Rational entries if the input game has Rational payoffs? support_enumeration supports this:

  julia> g = NormalFormGame(Player([3//1 3; 2 5; 0 6]),
                            Player([3//1 2 3; 2 6 1]))
  3×2 NormalFormGame{2, Rational{Int64}}
  
  julia> support_enumeration(g)
  3-element Vector{Tuple{Vector{Rational{Int64}}, Vector{Rational{Int64}}}}:
   ([1//1, 0//1, 0//1], [1//1, 0//1])
   ([4//5, 1//5, 0//1], [2//3, 1//3])
   ([0//1, 1//3, 2//3], [1//3, 2//3])
  

[oyamad]

• Please allow the user to pass a Polyhedra package to Polyhedra.polyhedron. As an example, see the plib option in outerapproximation.

[samwycherley]

Thanks for the suggestions! It should now work that inputting rational payoffs returns a vector of rational Nash equilibria, and I have also implemented the other suggestions.

[oyamad]

Great!

• Could you add a test with a Rational input (see this for an example)?

[samwycherley]

Added. I've also moved NEs_approx_equal from test_support_enumeration.jl to runtests.jl since I changed the vertex enumeration tests to use it