Competitive Cost Sharing with Economies of Scale

Abstract

We consider a general class of non-cooperative buy-at-bulk cost sharing games, inwhich 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 NPhard. 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.