On approximating optimal auctions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On approximating optimal auctions

Full text

Pdf (196 KB)

Source

Electronic Commerce archive
Proceedings of the 3rd ACM conference on Electronic Commerce table of contents

Tampa, Florida, USA

Pages: 11 - 17

Year of Publication: 2001

ISBN:1-58113-387-1

Author

Amir Ronen

Stanford University, Stanford, CA

Sponsor

SIGEcom: ACM Special Interest Group on Electronic Commerce

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 34, Citation Count: 9

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

ABSTRACT

We study the following problem: A seller wishes to sell an item to a group of self-interested agents. Each agent i has a privately known valuation vⁱ for the object. Given a distribution on these valuations, our goal is to construct an auction that maximizes the seller's expected revenue (optimal auction). The auction must be incentive compatible and satisfy individual rationality. We present a simple generic auction that guarantees at least half of the optimal revenue. We generalize this result in several directions, in particular, for the case of multiple copies with unit demand. Our auction requires the ability to learn (or compute) in polynomial time the conditional distribution of the agent with the maximal valuation, given the valuations of the other agents. We show that this ability is in some sense essential. Finally we suggest a generalization of our auction and argue that it will generate a revenue which is close to optimal for reasonable distributions. In particular we show this under an independence assumption

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	Jacques Cremer and McLean Richard.Optimal selling strategies under uncertainty for a discriminating monopolist when demands are nterpendent. Econometrica ,53:345 -61,1985.
	2	A.V.Goldberg,J.D.Hartline,and A.Wright. Competitive auctions for multiple digital goods. Technical report,Technical Report STAR-TR-00.05-02,InterTrust Technologies Corp, 2000.
	3	Andrew V. Goldberg , Jason D. Hartline , Andrew Wright, Competitive auctions and digital goods, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.735-744, January 07-09, 2001, Washington, D.C., United States
	4	O.Goldreich,S.Goldwasser,and S.Michali.How to construct pseudo random functions.In The 25th Symp.on foundations of computer science ,pages 464 -479,1984.
	5	Oded Goldreich.The foundations of cryptography. http://www.wisdom.weizmann.ac.il/oded/focbook.html.
	6	Paul Klemperer.Auction theory:a guide to the literature.Journal of economic surveys ,pages 227 -286,1999.
	7	Paul Klemperer.The economic theory of auctions . Edward Elgar Publishing,2000.
	8	Daniel Lehmann , Liaden Ita O'Callaghan , Yoav Shoham, Truth revelation in approximately efficient combinatorial auctions, Proceedings of the 1st ACM conference on Electronic commerce, p.96-102, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337016]
	9	A.Mas-Collel,Whinston W.,and J.Green. Microeconomic Theory .Oxford university press,1995.
	10	R.B.Myrson.Optimal auction design.Mathematics of operational research ,6:58 -73,1981.
	11	Amir Ronen, Algorithms for Rational Agents, Proceedings of the 27th Conference on Current Trends in Theory and Practice of Informatics, p.56-70, November 25-December 02, 2000
	12	W.Vickrey.Counterspeculation,auctions and competitive sealed tenders.Journal of Finance ,pages 8-37, 1961.

CITED BY 9

	Ziv Bar-Yossef , Kirsten Hildrum , Felix Wu, Incentive-compatible online auctions for digital goods, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.964-970, January 06-08, 2002, San Francisco, California
	Rene Beier , Artur Czumaj , Piotr Krysta , Berthold Vöcking, Computing equilibria for congestion games with (im)perfect information, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Aranyak Mehta , Vijay V. Vazirani, Randomized truthful auctions of digital goods are randomizations over truthful auctions, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA
	Amir Ronen , Daniel Lehmann, Nearly optimal multi attribute auctions, Proceedings of the 6th ACM conference on Electronic commerce, p.279-285, June 05-08, 2005, Vancouver, BC, Canada
	Rene Beier , Artur Czumaj , Piotr Krysta , Berthold Vöcking, Computing equilibria for a service provider game with (Im)perfect information, ACM Transactions on Algorithms (TALG), v.2 n.4, p.679-706, October 2006
	Edith Elkind, Designing and learning optimal finite support auctions, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.736-745, January 07-09, 2007, New Orleans, Louisiana
	Baharak Rastegari , Anne Condon , Kevin Leyton-Brown, Stepwise randomized combinatorial auctions achieve revenue monotonicity, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.738-747, January 04-06, 2009, New York, New York
	Baharak Rastegari , Anne Condon , Kevin Leyton-Brown, Revenue monotonicity in combinatorial auctions, Proceedings of the 22nd national conference on Artificial intelligence, p.122-127, July 22-26, 2007, Vancouver, British Columbia, Canada
	Jason D. Hartline , Tim Roughgarden, Simple versus optimal mechanisms, Proceedings of the tenth ACM conference on Electronic commerce, July 06-10, 2009, Stanford, California, USA