3
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 4
    $\begingroup$ 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. $\endgroup$ – Peter Shor Dec 28 '13 at 16:56
  • $\begingroup$ 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? $\endgroup$ – user1071138 Dec 28 '13 at 17:39
  • $\begingroup$ Your comment should be a separate question. $\endgroup$ – Jeffε Dec 31 '13 at 6:59
7
$\begingroup$

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.

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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.)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.