Mechanisms for Combinatorial Auctions with Budget Constraints

Le, Phuong (2015): Mechanisms for Combinatorial Auctions with Budget Constraints.

Abstract

This paper studies combinatorial auctions with budget-constrained bidders from a mechanism design perspective. I search for mechanisms that are incentive compatible, individually rational, symmetric, non-wasteful and non-bossy. First focusing on the greedy domain, in which any increase in a bidder's valuation always exceeds his budget, I derive the unique mechanism, called the Iterative Second Price Auction. For the general domain, however, no such mechanism exists.

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

References

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

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

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

Bulow J, Levin J, Milgrom P (2009) Winning play in spectrum auctions. NBER Working Paper

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

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

Day R, Milgrom P (2008) Core-selecting package auctions. International Journal of Game Theory 36:393--440

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

Dughmi S, Vondrak J (2011) Limitations of randomized mechanisms for combinatorial auctions. FOCS pp 502--511

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

Gagan~Goel RPL Vahab~Mirrokni (2012) Polyhedral clinching auctions and the adwords polytope. In: STOC '12 Proceedings of the forty-fourth annual ACM symposium on the Theory of Computing, ACM New York, pp 107-122

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

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

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

Nisan N, Ronen A (2007) Computationally feasible vcg mechanisms. Journal of Artificial Intelligence Research 29:19--47

R~Lavi MM (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, Springer Berlin Heidelberg, p 417

Satterthwaite MA, Sonnenschein H (1981) Strategy-proof allocation mechanisms at differentiable points. The Review of Economic Studies 48(4):587--597

Segal I, Milgrom P (2014) Deferred acceptance auctions and radio spectrum reallocation, mimeo