Martin Hoefer
We consider a general class of non-cooperative buy-at-bulk cost sharing games,
in which k players must contribute to purchase a number of resources. The
resources have costs and must be paid for to be available to players. Each
player can specify payments and has a certain constraint on the number and
types of resources that she needs to have available. She strives to fulfill
this 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. The cost increase for larger sets of players is composed
of a fixed price c(r) for each resource r and a global concave capacity
function g. This cost can be shared arbitrarily between players.
We consider the quality
and existence 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. Some of our results can be extended to games based on facility
location problems.
The full version appears in
Martin Hoefer.
Cost Sharing with Economies of Scale.
Algorithmica, to appear, 2009.
| Download full version: |
|
Download proceedings version,
© Springer Verlag