A new approach to auctions and resilient mechanism design

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A new approach to auctions and resilient mechanism design

Full text

Pdf (500 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the 41st annual ACM symposium on Theory of computing table of contents

Bethesda, MD, USA

SESSION: Economics table of contents

Pages 503-512

Year of Publication: 2009

ISBN:978-1-60558-506-2

Authors

Jing Chen	CSAIL, MIT, Cambridge, MA, USA
Silvio Micali	CSAIL, MIT, Cambridge, MA, USA

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 46, Downloads (12 Months): 99, Citation Count: 0

Additional Information:

abstract references 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/1536414.1536484 What is a DOI?

ABSTRACT

We put forward a new approach to mechanism design, and exemplify it via a new mechanism guaranteeing significant revenue in unrestricted combinatorial auctions. Our mechanism (1) succeeds in a new and very adversarial collusion model; (2) works in a new, equilibrium-less, and very strong solution concept; (3) benchmarks its performance against the knowledge that the players have about each other; (4) is computationally efficient and preserves the players' privacy to an unusual extent.

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	L.M. Ausubel and P. Milgrom. The Lovely but Lonely Vickrey Auction. Combinatorial Auctions, MIT Press, pp. 17--40, 2006.
	2	Moshe Babaioff , Ron Lavi , Elan Pavlov, Single-value combinatorial auctions and implementation in undominated strategies, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1054-1063, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109674]
	3	M.F. Balcan, A. Blum, and Y. Mansour. Single Price Mechanisms for Revenue Maximization in Unlimited Supply Combinatorial Auctions. CMU-CS-07-111.
	4	E.H. Clarke. Multipart Pricing of Public Goods. Public Choice, Vol.11, No.1, pp. 17--33, Sep., 1971.
	5	J. Cremer and R.P. McLean. Full Extraction of the Surplus in Bayesian and Dominant Strategy Auctions. Econometrica, Vol.56, No.6, pp. 1247--1257, Nov., 1988.
	6	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]
	7	Andrew V. Goldberg , Jason D. Hartline, Collusion-resistant mechanisms for single-parameter agents, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	8	A. Goldberg, J. Hartline, A. Karlin, M. Saks, and A. Wright. Competitive Auctions. Games and Economic Behavior, Vol. 55, Issue 2, pp. 242--269, May, 2006.
	9	T. Groves. Incentives in Teams. Econometrica, Vol. 41, No. 4, pp. 617--631, 1973.
	10	Venkatesan Guruswami , Jason D. Hartline , Anna R. Karlin , David Kempe , Claire Kenyon , Frank McSherry, On profit-maximizing envy-free pricing, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	11	S. Izmalkov, M. Lepinski, and S. Micali. Perfect Implementation of Normal-Form Mechanisms. FOCS 2005, pp. 585--595. Also: MIT-CSAIL-TR-2008-028.
	12	M. Jackson. Implementation in Undominated Strategies: a Look at Bounded Mechanisms. Review of Economic Studies, Vol. 59, No. 201, pp. 757--775, 1992.
	13	Kamal Jain , Vijay Vazirani, Applications of approximation algorithms to cooperative games, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.364-372, July 2001, Hersonissos, Greece [doi>10.1145/380752.380825]
	14	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 [doi>10.1145/585265.585266]
	15	A. Likhodedov and T. Sandholm. Approximating Revenue-Maximizing Combinatorial Auctions. AAAI 2005, pp. 267--274.
	16	S. Micali and P. Valiant. Resilient Mechanisms for Unrestricted Combinatorial Auctions. Available at http://people.csail.mit.edu/silvio/Selected Scientific Papers/Mechanism Design.
	17	H. Moulin and S. Shenker. Strategyproof Sharing of Submodular Costs: Budget Balance Versus Efficiency. Economic Theory, Vol.18, No.3, pp. 511--533, 2001.
	18	W. Vickrey. Counterspeculation, Auctions, and Competitive Sealed Tenders. The Journal of Finance, Vol. 16, No. 1, pages 8--37, Mar., 1961.