Computer Science – Computer Science and Game Theory
Scientific paper
2011-09-28
Computer Science
Computer Science and Game Theory
14 pages. Short version to appear in WINE 2011
Scientific paper
We analyze the problem of computing a correlated equilibrium that optimizes some objective (e.g., social welfare). Papadimitriou and Roughgarden [2008] gave a sufficient condition for the tractability of this problem; however, this condition only applies to a subset of existing representations. We propose a different algorithmic approach for the optimal CE problem that applies to all compact representations, and give a sufficient condition that generalizes that of Papadimitriou and Roughgarden. In particular, we reduce the optimal CE problem to the deviation-adjusted social welfare problem, a combinatorial optimization problem closely related to the optimal social welfare problem. This framework allows us to identify new classes of games for which the optimal CE problem is tractable; we show that graphical polymatrix games on tree graphs are one example. We also study the problem of computing the optimal coarse correlated equilibrium, a solution concept closely related to CE. Using a similar approach we derive a sufficient condition for this problem, and use it to prove that the problem is tractable for singleton congestion games.
Jiang Albert Xin
Leyton-Brown Kevin
No associations
LandOfFree
A General Framework for Computing Optimal Correlated Equilibria in Compact Games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A General Framework for Computing Optimal Correlated Equilibria in Compact Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A General Framework for Computing Optimal Correlated Equilibria in Compact Games will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-42449