It is well known that a correlated equilibrium can be computed in polynomial time in the size of the game. In a beautiful paper published several years ago, Papadimitriou and Roughgarden proved that this extends even to games that are given concisely. I.e. for many natural ways of succinctly representing “exponential size” games, one can still compute a correlated equilibrium in time that is polynomial in the representation length. This holds for graphical games, anonymous games, polymatrix games, congestion games, scheduling games, local effect games, as well as several generalizations. The logic of the algorithm is as follows: A correlated equilibrium can be expressed as a solution to a linear program. In the case of a succinctly represented game the LP has exponentially many variables but only polynomially many constraints, and thus it’s dual can be solved by the Ellipsoid algorithm — provided that an appropriate separation oracle can be provided. It turns out that, for many succinct representations, this can indeed be done, using a technique of Hart and Schmeidler. The details are somewhat more delicate as the primal LP is unbounded and thus its dual is known to be infeasible, so “solving the dual” will certainly fail, but the failure will supply enough information as to find a solution to the primal.

In a paper by Stein, Parrilo, and Ozdaglar, recently uploaded to the arXiv, the authors claim to have found a bug in the Papadimitriou and Roughgarden paper (I have only skimmed the paper and have not verified it). They note that the Ellipsoid-based algorithm sketched above returns a correlated equilibrium with three properties:

- All its coefficients are rational numbers, if so was the input.
- It is a convex combination of product distributions
- It is symmetric, if so was the game.

However, they exhibit a simple 3-player symmetric game that has a unique equilibrium satisfying the last two properties, an equilibrium with irrational coordinates. (The game gives each player a strategy set of {0,1}, and the common utility of all players is .) They also isolate the problem: when attempting to move from the dual LP to the primal solution, the precision needs to go up, requiring an increase in the bounding Ellipsoid. Finally, they show that the algorithm still finds an *approximate* correlated equilibrium (in time that is polynomial also in ). The question of whether one can find an exact correlated equilibrium of succinctly represented games in polynomial time remains open.

on October 15, 2010 at 9:45 pm |RobiNoam, what does it mean to compute an exact eqm. if its coordinates are (could be) irrational?

It seems like approximation within arbitrary good accuracy is as good as its gets to exact computation, no?

Here, I mean approximation of the coefficients describing an exact eqm, rather than an approximate eqm. in the sense of epsilon-best-response. Or perhaps what’s shown in this recent arxiv paper is the latter concept (computing approximate eqm.)?

Robi.

on October 16, 2010 at 7:30 am |noamnisanWell, there *is* a correlated equilibrium with all-rational coordinates, it just isn’t a symmetric convex combination of product distributions. Thus for example some form of exhaustive search algorithm will find exactly an all-rational equilibrium.

on October 16, 2010 at 5:50 am |ThorstenThis blog makes an appearance on an economics discussion board: http://www.econjobrumors.com/topic.php?id=15883

on October 16, 2010 at 6:27 am |Gil KalaiNoam, there is a paper of Hart and Mas-Colell with a simple dynamic process leading to correlated equilibrium. Does this has some computational consequences?

on October 16, 2010 at 7:31 am |noamnisanThat gives approximation also but the running time would be polynomial in rather than its log.

on October 18, 2010 at 9:29 pm |Noah SteinThanks for the nice summary of our paper. I just want to make a minor clarification on bullet 3: it is important that each of the product distributions from bullet 2 be symmetric (assuming the game was), not just that the resulting convex combination of products be symmetric. For an example to illustrate the difference, consider the 2×2 symmetric probability matrix with zeros on the diagonals and 1/2 on the antidiagonals. This can be written as a convex combination of products: 1/2 times the matrix with a 1 in the upper right plus 1/2 times the matrix with a 1 in the lower left. But these product distributions are not symmetric matrices and indeed this matrix cannot be written as a convex combination of symmetric products.

on October 19, 2010 at 5:33 pm |noamnisanOh, thanks: this is a delicate distinction that I missed.

on October 25, 2010 at 4:22 pm |Christos PapadimitriouSorry that I had not seen this posting for some time. Here is my take.

First of all, to compute a number efficiently means to compute it approximately in time polynomial in the input and the precision bits (since Turing’s paper, recall the title…). So, our theorem is correct, our algorithm does compute a correlated equilibrium efficiently.

In fact, it’s a little better: In this case, the exact solution can be found by a simple, natural and well known trick (first pointed out in a paper by Karp and myself in the early 1980s): Once the precision is twice that of your instance, round to the closest small rational. If it is not a solution, this means that you are very close to a constraint, and you can set it to equality, and proceed from there. We should have mentioned this aspect in our original paper.

The authors do catch an easily fixable bug in our paper: Our “ellipsoid against hope” technique will yield a modified dual which could have a feasible solution (which must be huge), and we don’t want that. In our paper we fix it by enlarging the ellipsoid, and the authors here point out that this does not work. But an easier trick does: explicitly bound the variables.

So, the way this new paper is written (and its title) is a result of cross-cultural misunderstanding and unfamiliarity. We have explained this to the authors, and I believe they are about to remove their paper from the arxiv.

Thanks,

Christos

on October 25, 2010 at 5:45 pm |noamnisanThanks for the clarification, Christos.

I suppose that the strange thing that still remains is that it is not clear how to efficiently find a *rational* equilibrium.

on October 25, 2010 at 7:42 pmChristos PapadimitriouNo, this is an LP, there can be no mystery, look again at my third paragraph.

—c

on October 25, 2010 at 10:32 pmnoamnisanI assume that you are referring to setting the constraints that you are close to to be equalities. It seems that this can maintain symmetry, so I suppose that the point is that you no longer get a convex combination of products?

on October 25, 2010 at 11:28 pm |Christos PapadimitriouDetails need to be worked out, how the repeated projection method works in this context: exponential dimension, implicit variables via product distributions. We hadn’t thought about it (because one gets fast approximation directly — as it turns out with the slight modification proposed in this paper) but we should have. I’m pretty sure it should work. And it may violate both symmetry and product, I’ll think about it.

—c

on October 27, 2010 at 6:56 am |Amos FiatStein, Parrilo, and Ozdaglar paper seemingly withdrawn from ArXiv.

on November 2, 2010 at 12:51 pm |Computation of Correlated Equilibira (cont.) « Algorithmic Game-Theory/Economics[…] 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 […]

on January 1, 2011 at 8:49 am |AGT/E 2010 year in review « Algorithmic Game-Theory/Economics[…] 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 […]

on August 22, 2011 at 6:27 am |Cheree BratuI must convey my love for your generosity supporting those who should have guidance on your niche. Your personal commitment to passing the message across turned out to be extraordinarily beneficial and has continually helped individuals like me to get to their desired goals. Your entire helpful tutorial can mean this much to me and still more to my office workers. Best wishes; from everyone of us.