Revenue submodularity

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Revenue submodularity

Full text

Pdf (433 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 243-252

Year of Publication: 2009

ISBN:978-1-60558-458-4

Authors

Shaddin Dughmi	Stanford University, Stanford, CA, USA
Tim Roughgarden	Stanford University, Stanford, CA, USA
Mukund Sundararajan	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): 10, Downloads (12 Months): 33, 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/1566374.1566409 What is a DOI?

ABSTRACT

We introduce revenue submodularity, the property that market expansion has diminishing returns on an auction's expected revenue. We prove that revenue submodularity is generally possible only in matroid markets, that Bayesian-optimal auctions are always revenue-submodular in such markets, and that the VCG mechanism is revenue-submodular in matroid markets with i.i.d bidders and "sufficient competition". We also give two applications of revenue submodularity: good approximation algorithms for novel market expansion problems, and approximate revenue guarantees for the VCG mechanism with i.i.d bidders.

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	Gagan Aggarwal , Ashish Goel , Rajeev Motwani, Truthful auctions for pricing search keywords, Proceedings of the 7th ACM conference on Electronic commerce, p.1-7, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134708]
	2	Moshe Babaioff , Nicole Immorlica , Robert Kleinberg, Matroids, secretary problems, and online mechanisms, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.434-443, January 07-09, 2007, New Orleans, Louisiana
	3	Sushil Bikhchandani , Sven de Vries , James Schummer , Rakesh V. Vohra, Ascending auctions for integral (poly)matroids with concave nondecreasing separable values, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.864-873, January 20-22, 2008, San Francisco, California
	4	J. Bulow and P. Klemperer. Auctions versus negotiations. American Economic Review, 86(1):180--194, 1996.
	5	Gruia Calinescu , Chandra Chekuri , Martin Pál , Jan Vondrák, Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract), Proceedings of the 12th international conference on Integer Programming and Combinatorial Optimization, June 25-27, 2007, Ithaca, NY, USA [doi>10.1007/978-3-540-72792-7_15]
	6	Matthew C. Cary , Abraham D. Flaxman , Jason D. Hartline , Anna R. Karlin, Auctions for structured procurement, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.304-313, January 20-22, 2008, San Francisco, California
	7	Florin Constantin , Jon Feldman , S. Muthukrishnan , Martin Pál, An online mechanism for ad slot reservations with cancellations, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.1265-1274, January 04-06, 2009, New York, New York
	8	B. Edelman, M. Ostrovsky, and M. Schwarz. Internet advertising and the generalized second price auction: Selling billions of dollars worth of keywords. American Economic Review, 97(1):242--259, 2007.
	9	B. Edelman and M. Schwarz. Optimal auction design in a multi-unit environment: The case of sponsored search auctions. Unpublished manuscript, 2006.
	10	Uriel Feige , Vahab S. Mirrokni , Jan Vondrak, Maximizing Non-Monotone Submodular Functions, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.461-471, October 21-23, 2007 [doi>10.1109/FOCS.2007.40]
	11	P.R. Goundan and A.S. Schulz. Revisiting the greedy approach to submodular set function maximization. Preprint, 2009.
	12	J.D. Hartline and T. Roughgarden. Simple versus optimal auctions. In these proceedings.
	13	Dexter C. Kozen, The design and analysis of algorithms, Springer-Verlag New York, Inc., New York, NY, 1992
	14	Nicolas S. Lambert , Yoav Shoham, Asymptotically optimal repeated auctions for sponsored search, Proceedings of the ninth international conference on Electronic commerce, August 19-22, 2007, Minneapolis, MN, USA [doi>10.1145/1282100.1282112]
	15	P. Milgrom. Putting Auction Theory to Work. Cambridge, 2004.
	16	R. Myerson. Optimal auction design. Mathematics of Operations Research, 6(1):58--73, 1981.
	17	Z. Neeman. The effectiveness of English auctions. Games and Economic Behavior, 43(2):214--238, 2003.
	18	G.L. Nemhauser, L.A. Wolsey, and M.L. Fisher. An analysis of approximations for maximizing submodular set functions -- I. Mathematical Programming, 14(3):265--294, 1978.
	19	J.G. Oxley. Matroid Theory. Oxford, 1992.
	20	Baharak Rastegari , Anne Condon , Kevin Leyton-Brown, Revenue monotonicity in combinatorial auctions, ACM SIGecom Exchanges, v.7 n.1, p.45-47, December 2007 [doi>10.1145/1345037.1345048]
	21	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
	22	A. Vardy. The intractability of computing the minimum distance of a code. IEEE Transactions on Information Theory, 43(6):1757--1766, 1997.
	23	H. Varian. Position auctions. International Journal of Industrial Organization, 25(6):1163--1178, 2007.
	24	D.J. Welsh. Matroid Theory. Academic Press, 1976.