Improved lower bounds on the price of stability of undirected network design games

Vittorio Bilò (), Ioannis Caragiannis (), Angelo Fanelli () and Gianpiero Monaco ()
Additional contact information
Vittorio Bilò: Dipartimento di Matematica Ennio De Giorgi - Università del Salento = University of Salento [Lecce]
Ioannis Caragiannis: CTI - Computer Technology Institute - Computer Technology Institute
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
Gianpiero Monaco: UNIVAQ - Università degli Studi dell'Aquila = University of L'Aquila = Université de L'Aquila, I3S - Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis - UNS - Université Nice Sophia Antipolis (1965 - 2019) - CNRS - Centre National de la Recherche Scientifique - UniCA - Université Côte d'Azur

Post-Print from HAL

Abstract: Bounding the price of stability of undirected network design games with fair cost allocation is a challenging open problem in the Algorithmic Game Theory research agenda. Even though the generalization of such games in directed networks is well understood in terms of the price of stability (it is exactly H n , the n-th harmonic number, for games with n players), far less is known for network design games in undirected networks. The upper bound carries over to this case as well while the best known lower bound is 42/23≈1.826. For more restricted but interesting variants of such games such as broadcast and multicast games, sublogarithmic upper bounds are known while the best known lower bound is 12/7≈1.714. In the current paper, we improve the lower bounds as follows. We break the psychological barrier of 2 by showing that the price of stability of undirected network design games is at least 348/155≈2.245. Our proof uses a recursive construction of a network design game with a simple gadget as the main building block. For broadcast and multicast games, we present new lower bounds of 20/11≈1.818 and 1.862, respectively.

Keywords: network design; price of stability (search for similar items in EconPapers)
Date: 2012
References: Add references at CitEc
Citations:

Published in Theory of Computing Systems, 2012, Lecture Notes in Computer Science, 52 (4), pp.668-686. ⟨10.1007/s00224-012-9411-6⟩

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-01103979

DOI: 10.1007/s00224-012-9411-6

Access Statistics for this paper

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