TY - GEN

T1 - Online multicast with egalitarian cost sharing

AU - Charikar, Moses

AU - Karloff, Howard

AU - Mathieu, Claire

AU - Naor, Joseph

AU - Saks, Michael

PY - 2008

Y1 - 2008

N2 - We consider a multicast game played by a set of selfish noncoop-erative 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. Furthermore, we consider what happens if the players, in a second phase, are allowed to change their paths in order to decrease their costs. Thus, in the second phase players play best response dynamics until eventually a Nash equilibrium is reached. We show that the price of anarchy is O(log3 n) and Ω(log n). We also make progress towards understanding the challenging case where arrivals and path changes by existing terminals are interleaved. In particular, we analyze the interesting special case where the terminals fire in random order and prove that the cost of the solution produced (with arbitrary interleaving of actions) is at most O(polylog(n) √n) times the optimum.

AB - We consider a multicast game played by a set of selfish noncoop-erative 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. Furthermore, we consider what happens if the players, in a second phase, are allowed to change their paths in order to decrease their costs. Thus, in the second phase players play best response dynamics until eventually a Nash equilibrium is reached. We show that the price of anarchy is O(log3 n) and Ω(log n). We also make progress towards understanding the challenging case where arrivals and path changes by existing terminals are interleaved. In particular, we analyze the interesting special case where the terminals fire in random order and prove that the cost of the solution produced (with arbitrary interleaving of actions) is at most O(polylog(n) √n) times the optimum.

KW - Best response

KW - Nash equilibrium

KW - Price of anarchy

KW - Shapley value

UR - http://www.scopus.com/inward/record.url?scp=57349163108&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=57349163108&partnerID=8YFLogxK

U2 - 10.1145/1378533.1378544

DO - 10.1145/1378533.1378544

M3 - Conference contribution

AN - SCOPUS:57349163108

SN - 9781595939739

T3 - Annual ACM Symposium on Parallelism in Algorithms and Architectures

SP - 70

EP - 76

BT - SPAA'08 - Proceedings of the 20th Annual Symposium on Parallelism in Algorithms and Architectures

T2 - 20th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA'08

Y2 - 14 June 2008 through 16 June 2008

ER -