The ring design game with fair cost allocation

Angelo Fanelli (), Darius Leniowski, Gianpiero Monaco () and Piotr Sankowski ()
Additional contact information
Angelo Fanelli: CREM - Centre de recherche en économie et management - UNICAEN - Université de Caen Normandie - NU - Normandie Université - UR - Université de Rennes - CNRS - Centre National de la Recherche Scientifique, DI - Dipartimento di Informatica [Italy] - UNIVAQ - Università degli Studi dell'Aquila = University of L'Aquila = Université de L'Aquila
Darius Leniowski: DI - Dipartimento di Informatica [Italy] - UNIVAQ - Università degli Studi dell'Aquila = University of L'Aquila = Université de L'Aquila
Gianpiero Monaco: DI - Dipartimento di Informatica [Italy] - UNIVAQ - Università degli Studi dell'Aquila = University of L'Aquila = Université de L'Aquila
Piotr Sankowski: UW - Uniwersytet Warszawski [Polska] = University of Warsaw [Poland] = Université de Varsovie [Pologne]

Post-Print from HAL

Abstract: In this paper we study the network design game when the underlying network is a ring. In a network design game we have a set of players, each of them aims at connecting nodes in a network by installing links and equally sharing the cost of the installation with other users. The ring design game is the special case in which the potential links of the network form a ring. It is well known that in a ring design game the price of anarchy may be as large as the number of players. Our aim is to show that, despite the worst case, the ring design game always possesses good equilibria. In particular, we prove that the price of stability of the ring design game is at most 3/2, and such bound is tight. Moreover, we observe that the worst Nash equilibrium cannot cost more than 2 times the optimum if the price of stability is strictly larger than 1. We believe that our results might be useful for the analysis of more involved topologies of graphs, e.g., planar graphs.

Keywords: Network design; Nash equilibria; price of stability; Shapley cost-sharing (search for similar items in EconPapers)
Date: 2015-01
References: Add references at CitEc
Citations:

Published in Theoretical Computer Science, 2015, 562, pp.90-100. ⟨10.1016/j.tcs.2014.09.035⟩

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:hal-01103950

DOI: 10.1016/j.tcs.2014.09.035

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().