# Polynomial algorithm for correlated equilibrium

I searched through the web for a polynomial algorithm for correlated equilibrium. I found a lot of papers by C.H. Papadimitriou that proposes a solution using the ellipsoid algorithm.

Is there a simpler algorithm to get the correlated equilibrium, or a paper to start from?

• Wikipedia says "One of the advantages of correlated equilibria is that they are computationally less expensive than are Nash equilibria. This can be captured by the fact that computing a correlated equilibrium only requires solving a linear program whereas solving a Nash equilibrium requires finding its fixed point completely." There are potentially lots of more practical alternatives in the cases where you have linear programs that theoretically need the ellipsoid algorithm to be polynomial-time. Deciding which, if any, work, requires some understanding LP and of the specific problem. – Peter Shor Dec 28 '13 at 16:56
• My problem is: restricted scheduling game with unweighted jobs. I have formulated the LP problem, which is: $$min \sum_{s \in S} \sum_{i \in M} \pi(s) c_i(s)$$ $$\forall machines \sum_{s \in S}\pi(s) c_i(s) \le \sum_{s'\in S}\pi(s) c_i(s')$$. s' derives from s, changing only the i-th choice. Finally: $$\sum_{i=1}^{|M|}\pi_{i} \le 1$$. M is the set of all machines and S is the set of all strategies. Which methods we can apply to solve it? – user1071138 Dec 28 '13 at 17:39
• Your comment should be a separate question. – Jeffε Dec 31 '13 at 6:59

The linear program for computing a correlated equilibrium in a game has size that is polynomial in the size of the game matrix: i.e. exponential in the number of players. The scheduling game that you describe is an $n$ player game, so the linear program will not be polynomially sized. However, it is a compactly represented game, so you can in principle use the Ellipsoid approach of Papadimitirou and Roughgarden.