Stackelberg strategies for network design games

Michele Flammini (), Luca Moscardelli () and Angelo Fanelli ()
Additional contact information
Michele Flammini: DI - Dipartimento di Informatica [Italy] - UNIVAQ - Università degli Studi dell'Aquila = University of L'Aquila = Université de L'Aquila
Luca Moscardelli: Dipartimento di Scienze - Universita di Chieti-Pescara - UNICH - Universita' degli Studi "G. d'Annunzio" Chieti-Pescara
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

Post-Print from HAL

Abstract: We consider the network-design game introduced by Anshelevich et al. in which n source–destination pairs must be connected by n respective players equally sharing the cost of the used links. It is well known that the price of anarchy for this class of games may be as large as n. One approach for reducing this bound is that of resorting to the Stackelberg model, in which for a subset of at most ⌊αn⌋ coordinated players, with 0⩽α⩽1, communication paths inducing better equilibria are fixed. In this paper we show the effectiveness of Stackelberg strategies by providing optimal and nearly optimal bounds on the performance achievable by such Stackelberg strategies. In particular, in contrast to previous works, we are also able to provide Stackelberg strategies computable in polynomial time and lowering the price of anarchy from n to . Most of the results are extended to the case in which each player aims at connecting k>2 nodes of the network.

Keywords: network design; Stackelberg strategies; price of anarchy (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations:

Published in Internet Mathematics, 2013, 9 (4), pp.336-359. ⟨10.1080/15427951.2012.727772⟩

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

DOI: 10.1080/15427951.2012.727772

Access Statistics for this paper

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