Revenue Submodularity

by Shaddin Dughmi, Tim Roughgarden, and Mukund Sundararajan

Theory of Computing, Volume 8(5), pp. 95-119, 2012

Bibliography with links to cited articles

[1]   Gagan Aggarwal, Ashish Goel, and Rajeev Motwani: Truthful auctions for pricing search keywords. In Proc. 7th ACM Conf. on Electronic Commerce, pp. 1–7. ACM Press, 2006. [doi:10.1145/1134707.1134708]

[2]   Lawrence M. Ausubel and Paul R. Milgrom: Ascending auctions with package bidding. Frontiers of Theoretical Economics, 1(1), 2002. Article 1.

[3]   Moshe Babaioff, Nicole Immorlica, and Robert D. Kleinberg: Matroids, secretary problems, and online mechanisms. In Proc. 18th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’07), pp. 434–443. ACM Press, 2007. [ACM DL] .

[4]   Sushil Bikhchandani, Sven de Vries, James Schummer, and Rakesh V. Vohra: Ascending auctions for integral (poly)matroids with concave nondecreasing separable values. In Proc. 19th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’08), pp. 864–873. ACM Press, 2008. [ACM DL] .

[5]   Jeremy Bulow and Paul Klemperer: Auctions versus negotiations. American Economic Review, 86(1):180–94, March 1996.

[6]   Matthew C. Cary, Abraham D. Flaxman, Jason D. Hartline, and Anna R. Karlin: Auctions for structured procurement. In Proc. 19th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’08), pp. 304–313. ACM Press, 2008. [ACM DL] .

[7]   Florin Constantin, Jon Feldman, S. Muthu Muthukrishnan, and Martin Pál: An online mechanism for ad slot reservations with cancellations. In Proc. 20th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’09), pp. 1265–1274. ACM Press, 2009. [SODA PDF] .

[8]   Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz: Internet advertising and the generalized second price auction: Selling billions of dollars worth of keywords. American Economic Review, 97(1):242–259, 2007. [doi:10.1257/aer.97.1.242]

[9]   Benjamin Edelman and Michael Schwarz: Optimal auction design and equilibrium selection in sponsored search auctions. American Economic Review, 100(2):597–602, 2010. [doi:10.1257/aer.100.2.597]

[10]   Uri Feige, Vahab S. Mirrokni, and Jan Vondrák: Maximizing non-monotone submodular functions. SIAM J. Comput., 40(4):1133–1153, 2011. [doi:10.1137/090779346]

[11]   Michael R. Garey and David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, 1979.

[12]   Pranava R. Goundan and Andreas S. Schulz: Revisiting the greedy approach to submodular set function maximization. Preprint, 2009.

[13]   Jason D. Hartline: Lectures on frugal mechanism design. EECS 510 Lecture Notes. http://users.eecs.northwestern.edu/~hartline/frugality.ps, 2008.

[14]   Jason D. Hartline: Approximation in Economic Design. 2011. Book in preparation. http://www.eecs.northwestern.edu/hartline.

[15]   Jason D. Hartline and Tim Roughgarden: Simple versus optimal mechanisms. In Proc. 10th ACM Conf. on Electronic Commerce, pp. 225–234, 2009. [doi:10.1145/1566374.1566407]

[16]   Anna R. Karlin, David Kempe, and Tami Tamir: Beyond VCG: Frugality of truthful mechanisms. In Proc. 46th FOCS, pp. 615–626. IEEE Comp. Soc. Press, 2005. [doi:10.1109/SFCS.2005.25]

[17]   René Kirkegaard: A short proof of the Bulow-Klemperer auctions vs.  negotiations result. Economic Theory, 28(2):449–452, 2006. [doi:10.1007/s00199-004-0593-2]

[18]   Dexter C. Kozen: The Design and Analysis of Algorithms. Springer-Verlag, New York, 1991.

[19]   Nicolas S. Lambert and Yoav Shoham: Asymptotically optimal repeated auctions for sponsored search. In Proc. 8th ACM Conf. on Electronic Commerce, pp. 55–64, 2007. [doi:10.1145/1282100.1282112]

[20]   Paul R. Milgrom: Putting Auction Theory to Work. Cambridge University Press, 2004. http://econpapers.repec.org/RePEc:cup:cbooks:9780521536721.

[21]   Roger B. Myerson: Optimal auction design. Math. Oper. Res., 6(1):58–73, 1981. [doi:10.1287/moor.6.1.58]

[22]   Zvika Neeman: The effectiveness of English auctions. Games and Economic Behavior, 43(2):214–238, 2003. [doi:10.1016/S0899-8256(03)00005-8]

[23]   G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher: An analysis of approximations for maximizing submodular set functions – I. Math. Program., 14(3):265–294, 1978. [doi:10.1007/BF01588971]

[24]   James Oxley: Matroid Theory. Oxford, 1992.

[25]   Baharak Rastegari, Anne Condon, and Kevin Leyton-Brown: Revenue monotonicity in combinatorial auctions. SIGecom Exchanges, 7(1):45–47, 2007. [doi:10.1145/1345037.1345048]

[26]   Kunal Talwar: The price of truth: Frugality in truthful mechanisms. In Proc. 20th Symp. Theoretical Aspects of Comp. Sci. (STACS’03), volume 2607 of LNCS, pp. 608–619. Springer, 2003.

[27]   Alexander Vardy: The intractability of computing the minimum distance of a code. IEEE Trans. Inform. Theory, 43(6):1757–1766, 1997. [doi:10.1109/18.641542]

[28]   Hal R. Varian: Position auctions. Internat. J. of Industrial Organization, 25(6):1163–1178, 2007. [doi:10.1016/j.ijindorg.2006.10.002]

[29]   Jan Vondrák: Optimal approximation for the submodular welfare problem in the value oracle model. In Proc. 40th STOC, pp. 67–74. ACM Press, 2008. [doi:10.1145/1374376.1374389]

[30]   D. J. A. Welsh: Matroid Theory. Academic Press, 1976.