Gagan Goel
Skip Abstract Section
Abstract
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 budget constraints. Achieving this goal is particularly challenging in the presence of nontrivial combinatorial constraints over the set of feasible allocations.
Toward this goal and motivated by AdWords auctions, we present an auction for polymatroidal environments satisfying these properties. Our auction employs a novel clinching technique with a clean geometric description and only needs an oracle access to the submodular function defining the polymatroid. As a result, this auction not only simplifies and generalizes all previous results, it applies to several new applications including AdWords Auctions, bandwidth markets, and video on demand. In particular, our characterization of the AdWords auction as polymatroidal constraints might be of independent interest. This allows us to design the first mechanism for Ad Auctions taking into account simultaneously budgets, multiple keywords and multiple slots.
We show that it is impossible to extend this result to generic polyhedral constraints. This also implies an impossibility result for multiunit auctions with decreasing marginal utilities in the presence of budget constraints.
- Zoë Abrams. 2006. Revenue maximization when bidders have budgets. In Proceedings of SODA. 1074--1082. Google Scholar
Digital Library
- Gagan Aggarwal, S. Muthukrishnan, Dávid Pál, and Martin Pál. 2009. General auction mechanism for search advertising. In Proceedings of WWW. 241--250. Google ScholarDigital Library
- Saeed Alaei, Kamal Jain, and Azarakhsh Malekian. 2010. Walrasian equilibrium for unit demand buyers with non-quasi-linear utilities. CoRR abs/1006.4696.Google Scholar
- Aaron Archer and Éva Tardos. 2001. Truthful mechanisms for one-parameter agents. In Proceedings of FOCS. 482--491. Google ScholarDigital Library
- Itai Ashlagi, Mark Braverman, Avinatan Hassidim, Ron Lavi, and Moshe Tennenholt. 2010. Position auctions with budgets: Existence and uniqueness. B.E. J. Theoret. Econ. Adv. 10, 1, DOI:10.2202/1935-1704/648.Google Scholar
- Lawrence M. Ausubel. 1997. An efficient ascending-bid auction for multiple objects. Amer. Econ. Rev. 94.Google Scholar
- Jean-Pierre Benoit and Vijay Krishna. 2001. Multiple-object auctions with budget constrained bidders. Rev. Econ. Stud. 68, 1, 155--179.Google ScholarCross Ref
- Sayan Bhattacharya, Vincent Conitzer, Kamesh Munagala, and Lirong Xia. 2010a. Incentive compatible budget elicitation in multiunit auctions. In Proceedings of SODA. 554--572. Google ScholarDigital Library
- Sayan Bhattacharya, Gagan Goel, Sreenivas Gollapudi, and Kamesh Munagala. 2010b. Budget constrained auctions with heterogeneous items. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC'10). 379--388. DOI:http://dx.doi.org/10.1145/1806689.1806742 Google ScholarDigital Library
- Sushil Bikhchandani, Sven de Vries, James Schummer, and Rakesh V. Vohra. 2011. An ascending vickrey auction for selling bases of a matroid. Oper. Res. 59, 2, 400--413. Google ScholarDigital Library
- Christian Borgs, Jennifer T. Chayes, Nicole Immorlica, Mohammad Mahdian, and Amin Saberi. 2005. Multi-unit auctions with budget-constrained bidders. In Proceedings of the ACM Conference on Electronic Commerce. 44--51. Google ScholarDigital Library
- Yang Cai, Constantinos Daskalakis, and S. Matthew Weinberg. 2012. Optimal multi-dimensional mechanism design: Reducing revenue to welfare maximization. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'12), 130--139. DOI:http://dx.doi.org/10.1109/FOCS.2012.88 Google ScholarDigital Library
- Ioannis Caragiannis, Panagiotis Kanellopoulos, Christos Kaklamanis, and Maria Kyropoulou. 2011. On the Efficiency of Equilibria in Generalized Second Price Auctions. In Proceedings of EC'11. Google ScholarDigital Library
- Shuchi Chawla, David L. Malec, and Azarakhsh Malekian. 2011. Bayesian mechanism design for budget-constrained agents. In Proceedings the 12th ACM Conference on Electronic Commerce (EC-11). 253--262. DOI:http://dx.doi.org/10.1145/1993574.1993613 Google ScholarDigital Library
- Yeon-Koo Che and Ian Gale. 1998. Standard auctions with financially constrained bidders. Rev. Econ. Stud. 65, 1, 1--21.Google ScholarCross Ref
- Riccardo Colini-Baldeschi, Monika Henzinger, Stefano Leonardi, and Martin Starnberger. 2012. On multiple keyword sponsored search auctions with budgets. In Proceedings of ICALP (2). 1--12. Google ScholarDigital Library
- Nikhil R. Devanur, Bach Q. Ha, and Jason D. Hartline. 2013. Prior-free auctions for budgeted agents. In Proceedings of the ACM Conference on Electronic Commerce. 287--304. Google ScholarDigital Library
- Peerapong Dhangwatnotai. 2011. Multi-keyword sponsored search. In Proceedings of the ACM Conference on Electronic Commerce. 91--100. Google ScholarDigital Library
- Shahar Dobzinski, Ron Lavi, and Noam Nisan. 2008. Multi-unit auctions with budget limits. In Proceedings of FOCS. 260--269. Google ScholarDigital Library
- Shahar Dobzinski and Renato Paes Leme. 2013. Efficiency guarantees in auctions with budgets. CoRR abs/1304.7048.Google Scholar
- Danny Dolev, Dror G. Feitelson, Joseph Y. Halpern, Raz Kupferman, and Nathan Linial. 2012. No justified complaints: On fair sharing of multiple resources. In Proceedings of ICTS. 68--75. Google ScholarDigital Library
- Paul Dütting, Monika Henzinger, and Ingmar Weber. 2013. Sponsored search, market equilibria, and the Hungarian Method. Inf. Process. Lett. 113, 3, 67--73. Google ScholarDigital Library
- Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz. 2007. Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords. Amer. Econ. Rev. 97, 1, 242--259. DOI:http://dx.doi.org/10.1257/000282807780323523Google ScholarCross Ref
- Jon Feldman, S. Muthukrishnan, Evdokia Nikolova, and Martin Pál. 2008. A truthful mechanism for offline ad slot scheduling. In Proceedings of SAGT. 182--193. Google ScholarDigital Library
- Amos Fiat, Stefano Leonardi, Jared Saia, and Piotr Sankowski. 2011. Single valued combinatorial auctions with budgets. In Proceedings of the ACM Conference on Electronic Commerce. 223--232. Google ScholarDigital Library
- Gagan Goel, Vahab S. Mirrokni, and Renato Paes Leme. 2012. Polyhedral clinching auctions and the adwords polytope. In Proceedings of the 44th Symposium on Theory of Computing Conference (STOC'12). 107--122. http://doi.acm.org/10.1145/2213977.2213990 Google ScholarDigital Library
- Gagan Goel, Vahab S. Mirrokni, and Renato Paes Leme. 2013. Clinching auction with online supply. In Proceedings of SODA. 605--619. Google ScholarDigital Library
- Gagan Goel, Vahab S. Mirrokni, and Renato Paes Leme. 2014. Clinching auctions beyond hard budget constraints. In Proceedings of the ACM Conference on Economics and Computation (EC'14). 167--184. DOI:http://dx.doi.org/10.1145/2600057.2602851 Google ScholarDigital Library
- R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan. 1979. Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Discrete Math. 4, 287--326.Google ScholarCross Ref
- Isa E. Hafalir, R. Ravi, and Amin Sayedi. 2012. A near Pareto optimal auction with budget constraints. Games Econ. Behav. 74, 2, 699--708.Google ScholarCross Ref
- Satoru Iwata and James B. Orlin. 2009. A simple combinatorial algorithm for submodular function minimization. In Proceedings of SODA. 1230--1237. Google ScholarDigital Library
- Ron Lavi and Marina May. 2011. A note on the incompatibility of strategy-proofness and pareto-optimality in quasi-linear settings with public budgets. WINE. Google ScholarDigital Library
- Brendan Lucier and Renato Paes Leme. 2011. GSP auctions with correlated types. In Proceedings of EC'11. Google ScholarDigital Library
- Brendan Lucier, Renato Paes Leme, and Éva Tardos. 2011. On revenue in the generalized second price auction. In Proceedings of the Ad Auctions Workshop.Google Scholar
- Colin J. H. McDiarmid. 1975. Rado's theorem for polymatroids. Math. Proce. Cambridge Phil. Soc. 78, 2, 263--281. DOI:http://dx.doi.org/10.1017/S0305004100051677Google ScholarCross Ref
- R. Myerson. 1981. Optimal auction design. Math. Oper. Res. 6, 1, 58--73. http://www.sciencedirect.com/science/article/B6WS6-40417R4-179/2/f44ded75bd455529f12b470ea9cf2783 Google ScholarDigital Library
- Thành Nguyen and Éva Tardos. 2007. Approximately maximizing efficiency and revenue in polyhedral environments. In Proceedings of the ACM Conference on Electronic Commerce. 11--19. Google ScholarDigital Library
- Thành Nguyen and Milan Vojnovic. 2011. The weighted proportional sharing mechanisms. In Proceedings of SIGMETRICS.Google Scholar
- James B. Orlin. 2007. A faster strongly polynomial time algorithm for submodular function minimization. In Proceedings of IPCO. 240--251. Google ScholarDigital Library
- Renato Paes Leme and Éva Tardos. 2010. Pure and Bayes-Nash price of anarchy for generalized second price auctions. In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS'10). Google ScholarDigital Library
- Mallesh M. Pai and Rakesh Vohra. 2008. Optimal Auctions with Financially Constrained Bidders. Discussion papers. Northwestern University, Center for Mathematical Studies in Economics and Management Science.Google Scholar
- A. Schrijver. 2003. Combinatorial Optimization - Polyhedra and Efficiency. Springer.Google Scholar
- Hal R. Varian. 2006. Position auctions. Int. J. Indust. Org.Google Scholar
Index Terms
- Polyhedral Clinching Auctions and the AdWords Polytope
Recommendations
Polyhedral clinching auctions and the adwords polytope
STOC '12: Proceedings of the forty-fourth annual ACM symposium on Theory of computingA 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 ...
Polyhedral Clinching Auctions for Indivisible Goods
Web and Internet EconomicsAbstractIn this study, we propose the polyhedral clinching auction for indivisible goods, which has so far been studied for divisible goods. As in the divisible setting by Goel et al. (2015), our mechanism enjoys incentive compatibility, individual ...
Clinching auctions beyond hard budget constraints
EC '14: Proceedings of the fifteenth ACM conference on Economics and computationConstraints on agent's ability to pay play a major role in auction design for any setting where the magnitude of financial transactions is sufficiently large. Those constraints have been traditionally modeled in mechanism design as hard budget, i.e., ...
Comments