<p>In <a href="http://agtb.wordpress.com/2009/05/10/correlated-equilibria-some-cs-perspectives/" rel="nofollow">this blog post</a> an example where there is an unbounded gap between the price of stability of CE and MN is given; I believe that something similar would show an unbounded gap for the PoA too.</p>

CC BY-SA 2.5
2010-10-18T15:17:25.007Z
2010-10-18T15:17:25.007Z
Noam
<p>The ratio between $POA(MN)$ and $POA(PN)$ can be arbitrarily large. Consider the following congestion game; we have $n$ players and $n$ items, and each player can choose any item. The cost to a player depends on the congestion of the item picked; it is $f(x)$ if $x$ players pick that item. $f$ will be a sharply growing function.</p>

<p>The only pure Nash has each player picking a unique item, so everyone pays $f(1)$. On the other hand, by symmetry, the randomized strategy where each player picks a uniformly random item is a mixed Nash. If $f$ grows steeply, the total cost will be much more expensive, since there is some chance that multiple players pick the same item.</p>

CC BY-SA 2.5
2010-08-26T18:01:15.797Z
2010-08-26T18:01:15.797Z
Neil Olver
<p>We know and love a bunch of nested classes of solution concepts:</p>

<ul>
<li>PN: Pure Nash Equilibrium</li>
<li>MN: Mixed Nash Equilibrium</li>
<li>CE: Correlated equilibrium</li>
<li>CCE: Course correlated equilibrium.</li>
</ul>

<p>The relationship between these sets is:
$$PN \subset MN \subset CE \subset CCE$$
We can consider the price of anarchy over any one of these solution concepts: the worst case social welfare for any profile in the set, divided by the optimal social welfare:
$$POA(S) = \max_{s \in S}\frac{COST(s)}{OPT}$$
So, by the above containments:
$$POA(PN) \leq POA(MN) \leq POA(CE) \leq POA(CCE)$$
My question: are their known bounds on how fast this quantity can grow? It is possible to have a game with $POA(PN)$ finite, but $POA(CCE)$ unboundedly large. But if I know $POA(PN)$ is finite, does $POA(MN)$ also have to be finite? $POA(CE)$? How much larger can they be?</p>

<gt.game-theory>
Bounding the rate of increase of the price of anarchy across equilibrium concepts
Aaron Roth
# Bounding the rate of increase of the price of anarchy across equilibrium concepts

(Asked by: username_0 on 2010-08-26)

We know and love a bunch of nested classes of solution concepts:

* PN: Pure Nash Equilibrium
* MN: Mixed Nash Equilibrium
* CE: Correlated equilibrium
* CCE: Course correlated equilibrium.

The relationship between these sets is:
$$PN \subset MN \subset CE \subset CCE$$
We can consider the price of anarchy over any one of these solution concepts: the worst case social welfare for any profile in the set, divided by the optimal social welfare:
$$POA(S) = \max\_{s \in S}\frac{COST(s)}{OPT}$$
So, by the above containments:
$$POA(PN) \leq POA(MN) \leq POA(CE) \leq POA(CCE)$$
My question: are their known bounds on how fast this quantity can grow? It is possible to have a game with $POA(PN)$ finite, but $POA(CCE)$ unboundedly large. But if I know $POA(PN)$ is finite, does $POA(MN)$ also have to be finite? $POA(CE)$? How much larger can they be?

**Tags:** gt.game-theory


---

## 2 answers

### Answer by username_2 on 2010-08-26. Score: 6 | Accepted answer

The ratio between $POA(MN)$ and $POA(PN)$ can be arbitrarily large. Consider the following congestion game; we have $n$ players and $n$ items, and each player can choose any item. The cost to a player depends on the congestion of the item picked; it is $f(x)$ if $x$ players pick that item. $f$ will be a sharply growing function.

The only pure Nash has each player picking a unique item, so everyone pays $f(1)$. On the other hand, by symmetry, the randomized strategy where each player picks a uniformly random item is a mixed Nash. If $f$ grows steeply, the total cost will be much more expensive, since there is some chance that multiple players pick the same item.


---

### Answer by username_1 on 2010-10-18. Score: 6

In [this blog post](http://agtb.wordpress.com/2009/05/10/correlated-equilibria-some-cs-perspectives/) an example where there is an unbounded gap between the price of stability of CE and MN is given; I believe that something similar would show an unbounded gap for the PoA too.


---

