2010 | OriginalPaper | Chapter
Bottleneck Congestion Games with Logarithmic Price of Anarchy
Authors : Rajgopal Kannan, Costas Busch
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
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
$\mathcal{M}^{C_r}$
, where
C
r
denotes the number of players that use
r
, and
$\mathcal{M}$
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.