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

<pre><code>M   | 1+e  | 2e   |  e

1+e |  1   |  e   |  0

2e  |  e   |  M   | 1+e

e   |  0   | 1+e  | 1
</code></pre>

<p>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:</p>

<pre><code>M  |  2e

2e |  M
</code></pre>

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

<p>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 &lt; 1, so deviation is not profitable. </p>

CC BY-SA 2.5
2010-10-18T15:21:26.600Z
2010-10-23T11:58:17.700Z
2010-10-23T11:58:17.700Z
Noam
<p>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?</p>

<p>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 <em>only</em> 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 <em>multiple</em> deviations, conditioned on his signal of the play profile drawn from the equilibrium distribution. </p>

<p>Are such separations known?</p>

<gt.game-theory><online-learning>
Separation between coarse correlated equilibria and correlated equilibria
Aaron Roth
# Separation between coarse correlated equilibria and correlated equilibria

(Asked by: username_0 on 2010-10-18)

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?

**Tags:** gt.game-theory, online-learning

---

## 1 answers

### Answer by username_1 on 2010-10-18. Score: 7 | Accepted answer

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.


---

