Online multicast with egalitarian cost sharing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Online multicast with egalitarian cost sharing

Full text

Pdf (384 KB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures table of contents

Munich, Germany

SESSION: Broadcasting in networks table of contents

Pages 70-76

Year of Publication: 2008

ISBN:978-1-59593-973-9

Authors

Moses Charikar	Princeton University, Princeton, NJ, USA
Howard Karloff	AT&T Labs, Florham Park, NJ, USA
Claire Mathieu	Brown University, Providence, RI, USA
Joseph (Seffi) Naor	Technion, Haifa, Israel
Michael Saks	Rutgers University, Piscataway, NJ, Israel

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 94, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1378533.1378544 What is a DOI?

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(log² 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(log ³ 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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	A. Agarwal and M. Charikar. On the price of stability for undirected multicast, manuscript, 2006.
	2	Elliot Anshelevich , Anirban Dasgupta , Jon Kleinberg , Eva Tardos , Tom Wexler , Tim Roughgarden, The Price of Stability for Network Design with Fair Cost Allocation, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.295-304, October 17-19, 2004 [doi>10.1109/FOCS.2004.68]
	3	C. Chekuri, J. Chuzhoy, L. Lewin-Eytan, J. Naor, and A. Orda. Noncooperative multicast and facility location games. IEEE Journal on Selected Areas in Communications, Vol. 25 (2007), pp. 1193--1206.
	4	Ho-Lin Chen , Tim Roughgarden, Network design with weighted players, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA [doi>10.1145/1148109.1148114]
	5	A. Fiat, H. Kaplan, M. Levy, S. Olonetsky, and R. Shabo. On the price of stability for designing undirected networks with fair cost allocations. Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, 2006, pp. 608--618.
	6	R. Holzman and N. Law-Yone. Strong equilibrium in congestion games. Games and Economic Behavior, Vol. 21 (1997), pp. 85--101.
	7	M. Imase and B. Waxman. Dynamic steiner tree problem. SIAM J. on Discrete Mathematics, Vol. 4 (1991), 369--384.
	8	E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. 16th Annual Symposium on Theoretical Aspects of Computer Science, 1999, pp. 404--413.
	9	I. Milchtaich. Congestion games with player-specific payoff functions. Games and Economic Behavior, Vol. 13 (1996), 111--124.
	10	V. Mirrokni and A. Vetta. Convergence issues in competitive games. 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, 2004, pp. 183--194.
	11	D. Monderer and L. S. Shapley. Potential games. Games and Economic Behavior, Vol. 14 (1996), pp. 124--143.
	12	R. W. Rosenthal. A class of games possessing pure strategy Nash equilibria. International Journal of Game Theory, Vol. 2 (1973), pp. 65--67.
	13	Tim Roughgarden , Éva Tardos, How bad is selfish routing?, Journal of the ACM (JACM), v.49 n.2, p.236-259, March 2002 [doi>10.1145/506147.506153]
	14	L. S. Shapley. A value for n-person games. Contribution to the Theory of Games, pp. 31-40, Princeton University Press, Princeton, 1953.
	15	M. Voorneveld, P. Borm, F. van Megen, S. Tijs and G. Faccini. Congestion games and potentials reconsidered. International Game Theory Review, Vol. 1 (1999), pp. 283--299.