2005-11: A Counterexample to the Fully Mixed Nash Equilibrium Conjecture
10 May
2005
10 May
'05
10:03 a.m.
The following technical report is available from http://aib.informatik.rwth-aachen.de/: A Counterexample to the Fully Mixed Nash Equilibrium Conjecture Simon Fischer, Berthold Vöcking AIB 2005-11 We study a well-known resource allocation game introduced by Koutsoupias and Papadimitriou. It was conjectured by Gairing et al. that the fully mixed Nash equilibrium is the worst Nash equilibrium for this game. The known algorithms for approximating the so-called "price of anarchy" w.r.t. mixed equilibria rely on this conjecture. We present a counterexample to the conjecture showing that fully mixed equilibria cannot be used to approximate the price of anarchy within reasonable factors.
7165
Age (days ago)
7165
Last active (days ago)
0 comments
1 participants
participants (1)
-
Volker Stolz