Modified VCG Mechanisms in Combinatorial Auctions with Budget Constraints

Le, Phuong (2014): Modified VCG Mechanisms in Combinatorial Auctions with Budget Constraints.

Abstract

I present two modifications of the Vickrey-Clark-Groves mechanism to accommodate bidders' budget constraints in the combinatorial auction setting and show that they are Pareto-Optimal and (partially) incentive compatible in certain domains.

• Item Type: MPRA Paper
• Language: English
• Keywords: Vickrey-Clark-Groves, Combinatorial Auctions, Budget Constraints, Pareto-Optimal, Mechanism Design
• Subjects: D - Microeconomics > D4 - Market Structure, Pricing, and Design > D44 - Auctions; D - Microeconomics > D4 - Market Structure, Pricing, and Design > D47 - Market Design

References

Ausubel, L.~M. (2004). An efficient ascending-bid auction for multiple objects. American Economic Review, 94(5):1452--1475.

Bhattacharya, S., Conitze, V., Munagala, K., and Xia, L. (2010). Incentive compatible budget elicitation in multi-unit auctions. In Proceedings of the Annual AM-SIAM Symposium on Disrete Algorithms, pages 554--572.

Borgs, C., Chayes, J., Immorlica, N., Mahdian, M., and Saberi, A. (2005). Multi-unit auctions with budget-constrained bidders. EC 05: Proceedings of the 6th ACM conference on Electronic commerce, pages 44--51.

Bulow, J., Levin, J., and Milgrom, P. (2009). Winning play in spectrum auctions. Technical report, National Bureau of Economic Research.

Che, Y.-K. and Gale, I. (1996). Expected revenue of all-pay auctions and first-price sealed-bid auctions with budget constraints. Economic Letters, 50:373--379.

Che, Y.-K. and Gale, I. (2000). The optimal mechanism for selling to a budget-constrained buyer. Journal of Economic Theory, 92:198--2000.

Dobzinski, S., Lavi, R., and Nisan, N. (2008). Multi-unit auctions with budget limits. FOCS.

Fiat, A., Leonardi, S., Saia, J., and Sankowski, P. (2011). Single valued combinatorial auctions with budgets. ACM Conference on Electronic Commerce.

Goel, G., Mirrokni, V., and Leme, R.~P. (2012). Polyhedral clinching auctions and the adwords polytope. In STOC '12 Proceedings of the forty-fourth annual ACM symposium on the Theory of Computing, pages 107--122. ACM New York.

Gul, F. and Stacchetti, E. (2000). The English auction with differentiated commodities. Journal of Economic theory, 92(1):66--95.

Hafalir, I.~E., Ravi, R., and Sayedi, A. (2011). A near Pareto-optimal auction with budget constraints. Games and Economic Behavior, 74:699--708.

Laffront, J.-J. and Robert, J. (1996). Optimal auction with financially constrained buyers. Economic Letters, 52(2):181--186.

Lavi, R. and May, M. (2011). A note on the incompatibility of strategy-proofness and Pareto-optimality in quasi-linear settings with public budgets. In Internet and Network Economics, Lecture Notes in Computer Science, page 417. Springer Berlin Heidelberg.

Lehmann, D., Ocallaghan, L.~I., and Shoham, Y. (2002). Truth revelation in approximately efficient combinatorial auctions. J. ACM}, 49(5):577--602.

Milgrom, P. (2000). Putting auction theory to work: The simultaneous ascending auction. Journal of Political Economy, 108(2):245--272.