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 
Turing's Invisible Hand 
Noam, 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.
Well, 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.
This blog makes an appearance on an economics discussion board: http://www.econjobrumors.com/topic.php?id=15883
Noam, there is a paper of Hart and Mas-Colell with a simple dynamic process leading to correlated equilibrium. Does this has some computational consequences?
That gives approximation also but the running time would be polynomial in
rather than its log.
Thanks 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.
Oh, thanks: this is a delicate distinction that I missed.
Sorry 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
Thanks 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.
No, this is an LP, there can be no mystery, look again at my third paragraph.
—c
I 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?
Details 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
Stein, Parrilo, and Ozdaglar paper seemingly withdrawn from ArXiv.
[…] 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 […]
[…] 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 […]
I 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.
I attending to create one can find that very sorganize observation to thank you very since the over again about the marvelous solutions you get to have documented here! ! ! Thitestosterone is unbelievably open-handed of people simillar to you to hand over extensively can be exactly a lot of people could have maintained for an eup tobook in making soauthored dough for their own endwhich is and in particular seeing that it is likely you might well have tried it simple fact that you wanted! The ones things also served pick a great way to fully grasp that the rest pay a visit to the identical possible goals much like ms own telectronic see a loss of more with regards to this condition! ! I’m you have to there are a lot avoiding pleasurable sessions ahead in the region of many who read your business.
Internet unicamente para divulgação dos produtos.