×

zbMATH — the first resource for mathematics

Approximate revenue maximization with multiple items. (English) Zbl 1414.91151
Summary: Maximizing the revenue from selling more than one good (or item) to a single buyer is a notoriously difficult problem, in stark contrast to the one-good case. For two goods, we show that simple “one-dimensional” mechanisms, such as selling the goods separately, guarantee at least 73% of the optimal revenue when the valuations of the two goods are independent and identically distributed, and at least 50% when they are independent.
For the case of \(k>2\) independent goods, we show that selling them separately guarantees at least a \(c/\log^2k\) fraction of the optimal revenue; and, for independent and identically distributed goods, we show that selling them as one bundle guarantees at least a \(c/\log k\) fraction of the optimal revenue.
Additional results compare the revenues from the two simple mechanisms of selling the goods separately and bundled, identify situations where bundling is optimal, and extend the analysis to multiple buyers.

MSC:
91B26 Auctions, bargaining, bidding and selling, and other market models
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alaei, S.; Fu, H.; Haghpanah, N.; Hartline, J.; Malekian, A., Bayesian optimal auctions via multi- to single-agent reduction, (EC 2012: Proceedings of the 13th ACM Conference on Electronic Commerce, (2012))
[2] Armstrong, M., Price discrimination by a many-product firm, Rev. Econ. Stud., 66, 151-168, (1999) · Zbl 0947.91052
[3] Babaioff, M.; Gonczarowski, Y.; Nisan, N., The menu-size complexity of revenue approximation, (STOC 2017: Proceedings of the 49th ACM Symposium on Theory of Computing, (2017)), 869-877 · Zbl 1369.68227
[4] Babaioff, M.; Immorlica, N.; Lucier, B.; Weinberg, S. M., A simple and approximately optimal mechanism for an additive buyer, (FOCS 2014: Proceedings of the 55th Annual Symposium on Foundations of Computer Science, (2014)), 21-30
[5] Bakos, Y.; Brynjolfsson, E., Bundling information goods: pricing, profits, and efficiency, Manag. Sci., 45, 1613-1630, (1999) · Zbl 1231.91296
[6] Border, K. C., Implementation of reduced form auctions: a geometric approach, Econometrica, 59, 1175-1187, (1991) · Zbl 0754.90018
[7] Briest, P.; Chawla, S.; Kleinberg, R.; Weinberg, M., Pricing randomized allocations, J. Econ. Theory, 156, 144-174, (2015) · Zbl 1314.91108
[8] Cai, Y.; Daskalakis, C.; Weinberg, S. M., An algorithmic characterization of multi-dimensional mechanisms, (STOC 2012: Proceedings of the 44th Annual ACM Symposium on Theory of Computing, (2012)), 459-478 · Zbl 1286.91052
[9] Cai, Y.; Daskalakis, C.; Weinberg, S. M., Optimal multi-dimensional mechanism design: reducing revenue to welfare maximization, (FOCS 2012: Proceedings of the 55th Annual Symposium on Foundations of Computer Science, (2012))
[10] Chawla, S.; Hartline, J. D.; Kleinberg, R. D., Algorithmic pricing via virtual valuations, (EC 2007: Proceedings of the 8th ACM Conference on Electronic Commerce, (2007)), 243-251
[11] Chawla, S.; Hartline, J. D.; Malec, D. L.; Sivan, B., Multi-parameter mechanism design and sequential posted pricing, (STOC 2010: Proceedings of the 42nd ACM Symposium on Theory of Computing, (2010)), 311-320 · Zbl 1293.91078
[12] Chawla, S.; Malec, D. L.; Sivan, B., The power of randomness in Bayesian optimal mechanism design, (EC 2010: Proceedings of the 11th ACM Conference on Electronic Commerce, (2010)), 149-158
[13] CrĂ©mer, J.; McLean, R. P., Full extraction of the surplus in Bayesian and dominant strategy auctions, Econometrica, 56, 1247-1257, (1988) · Zbl 0661.90104
[14] Daskalakis, C.; Deckelbaum, A.; Tzamos, C., Mechanism design via optimal transport, (EC 2013: Proceedings of the 14th ACM Conference on Electronic Commerce, (2013)), 269-286
[15] Daskalakis, C.; Deckelbaum, A.; Tzamos, C., The complexity of optimal mechanism design, (SODA 2014: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, (2014)), 1302-1318 · Zbl 1421.68060
[16] Daskalakis, C.; Deckelbaum, A.; Tzamos, C., Strong duality for a multiple-good monopolist, Econometrica, 85, 735-767, (2017) · Zbl 1420.91090
[17] Dughmi, S.; Han, L.; Nisan, N., Sampling and representation complexity of revenue maximization, Lecture Notes in Computer Science, vol. 8877, 277-291, (2014) · Zbl 1406.91171
[18] Fang, H.; Norman, P., To bundle or not to bundle, Rand J. Econ., 37, 946-963, (2006)
[19] Giannakopoulos, Y., Bounding optimal revenue in multiple-items auctions, (2014)
[20] Giannakopoulos, Y.; Koutsoupias, E., Duality and optimality of auctions for uniform distributions, (EC 2014: Proceedings of the 15th ACM Conference on Electronic Commerce, (2014)), 259-276
[21] Hart, S., 2012. A Curious Property of Convex Functions and Mechanism Design. Mimeo.
[22] Hart, S.; Nisan, N., Approximate revenue maximization with multiple items, (2012), The Hebrew University of Jerusalem, Center for Rationality DP-606 · Zbl 1414.91151
[23] Hart, S.; Nisan, N., The menu-size complexity of auctions, (2013), The Hebrew University of Jerusalem, Center for Rationality DP-637
[24] Hart, S.; Reny, P. J., Maximal revenue with multiple goods: nonmonotonicity and other observations, Theor. Econ., 10, 893-922, (2015) · Zbl 1395.91533
[25] Hart, S.; Reny, P. J., Implementation of reduced form mechanisms: a simple approach and a new characterization, Econ. Theory Bull., 3, 1-8, (2015)
[26] Jehiel, P.; Meyer-ter-Vehn, M.; Moldovanu, B., Mixed bundling auctions, J. Econ. Theory, 134, 494-512, (2007) · Zbl 1156.91353
[27] Krishna, V., Auction theory, (2010), Academic Press
[28] Kupfer, R., A note on the ratio of revenues between selling in a bundle and separately, (2016)
[29] Lev, O., A two-dimensional problem of revenue maximization, J. Math. Econ., 47, 718-727, (2011) · Zbl 1231.91123
[30] Li, X.; Yao, A. C.-C., On revenue maximization for selling multiple independently distributed items, Proc. Natl. Acad. Sci., 110, 11232-11237, (2013) · Zbl 1292.91086
[31] Manelli, A. M.; Vincent, D. R., Bundling as an optimal selling mechanism for a multiple-good monopolist, J. Econ. Theory, 127, 1-35, (2006) · Zbl 1122.91032
[32] Manelli, A. M.; Vincent, D. R., Multidimensional mechanism design: revenue maximization and the multiple-good monopoly, J. Econ. Theory, 137, 153-185, (2007) · Zbl 1132.91435
[33] Manelli, A. M.; Vincent, D. R., Multidimensional mechanism design: revenue maximization and the multiple-good monopoly. A corrigendum, J. Econ. Theory, 147, 2492-2493, (2012) · Zbl 1258.91066
[34] McAfee, R. P.; McMillan, J., Multidimensional incentive compatibility and mechanism design, J. Econ. Theory, 46, 335-354, (1988) · Zbl 0661.90008
[35] Menicucci, D.; Hurkens, S.; Jeonc, D.-S., On the optimality of pure bundling for a monopolist, J. Math. Econ., 60, 33-42, (2015) · Zbl 1368.91104
[36] Morgenstern, J.; Roughgarden, T., Learning simple auctions, (JLMR: Workshop and Conference Proceedings, vol. 49, (2016)), 1-21
[37] Myerson, R. B., Optimal auction design, Math. Oper. Res., 6, 58-73, (1981) · Zbl 0496.90099
[38] Pavlov, G., Optimal mechanism for selling two goods, B. E. J. Theor. Econ., 11, 1, (2011) · Zbl 1277.91068
[39] Pycia, M., 2006. Stochastic vs Deterministic Mechanisms in Multidimensional Screening. MIT (Mimeo).
[40] Riley, J. G.; Samuelson, W. F., Optimal auctions, Am. Econ. Rev., 71, 381-392, (1981)
[41] Riley, J.; Zeckhauser, R., Optimal selling strategies: when to haggle, when to hold firm, Q. J. Econ., 98, 267-289, (1983)
[42] Rochet, J.-C., The taxation principle and multi-time Hamilton-Jacobi equations, J. Math. Econ., 14, 113-128, (1985) · Zbl 0594.90006
[43] Rockafellar, T. R., Convex analysis, (1970), Princeton University Press · Zbl 0202.14303
[44] Rubinstein, A.; Weinberg, S. M., Simple mechanisms for a subadditive buyer and applications to revenue monotonicity, (EC 2015: Proceedings of the Sixteenth ACM Conference on Economics and Computation, (2015)), 377-394
[45] Shaked, M.; Shantikumar, J. G., Stochastic orders, (2010), Springer
[46] Tang, P.; Wang, Z., Optimal mechanisms with simple menus, J. Math. Econ., 69, 54-70, (2017) · Zbl 1395.91240
[47] Thanassoulis, J., Haggling over substitutes, J. Econ. Theory, 117, 217-245, (2004) · Zbl 1181.91117
[48] Yao, A. C.-C., An n-to-1 bidder reduction for multi-item auctions and its applications, (Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, (2014)), 92-109 · Zbl 1372.91051
[49] Zaliapin, I. V.; Kagan, Y. Y.; Schoenberg, F. P., Approximating the distribution of Pareto sums, Pure Appl. Geophys., 162, 1187-1228, (2005)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.