Feeds:
Posts

## Computation of Correlated Equilibira (cont.)

Albert Xin Jiang and Kevin Leyton-Brown have uploaded to the arXiv a new paper, Polynomial-time Computation of Exact Correlated Equilibrium in Compact Games, that simplifies the algorithm of Papadimitriou and Roughgarden and avoids completely the delicate issues of numerical precision raised by Stein, Parrilo, and Ozdaglar described here in a previous blog post.  This also makes it completely clear that the algorithm operates also in the communication complexity setting described by Hart and Mansour.

A correlated equilibrium is defined by a linear program which, in the context under question, has exponentially many variables and polynomially many constraints.  Papadimitriou and Roughgarden suggest running the Ellipsoid on the dual LP which thus has polynomially many variables and exponentially many constraints.  The key step is providing the separating hyperplane oracle needed for the Ellipsoid algorithm, a feat that is accomplished leveraging the proof of existence in Hart and Schmeidler.  The problem with using these separating hyperplanes in the algorithm is that they are not any of the original inequalities, which causes delicate numerical difficulties when trying to go back from the dual solution to the primal one (in our context, actually from the discovery of the in-feasibility of the dual to a primal solution).  The new paper suggests a simple way to provide the Ellipsoid method with a violated inequality rather than with an arbitrary separating hyperplane.  This makes going from the dual back to the primal trivial, as we simply get to eliminate all but a polynomially-large  subset of the original variables, without any numerical issues.  It also ensures that the final correlated equilibrium that we get has polynomial sized support.

The simple observation is that the Hart-Schmeidler separating hyperplane is a convex combination of inequalities, equivalently a probability distribution over them.  Finding a a single violated inequality is thus a de-randomization challenge which in this case is solved using the classical method of conditional expectations.