## Computation of Correlated Equilibira (cont.)

November 2, 2010 by Noam Nisan

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.

on November 2, 2010 at 4:01 pm |JackI’m confused — based on the comments in your last post, it seemed like there were not actually serious problems with the Papadimitriou/Roughgarden paper, and that the MIT authors withdrew their paper. Is the original paper flawed, or not?

on November 5, 2010 at 4:40 am |Albert JiangThanks for the very nice summary of our result! In reply to the comment by Jack, we believe that our approach has some independently interesting properties, regardless of the severity of the issues in the Papadimitriou&Roughgarden paper. For example, the resulting correlated equilibrium has polynomial-sized support, which is simpler to represent and to sample from than the mixture of product distributions generated by the previous algorithms. Also, while our approach for computing a small-support correlated equilibrium requires an efficient subroutine for computing expected utility under product distributions, *verifying* such a small-support correlated equilibrium does not require such a subroutine.

on January 1, 2011 at 8:49 am |AGT/E 2010 year in review « Algorithmic Game-Theory/Economics[…] On the core algorithmic/complexity questions of the computational difficulty of finding equilibria in games and markets we have seen only little progress, mostly for some market variants. There was some commotion regrading the complexity of correlated equilibria in concise games, but that was soon settled. […]