Network Creation Games with Disconnected Equilibria


Dateien zu dieser Ressource

Prüfsumme: 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, 17. Dez 2008 - 20. Dez 2008. In: PAPADIMITRIOU, Christos, ed., Shuzhong ZHANG, ed.. Internet and Network Economics : 4th International Workshop, WINE 2008, Proceedings. 4th International Workshop on Internet and Network Economics : WINE 2008. Shanghai, China, 17. Dez 2008 - 20. Dez 2008. Berlin; Heidelberg:Springer, pp. 394-401. ISBN 978-3-540-92184-4

@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:rdf="" xmlns:bibo="" xmlns:dc="" xmlns:dcterms="" xmlns:xsd="" > <rdf:Description rdf:about=""> <dc:language>eng</dc:language> <dc:contributor>Brandes, Ulrik</dc:contributor> <dcterms:issued>2008</dcterms:issued> <dc:creator>Hoefer, Martin</dc:creator> <dc:rights>deposit-license</dc:rights> <bibo:uri rdf:resource=""/> <dc:creator>Brandes, Ulrik</dc:creator> <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> <dcterms:available rdf:datatype="">2011-03-23T10:16:00Z</dcterms:available> <dcterms:title>Network Creation Games with Disconnected Equilibria</dcterms:title> <dc:contributor>Hoefer, Martin</dc:contributor> <dc:creator>Nick, Bobo</dc:creator> <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> <dcterms:rights rdf:resource=""/> </rdf:Description> </rdf:RDF>

Dateiabrufe seit 01.10.2014 (Informationen über die Zugriffsstatistik)

Brandes_opus-117981.pdf 2

Das Dokument erscheint in:

KOPS Suche


Mein Benutzerkonto