# 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. Dec 28, 2013 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? Dec 28, 2013 at 17:39
• Your comment should be a separate question. Dec 31, 2013 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.