Name
Abstract | ||
|---|---|---|
We study the complexity of finding extreme pure Nash equi- libria in symmetric (unweighted) network congestion games. In our con- text best and worst equilibria are those with minimum respectively max- imum 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 net- work topologies also finding a worst equilibrium is NP-hard. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.tcs.2009.07.046 | Workshop on Internet and Network Economics |
Keywords | Field | DocType |
network congestion game unsplittable flow makespan objective extreme equilibria complexity c72 non-cooperative games,Network congestion game,Complexity,Unsplittable flow,C72 [non-cooperative games],Extreme equilibria,Makespan objective | Combinatorics,Mathematical optimization,Mathematical economics,Epsilon-equilibrium,Job shop scheduling,Price of stability,Best response,Network topology,Network congestion,Nash equilibrium,Lemke–Howson algorithm,Mathematics | Journal |
Volume | Issue | ISSN |
410 | 47 | Theoretical Computer Science |
Citations | PageRank | References |
2 | 0.40 | 14 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Elisabeth Gassner | 1 | 159 | 11.92 |
| Johannes Hatzl | 2 | 59 | 7.96 |
| Sven O. Krumke | 3 | 308 | 36.62 |
| Heike Sperber | 4 | 8 | 1.29 |
| Gerhard Woeginger | 5 | 4176 | 384.37 |