Separation between coarse correlated equilibria and correlated equilibria

Question

I am looking for examples of techniques for proving price of anarchy bounds that have the power to separate the price of anarchy over coarse correlated equilibria (the limiting set of no-external-regret dynamics) from the price of anarchy over correlated equilibria (the limiting set of no-swap-regret dynamics). Are natural separations of this type known?

One obstruction towards separating these two classes is that the most natural (and common) way to prove price of anarchy bounds is to observe only that at equilibrium, no player has any incentive to deviate to playing his action at OPT, and to somehow use this to connect the social welfare at some configuration to the social welfare of OPT. Unfortunately, any proof that the price of anarchy over coarse correlated equilibria is small that only considers deviations of each player to a single alternative action (say the action from OPT) necessarily also holds for correlated equilibria, and so cannot provide a separation. This is because the only difference between a coarse correlated equilibrium and a correlated equilibrium is the ability of a player in a correlated equilibrium to simultaneously consider multiple deviations, conditioned on his signal of the play profile drawn from the equilibrium distribution.

Are such separations known?

Answer 1

Fix M>>1>>e and look at the following two player coordination game (both players get the same utility):

M   | 1+e  | 2e   |  e

1+e |  1   |  e   |  0

2e  |  e   |  M   | 1+e

e   |  0   | 1+e  | 1

The second and fourth row and column are strictly dominated so any correlated equilibrium cannot have them in its support, thus it would be on the sub-game:

M  |  2e

2e |  M

for which every correlated equilibrium would give each player more than M/2 utility.

On the other hand, consider the joint probability distribution giving probability 1/2 to each of the 1's, and thus utility 1 to each player. The claim is that this is a coarse equilibrium. In a coarse equilibrium the possible deviations of the row player are to one of the pure strategies independently of the outcome of the joint distribution. Now if it is only known that the column player is mixing evenly between the 2nd and 4th column, then the maximum utility the row player can get is 0.5+e < 1, so deviation is not profitable.