2012 | OriginalPaper | Chapter
Capacitated Network Design Games
Authors : Michal Feldman, Tom Ron
Published in: Algorithmic Game Theory
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We study a
capacitated
symmetric network design game, where each of
n
agents wishes to construct a path from a network’s source to its sink, and the cost of each edge is shared equally among its agents. The uncapacitated version of this problem has been introduced by Anshelevich
et al.
(2003) and has been extensively studied. We find that the consideration of edge capacities entails a significant effect on the quality of the obtained Nash equilibria (NE), under both the utilitarian and the egalitarian objective functions, as well as on the convergence rate to an equilibrium. The following results are established. First, we provide bounds for the price of anarchy (PoA) and the price of stability (PoS) measures with respect to the utilitarian (i.e., sum of costs) and egalitarian (i.e., maximum cost) objective functions. Our main result here is that, unlike the uncapacitated version, the network topology is a crucial factor in the quality of NE. Specifically, a network topology has a bounded PoA if and only if it is
series-parallel
(SP). Second, we show that the convergence rate of best-response dynamics (BRD) may be super linear (in the number of agents). This is in contrast to the uncapacitated version, where convergence is guaranteed within at most
n
iterations.