We consider the Network Design game introduced by Anshelevich et al. [1] in which n source-destination pairs must be connected by n respective players equally sharing the cost of the used links. By considering the classical SUM social function corresponding to the total network cost, 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 on the Stackelberg model in which for a subset of left perpendicular alpha nright perpendicular coordinated players, with 0 <= alpha <= 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 strategies. In particular, differently from 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/alpha + 1). Most of the results are extended to the social function MAX, in which the maximum player cost is considered.

Stackelberg Strategies for Network Design Games

MOSCARDELLI, Luca
2010-01-01

Abstract

We consider the Network Design game introduced by Anshelevich et al. [1] in which n source-destination pairs must be connected by n respective players equally sharing the cost of the used links. By considering the classical SUM social function corresponding to the total network cost, 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 on the Stackelberg model in which for a subset of left perpendicular alpha nright perpendicular coordinated players, with 0 <= alpha <= 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 strategies. In particular, differently from 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/alpha + 1). Most of the results are extended to the social function MAX, in which the maximum player cost is considered.
2010
LECTURE NOTES IN COMPUTER SCIENCE
978-3-642-17571-8
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/11564/210365
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 7
social impact