Budget-Constrained Auctions with Heterogeneous Items

by Sayan Bhattacharya, Gagan Goel, Sreenivas Gollapudi, and Kamesh Munagala

Theory of Computing, Volume 8(20), pp. 429-460, 2012

Bibliography with links to cited articles

[1]   Zoë Abrams: Revenue maximization when bidders have budgets. In Proc. 17th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’06), pp. 1074–1082. ACM Press, 2006. [doi:10.1145/1109557.1109676]

[2]   Aaron Archer, Christos Papadimitriou, Kunal Talwar, and Éva Tardos: An approximate truthful mechanism for combinatorial auctions with single parameter agents. Internet Mathematics, 1(2):129–150, 2004. Preliminary version in SODA’03. [doi:10.1080/15427951.2004.10129086]

[3]   Lawrence M. Ausubel: An efficient ascending-bid auction for multiple objects. American Economic Review, 94(5):1452 – 1475, 2004. [doi:10.1257/0002828043052330]

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

[5]   Jean-Pierre Benoît and Vijay Krishna: Multiple-object auctions with budget constrained bidders. Review of Economic Studies, 68(1):155 – 179, 2001. [doi:10.1111/1467-937X.00164]

[6]   Sayan Bhattacharya, Vincent Conitzer, Kamesh Munagala, and Lirong Xia: Incentive compatible budget elicitation in multi-unit auctions. In Proc. 21st Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’10), pp. 554–572. ACM Press, 2010. [ACM:1873648]

[7]   Kim C. Border: Reduced form auctions revisited. Economic Theory, 31(1):167–181, 2007. [doi:10.1007/s00199-006-0080-z]

[8]   Christian Borgs, Jennifer Chayes, Nicole Immorlica, Mohammad Mahdian, and Amin Saberi: Multi-unit auctions with budget-constrained bidders. In Proc. 6th ACM Conf. Electronic Commerce (ACM-EC’05), pp. 44–51. ACM Press, 2005. [doi:10.1145/1064009.1064014]

[9]   Patrick Briest: Uniform budgets and the envy-free pricing problem. In Proc. 35th Internat. Colloq. on Automata, Languages and Programming (ICALP’08), pp. 808–819. Springer, 2008. [doi:10.1007/978-3-540-70575-8_66]

[10]   Patrick Briest, Shuchi Chawla, Robert Kleinberg, and S. Matthew Weinberg: Pricing randomized allocations. In Proc. 21st Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’10), pp. 585–597. ACM Press, 2010. [ACM:1873601.1873650]

[11]   Sandro Brusco and Giuseppe Lopomo: Budget constraints and demand reduction in simultaneous ascending-bid auctions. Journal of Industrial Economics, 56(1):113–142, 2008. [doi:10.1111/j.1467-6451.2008.00335.x]

[12]   Shuchi Chawla, Jason D. Hartline, and Robert Kleinberg: Algorithmic pricing via virtual valuations. In Proc. 8th ACM Conf. Electronic Commerce (ACM-EC’07), pp. 243–251. ACM Press, 2007. [doi:10.1145/1250910.1250946]

[13]   Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan: Multi-parameter mechanism design and sequential posted pricing. In Proc. 42nd STOC, pp. 311–320. ACM Press, 2010. [doi:10.1145/1806689.1806733]

[14]   Yeon-Koo Che and Ian Gale: Expected revenue of all-pay auctions and first-price sealed-bid auctions with budget constraints. Economics Letters, 50:373–379, 1996. [doi:10.1016/0165-1765(95)00766-0]

[15]   Yeon-Koo Che and Ian Gale: The optimal mechanism for selling to a budget-constrained buyer. J. Economic Theory, 92(2):198–233, 2000. [doi:10.1006/jeth.1999.2639]

[16]   Ning Chen, Nicole Immorlica, Anna R. Karlin, Mohammad Mahdian, and Atri Rudra: Approximating matches made in heaven. In Proc. 36th Internat. Colloq. on Automata, Languages and Programming (ICALP’09), pp. 266–278. Springer, 2009. [doi:10.1007/978-3-642-02927-1_23]

[17]   Edward H. Clarke: Multipart pricing of public goods. Public Choice, 11(1):17–33, 1971. [doi:10.1007/BF01726210]

[18]   Shahar Dobzinski, Ron Lavi, and Noam Nisan: Multi-unit auctions with budget limits. Games and Economic Behavior, 74(2):486–503, 2012. Preliminary version in FOCS’08. [doi:10.1016/j.geb.2011.08.003]

[19]   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]

[20]   Edith Elkind and Shaheen Fatima: Maximizing revenue in sequential auctions. In Proc. 3rd Internat. Workshop on Internet and Network Economics (WINE’07), pp. 491–502. Springer, 2007. [doi:10.1007/978-3-540-77105-0_53]

[21]   Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, Michael Saks, and Andrew Wright: Competitive auctions. Games and Economic Behavior, 55(2):242–269, 2006. [doi:10.1016/j.geb.2006.02.003]

[22]   Andrew V. Goldberg, Jason D. Hartline, and Andrew Wright: Competitive auctions and digital goods. In Proc. 12th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’01), pp. 735–744. ACM Press, 2001. [ACM:365411.365768]

[23]   Theodore Groves: Incentives in teams. Econometrica, 41(4):617–631, 1973. JSTOR.

[24]   Venkatesan Guruswami, Jason D. Hartline, Anna R. Karlin, David Kempe, Claire Kenyon, and Frank McSherry: On profit-maximizing envy-free pricing. In Proc. 16th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’05), pp. 1164–1173. ACM Press, 2005. [ACM:1070432.1070598]

[25]   Isa Emin Hafalir, R. Ravi, and Amin Sayedi: Sort-cut: A pareto optimal and semi-truthful mechanism for multi-unit auctions with budget-constrained bidders. Technical report, 2009. [arXiv:0903.1450v1]

[26]   Jason D. Hartline and Tim Roughgarden: Simple versus optimal mechanisms. In Proc. 10th ACM Conf. on Electronic Commerce (ACM-EC’09), pp. 225–234. ACM Press, 2009. [doi:10.1145/1566374.1566407]

[27]   Jean-Jacques Laffont and Jacques Robert: Optimal auction with financially constrained buyers. Economics Letters, 52(2):181–186, 1996. [doi:10.1016/S0165-1765(96)00849-X]

[28]   Ron Lavi and Chaitanya Swamy: Truthful and near-optimal mechanism design via linear programming. J. ACM, 58(6/25):1–24, 2011. Preliminary version in FOCS’05. [doi:10.1145/2049697.2049699]

[29]   Alejandro M. Manellia and Daniel R. Vincent: Multidimensional mechanism design: Revenue maximization and the multiple-good monopoly. J. Economic Theory, 137(1):153–185, 2007. [doi:10.1016/j.jet.2006.12.007]

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

[31]   Noam Nisan, Jason Bayer, Deepak Chandra, Tal Franji, Robert Gardner, Yossi Matias, Neil Rhodes, Misha Seltzer, Danny Tom, Hal Varian, and Dan Zigmond: Google’s auction for TV ads. In Proc. 36th Internat. Colloq. on Automata, Languages and Programming (ICALP’09), pp. 309–327. Springer, 2009. See also ESA’09 and SODA’10. [doi:10.1007/978-3-642-02930-1_26]

[32]   Mallesh M. Pai and Rakesh Vohra: Optimal auctions with financially constrained bidders. Working Paper, 2008. CiteSeerX.

[33]   John Thanassoulis: Haggling over substitutes. J. Economic Theory, 117(2):217–245, 2004. [doi:10.1016/j.jet.2003.09.002]

[34]   William Vickrey: Counterspeculation, auctions and competitive sealed tenders. J. Finance, 16(1):8–37, 1961. [doi:10.1111/j.1540-6261.1961.tb02789.x]

[35]   Robert B. Wilson: Nonlinear Pricing. Oxford University Press, 1997.