Network Creation Games with Disconnected Equilibria

Cite This

Files in this item

Checksum: MD5:ae6e7153eb327af4b01946b00d6b7c39

BRANDES, Ulrik, Martin HOEFER, Bobo NICK, 2008. Network Creation Games with Disconnected Equilibria. 4th International Workshop on Internet and Network Economics : WINE 2008. Shanghai, China, Dec 17, 2008 - Dec 20, 2008. In: PAPADIMITRIOU, Christos, ed., Shuzhong ZHANG, ed.. Internet and Network Economics : 4th International Workshop, WINE 2008, Proceedings. Berlin; Heidelberg:Springer, pp. 394-401. ISBN 978-3-540-92184-4. Available under: doi: 10.1007/978-3-540-92185-1_45

@inproceedings{Brandes2008Netwo-3063, title={Network Creation Games with Disconnected Equilibria}, year={2008}, doi={10.1007/978-3-540-92185-1_45}, number={5385}, isbn={978-3-540-92184-4}, address={Berlin; Heidelberg}, publisher={Springer}, series={Lecture Notes in Computer Science}, booktitle={Internet and Network Economics : 4th International Workshop, WINE 2008, Proceedings}, pages={394--401}, editor={Papadimitriou, Christos and Zhang, Shuzhong}, author={Brandes, Ulrik and Hoefer, Martin and Nick, Bobo} }

<rdf:RDF xmlns:dcterms="" xmlns:dc="" xmlns:rdf="" xmlns:bibo="" xmlns:dspace="" xmlns:foaf="" xmlns:void="" xmlns:xsd="" > <rdf:Description rdf:about=""> <dc:language>eng</dc:language> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dcterms:isPartOf rdf:resource=""/> <dc:contributor>Brandes, Ulrik</dc:contributor> <dcterms:issued>2008</dcterms:issued> <dc:creator>Hoefer, Martin</dc:creator> <bibo:uri rdf:resource=""/> <dc:rights>terms-of-use</dc:rights> <dcterms:rights rdf:resource=""/> <dcterms:abstract xml:lang="eng">In this paper we extend a popular non-cooperative network creation game (NCG) [11] to allow for disconnected equilibrium networks. There are n players, each is a vertex in a graph, and a strategy is a subset of players to build edges to. For each edge a player must pay a cost α, and the individual cost for a player represents a trade-off between edge costs and shortest path lengths to all other players. We extend the model to a penalized game (PCG), for which we reduce the penalty for a pair of disconnected players to a finite value β. We prove that the PCG is not a potential game, but pure Nash equilibria always exist, and pure strong equilibria exist in many cases. We provide tight conditions under which disconnected (strong) Nash equilibria can evolve. Components of these equilibria must be (strong) Nash equilibria of a smaller NCG. But in contrast to the NCG, for the vast majority of parameter values no tree is a stable component. Finally, we show that the price of anarchy is Θ(n), several orders of magnitude larger than in the NCG. Perhaps surprisingly, the price of anarchy for strong equilibria increases only to at most 4.</dcterms:abstract> <dc:creator>Brandes, Ulrik</dc:creator> <dcterms:hasPart rdf:resource=""/> <dcterms:available rdf:datatype="">2011-03-23T10:16:00Z</dcterms:available> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dcterms:title>Network Creation Games with Disconnected Equilibria</dcterms:title> <dc:creator>Nick, Bobo</dc:creator> <dc:contributor>Hoefer, Martin</dc:contributor> <dspace:isPartOfCollection rdf:resource=""/> <dspace:hasBitstream rdf:resource=""/> <dc:date rdf:datatype="">2011-03-23T10:16:00Z</dc:date> <dcterms:bibliographicCitation>Publ. in: Internet and Network Economics. Berlin, Heidelberg: Springer, 2008, pp. 394-401</dcterms:bibliographicCitation> <dc:contributor>Nick, Bobo</dc:contributor> </rdf:Description> </rdf:RDF>

Downloads since Oct 1, 2014 (Information about access statistics)

Brandes_opus-117981.pdf 179

This item appears in the following Collection(s)

Search KOPS


My Account