Computing pure Nash and strong equilibria in bottleneck congestion games (Q378094)

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.