Applications of approximation algorithms to cooperative games

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Applications of approximation algorithms to cooperative games

Full text

Pdf (209 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-third annual ACM symposium on Theory of computing table of contents

Hersonissos, Greece

Pages: 364 - 372

Year of Publication: 2001

ISBN:1-58113-349-9

Authors

Kamal Jain	One Microsoft Way, Redmond, WA
Vijay Vazirani	College of Computing, Georgia Institute of Technology, Atlanta, GA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 15, Downloads (12 Months): 107, Citation Count: 47

Additional Information:

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/380752.380825 What is a DOI?

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	M. L. Balinski. On finding integer solutions to linear programs. In Proc. IBM Scientific Computing Symp. on Combinatorial Problems, pages 225-248, 1966.
	2	C. Bird. On cost allocation for a spanning tree: a game theoretic approach. Networks, 6:335-350, 1976.
	3	O. N. Bondareva. Some applications of linear programming to cooperative games. Problemy Kibernetiki, 10:119-139, 1963.
	4	Stephen E. Deering , David R. Cheriton, Multicast routing in datagram internetworks and extended LANs, ACM Transactions on Computer Systems (TOCS), v.8 n.2, p.85-110, May 1990 [doi>10.1145/78952.78953]
	5	B. Dutta and D. Ray. A concept of egalitarianism under participation constraints. Econometrica, 57:615-635.
	6	J. Edmonds. Optimum branchings. J. Res. Nat. Bur. Standards, B71:233-240, 1967.
	7	U. Faigle, S. Fekete, W. Hochstattler, and W. Kern. On approximation fair cost allocation in euclidean tsp games. In Electronic Colloquium on Computational Complexity, pages TR95-016, 1995.
	8	Joan Feigenbaum , Christos Papadimitriou , Scott Shenker, Sharing the cost of muliticast transmissions (preliminary version), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.218-227, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335332]
	9	S. P. Fekete and W. R. Pulleyblank. A note on the traveling preacher problem. submitted to,Operations Research Letter.
	10	Michel X. Goemans , Martin Skutella, Cooperative facility location games, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.76-85, January 09-11, 2000, San Francisco, California, United States
	11	D. Granot and G. Huberman. On minimum cost spanning tree games. Mathematical Programming, 21:1-18, 1981.
	12	D. Granot and G. Huberman. On the core and nucleolus of minimum cost spanning tree games. Mathematical Programming, 29:323-347, 1984.
	13	J. Green, E. Kohlberg, and J. J. Laffont. Partial equilibirium approach to the free rider problem. Journal of Public Economics, 6:375-394, 1976.
	14	K. Jain and V. V. Vazirani. Group strategyproof cost allocation under a broader notion of a egalitarianism. In preparation.
	15	R. Karp , E. Koutsoupias , C. Papadimitriou , S. Shenker, Optimization problems in congestion control, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.66, November 12-14, 2000
	16	K. Kent and D. Skorin-Kapov. On the core of the minimum steiner tree game in networks. In Annals of Operation Research, volume 57, pages 233-249, 1995.
	17	K. Kent and D. Skorin-Kapov. Population monotonic cost allocation on mst's. In Operational Reearch Proceedings KOI, pages 43-48, 1996.
	18	K. Kent and D. Skorin-Kapov. Distance monotonic stable cost allocation scheme for the minimum cost spanning tree network. In Proceedings of the 19th Conference Information Technology Interfaces ITI, pages 463-468, 1997.
	19	L. Kou, G. Markowsky, and L. Berman. A fast algorithm for Steiner trees. Acta Informatica, 15:141-145, 1981.
	20	Koutsoupias and Papadimitriou. Worst-case equilibria. In Proceedings of STACS, 1998.
	21	A. Kumar , J. Kleinberg, Fairness measures for resource allocation, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.75, November 12-14, 2000
	22	N. Megiddo. Cost allocation for steiner trees. Networks, 8:1-6, 1978.
	23	H. Moulin. Incremental cost sharing: characterization by coalition strategy-proofness. Social Choice and Welfare, 16:279-320, 1999.
	24	H. Moulin and S. Shenker. Strategyproof sharing of submodular costs: budget balance versus efficiency. http://www.aciri.org/shenker/cost.ps, 1997.
	25	S. Mutuswami. Strategyproof mechanism for cost sharing. working paper, Indian statistical Institute.
	26	Nisan. Algorithms for selfish agents - mechanism design for distributed computation. In Proceedings of STACS, 1999.
	27	Noam Nisan , Amir Ronen, Algorithmic mechanism design (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.129-140, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301287]
	28	K. Roberts. The characterization of implementable choice rules. In J. J. Laffont, editor, Aggregation and Revealation of Preferences, pages 321-348, North Holland, 1979.
	29	T. Roughgarden , E. Tardos, How bad is selfish routing?, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.93, November 12-14, 2000
	30	L. S. Shapley. On balanced sets and cores. Naval Research Logistics Quarterly, 14:453-460.
	31	L. S. Shapley. Avalue of n-person games. In H. Kuhn and W. Tucker, editors, Contributions to the theory of games, pages 31-40. Princeton University Press, 1953.
	32	Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001

CITED BY 47

	Aranyak Mehta , Scott Shenker , Vijay V. Vazirani, Profit-maximizing multicast pricing by approximating fixed points [Extended Abstract], Proceedings of the 4th ACM conference on Electronic commerce, June 09-12, 2003, San Diego, CA, USA
	Evangelos Markakis , Amin Saberi, On the core of the multicommodity flow game, Proceedings of the 4th ACM conference on Electronic commerce, p.93-97, June 09-12, 2003, San Diego, CA, USA
	Kamal Jain , Vijay V. Vazirani, Equitable cost allocations via primal-dual-type algorithms, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Micah Adler , Dan Rubenstein, Pricing multicasting in more practical network models, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.981-990, January 06-08, 2002, San Francisco, California
	Joan Feigenbaum , Scott Shenker, Distributed algorithmic mechanism design: recent results and future directions, Proceedings of the 6th international workshop on Discrete algorithms and methods for mobile computing and communications, September 28-28, 2002, Atlanta, Georgia, USA
	Kamal Jain , Mohammad Mahdian , Evangelos Markakis , Amin Saberi , Vijay V. Vazirani, Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP, Journal of the ACM (JACM), v.50 n.6, p.795-824, November 2003
	Markus Bläser , Bodo Manthey, Budget balanced mechanisms for the multicast pricing problem with rates, Proceedings of the 4th ACM conference on Electronic commerce, June 09-12, 2003, San Diego, CA, USA
	Elliot Anshelevich , Anirban Dasgupta , Eva Tardos , Tom Wexler, Near-optimal network design with selfish agents, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Nikhil R. Devanur , Milena Mihail , Vijay V. Vazirani, Strategyproof cost-sharing mechanisms for set cover and facility location games, Proceedings of the 4th ACM conference on Electronic commerce, p.108-114, June 09-12, 2003, San Diego, CA, USA
	Daniel Lehmann , Liadan Ita Oćallaghan , Yoav Shoham, Truth revelation in approximately efficient combinatorial auctions, Journal of the ACM (JACM), v.49 n.5, p.577-602, September 2002
	Susanne Albers , Stefan Eilts , Eyal Even-Dar , Yishay Mansour , Liam Roditty, On nash equilibria for a network creation game, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.89-98, January 22-26, 2006, Miami, Florida
	Aranyak Mehta , Scott Shenker , Vijay V. Vazirani, Posted price profit maximization for multicast by approximating fixed points, Journal of Algorithms, v.58 n.2, p.150-164, February 2006
	Stefano Leonardi , Guido Schaefer, Cross-monotonic cost-sharing methods for connected facility location games, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA
	Joan Feigenbaum , Arvind Krishnamurthy , Rahul Sami , Scott Shenker, Hardness results for multicast cost sharing, Theoretical Computer Science, v.304 n.1-3, p.215-236, 28 July 2003
	Vittorio Bilè , Chiara Di Francescomarino , Michele Flammini , Giovanna Melideo, Sharing the cost of multicast transmissions in wireless networks, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	Artur Czumaj , Amir Ronen, On the expected payment of mechanisms for task allocation, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Stefano Leonardi , Guido Schäfer, Cross-monotonic cost sharing methods for connected facility location games, Theoretical Computer Science, v.326 n.1-3, p.431-442, 20 October 2004
	Weizhao Wang , Xiang-Yang Li, Low-Cost Routing in Selfish and Rational Wireless Ad Hoc Networks, IEEE Transactions on Mobile Computing, v.5 n.5, p.596-607, May 2006
	Amos Fiat , Andrew V. Goldberg , Jason D. Hartline , Anna R. Karlin, Competitive generalized auctions, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Anupam Gupta , Martin Pál , R. Ravi , Amitabh Sinha, Boosted sampling: approximation algorithms for stochastic optimization, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Debasis Mishra , Bharath Rangarajan, Cost sharing in a job scheduling problem using the Shapley value, Proceedings of the 6th ACM conference on Electronic commerce, p.232-239, June 05-08, 2005, Vancouver, BC, Canada
	Éva Tardos, Network games, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.341-342, June 13-16, 2004, Chicago, IL, USA
	Jochen Könemann , Stefano Leonardi , Guido Schäfer, A group-strategyproof mechanism for Steiner forests, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Evangelos Markakis , Amin Saberi, On the core of the multicommodity flow game, Decision Support Systems, v.39 n.1, p.3-10, March 2005
	Nikhil R. Devanur , Milena Mihail , Vijay V. Vazirani, Strategyproof cost-sharing mechanisms for set cover and facility location games, Decision Support Systems, v.39 n.1, p.11-22, March 2005
	Micah Adler , Dan Rubenstein, Pricing multicasting in more flexible network models, ACM Transactions on Algorithms (TALG), v.1 n.1, p.48-73, July 2005
	Luca Becchetti , Jochen Könemann , Stefano Leonardi , M. Pál, Sharing the cost more efficiently: improved approximation for multicommodity rent-or-buy, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Mohammad Taghi Hajiaghayi , Kamal Jain, The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.631-640, January 22-26, 2006, Miami, Florida
	Patrick Briest , Piotr Krysta , Berthold Vöcking, Approximation techniques for utilitarian mechanism design, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Nicole Immorlica , Mohammad Mahdian , Vahab S. Mirrokni, Limitations of cross-monotonic cost sharing schemes, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Ho-Lin Chen , Tim Roughgarden , Gregory Valiant, Designing networks with good equilibria, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.854-863, January 20-22, 2008, San Francisco, California
	Vittorio Bilò , Michele Flammini , Giovanna Melideo , Luca Moscardelli, On Nash equilibria for multicast transmissions in ad-hoc wireless networks, Wireless Networks, v.14 n.2, p.147-157, March 2008
	Chandra Chekuri , Julia Chuzhoy , Liane Lewin-Eytan , Joseph (Seffi) Naor , Ariel Orda, Non-cooperative multicast and facility location games, Proceedings of the 7th ACM conference on Electronic commerce, p.72-81, June 11-15, 2006, Ann Arbor, Michigan, USA
	Tim Roughgarden , Mukund Sundararajan, New trade-offs in cost-sharing mechanisms, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	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
	V. Bilò , M. Flammini , G. Melideo , L. Moscardelli , A. Navarra, Sharing the cost of multicast transmissions in wireless networks, Theoretical Computer Science, v.369 n.1, p.269-284, 15 December 2006
	Anupam Gupta , Amit Kumar , Martin P´al , Tim Roughgarden, Approximation via cost sharing: Simpler and better approximation algorithms for network design, Journal of the ACM (JACM), v.54 n.3, p.11-es, June 2007
	L. Becchetti , J. Könemann , S. Leonardi , M. Páal, Sharing the cost more efficiently: Improved approximation for multicommodity rent-or-buy, ACM Transactions on Algorithms (TALG), v.3 n.2, p.23-es, May 2007
	Aranyak Mehta , Tim Roughgarden , Mukund Sundararajan, Beyond moulin mechanisms, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA
	Angelo Fanelli , Michele Flammini , Luca Moscardelli, On the convergence of multicast games in directed networks, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA
	Susanne Albers, On the value of coordination in network design, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.294-303, January 20-22, 2008, San Francisco, California
	Janina Brenner , Guido Schäfer, Group-strategyproof cost sharing mechanisms for makespan and other scheduling problems, Theoretical Computer Science, v.401 n.1-3, p.96-106, July, 2008
	Nicole Immorlica , Mohammad Mahdian , Vahab S. Mirrokni, Limitations of cross-monotonic cost-sharing schemes, ACM Transactions on Algorithms (TALG), v.4 n.2, p.1-25, May 2008
	A. Gupta , J. Könemann , S. Leonardi , R. Ravi , G. Schäfer, An efficient cost-sharing mechanism for the prize-collecting Steiner forest problem, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1153-1162, January 07-09, 2007, New Orleans, Louisiana
	Jing Chen , Silvio Micali, A new approach to auctions and resilient mechanism design, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	Yvonne Bleischwitz , Burkhard Monien, Fair cost-sharing methods for scheduling jobs on parallel machines, Journal of Discrete Algorithms, v.7 n.3, p.280-290, September, 2009
	Tim Roughgarden , Mukund Sundararajan, Quantifying inefficiency in cost-sharing mechanisms, Journal of the ACM (JACM), v.56 n.4, p.1-33, June 2009