Simple versus optimal mechanisms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Simple versus optimal mechanisms

Full text

Pdf (464 KB)

Source

Electronic Commerce archive
Proceedings of the tenth ACM conference on Electronic commerce table of contents

Stanford, California, USA

SESSION: Session 7 table of contents

Pages 225-234

Year of Publication: 2009

ISBN:978-1-60558-458-4

Authors

Jason D. Hartline	Northwestern University, Evanston, IL, USA
Tim Roughgarden	Stanford University, Stanford, CA, USA

Sponsors

ACM: Association for Computing Machinery
SIGEcom: ACM Special Interest Group on Electronic Commerce

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 37, 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/1566374.1566407 What is a DOI?

ABSTRACT

The monopolist's theory of optimal single-item auctions for agents with independent private values can be summarized by two statements. The first is from Myerson [8]: the optimal auction is Vickrey with a reserve price. The second is from Bulow and Klemperer [1]: it is better to recruit one more bidder and run the Vickrey auction than to run the optimal auction. These results hold for single-item auctions under the assumption that the agents' valuations are independently and identically drawn from a distribution that satisfies a natural (and prevalent) regularity condition.

These fundamental guarantees for the Vickrey auction fail to hold in general single-parameter agent mechanism design problems. We give precise (and weak) conditions under which approximate analogs of these two results hold, thereby demonstrating that simple mechanisms remain almost optimal in quite general single-parameter agent settings.

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	J. Bulow and P. Klemperer. Auctions versus negotiations. American Economic Review, 86(1):180--194, 1996.
	2	Shuchi Chawla , Jason D. Hartline , Robert Kleinberg, Algorithmic pricing via virtual valuations, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA [doi>10.1145/1250910.1250946]
	3	R. Day and P. Milgrom. Core-selecting auctions. International Journal of Game Theory, 36(3-4):393--407, 2008.
	4	S. Dughmi, T. Roughgarden, and M. Sundararajan. Revenue submodularity. In these proceedings.
	5	A.V. Goldberg, J.D. Hartline, A. Karlin, M. Saks, and A. Wright. Competitive auctions. Games and Economic Behavior, 55(2):242--269, 2006.
	6	Jason D. Hartline , Tim Roughgarden, Optimal mechanism design and money burning, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374390]
	7	Anna R. Karlin , David Kempe , Tami Tamir, Beyond VCG: Frugality of Truthful Mechanisms, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.615-626, October 23-25, 2005 [doi>10.1109/SFCS.2005.25]
	8	R. Myerson. Optimal auction design. Mathematics of Operations Research, 6(1):58--73, 1981.
	9	Z. Neeman. The effectiveness of English auctions. Games and Economic Behavior, 43(2):214--238, 2003.
	10	Amir Ronen, On approximating optimal auctions, Proceedings of the 3rd ACM conference on Electronic Commerce, p.11-17, October 14-17, 2001, Tampa, Florida, USA [doi>10.1145/501158.501160]
	11	A. Schrijver. Combinatorial Optimziation: Polyhedra and Efficiency. Springer, 2003.
	12	Kunal Talwar, The Price of Truth: Frugality in Truthful Mechanisms, Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, p.608-619, February 27-March 01, 2003