Sayan Bhattacharya
ABSTRACT
In this paper, we present the first approximation algorithms for the problem of designing revenue optimal Bayesian incentive compatible auctions when there are multiple (heterogeneous) items and when bidders have arbitrary demand and budget constraints (and additive valuations). Our mechanisms are surprisingly simple: We show that a sequential all-pay mechanism is a 4 approximation to the revenue of the optimal ex-interim truthful mechanism with a discrete type space for each bidder, where her valuations for different items can be correlated. We also show that a sequential posted price mechanism is a O(1) approximation to the revenue of the optimal ex-post truthful mechanism when the type space of each bidder is a product distribution that satisfies the standard hazard rate condition. We further show a logarithmic approximation when the hazard rate condition is removed, and complete the picture by showing that achieving a sub-logarithmic approximation, even for regular distributions and one bidder, requires pricing bundles of items. Our results are based on formulating novel LP relaxations for these problems, and developing generic rounding schemes from first principles.
- Z. Abrams. Revenue maximization when bidders have budgets. In SODA, pages 1074--1082, 2006. Google Scholar
Digital Library
- L. M. Ausubel. An efficient ascending-bid auction for multiple objects. American Economic Review, 94(5):1452--1475, 2004.Google ScholarCross Ref
- L. M. Ausubel and P. Milgrom. Ascending auctions with package bidding. Working Paper, 2002.Google Scholar
- J. Benoit and V. Krishna. Multiple-object auctions with budget constrained bidders. Review of Economic Studies, 68:155--179, 2001.Google ScholarCross Ref
- S. Bhattacharya, V. Conitzer, K. Munagala, and L. Xia. Incentive compatible budget elicitation in multi-unit auctions. In SODA, 2010. Google ScholarDigital Library
- K. C. Border. Reduced form auctions revisited. Economic Theory, 31(1):167--181, 2007.Google ScholarCross Ref
- C. Borgs, J. T. Chayes, N. Immorlica, M. Mahdian, and A. Saberi. Multi-unit auctions with budget-constrained bidders. In ACM Conference on Electronic Commerce, pages 44---51, 2005. Google ScholarDigital Library
- P. Briest. Uniform budgets and the envy-free pricing problem. In ICALP(1), pages 808--819, 2008. Google ScholarDigital Library
- P. Briest, S. Chawla, R. D. Kleinberg, and S. M. Weinberg. Pricing randomized allocations. In SODA, 2010. Google ScholarDigital Library
- S. Brusco and G. Lopomo. Simultaneous ascending bid auctions with privately known budget constraints. Journal of Industrial Economics, 56(1):113--142, 2008.Google ScholarCross Ref
- S. Chawla, J. D. Hartline, and R. D. Kleinberg. Algorithmic pricing via virtual valuations. In ACM Conference on Electronic Commerce, pages 243--251, 2007. Google ScholarDigital Library
- S. Chawla, J. D. Hartline, D. Malec, and B. Sivan. Sequential posted pricing and multi-parameter mechanism design. In STOC, 2010. Google ScholarDigital Library
- Y. Che and J. Gale. Expected revenue of the all-pay auctions and first-price sealed bid auctions with budget constraints. Economic Letters, 50:373--380, 1996.Google ScholarCross Ref
- Y. Che and J. Gale. The optimal mechanism for selling to a budget constrained buyer. Journal of Economic Theory, 92(2):198--233, 2000.Google ScholarCross Ref
- N. Chen, N. Immorlica, A. R. Karlin, M. Mahdian, and A. Rudra. Approximating matches made in heaven. In ICALP(1), pages 266--278, 2009. Google ScholarDigital Library
- S. Dobzinski, R. Lavi, and N. Nisan. Multi-unit auctions with budget limits. In FOCS, pages 260--269, 2008. Google ScholarDigital Library
- E. Elkind and S. S. Fatima. Maximizing revenue in sequential auctions. In WINE, pages 491--502, 2007. Google ScholarDigital Library
- A. V. Goldberg, J. D. Hartline, and A. Wright. Competitive auctions and digital goods. In SODA, pages 735--744, 2001. Google ScholarDigital Library
- V. Guruswami, J. D. Hartline, A. R. Karlin, D. Kempe, C. Kenyon, and F. McSherry. On profit-maximizing envy-free pricing. In SODA, pages 1164--1173, 2005. Google ScholarDigital Library
- I. Hafalir, R. Ravi, and A. Sayedi. Sort-cut: Apareto optimal and semi-truthful mechanism for multi-unit auctions with budget-constrained bidders. CoRR, abs/0903.1450, 2009.Google Scholar
- J. D. Hartline and T. Roughgarden. Simple versus optimal mechanisms. In ACM Conference on Electronic Commerce, pages 225--234, 2009. Google ScholarDigital Library
- J.-J. Lafont and J. Robert. Optimal auction with financially constrained buyers. Economic Letters, 52(2):181--186, 1996.Google ScholarCross Ref
- A. M. Manellia and D. R. Vincent. Multidimensional mechanism design: Revenue maximization and the multiple-good monopoly. Journal of Economic Theory, 137(1):153--185, 2007.Google ScholarCross Ref
- R. B. Myerson. Optimal auction design. Mathematics of Operations Research, 6(1):58--73, 1981.Google ScholarDigital Library
- N. Nisan. Google's auction for tv ads. In ESA, page 553, 2009.Google Scholar
- M. Pai and R. Vohra. Optimal auctions with financially constrained bidders. Working Paper, 2008.Google Scholar
- J. Thanassoulis. Haggling over substitutes. Journal of Economic Theory, 117(2):217--245, 2004.Google ScholarCross Ref
- R. B. Wilson. Nonlinear Pricing. Oxford University Press, 1997.Google Scholar
Index Terms
- Budget constrained auctions with heterogeneous items
Recommendations
Multi-unit auctions with budget-constrained bidders
EC '05: Proceedings of the 6th ACM conference on Electronic commerceWe study a multi-unit auction with multiple bidders, each of whom has a private valuation and a budget. The truthful mechanisms of such an auction are characterized, in the sense that, under standard assumptions, we prove that it is impossible to design ...
Auctions for Heterogeneous Items and Budget Limits
We study individual rational, Pareto-optimal, and incentive compatible mechanisms for auctions with heterogeneous items and budget limits. We consider settings with multiunit demand and additive valuations. For single-dimensional valuations we prove a ...
Incentive compatible budget elicitation in multi-unit auctions
SODA '10: Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithmsIn this paper, we consider the problem of designing incentive compatible auctions for multiple (homogeneous) units of a good, when bidders have private valuations and private budget constraints. When only the valuations are private and the budgets are ...
Comments