9
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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