How hard is it to find extreme Nash equilibria in network congestion games?

In: Christos Papadimitriou and Shuzhong Zhang ed., The 4th International Workshop On Internet And Network Economics (WINE 2008) , Shanghai, China. LNCS, Volume 5385, Springer, P. 82-93, December, 2008

Authors

• Elisabeth Gassner
• Johannes Hatzl
• Sven O. Krumke
• Heike Sperber
• Gerhard J. Woeginger

Abstract

"We study the complexity of finding extreme pure Nash equilibria in symmetric (unweighted) network congestion games. In our context best and worst equilibria are those with minimum respectively maximum makespan. On series-parallel graphs a worst Nash equilibrium can be found by a Greedy approach while finding a best equilibrium is NP-hard. For a fixed number of users we give a pseudo-polynomial algorithm to find the best equilibrium in series-parallel networks. For general network topologies also finding a worst equilibrium is NP-hard."

BibTeX

 
@InProceedings{ Gassner.Etal08ExtremeNashEquilibria, 
   title = { How hard is it to find extreme Nash equilibria in network congestion games? }, 
   author = { Elisabeth Gassner and Johannes Hatzl and Sven O. Krumke and Heike Sperber and Gerhard J. Woeginger },  
   editor = { Christos Papadimitriou and Shuzhong Zhang }, 
   booktitle = { The 4th International Workshop On Internet And Network Economics (WINE 2008) , Shanghai, China },  
   series = { LNCS }, 
   volume = { 5385 },     
   publisher = { Springer },   
   pages = { 82-93 },  
   month = dec, 
   year = 2008, 
} 

---

This publication belongs to the project DeNDeMA.