Facets of the Fully Mixed Nash Equilibrium Conjecture

Rainer Feldmann, Marios Mavronicolas, Andreas Pieris

Research output: Contribution to journalArticlepeer-review

Abstract

In this work, we continue the study of the many facets of the Fully Mixed Nash Equilibrium Conjecture, henceforth abbreviated as the backslashmathsfFMNE 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.
Original languageEnglish
Pages (from-to)60-112
Number of pages53
JournalTheory of Computing Systems
Volume47
Issue number1
Early online date13 Mar 2009
DOIs
Publication statusPublished - Jul 2010

Fingerprint

Dive into the research topics of 'Facets of the Fully Mixed Nash Equilibrium Conjecture'. Together they form a unique fingerprint.

Cite this