Skip to main content
2 of 2
edited tags
Daniel Apon
  • 6.1k
  • 1
  • 38
  • 53

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

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?

Aaron Roth
  • 9.9k
  • 1
  • 44
  • 68