2011 | OriginalPaper | Chapter
A General Framework for Computing Optimal Correlated Equilibria in Compact Games
(Extended Abstract)
Authors : Albert Xin Jiang, Kevin Leyton-Brown
Published in: Internet and Network Economics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 [2008]. 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.