Stackelberg Strategies for Network Design Games

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.