Facets of the fully mixed Nash equilibrium conjecture
Date
2010Author
Feldmann, R.Mavronicolas, Marios
Pieris, Andreas
ISSN
1432-4350Source
Theory of Computing SystemsVolume
47Issue
1Pages
60-112Google Scholar check
Keyword(s):
Metadata
Show full item recordAbstract
In this work, we continue the study of the many facets of the Fully Mixed Nash Equilibrium Conjecture, henceforth abbreviated as the FMNE Conjecture, in selfish routing for the special case of n identical users over two (identical) parallel links. We introduce a new measure of Social Cost, defined as the expectation of the square of the maximum congestion on a link we call it Quadratic Maximum Social Cost. A Nash equilibrium is a stable state where no user can improve her (expected) latency by switching her mixed strategy a worst-case Nash equilibrium is one that maximizes Quadratic Maximum Social Cost. In the fully mixed Nash equilibrium, all mixed strategies achieve full support. Formulated within this framework is yet another facet of the FMNE Conjecture, which states that the fully mixed Nash equilibrium is the worst-case Nash equilibrium. We present an extensive proof of the FMNE Conjecture the proof employs a combination of combinatorial arguments and analytical estimations. © Springer Science+Business Media, LLC 2009.