research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:
TitleWhich Is the Worst-Case Nash Equilibrium?
Bibtex cite IDRACTI-RU1-2003-13
Booktitle Mathematical Foundations of Computer Science
Series Lecture Notes in Computer Science
Year published 2003
Month February
Volume 2717
Pages 551-561
Publisher Springer Berlin / Heidelberg
DOI 10.1007/b11836
A Nash equilibrium of a routing network represents a stable state of the network where no user finds it beneficial to unilaterally deviate from its routing strategy. In this work, we investigate the structure of such equilibria within the context of a certain game that models selfish routing for a set of n users each shipping its traffic over a network consisting of m parallel links. In particular, we are interested in identifying the worst-case Nash equilibrium – the one that maximizes social cost. Worst-case Nash equilibria were first introduced and studied in the pioneering work of Koutsoupias and Papadimitriou [9]. More specifically, we continue the study of the Conjecture of the Fully Mixed Nash Equilibrium, henceforth abbreviated as FMNE Conjecture, which asserts that the fully mixed Nash equilibrium, when existing, is the worst-case Nash equilibrium. (In the fully mixed Nash equilibrium, the mixed strategy of each user assigns (strictly) positive probability to every link.) We report substantial progress towards identifying the validity, methodologies to establish, and limitations of, the FMNE Conjecture.
Lucking, Thomas
Mavronicolas, Marios
Monien, Burkhart
Rode, Manuel
Spirakis, Paul
Vrto, Imrich
fulltext.pdf (main file)
Publication ID277