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

View/Open
Type
Communication / Conférence
Date
2008
Conference title
4th International Workshop, WINE 2008
Conference date
2008-12
Conference city
Shanghaï
Conference country
Chine
Book title
Internet and Network Economics. 4th International Workshop, WINE 2008, Shanghai, China, December 17-20, 2008. Proceedings
Publisher
Springer-Verlag
Series title
Lecture Notes in Computer Science
Series number
5385
Published in
Berlin
ISBN
978-3-540-92184-4
Pages
465-476
Publication identifier
Metadata
Show full item record
Author(s)
Gourvès, Laurent
Monnot, Jérôme cc
Abstract (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.
Subjects / Keywords
price of anarchy; Network; edge-weighted graph