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

Heike Sperber ()

Mathematical Methods of Operations Research, 2010, vol. 71, issue 2, 245-265

Abstract: We study the complexity of finding extreme pure Nash equilibria in symmetric network congestion games and analyse how it is influenced by the graph topology and the number of users. In our context best and worst equilibria are those with minimum or maximum total latency, respectively. We establish that both problems can be solved by a Greedy type algorithm equipped with a suitable tie breaking rule on extension-parallel graphs. 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. Copyright Springer-Verlag 2010

Keywords: Network congestion game; Total latency; Extreme equilibria; Complexity (search for similar items in EconPapers)
Date: 2010
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1007/s00186-009-0293-6 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:mathme:v:71:y:2010:i:2:p:245-265

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/s00186-009-0293-6

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().