Martin Hoefer
We consider a general class of non-cooperative buy-at-bulk
cost sharing games, in which k players make investments to
purchase a set of resources. Each resource has a certain cost and
must bought to be available to the players. Each player has a
certain constraint on the number and types of resources that she
needs to have available, and she can specify payments to make a
resource available to her. She strives to fulfill her constraint
with the smallest investment possible. Our model includes a natural
economy of scale: for a subset of players capacity must be installed
at the resources, and the cost increase for a resource r is
composed of a fixed price c(r) and a global concave capacity
function g. This cost can be shared arbitrarily between players.
We consider the existence and total cost of pure-strategy exact and
approximate Nash equilibria. In general, prices of anarchy and
stability depend heavily on the economy of scale and are
Θ(k/g(k)). For non-linear functions g pure Nash equilibria might
not exist, and deciding their existence is NP-hard. For subclasses of
games corresponding to covering problems, primal-dual methods can be
applied to derive cheap and stable approximate Nash equilibria in
polynomial time. In addition, for singleton games optimal Nash
equilibria exist. In this case expensive exact as well as cheap
approximate Nash equilibria can be computed in polynomial time. Most
of these results can be extended to games based on facility location
problems.
This work is an extension of an
extended abstract in LATIN 2008.
| Download: |
|