Further Results on Capacitated Network Design Games

摘要

In a capacitated network design game, each of n players selects a path from her source to her sink. The cost of each edge is shared equally among the players using the edge. Every edge has a finite capacity that limits the number of players using the edge. We study the price of stability for such games with respect to the max-cost objective, i.e., the maximum cost paid by any player. We show that the price of stability is O(n) for symmetric games, and this bound is tight. Furthermore, we show that the price of stability for asymmetric games can be Ω(n logn), matching the previously known upper bound. We also prove that the convergence time of best response dynamics cannot be bounded by any function of n.