Paper Info
Title
Which Is the Worst-Case Nash Equilibrium?
Abstract
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.
Year
DOI
Venue
2003
10.1007/978-3-540-45138-9_49
Lecture Notes in Computer Science
Keywords
Field
DocType
nash equilibrium,mixed strategy,nash equilibria
Correlated equilibrium,Mathematical economics,Mathematical optimization,Epsilon-equilibrium,Risk dominance,Computer science,Best response,Equilibrium selection,Nash equilibrium,Folk theorem,Trembling hand perfect equilibrium
Conference
Volume
ISSN
Citations 
2747
0302-9743
25
PageRank 
References 
Authors
2.49
12
6
Name
Order
Citations
PageRank
Thomas Lücking135328.79
Marios Mavronicolas21010115.73
Burkhard Monien32199279.35
Manuel Rode419213.92
Paul G. Spirakis52222299.05
Imrich Vrto629633.00