Abstract
We study the problem of multi-dimensional revenue maximization when selling m items to a buyer that has additive valuations for them, drawn from a (possibly correlated) prior distribution. Unlike traditional Bayesian auction design, we assume that the seller has a very restricted knowledge of this prior: they only know the mean \(\mu _j\) and an upper bound \(\sigma _j\) on the standard deviation of each item’s marginal distribution. Our goal is to design mechanisms that achieve good revenue against an ideal optimal auction that has full knowledge of the distribution in advance. Informally, our main contribution is a tight quantification of the interplay between the dispersity of the priors and the aforementioned robust approximation ratio. Furthermore, this can be achieved by very simple selling mechanisms.
More precisely, we show that selling the items via separate price lotteries achieves an \(O(\log r)\) approximation ratio where \(r=\max _j(\sigma _j/\mu _j)\) is the maximum coefficient of variation across the items. If forced to restrict ourselves to deterministic mechanisms, this guarantee degrades to \(O(r^2)\). Assuming independence of the item valuations, these ratios can be further improved by pricing the full bundle. For the case of identical means and variances, in particular, we get a guarantee of \(O(\log (r/m))\) which converges to optimality as the number of items grows large. We demonstrate the optimality of the above mechanisms by providing matching lower bounds. Our tight analysis for the deterministic case resolves an open gap from the work of Azar and Micali [ITCS’13].
Supported by the Alexander von Humboldt Foundation with funds from the German Federal Ministry of Education and Research (BMBF). The last author further acknowledges the support of the German Research Foundation (DFG) within the Research Training Group AdONE (GRK 2201). A full version of this paper can be found at [27]: arxiv.org/abs/1907.04220.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Azar, P., Daskalakis, C., Micali, S., Weinberg, S.M.: Optimal and efficient parametric auctions. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 596–604 (2013). https://doi.org/10.1137/1.9781611973105.43
Azar, P., Micali, S.: Optimal parametric auctions. Technical report, MIT-CSAIL-TR-2012-015 (2012). http://hdl.handle.net/1721.1/70556
Azar, P.D., Micali, S.: Parametric digital auctions. In: Proceedings of the 4th Conference on Innovations in Theoretical Computer Science (ITCS), pp. 231–232 (2013). https://doi.org/10.1145/2422436.2422464
Babaioff, M., Immorlica, N., Lucier, B., Weinberg, S.M.: A simple and approximately optimal mechanism for an additive buyer. In: Proceedings of the 55th Annual Symposium on Foundations of Computer Science (FOCS), pp. 21–30 (2014). https://doi.org/10.1109/FOCS.2014.11
Bandi, C., Bertsimas, D.: Optimal design for multi-item auctions: a robust optimization approach. Math. Oper. Res. 39(4), 1012–1038 (2014). https://doi.org/10.1287/moor.2014.0645
Bei, X., Gravin, N., Lu, P., Tang, Z.G.: Correlation-robust analysis of single item auction. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 193–208 (2019). https://doi.org/10.1137/1.9781611975482.13
Bergemann, D., Schlag, K.: Robust monopoly pricing. J. Econ. Theory 146(6), 2527–2543 (2011). https://doi.org/10.1016/j.jet.2011.10.018
Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)
Bulow, J., Klemperer, P.: Auctions versus negotiations. Am. Econ. Rev. 86(1), 180–194 (1996)
Cai, Y., Daskalakis, C.: Learning multi-item auctions with (or without) samples. In: Proceedings of the 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 516–527 (2017). https://doi.org/10.1109/FOCS.2017.54
Cai, Y., Devanur, N.R., Weinberg, S.M.: A duality based unified approach to Bayesian mechanism design. In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 926–939. ACM Press (2016). https://doi.org/10.1145/2897518.2897645
Cai, Y., Zhao, M.: Simple mechanisms for subadditive buyers via duality. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 170–183 (2017). https://doi.org/10.1145/3055399.3055465
Carrasco, V., Luz, V.F., Kos, N., Messner, M., Monteiro, P., Moreira, H.: Optimal selling mechanisms under moment conditions. J. Econ. Theory 177, 245–279 (2018). https://doi.org/10.1016/j.jet.2018.05.005
Carroll, G.: Robustness and separation in multidimensional screening. Econometrica 85(2), 453–488 (2017). https://doi.org/10.3982/ECTA14165
Carroll, G.: Robustness in mechanism design and contracting. Annu. Rev. Econ. 11(1), 139–166 (2019). https://doi.org/10.1146/annurev-economics-080218-025616
Chawla, S., Fu, H., Karlin, A.R.: Approximate revenue maximization in interdependent value settings. CoRR abs/1408.4424 (2014)
Chawla, S., Hartline, J.D., Malec, D.L., Sivan, B.: Multi-parameter mechanism design and sequential posted pricing. In: Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), pp. 311–320 (2010). https://doi.org/10.1145/1806689.1806733
Chen, J., Li, B., Li, Y., Lu, P.: Bayesian auctions with efficient queries. CoRR abs/1804.07451 (2018)
Chen, X., Diakonikolas, I., Orfanou, A., Paparas, D., Sun, X., Yannakakis, M.: On the complexity of optimal lottery pricing and randomized mechanisms. In: Proceedings of 56th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1464–1479 (2015). https://doi.org/10.1109/FOCS.2015.93
Chen, X., Matikas, G., Paparas, D., Yannakakis, M.: On the complexity of simple and optimal deterministic mechanisms for an additive buyer. In: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2036–2049 (2018). https://doi.org/10.1137/1.9781611975031.133
Daskalakis, C., Deckelbaum, A., Tzamos, C.: The complexity of optimal mechanism design. In: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1302–1318 (2013). https://doi.org/10.1137/1.9781611973402.96
Daskalakis, C., Deckelbaum, A., Tzamos, C.: Strong duality for a multiple-good monopolist. Econometrica 85(3), 735–767 (2017). https://doi.org/10.3982/ECTA12618
Dhangwatnotai, P., Roughgarden, T., Yan, Q.: Revenue maximization with a single sample. Games Econ. Behav. 91(C), 318–333 (2014)
Dütting, P., Roughgarden, T., Talgam-Cohen, I.: Simple versus optimal contracts. In: Proceedings of the 20th ACM Conference on Economics and Computation (EC), pp. 369–387 (2019). https://doi.org/10.1145/3328526.3329591
Fu, H., Immorlica, N., Lucier, B., Strack, P.: Randomization beats second price as a prior-independent auction. In: Proceedings of the 16th ACM Conference on Economics and Computation (EC), p. 323 (2015). https://doi.org/10.1145/2764468.2764489
Giannakopoulos, Y., Koutsoupias, E.: Duality and optimality of auctions for uniform distributions. SIAM J. Comput. 47(1), 121–165 (2018). https://doi.org/10.1137/16M1072218
Giannakopoulos, Y., Poças, D., Tsigonias-Dimitriadis, A.: Robust revenue maximization under minimal statistical information. CoRR abs/1907.04220 (2019)
Gravin, N., Lu, P.: Separation in correlation-robust monopolist problem with budget. In: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2069–2080 (2018). https://doi.org/10.1137/1.9781611975031.135
Haghpanah, N., Hartline, J.: Reverse mechanism design. In: Proceedings of the 16th ACM Conference on Economics and Computation (EC), pp. 757–758 (2015). https://doi.org/10.1145/2764468.2764498
Hart, S., Nisan, N.: The menu-size complexity of auctions. In: Proceedings of the 14th ACM Conference on Electronic Commerce (EC), pp. 565–566 (2013). https://doi.org/10.1145/2482540.2482544
Hart, S., Nisan, N.: Approximate revenue maximization with multiple items. J. Econ. Theory 172, 313–347 (2017). https://doi.org/10.1016/j.jet.2017.09.001
Hartline, J.D.: Mechanism design and approximation (2013), manuscript. http://jasonhartline.com/MDnA/
Hartline, J.D., Roughgarden, T.: Simple versus optimal mechanisms. In: Proceedings of the 10th ACM Conference on Electronic Commerce (EC), pp. 225–234 (2009). https://doi.org/10.1145/1566374.1566407
Kendall, M.G.: The Advanced Theory of Statistics, vol. I, 4th edn. Charles Griffin, Glasgow (1948)
Li, X., Yao, A.C.C.: On revenue maximization for selling multiple independently distributed items. Proc. Nat. Acad. Sci. 110(28), 11232–11237 (2013). https://doi.org/10.1073/pnas.1309533110
Li, Y., Lu, P., Ye, H.: Revenue maximization with imprecise distribution. In: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), pp. 1582–1590 (2019). http://dl.acm.org/citation.cfm?id=3306127.3331877
Manelli, A.M., Vincent, D.R.: Multidimensional mechanism design: revenue maximization and the multiple-good monopoly. J. Econ. Theory 137(1), 153–185 (2007). https://doi.org/10.1016/j.jet.2006.12.007
Milgrom, P.: Putting Auction Theory to Work. Cambridge University Press, Cambridge (2004). https://doi.org/10.1017/CBO9780511813825.009
Mood, A.M., Graybill, F.A., Boes, D.C.: Introduction to the Theory of Statistics, 3rd edn. McGraw-Hill, New York (1974)
Moriguti, S.: Extremal properties of extreme value distributions. Ann. Math. Stat. 22(4), 523–536 (1951)
Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)
Myerson, R.B.: Optimal auction design. Math. Oper. Res. 6(1), 58–73 (1981). https://doi.org/10.1287/moor.6.1.58
Roughgarden, T., Talgam-Cohen, I.: Approximately optimal mechanism design. Annu. Rev. Econ. 11(1), 355–381 (2019). https://doi.org/10.1146/annurev-economics-080218-025607
Rubinstein, A., Weinberg, S.M.: Simple mechanisms for a subadditive buyer and applications to revenue monotonicity. ACM Trans. Econ. Comput. 6(3–4), 19:1–19:25 (2018). https://doi.org/10.1145/3105448
Wilson, R.: Game-theoretic analyses of trading processes. In: Advances in Economic Theory: Fifth World Congress, pp. 33–70. Econometric Society Monographs, Cambridge University Press (1987). https://doi.org/10.1017/CCOL0521340446.002
Yao, A.C.C.: An \(n\)-to-\(1\) bidder reduction for multi-item auctions and its applications. In: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 92–109 (2015). https://doi.org/10.1137/1.9781611973730.8
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Giannakopoulos, Y., Poças, D., Tsigonias-Dimitriadis, A. (2020). Robust Revenue Maximization Under Minimal Statistical Information. In: Chen, X., Gravin, N., Hoefer, M., Mehta, R. (eds) Web and Internet Economics. WINE 2020. Lecture Notes in Computer Science(), vol 12495. Springer, Cham. https://doi.org/10.1007/978-3-030-64946-3_13
Download citation
DOI: https://doi.org/10.1007/978-3-030-64946-3_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-64945-6
Online ISBN: 978-3-030-64946-3
eBook Packages: Computer ScienceComputer Science (R0)