TY - GEN
T1 - Bottleneck congestion games with logarithmic price of anarchy
AU - Kannan, Rajgopal
AU - Busch, Costas
N1 - Funding Information:
This work was supported in part by NSF grants #CNS-1018273, #IIS-0905478 and a BBN subcontract from #CNS-0940805.
PY - 2010
Y1 - 2010
N2 - We study bottleneck congestion games where the social cost is determined by the worst congestion on any resource. In the literature, bottleneck games assume player utility costs determined by the worst congested resource in their strategy. However, the Nash equilibria of such games are inefficient since the price of anarchy can be very high and proportional to the number of resources. In order to obtain smaller price of anarchy we introduce exponential bottleneck games, where the utility costs of the players are exponential functions of their congestions. In particular, the delay function for any resource r is , where C r denotes the number of players that use r, and is an integer constant. We find that exponential bottleneck games are very efficient and give the following bound on the price of anarchy: O(log|R|), where R is the set of resources. This price of anarchy is tight, since we demonstrate a game with price of anarchy Ω(log|R|). We obtain our tight bounds by using two novel proof techniques: transformation, which we use to convert arbitrary games to simpler games, and expansion, which we use to bound the price of anarchy in a simpler game.
AB - We study bottleneck congestion games where the social cost is determined by the worst congestion on any resource. In the literature, bottleneck games assume player utility costs determined by the worst congested resource in their strategy. However, the Nash equilibria of such games are inefficient since the price of anarchy can be very high and proportional to the number of resources. In order to obtain smaller price of anarchy we introduce exponential bottleneck games, where the utility costs of the players are exponential functions of their congestions. In particular, the delay function for any resource r is , where C r denotes the number of players that use r, and is an integer constant. We find that exponential bottleneck games are very efficient and give the following bound on the price of anarchy: O(log|R|), where R is the set of resources. This price of anarchy is tight, since we demonstrate a game with price of anarchy Ω(log|R|). We obtain our tight bounds by using two novel proof techniques: transformation, which we use to convert arbitrary games to simpler games, and expansion, which we use to bound the price of anarchy in a simpler game.
UR - http://www.scopus.com/inward/record.url?scp=78649534215&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=78649534215&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-16170-4_20
DO - 10.1007/978-3-642-16170-4_20
M3 - Conference contribution
AN - SCOPUS:78649534215
SN - 3642161693
SN - 9783642161698
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 222
EP - 233
BT - Algorithmic Game Theory - Third International Symposium, SAGT 2010, Proceedings
T2 - 3rd International Symposium on Algorithmic Game Theory, SAGT 2010
Y2 - 18 October 2010 through 20 October 2010
ER -