Type of Publication:  Contribution to a conference 
Author:  Hoefer, Martin 
Year of publication:  2008 
Published in:  LATIN 2008 : Theoretical Informatics / Laber, Eduardo Sany; Bornstein, Claudson; Nogueira, Loana Tito; Faria, Luerbio (ed.).  Berlin, Heidelberg : Springer Berlin Heidelberg, 2008.  (Lecture Notes in Computer Science ; 4957).  pp. 339349.  ISBN 9783540787723 
DOI (citable link):  https://dx.doi.org/10.1007/9783540787730_30 
Summary: 
We consider a general class of noncooperative buyatbulk 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 purestrategy 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 nonlinear functions g pure Nash equilibria might not exist and deciding their existence is NPhard. For subclasses of games corresponding to covering problems, primaldual 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.

Subject (DDC):  004 Computer Science 
Files  Size  Format  View 

There are no files associated with this item. 
HOEFER, Martin, 2008. Competitive Cost Sharing with Economies of Scale. In: LABER, Eduardo Sany, ed., Claudson BORNSTEIN, ed., Loana Tito NOGUEIRA, ed., Luerbio FARIA, ed.. LATIN 2008 : Theoretical Informatics. Berlin, Heidelberg:Springer Berlin Heidelberg, pp. 339349. ISBN 9783540787723. Available under: doi: 10.1007/9783540787730_30
@inproceedings{Hoefer2008Compe3020, title={Competitive Cost Sharing with Economies of Scale}, year={2008}, doi={10.1007/9783540787730_30}, number={4957}, isbn={9783540787723}, address={Berlin, Heidelberg}, publisher={Springer Berlin Heidelberg}, series={Lecture Notes in Computer Science}, booktitle={LATIN 2008 : Theoretical Informatics}, pages={339349}, editor={Laber, Eduardo Sany and Bornstein, Claudson and Nogueira, Loana Tito and Faria, Luerbio}, author={Hoefer, Martin} }
<rdf:RDF xmlns:dcterms="http://purl.org/dc/terms/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:rdf="http://www.w3.org/1999/02/22rdfsyntaxns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dspace="http://digitalrepositories.org/ontologies/dspace/0.1.0#" xmlns:foaf="http://xmlns.com/foaf/0.1/" xmlns:void="http://rdfs.org/ns/void#" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > <rdf:Description rdf:about="https://kops.unikonstanz.de/rdf/resource/123456789/3020"> <dc:language>eng</dc:language> <dspace:isPartOfCollection rdf:resource="https://kops.unikonstanz.de/rdf/resource/123456789/36"/> <dcterms:bibliographicCitation>Publ. in: LATIN 2008: Theoretical informatics : 8th Latin American Symposium, Búzios, Brazil, April 7  11, 2008; proceedings / Eduardo Sany Laber ... (eds.). Berlin ; Heidelberg [u.a.] : Springer, 2008, pp. 339349.  (Lecture Notes in Computer Science ; 4957)</dcterms:bibliographicCitation> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dc:rights>termsofuse</dc:rights> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">20110323T10:15:48Z</dcterms:available> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dcterms:title>Competitive Cost Sharing with Economies of Scale</dcterms:title> <dcterms:issued>2008</dcterms:issued> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">20110323T10:15:48Z</dc:date> <dc:creator>Hoefer, Martin</dc:creator> <dcterms:rights rdf:resource="https://kops.unikonstanz.de/page/termsofuse"/> <dcterms:isPartOf rdf:resource="https://kops.unikonstanz.de/rdf/resource/123456789/36"/> <dcterms:abstract xml:lang="eng">We consider a general class of noncooperative buyatbulk 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 purestrategy 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 nonlinear functions g pure Nash equilibria might not exist and deciding their existence is NPhard. For subclasses of games corresponding to covering problems, primaldual 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.</dcterms:abstract> <bibo:uri rdf:resource="http://kops.unikonstanz.de/handle/123456789/3020"/> <dc:contributor>Hoefer, Martin</dc:contributor> </rdf:Description> </rdf:RDF>