Abstract of Paper

Which is the Worst-case Nash Equilibrium?
by Thomas Luecking, Marios Mavronicolas, Burkhard Monien, Manuel Rode, Paul Spirakis, Imrich Vrto

Abstract:

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.
 
Our first set of results provides strong evidence for the validity of
the FMNE Conjecture by establishing it in a number of interesting
instances of the routing game. All these instances fall within the
model of related links, where there is a capacity $c^{j}$ for each link
j, and the individual delay of user i (with traffic $w_{i}$) on link j
is $w_{i}/ c^{j}$.
Specifically, we prove:

- The FMNE Conjecture is valid if all mixed strategies of the players
  are mutually disjoint, while link capacities vary arbitrarily.  In
  consequence, this implies the validity of the conjecture in case
  there are only two users and the network consists of just two links.
- The FMNE Conjecture is valid when there are just two links with
  identical capacities and an arbitrary (but even) number of users
  with identical traffics.  This is shown through an elegant
  combinatorial analysis, involving properties of binomial
  coefficients, that may be of independent interest.
- The FMNE Conjecture is valid when there are just two users with
  identical traffics and an arbitrary number of links with arbitrary
  capacities.  This is shown through elegant combinatorial arguments
  and an involved analytical approach.

Our second set of results applies to the case of unrelated links,
where no relation is assumed between the delays of a single user on
different links. We obtain here simple instances of the selfish
routing game for which the FMNE Conjecture is valid, and some other
simple instances of it for which the FMNE Conjecture
fails. Specifically, we prove:

- The FMNE Conjecture is valid if all strategies of the users are pure
  and $n\leq  m$; that is, the social cost of any pure Nash equilibrium is
  no more than the social cost of the fully mixed Nash equilibrium.
- The FMNE Conjecture is valid if $n=2$ and $m=2$, while it fails when $n=3$
  and $m=2$.

Most importantly, our results for the case of unrelated links provide
concrete limitations on the generality of the FMNE Conjecture,
since they imply that it is not valid for every game.