On the Convergence of Multicast Games in Directed Networks

摘要

We investigate the convergence of the price of anarchy after a limited number of moves in the classical multicast communication game when the underlying communication network is directed. Namely, a subset of nodes of the network are interested in receiving the transmission from a given source node and can share the cost of the used links according to fixed cost sharing methods. At each step, a single receiver is allowed to modify its communication strategy, that is to select a communication path from the source, and assuming a selfish or rational behavior, it will make a best response move, that is it will select a solution yielding the minimum possible payment or shared cost. We determine lower and upper bounds on the price of anarchy, that is the highest possible ratio among the overall cost of the links used by the receivers and the minimum possible cost realizing the required communications, after a limited number of moves under the fundamental Shapley cost sharing method. In particular, assuming that the initial set of connecting paths can be arbitrary, we show an upper bound on the price of anarchy after 2 rounds, during each of which all the receivers move exactly once, and a matching lower bound, that we also extend to for any number k≥2 rounds, where r is the number of receivers. Similarly, exactly matching upper and lower bounds equal to r are determined for any number of rounds when starting from the empty state in which no path has been selected. Analogous results are obtained also with respect to other three natural cost sharing methods considered in the literature, that is the egalitarian, path-proportional and egalitarian-path proportional ones. Most results are also extended to the undirected case in which the communication links are bidirectional. Keywords Non-cooperative networks - Multicast games - Limited number of best-response moves - Price of anarchy - Shapley cost allocation A preliminary version of this work appeared in the Proceedings of the 19th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), San Diego, California, USA, June 9–11, 2007