  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.
