Thumbnail

Three Selfish Spanning Tree Games

Gourvès, Laurent; Monnot, Jérôme (2008), Three Selfish Spanning Tree Games, Internet and Network Economics. 4th International Workshop, WINE 2008, Shanghai, China, December 17-20, 2008. Proceedings, Springer-Verlag : Berlin, p. 465-476. http://dx.doi.org/10.1007/978-3-540-92185-1_52

Voir/Ouvrir
Type
Communication / Conférence
Date
2008
Titre du colloque
4th International Workshop, WINE 2008
Date du colloque
2008-12
Ville du colloque
Shanghaï
Pays du colloque
Chine
Titre de l'ouvrage
Internet and Network Economics. 4th International Workshop, WINE 2008, Shanghai, China, December 17-20, 2008. Proceedings
Éditeur
Springer-Verlag
Titre de la collection
Lecture Notes in Computer Science
Numéro dans la collection
5385
Ville d’édition
Berlin
Isbn
978-3-540-92184-4
Pages
465-476
Identifiant publication
Métadonnées
Afficher la notice complète
Auteur(s)
Gourvès, Laurent
Monnot, Jérôme cc
Résumé (EN)
We study a problem in a network. The input is an edge-weighted graph G = (V,E) such that V contains a specific source node r. Every v ∈ V ∖ {r} is an entity which wants to be connected to r either directly or via other entities. The main question is how do the entities deviate from a socially optimal network if they are not monitored by a central authority. We provide theoretical bounds on the (strong) price of anarchy of this game. In particular, three variants – each of them being motivated by a practical situation – are studied.
Mots-clés
price of anarchy; Network; edge-weighted graph