caa a22 4500 445804513 CHVBK 20180317145152.0 cr unu---uuuuu 170323e20110801xx s 000 0 eng 10.1007/s00453-009-9367-3 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9367-3 Hoefer Martin Department of Computer Science, RWTH Aachen, Aachen, Germany aut Competitive Cost Sharing with Economies of Scale [Elektronische Daten] [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 functiong. 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 $\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. Springer Science+Business Media, LLC, 2009 Cost sharing nationallicence Price of anarchy nationallicence Approximate Nash equilibrium nationallicence Facility location nationallicence Algorithmica Springer-Verlag 60/4(2011-08-01), 743-765 0178-4617 60:4<743 2011 60 453 https://doi.org/10.1007/s00453-009-9367-3 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9367-3 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Hoefer Martin Department of Computer Science, RWTH Aachen, Aachen, Germany aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 60/4(2011-08-01), 743-765 0178-4617 60:4<743 2011 60 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer