ALCOMFT-TR-03-141

Martin Gairing, Thomas Lucking, Marios Mavronicolas, Burkhard Monien and Paul Spirakis
The Structure and Complexity of Extreme Nash Equilibria
Paderborn, Patras and Cyprus. Work packages 2 and 4. December 2003.

Abstract: We study the combinatorial structure and computational complexity of extreme Nash equilibria, ones that maximize or minimize a certain objective function, in the context of a selfish routing game. Specifically, we assume a collection of n users, each employing a mixed strategy, which is a probability distribution over m parallel links, to control the routing of its own assigned traffic. In a Nash equilibrium, each user selfishly routes its traffic on those links that minimize its expected latency cost. The social cost of a Nash equilibrium is the expectation, over all random choices of the users, of the maximum, over all links, latency through a link. We are interested in computing (exactly or approximately) the social cost of the worst and the best Nash equilibrium - the ones attaining the maximum ( worst) and the minimum ( best) social cost, respectively. We provide a comprehensive collection of structural and complexity results, where some of the latter benefit from the former.

Our structural results provide substantial evidence for the Fully Mixed Nash Equilibrium Conjecture, which states that the worst Nash equilibrium is the fully mixed Nash equilibrium, where each user chooses each link with positive probability. Specifically, we prove:

• The Fully Mixed Nash Equilibrium Conjecture is valid for pure Nash equilibria.

• Under a certain condition, the social cost of any Nash equilibrium is within a factor of 6 + epsilon, for any constant epsilon > 0, of that of the fully mixed Nash equilibrium, assuming that link capacities are identical. This is shown through applying and extending techniques from the theory of stochastic orders. The factor reduces to 1 if one traffic is at least as large as the sum of the other traffics.

Our complexity results include hardness, approximability and inapproximability ones.

• For identical link capacities and under a certain condition, there is a randomized, polynomial-time algorithm to approximate the worst social cost within a factor arbitrarily close to 6 + epsilon, for any constant epsilon > 0. This builds on the structural results and resorts to a known randomized, polynomial-time approximation scheme (RPTAS) for the social cost of the fully mixed Nash equilibrium.

• For any arbitrary integer k > 0, it is NP-hard to decide whether or not any given allocation of users to links can be transformed into a pure Nash equilibrium using at most k selfish steps, even if the number of links is 2.

• Assuming identical link capacities, there exists a polynomial-time approximation scheme (PTAS) to approximate the best social cost, over all pure Nash equilibria, within a factor of 1 + epsilon, for any arbitrary constant epsilon > 0. (This resorts to sorting traffics and a sequence of n selfish steps.)

• For any arbitrary constant epsilon > 0, it is NP-hard to approximate the worst social cost within a multiplicative factor 2 - (2)/( m+1 - epsilon). The quantity 2 - \frac2 m+1 is the tight upper bound on the ratio of the worst social cost and the optimal cost in the model of identical capacities. Moreover, for any fixed number of links, there exists a pseudopolynomial-time algorithm to compute the worst pure Nash equilibrium. \enditemize

Postscript file: ALCOMFT-TR-03-141.ps.gz (160 kb).