<p>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 <a href="http://dl.acm.org/citation.cfm?id=1379762" rel="nofollow">Ellipsoid approach of Papadimitirou and Roughgarden</a>.</p>

<p>If you are ok with an approximate correlated equilibrium, there are much simpler and easier to implement approaches based on no-regret algorithms. For a textbook exposition, check out <a href="http://www.cs.cmu.edu/~avrim/Papers/regret-chapter.pdf" rel="nofollow">Chapter 4 of Algorithmic Game Theory</a>.</p>

CC BY-SA 3.0
2013-12-28T22:26:29.597Z
2014-01-15T00:48:56.077Z
2014-01-15T00:48:56.077Z
Aaron Roth
<p>I would perhaps suggest taking a look at the "Algorithmic Game Theory" book by Noam Nisan et. al., which briefly discusses this problem. The solution however, is left up to the reader. </p>

<p>If you're needing to actually compute correlated equilibria, and your input is a payoff matrix, I would suggest formulating it as an LP and then applying a standard LP solver like CPLEX or Gurobi. To formulate it as an LP, you introduce a variable for each cell in the payoff matrix, and constrain their sum to one. Then, for each player, action, and action the player can deviate to, you introduce a constraint requiring the deviation to have no better utility, conditioned on the probability distribution induced by the choice of action revealed to the player. This constraint is linear, and I would suggest taking a look at page 14-15 in the Algorithmic Game Theory book for an explanation of the constraint.</p>

<p>If your input is not the payoff matrix, you might still be in luck. For another good paper on (exact) computation of correlated equilibria in compact games, check out "Polynomial-time Computation of Exact Correlated Equilibrium in Compact Games" by Albert Xin Jiang et. al. (Edit: See Albert's answer to this question: <a href="https://cstheory.stackexchange.com/questions/1994/algorithms-for-nash-equilibrium-computation?rq=1">Algorithms for Nash equilibrium computation.</a>)</p>

CC BY-SA 3.0
2013-12-28T20:46:33.803Z
2013-12-28T20:52:57.870Z
2017-04-13T12:32:28.080Z
bassen
<p>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 <a href="http://en.wikipedia.org/wiki/Ellipsoid_method" rel="nofollow">ellipsoid algorithm</a>.</p>

<p><strong>Is there a simpler algorithm to get the correlated equilibrium, or a paper to start from?</strong></p>

CC BY-SA 3.0
2013-12-28T16:56:24.140Z
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 
CC BY-SA 3.0
2013-12-28T17:39:45.003Z
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
CC BY-SA 3.0
2013-12-31T06:59:10.667Z
Your comment should be a separate question.
Jeffε
<linear-programming><gt.game-theory>
Polynomial algorithm for correlated equilibrium
user1071138
# Polynomial algorithm for correlated equilibrium

(Asked by: username_0 on 2013-12-28)

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](http://en.wikipedia.org/wiki/Ellipsoid_method).

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

**Tags:** linear-programming, gt.game-theory

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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?  
> **username_2**: Your comment should be a separate question.  

---

## 2 answers

### Answer by username_3 on 2013-12-28. Score: 7

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](http://dl.acm.org/citation.cfm?id=1379762).

If you are ok with an approximate correlated equilibrium, there are much simpler and easier to implement approaches based on no-regret algorithms. For a textbook exposition, check out [Chapter 4 of Algorithmic Game Theory](http://www.cs.cmu.edu/~avrim/Papers/regret-chapter.pdf).


---

### Answer by username_4 on 2013-12-28. Score: 4

I would perhaps suggest taking a look at the "Algorithmic Game Theory" book by Noam Nisan et. al., which briefly discusses this problem. The solution however, is left up to the reader.

If you're needing to actually compute correlated equilibria, and your input is a payoff matrix, I would suggest formulating it as an LP and then applying a standard LP solver like CPLEX or Gurobi. To formulate it as an LP, you introduce a variable for each cell in the payoff matrix, and constrain their sum to one. Then, for each player, action, and action the player can deviate to, you introduce a constraint requiring the deviation to have no better utility, conditioned on the probability distribution induced by the choice of action revealed to the player. This constraint is linear, and I would suggest taking a look at page 14-15 in the Algorithmic Game Theory book for an explanation of the constraint.

If your input is not the payoff matrix, you might still be in luck. For another good paper on (exact) computation of correlated equilibria in compact games, check out "Polynomial-time Computation of Exact Correlated Equilibrium in Compact Games" by Albert Xin Jiang et. al. (Edit: See Albert's answer to this question: [Algorithms for Nash equilibrium computation.](https://cstheory.stackexchange.com/questions/1994/algorithms-for-nash-equilibrium-computation?rq=1))


---

