ALCOMFT-TR-03-159

Martin Gairing, Thomas Lücking, Marios Mavronicolas and Burkhard Monien
Computing Nash Equilibria for Scheduling on Restricted Parallel Links
Paderborn and Cyprus. Work package 2. December 2003.

Abstract: We consider the problem of routing n users on m parallel links, under the restriction that each user may only be routed on a link from a certain set of allowed links for the user. Thus, the problem is equivalent to the correspondingly restricted problem of assigning n jobs to m parallel machines. In a pure Nash equilibrium, no user may improve its own individual cost (delay) by unilaterally switching to another link from its set of allowed links. As our main result, we introduce a polynomial time algorithm to compute from any given assignment a pure Nash Equilibrium with non-increased makespan. The algorithm gradually changes a given assignment by pushing unsplittable user traffics through a network that is defined by the users and the links. Here, we use ideas from blocking flows. Furthermore, we use similar techniques as in the generic Preflow-Push algorithm to approximate a schedule with minimum makespan, gaining an improved approximation factor of 2-1/w_1 for identical links, where w_1 is the largest user traffic. We extend this result to related links, gaining an approximation factor of 2. Our approximation algorithms run in polynomial time. We close with tight upper bounds on the coordination ratio for pure Nash Equilibria.

Postscript file: ALCOMFT-TR-03-159.ps.gz (139 kb).