Computing pure Nash and strong equilibria in bottleneck congestion games (Q378094): Difference between revisions

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.