Constantinos Daskalakis
Skip Abstract Section
Abstract
The best way to sell n items to a buyer who values each of them independently and uniformly randomly in [c, c+1] is to bundle them together, as long as c is large enough. Still, for any c, the grand bundling mechanism is never optimal for large enough n, despite the sharp concentration of the buyer's total value for the items as n grows. Optimal multi-item mechanisms are rife with unintuitive properties, making multi-item generalizations of Myerson's celebrated mechanism a daunting task. We survey recent work on the structure and computational complexity of revenue-optimal multi-item mechanisms, providing structural as well as algorithmic generalizations of Myerson's result to multi-item settings.
- Alaei, S., Fu, H., Haghpanah, N., Hartline, J., and Malekian, A. 2012. Bayesian Optimal Auctions via Multi- to Single-agent Reduction. In the 13th ACM Conference on Electronic Commerce (EC). Google Scholar
Digital Library
- Alaei, S., Fu, H., Haghpanah, N., and Hartline, J. D. 2013. The Simple Economics of Approximately Optimal Auctions. In the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS). Google ScholarDigital Library
- Anderson, E. J. and Nash, P. 1987. Linear Programming in Infinite-Dimensional Spaces: Theory and Applications. John Wiley & Sons.Google Scholar
- Babaioff, M., Immorlica, N., Lucier, B., and Weinberg, S. M. 2014. A Simple and Approximately Optimal Mechanism for an Additive Buyer. In the 55th Annual Symposium on Foundations of Computer Science (FOCS). Google ScholarDigital Library
- Bhalgat, A., Gollapudi, S., and Munagala, K. 2013. Optimal Auctions via the Multiplicative Weight Method. In the 14th ACM Conference on Electronic Commerce (EC). Google ScholarDigital Library
- Border, K. C. 1991. Implementation of Reduced Form Auctions: A Geometric Approach. Econometrica 59, 4, 1175--1187.Google Scholar
- Border, K. C. 2007. Reduced Form Auctions Revisited. Economic Theory 31, 167--181.Google ScholarCross Ref
- Briest, P., Chawla, S., Kleinberg, R., and Weinberg, S. M. 2010. Pricing Randomized Allocations. In the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Google ScholarDigital Library
- Cai, Y. and Daskalakis, C. 2011. Extreme-Value Theorems for Optimal Multidimensional Pricing. In the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS). Google ScholarDigital Library
- Cai, Y., Daskalakis, C., and Weinberg, S. M. 2012a. An Algorithmic Characterization of Multi-Dimensional Mechanisms. In the 44th Annual ACM Symposium on Theory of Computing (STOC). Google ScholarDigital Library
- Cai, Y., Daskalakis, C., and Weinberg, S. M. 2012b. Optimal Multi-Dimensional Mechanism Design: Reducing Revenue to Welfare Maximization. In the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS). Google ScholarDigital Library
- Cai, Y., Daskalakis, C., and Weinberg, S. M. 2013a. Reducing Revenue to Welfare Maximization : Approximation Algorithms and other Generalizations. In the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Google ScholarDigital Library
- Cai, Y., Daskalakis, C., and Weinberg, S. M. 2013b. Understanding Incentives: Mechanism Design Becomes Algorithm Design. In the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS). Google ScholarDigital Library
- Cai, Y., Daskalakis, C., and Weinberg, S. M. 2015. Reducing Bayesian Mechanism Design to Algorithm Design. Encyclopedia of Algorithms.Google Scholar
- Cai, Y. and Huang, Z. 2013. Simple and Nearly Optimal Multi-Item Auctions. In the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Google ScholarDigital Library
- Chawla, S., Hartline, J. D., and Kleinberg, R. D. 2007. Algorithmic Pricing via Virtual Valuations. In the 8th ACM Conference on Electronic Commerce (EC). Google ScholarDigital Library
- Chawla, S., Hartline, J. D., Malec, D. L., and Sivan, B. 2010. Multi-Parameter Mechanism Design and Sequential Posted Pricing. In the 42nd ACM Symposium on Theory of Computing (STOC). Google ScholarDigital Library
- Chawla, S. and Sivan, B. 2014. Bayesian Algorithmic Mechanism Design. ACM SIGecom Exchanges 13, 1, 5--49. Google ScholarDigital Library
- Che, Y.-K., Kim, J., and Mierendorff, K. 2011. Generalized Reduced-Form Auctions: A Network-Flow Approach. Econometrica 81, 6, 2487--2520.Google Scholar
- Chen, X., Diakonikolas, I., Paparas, D., Sun, X., and Yannakakis, M. 2014. The Complexity of Optimal Multidimensional Pricing. In the 25th Symposium on Discrete Algorithms (SODA). Google ScholarDigital Library
- Daskalakis, C. Spring 2015. Lecture 21. In Decision, Games, and Computation. EECS, MIT. https://stellar.mit.edu/S/course/6/sp15/6.891/index.html.Google Scholar
- Daskalakis, C., Deckelbaum, A., and Tzamos, C. 2012. Optimal Pricing is Hard. In the 8th Workshop on Internet & Network Economics (WINE). Google ScholarDigital Library
- Daskalakis, C., Deckelbaum, A., and Tzamos, C. 2013. Mechanism Design via Optimal Transport. In the 14th ACM Conference on Electronic Commerce (EC). Google ScholarDigital Library
- Daskalakis, C., Deckelbaum, A., and Tzamos, C. 2014. The Complexity of Optimal Mechanism Design. In the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA). Google ScholarDigital Library
- Daskalakis, C., Deckelbaum, A., and Tzamos, C. 2015. Strong Duality for a Multiple-Good Monopoly. In the 16th ACM Conference on Electronic Commerce (EC). Google ScholarDigital Library
- Daskalakis, C., Devanur, N., and Weinberg, S. M. 2015. Revenue Maximization and Ex-Post Budget Constraints. In the 16th ACM Conference on Electronic Commerce (EC). Google ScholarDigital Library
- Daskalakis, C. and Weinberg, S. M. 2015. Bayesian Truthful Mechanisms for Job Scheduling from Bi-criterion Approximation Algorithms. In the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Google ScholarDigital Library
- Giannakopoulos, Y. and Koutsoupias, E. 2014. Duality and Optimality of Auctions for Uniform Distributions. In the 15th ACM Conference on Electronic Commerce (EC). Google ScholarDigital Library
- Hart, S. and Nisan, N. 2012. Approximate Revenue Maximization with Multiple Items. In the 13th ACM Conference on Electronic Commerce (EC). Google ScholarDigital Library
- Hart, S. and Nisan, N. 2013. The Menu-Size Complexity of Auctions. In the 14th ACM Conference on Electronic Commerce (EC). Google ScholarDigital Library
- Hart, S. and Reny, P. 2012. Maximal Revenue with Multiple Goods: Nonmonotonicity and Other Observations. Center for the Study of Rationality.Google Scholar
- Hart, S. and Reny, P. J. 2014. Implementation of Reduced Form Mechanisms: A Simple Approach and a New Characterization. Economic Theory Bulletin 3, 1, 1--8.Google ScholarCross Ref
- Hartline, J. D. 2013. Bayesian Mechanism Design. Foundations and Trends in Theoretical Computer Science 8, 3.Google ScholarCross Ref
- Li, X. and Yao, A. C.-C. 2013. On Revenue Maximization for Selling Multiple Independently Distributed Items. Proceedings of the National Academy of Sciences 110, 28, 11232--11237.Google ScholarCross Ref
- Luenberger, D. G. 1968. Optimization by Vector Space Methods. John Wiley & Sons. Google ScholarDigital Library
- Manelli, A. and Vincent, D. 2006. Bundling as an Optimal Selling Mechanism for a Multiple-Good Monopolist. Journal of Economic Theory 127, 1, 1--35.Google ScholarCross Ref
- Manelli, A. M. and Vincent, D. R. 2007. Multidimensional Mechanism Design: Revenue Maximization and the Multiple-Good Monopoly. Journal of Economic Theory 137, 1, 153--185.Google ScholarCross Ref
- Myerson, R. B. 1981. Optimal Auction Design. Mathematics of Operations Research 6, 1, 58--73. Google ScholarDigital Library
- Pavlov, G. 2011. Optimal Mechanism for Selling Two Goods. The B.E. Journal of Theoretical Economics 11, 1 (February), 1--35.Google Scholar
- Riley, J. and Zeckhauser, R. 1983. Optimal Selling Strategies: When to Haggle, When to Hold Firm. The Quarterly Journal of Economics, 267--289.Google Scholar
- Rochet, J.-C. 1987. A Necessary and Sufficient Condition for Rationalizability in a Quasi-Linear Context. Journal of Mathematical Economics 16, 2 (April), 191--200.Google ScholarCross Ref
- Rochet, J.-C. and Stole, L. A. 2003. The Economics of Multidimensional Screening. Econometric Society Monographs 35, 150--197.Google Scholar
- Roughgarden, T. 2015. Approximately Optimal Mechanism Design: Motivation, Examples, and Lessons Learned. ACM SIGecom Exchanges 13, 2, 4--20. Google ScholarDigital Library
- Rubinstein, A. and Weinberg, S. M. 2015. Simple Mechanisms for a Subadditive Buyer and Applications to Revenue Monotonicity. In the 16th ACM Conference on Electronic Commerce (EC). Google ScholarDigital Library
- Tzamos, C. 2015. Optimal Mechanisms for Pairs of Beta Distributions. http://christos.me/betas.html.Google Scholar
- Yao, A. C. 2015. An n-to-1 Bidder Reduction for Multi-item Auctions and its Applications. In the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Google ScholarDigital Library
Index Terms
- Multi-item auctions defying intuition?
Recommendations
Envy-free auctions for digital goods
EC '03: Proceedings of the 4th ACM conference on Electronic commerceWe study auctions for a commodity in unlimited supply, e.g., a digital good. In particular we consider three desirable properties for auctions: item Competitive: the auction achieves a constant fraction of the optimal revenue even on worst case inputs. ...
Efficiency and price discovery in multi-item auctions
Distributed multi-item auctions offer great opportunities for integrating fragmented online auction markets into larger markets with more efficient outcomes. We extend the theory of multiitem ascending auctions in a multi-unit demand scenario. We show ...
Auctions and differential pricing: optimal seller and bidder strategies in second-chance offers
The second chance offer is a common seller practice on eBay. It consists of price discrimination against the losing bidder, who is offered an identical item at the value of his or her highest bid. Prior work has shown that, if the goods are private-...
Comments