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 2(1+1/α). Most of the results are extended to the case in which each player aims at connecting k>2 nodes of the network.

Stackelberg Strategies for Network Design Games

FLAMMINI, MICHELE;
2013-01-01

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 2(1+1/α). Most of the results are extended to the case in which each player aims at connecting k>2 nodes of the network.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11697/16300
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact