Online multicast with egalitarian cost sharing

Moses Charikar, Howard Karloff, Claire Mathieu, Joseph Naor, Michael Saks

Research output: Chapter in Book/Report/Conference proceedingConference contribution

41 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationSPAA'08 - Proceedings of the 20th Annual Symposium on Parallelism in Algorithms and Architectures
Pages70-76
Number of pages7
DOIs
StatePublished - 2008
Event20th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA'08 - Munich, Germany
Duration: Jun 14 2008Jun 16 2008

Publication series

NameAnnual ACM Symposium on Parallelism in Algorithms and Architectures

Other

Other20th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA'08
Country/TerritoryGermany
CityMunich
Period6/14/086/16/08

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

Keywords

  • Best response
  • Nash equilibrium
  • Price of anarchy
  • Shapley value

Fingerprint

Dive into the research topics of 'Online multicast with egalitarian cost sharing'. Together they form a unique fingerprint.

Cite this