extreme equilibria and components vs. cliques

[stengel]

This issue arises out of a currently inaccurate implementation of topological components vs. cliques in the gte implementation. The computation of an index of an equilibrium component requires fixing this. In addition, we might want to hook in different ways of obtaining extreme equilibria - Avis et al 2010, see https://github.com/stengel/gambit/wiki/Game-Theory-Resources give multiple options for this.

The output of finding equilibria for bimatrix games, as in the Avis et al 2010 paper (which contains all the details), consists of pair of vertices of certain polytopes which correspond to "extreme" equilibria.

Now, look at the bipartite graph with vertices x for player 1 and y for player 2 as nodes where there is an edge (x,y) if and only if (x,y) is a Nash equilibrium. If no other edge is incident to x or y, this is an isolated equilibrium. In general, one might have another equilibrium (x',y) which shares the equilibrium strategy y with (x,y), for example.

A connected component of this bipartite graph is exactly a connected component of Nash equilibria, as follows: Consider such a connected component and look at a maximal "clique" U times V (U x V) so that ALL (x,y) in U x V are equilibria. Then all convex combinations of these extreme equilibria are themselves equilibria.

The enumeration of NE should hence proceed as follows: Find the connected components of the graph, and then enumerate the cliques in it.

What Mark omitted in the GTE code (but not in my clique code which I posted at https://github.com/stengel/standalone/blob/master/coclique3.c ) is the identification of connected components, on which it then makes sense to separately run the clique algorithm.

In order to compute the index via Anne Balthasar's thesis paper (chapter 2) one does not need the cliques at all (and in fact wants to avoid them so as to not count multiple times an extreme (x,y) that belongs to multiple cliques), only the connected component itself.

Now, we have two sets of data:

1. the equilibria which come from vertex pairs; the information about the tableaux as they come from lrs is useful for the index computation (basis and cobasis variables representing the equilibria)
2. the naming of these equilibria with numbers as input for the component/clique algorithm which needs to be fixed.

Where are these things to be found? In

https://github.com/gambitproject/gte/tree/master/lib-algo/src/lse/math/games/matrix

?

[steven7woo]

In Equilibria class, the count() method returns the number of pairs of vertices. There are two HashMap<Integer, Equilibrium, vertexMap1 and vertexMap2 (basically two different permutations of all the EE). Each Equilibrium object contains 2 probability vectors: probVec1 and probVec2.

In BimatrixSolver class, the method findAllEq(Lrs lrs, Rational[][] a, Rational[][] b) computes all EE via LRS. The cobasis is stored in the two VPolygon's: lrsout1 and lrsout2. Essentially, the cobasis is generated by the run(HPolygon in) method in LrsAlgorithm class, and the it corresponds with the Dictionary from the two matrices a&b. I haven't found these in the lse.math.games.matrix package yet.