Paper Info
Title
Quality Of Service In Network Creation Games
Abstract
Network creation games model the creation and usage costs of networks formed by n selfish nodes. Each node v can buy a set of edges, each for a fixed price alpha > 0. Its goal is to minimize its private costs, i.e., the sum (SUM-game, Fabrikant et al., PODC 2003) or maximum (MAX-game, Demaine et al., PODC 2007) of distances from v to all other nodes plus the prices of the bought edges. The above papers show the existence of Nash equilibria as well as upper and lower bounds for the prices of anarchy and stability. In several subsequent papers, these bounds were improved for a wide range of prices a. In this paper, we extend these models by incorporating quality-of-service aspects: Each edge cannot only be bought at a fixed quality (edge length one) for a fixed price a. Instead, we assume that quality levels (i.e., edge lengths) are varying in a fixed interval [beta(sic), (beta) over cap],0 < beta(sic), <= <(beta)over cap> A node now cannot only choose which edge to buy, but can also choose its quality x, for the price p(x), for a given price function p. For both games and all price functions, we show that Nash equilibria exist and that the price of stability is either constant or depends only on the interval size of available edge lengths. Our main results are bounds for the price of anarchy. In case of the SUM-game, we show that they are tight if price functions decrease sufficiently fast.
Year
Venue
DocType
2014
WEB AND INTERNET ECONOMICS
Journal
Volume
ISSN
Citations 
8877
0302-9743
2
PageRank 
References 
Authors
0.43
7
3
Name
Order
Citations
PageRank
Andreas Cord-Landwehr120.43
Alexander Mäcker250.87
Friedhelm Meyer auf der Heide31744238.01