Computing pure Nash and strong equilibria in bottleneck congestion games (Q378094)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Computing pure Nash and strong equilibria in bottleneck congestion games |
scientific article |
Statements
Computing pure Nash and strong equilibria in bottleneck congestion games (English)
0 references
11 November 2013
0 references
The authors study computational complexity of pure Nash and strong equilibria in bottleneck congestion games. These games properly model the properties of many real-world network routing applications and are known to possess strong equilibria. The authors provide a generic centralized algorithm to compute strong equilibria in polynomial time for many classes of games (matroid or single-commodity). They examine natural improvement dynamics to reach equilibria in polynomial time. They further establish a variety of hardness results and lower bounds regarding the duration of unilateral and coalitional improvement dynamics.
0 references
bottleneck congestion games
0 references
computation of strong equilibria
0 references
improvement dynamics
0 references