Skip to main content
Springer Nature Link
Log in

Robust Revenue Maximization Under Minimal Statistical Information

  • Conference paper
  • First Online:
Web and Internet Economics (WINE 2020)

Part of the book series: Lecture Notes in Computer Science ((LNISA,volume 12495))

Included in the following conference series:

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
eBook
USD 39.99
Price excludes VAT (USA)
Softcover Book
USD 54.99
Price excludes VAT (USA)

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. 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

  2. Azar, P., Micali, S.: Optimal parametric auctions. Technical report, MIT-CSAIL-TR-2012-015 (2012). http://hdl.handle.net/1721.1/70556

  3. 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

  4. 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

  5. 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

    Article  MathSciNet  MATH  Google Scholar 

  6. 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

  7. 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

    Article  MathSciNet  MATH  Google Scholar 

  8. Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)

    MATH  Google Scholar 

  9. Bulow, J., Klemperer, P.: Auctions versus negotiations. Am. Econ. Rev. 86(1), 180–194 (1996)

    Google Scholar 

  10. 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

  11. 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

  12. 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

  13. 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

    Article  MathSciNet  MATH  Google Scholar 

  14. Carroll, G.: Robustness and separation in multidimensional screening. Econometrica 85(2), 453–488 (2017). https://doi.org/10.3982/ECTA14165

    Article  MathSciNet  MATH  Google Scholar 

  15. 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

    Article  Google Scholar 

  16. Chawla, S., Fu, H., Karlin, A.R.: Approximate revenue maximization in interdependent value settings. CoRR abs/1408.4424 (2014)

    Google Scholar 

  17. 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

  18. Chen, J., Li, B., Li, Y., Lu, P.: Bayesian auctions with efficient queries. CoRR abs/1804.07451 (2018)

    Google Scholar 

  19. 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

  20. 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

  21. 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

  22. 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

    Article  MathSciNet  MATH  Google Scholar 

  23. Dhangwatnotai, P., Roughgarden, T., Yan, Q.: Revenue maximization with a single sample. Games Econ. Behav. 91(C), 318–333 (2014)

    MathSciNet  MATH  Google Scholar 

  24. 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

  25. 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

  26. 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

    Article  MathSciNet  MATH  Google Scholar 

  27. Giannakopoulos, Y., Poças, D., Tsigonias-Dimitriadis, A.: Robust revenue maximization under minimal statistical information. CoRR abs/1907.04220 (2019)

    Google Scholar 

  28. 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

  29. 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

  30. 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

  31. 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

    Article  MathSciNet  MATH  Google Scholar 

  32. Hartline, J.D.: Mechanism design and approximation (2013), manuscript. http://jasonhartline.com/MDnA/

  33. 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

  34. Kendall, M.G.: The Advanced Theory of Statistics, vol. I, 4th edn. Charles Griffin, Glasgow (1948)

    Google Scholar 

  35. 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

    Article  MathSciNet  MATH  Google Scholar 

  36. 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

  37. 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

    Article  MathSciNet  MATH  Google Scholar 

  38. Milgrom, P.: Putting Auction Theory to Work. Cambridge University Press, Cambridge (2004). https://doi.org/10.1017/CBO9780511813825.009

    Book  Google Scholar 

  39. Mood, A.M., Graybill, F.A., Boes, D.C.: Introduction to the Theory of Statistics, 3rd edn. McGraw-Hill, New York (1974)

    MATH  Google Scholar 

  40. Moriguti, S.: Extremal properties of extreme value distributions. Ann. Math. Stat. 22(4), 523–536 (1951)

    Article  MathSciNet  Google Scholar 

  41. Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)

    Book  Google Scholar 

  42. Myerson, R.B.: Optimal auction design. Math. Oper. Res. 6(1), 58–73 (1981). https://doi.org/10.1287/moor.6.1.58

    Article  MathSciNet  MATH  Google Scholar 

  43. 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

    Article  Google Scholar 

  44. 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

    Article  MathSciNet  Google Scholar 

  45. 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

  46. 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

Download references

Author information

Authors and Affiliations

  1. TU Munich, Munich, Germany

    Yiannis Giannakopoulos & Alexandros Tsigonias-Dimitriadis

  2. LASIGE, Faculdade de Ciências, Universidade de Lisboa, Lisbon, Portugal

    Diogo Poças

Authors
  1. Yiannis Giannakopoulos
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Diogo Poças
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Alexandros Tsigonias-Dimitriadis
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Diogo Poças .

Editor information

Editors and Affiliations

  1. Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China

    Xujin Chen

  2. Shanghai University of Finance and Economics, Shanghai, China

    Nikolai Gravin

  3. Goethe University Frankfurt, Frankfurt am Main, Germany

    Martin Hoefer

  4. University of Illinois at Urbana-Champaign, Urbana, IL, USA

    Ruta Mehta

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

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)

Publish with us

Policies and ethics

Search

Navigation