Online multicast with egalitarian cost sharing

Abstract

We consider a multicast game played by a set of selfish noncooperative players (i.e., nodes) on a rooted undirected graph. Players arrive one by one and each connects to the root by greedily choosing a path minimizing its cost; the cost of using an edge is split equally among all users using the edge. How large can the sum of the players' costs be, compared to the cost of a "socially optimal" solution, defined to be a minimum Steiner tree connecting the players to the root? We show that the ratio is O(log2 n) and ©(log n), when there are n players. One can view this multicast game as a variant of Online Steiner Tree with a different cost sharing mechanism.