Bounding the rate of increase of the price of anarchy across equilibrium concepts

Question

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?

Answer 1

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 2

In this blog post 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.