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\textsf{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.
Keywords Cost sharing – Price of anarchy – Approximate Nash equilibrium – Facility location
Supported by DFG through UMIC Research Centre at RWTH Aachen University.
An extended abstract of this work has appeared in LATIN 2008 [26].