We know and love a bunch of nested classes of solution concepts:PN: Pure Nash EquilibriumMN: Mixed Nash EquilibriumCE: Correlated equilibriumCCE: 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?
Bounding the rate of increase of the price of anarchy across equilibrium concepts
gt.game theory
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.