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.