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
Index Terms
- Single valued combinatorial auctions with budgets
Recommendations
Truthful randomized mechanisms for combinatorial auctions
We present a new framework for the design of computationally-efficient and incentive-compatible mechanisms for combinatorial auctions. The mechanisms obtained via this framework are randomized, and obtain incentive compatibility in the universal sense (...
Bayesian Combinatorial Auctions
We study the following simple Bayesian auction setting: m items are sold to n selfish bidders in m independent second-price auctions. Each bidder has a private valuation function that specifies his or her complex preferences over all subsets of items. ...
Revenue monotonicity in deterministic, dominant-strategy combinatorial auctions
In combinatorial auctions using VCG, a seller can sometimes increase revenue by dropping bidders. In this paper we investigate the extent to which this counterintuitive phenomenon can also occur under other deterministic, dominant-strategy combinatorial ...
Comments