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.