ALCOMFT-TR-02-27

Artur Czumaj and Berthold Vöcking
Tight Bounds for Worst-Case Equilibria
MPI. Work packages 2 and 4. May 2002.

Abstract: The coordination ratio is a game theoretic measure that aims to reflect the price of selfish routing in a network. We show that the worst-case coordination ratio on m parallel links (of possibly different speeds) is \begindisplaymath \Theta\left(\frac\log m\log \log \log m\right) \enspace. \enddisplaymath Our bound is asymptotically tight and it entirely resolves an open question posed recently by Koutsoupias and Papadimitriou.

Postscript file: ALCOMFT-TR-02-27.ps.gz (76 kb).