Amos Fiat
Stefano Leonardi
Jared Saia
ABSTRACT
We consider budget constrained combinatorial auctions where each bidder has a private value for each of the items in some subset of the items and an overall budget constraint. Such auctions capture adword auctions, where advertisers offer a bid for those adwords that (hopefully) target their intended audience, and advertisers also have budgets. It is known that even if all items are identical and all budgets are public it is not possible to be truthful and efficient. Our main result is a novel auction that runs in polynomial time, is incentive compatible, and ensures Pareto-optimality. The auction is incentive compatible with respect to the private valuations whereas the budgets and the sets of interest are assumed to be public knowledge. This extends the result of Dobzinski, Lavi and Nisan (FOCS 2008) for auctions of multiple identical items with bugets to single-valued combinatorial auctions and address one of the basic challenges on auctioning web ads (see Nisan et al, 2009, Google auctions for tv ads).
- G. Aggarwal, S. Muthukrishnan, D. Pál, and M. Pál. General auction mechanism for search advertising. In WWW '09: Proceedings of the 18th international conference on World wide web, pages 241--250, New York, NY, USA, 2009. ACM. Google Scholar
Digital Library
- I. Ashlagi, M. Braverman, A. Hassidim, R. Lavi, and M. Tennenholtz. Position auctions with budgets: Existence and uniqueness, 2009.Google Scholar
- L. M. Ausubel. An efficient ascending-bid auction for multiple objects. American Economic Review, 94(5):1452--1475, December 2004.Google ScholarCross Ref
- L. M. Ausubel and P. R. Milgrom. Ascending auctions with package bidding. Frontiers of Theoretical Economics, 1:1019--1019, 2002.Google ScholarCross Ref
- S. Bhattacharya, V. Conitzer, K. Munagala, and L. Xia. Incentive compatible budget elicitation in multi-unit auctions. CoRR, abs/0904.3501, 2009.Google Scholar
- S. Bhattacharya, G. Goel, S. Gollapudi, and K. Munagala. Budget constrained auctions with heterogeneous items. In STOC '10: Proceedings of the 42nd ACM symposium on Theory of computing, pages 379--388, New York, NY, USA, 2010. ACM. Google ScholarDigital Library
- S. Dobzinski, R. Lavi, and N. Nisan. Multi-unit auctions with budget limits. In FOCS, pages 260--269. IEEE Computer Society, 2008. Google ScholarDigital Library
- S. Dobzinski, R. Lavi, and N. Nisan. Multi-unit auctions with budget limits, 2010.Google Scholar
- B. Edelman, M. Ostrovsky, M. Schwarz. Internet advertising and the generalized second price auction: Selling billions of dollars worth of keywords. American Economic Review, 97, 2005.Google Scholar
- J. Hatfield and P. Milgrom. Matching with contracts. The American Economic Review, 95(4):913--935, 2005.Google ScholarCross Ref
- P. Milgrom. Putting auction theory to work. Cambridge University Press, 2004.Google Scholar
- P. Milgrom. Putting auction theory to work: The simultaneous ascending auction. Journal of Political Economy, 108:245--272, 1998.Google ScholarCross Ref
- N. Nisan, J. Bayer, D. Chandra, Tal Franji, Robert Gardner, Yossi Matias, Neil Rhodes, Misha Seltzer, Danny Tom, Hal R. Varian, and Dan Zigmond. Google's auction for tv ads. In S. Albers, A. Marchetti-Spaccamela, Y. Matias, S. E. Nikoletseas, and W. Thomas, editors, ICALP (2), volume 5556 of Lecture Notes in Computer Science, pages 309--327. Springer, 2009. Google ScholarDigital Library
- W. Pulleyblank. Dual integrality in b-matching problems. In R. W. et. al. Cottle, editor, Combinatorial Optimization, volume 12 of Mathematical Programming Studies, pages 176--196. Springer Berlin Heidelberg, 1980.Google Scholar
- W. Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of Finance, 16(1):8--37, 1961.Google ScholarCross Ref
Recommendations
Polyhedral Clinching Auctions and the AdWords Polytope
A central issue in applying auction theory in practice is the problem of dealing with budget-constrained agents. A desirable goal in practice is to design incentive compatible, individually rational, and Pareto optimal auctions while respecting the ...
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 ...
Approximately Efficient Two-Sided Combinatorial Auctions
Special Issue on EC'17We develop and extend a line of recent work on the design of mechanisms for two-sided markets. The markets we consider consist of buyers and sellers of a number of items, and the aim of a mechanism is to improve the social welfare by arranging purchases ...
Comments