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/23approx 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/7approx 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/155approx 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/11approx 1.818$ and $1.862$, respectively.

Autore Pugliese

• Bilo' Vittorio

Tutti gli autori

• V. Bilò , I. Caragiannis , A. Fanelli , G. Monaco

Titolo volume/Rivista

THEORY OF COMPUTING SYSTEMS

Anno di pubblicazione

2013

ISSN

1432-4350

ISBN

Non Disponibile

Numero di citazioni Wos

Nessuna citazione

Ultimo Aggiornamento Citazioni

Non Disponibile

Numero di citazioni Scopus

11

Ultimo Aggiornamento Citazioni

28/04/2018

Settori ERC

Non Disponibile

Codici ASJC

Non Disponibile