How to find Nash equilibria with extreme total latency in network congestion games?

Heike Sperber

1st International Conference on Game Theory for Networks

Research Article

How to find Nash equilibria with extreme total latency in network congestion games?

Cite: BibTeX Plain Text

@INPROCEEDINGS{10.1109/GAMENETS.2009.5137397,
    author={Heike Sperber},
    title={How to find Nash equilibria with extreme total latency in network congestion games?},
    proceedings={1st International Conference on Game Theory for Networks},
    publisher={IEEE},
    proceedings_a={GAMENETS},
    year={2009},
    month={6},
    keywords={network congestion game total latency extreme equilibria complexity},
    doi={10.1109/GAMENETS.2009.5137397}
}

Heike Sperber
Year: 2009
How to find Nash equilibria with extreme total latency in network congestion games?
GAMENETS
IEEE
DOI: 10.1109/GAMENETS.2009.5137397

Heike Sperber¹^,*

1: University of Kaiserslautern, Department of Mathematics, Optimization Research Group, Kaiserslautern, Germany

*Contact email: sperber@mathematik.uni-kl.de

Abstract

We study the complexity of finding extreme pure Nash equilibria in symmetric network congestion games and analyse how it depends on the graph topology and the number of users. In our context best and worst equilibria are those with minimum respectively maximum total latency. We establish that both problems can be solved by a Greedy algorithm with a suitable tie breaking rule on parallel links. On series-parallel graphs finding a worst Nash equilibrium is NP-hard for two or more users while finding a best one is solvable in polynomial time for two users and NP-hard for three or more. Additionally we establish NP-hardness in the strong sense for the problem of finding a worst Nash equilibrium on a general acyclic graph.

Keywords: network congestion game total latency extreme equilibria complexity

Published: 2009-06-26
Publisher: IEEE

: http://dx.doi.org/10.1109/GAMENETS.2009.5137397