Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 6 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.