Document Open Access Logo

Asymptotically Optimal Welfare of Posted Pricing for Multiple Items with MHR Distributions

Authors Alexander Braun, Matthias Buttkus, Thomas Kesselheim

PDF
Thumbnail PDF

File

LIPIcs.ESA.2021.22.pdf
  • Filesize: 0.66 MB
  • 16 pages

Document Identifiers

Author Details

Alexander Braun
  • Institute of Computer Science, Universität Bonn, Germany
Matthias Buttkus
  • Institute of Computer Science, Universität Bonn, Germany
Thomas Kesselheim
  • Institute of Computer Science, Universität Bonn, Germany

Acknowledgements

We thank the anonymous reviewers for helpful comments on improving the presentation of the paper.

Cite AsGet BibTex

Alexander Braun, Matthias Buttkus, and Thomas Kesselheim. Asymptotically Optimal Welfare of Posted Pricing for Multiple Items with MHR Distributions. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ESA.2021.22

Abstract

We consider the problem of posting prices for unit-demand buyers if all n buyers have identically distributed valuations drawn from a distribution with monotone hazard rate. We show that even with multiple items asymptotically optimal welfare can be guaranteed. Our main results apply to the case that either a buyer’s value for different items are independent or that they are perfectly correlated. We give mechanisms using dynamic prices that obtain a 1 - Θ (1/(log n))-fraction of the optimal social welfare in expectation. Furthermore, we devise mechanisms that only use static item prices and are 1 - Θ ((log log log n)/(log n))-competitive compared to the optimal social welfare. As we show, both guarantees are asymptotically optimal, even for a single item and exponential distributions.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic mechanism design
  • Theory of computation → Online algorithms
Keywords
  • Prophet Inequalities
  • Monotone Hazard Rate
  • Competitive Analysis
  • Posted Prices
  • Combinatorial Auctions
  • Matching

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Melika Abolhassani, Soheil Ehsani, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Robert D. Kleinberg, and Brendan Lucier. Beating 1-1/e for ordered prophets. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 61-71. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055479.
  2. Saeed Alaei. Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. SIAM J. Comput., 43(2):930-972, 2014. URL: https://doi.org/10.1137/120878422.
  3. Barry C. Arnold, N. Balakrishnan, and H. N. Nagaraja. A First Course in Order Statistics (Classics in Applied Mathematics). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2008. Google Scholar
  4. Moshe Babaioff, Liad Blumrosen, Shaddin Dughmi, and Yaron Singer. Posting prices with unknown distributions. ACM Trans. Econ. Comput., 5(2), 2017. URL: https://doi.org/10.1145/3037382.
  5. Alexander Braun, Matthias Buttkus, and Thomas Kesselheim. Asymptotically optimal welfare of posted pricing for multiple items with mhr distributions, 2021. URL: http://arxiv.org/abs/2107.00526.
  6. Yang Cai and Mingfei Zhao. Simple mechanisms for subadditive buyers via duality. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 170-183. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055465.
  7. Shuchi Chawla, Nikhil R. Devanur, Alexander E. Holroyd, Anna R. Karlin, James B. Martin, and Balasubramanian Sivan. Stability of service under time-of-use pricing. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 184-197. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055455.
  8. Shuchi Chawla, Jason D. Hartline, and Robert D. Kleinberg. Algorithmic pricing via virtual valuations. In Jeffrey K. MacKie-Mason, David C. Parkes, and Paul Resnick, editors, Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), San Diego, California, USA, June 11-15, 2007, pages 243-251. ACM, 2007. URL: https://doi.org/10.1145/1250910.1250946.
  9. Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan. Multi-parameter mechanism design and sequential posted pricing. In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 311-320. ACM, 2010. URL: https://doi.org/10.1145/1806689.1806733.
  10. Edward Clarke. Multipart pricing of public goods. Public Choice, 11(1):17-33, 1971. URL: https://EconPapers.repec.org/RePEc:kap:pubcho:v:11:y:1971:i:1:p:17-33.
  11. José R. Correa, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk, and Tjark Vredeveld. Posted price mechanisms for a random stream of customers. In Constantinos Daskalakis, Moshe Babaioff, and Hervé Moulin, editors, Proceedings of the 2017 ACM Conference on Economics and Computation, EC '17, Cambridge, MA, USA, June 26-30, 2017, pages 169-186. ACM, 2017. URL: https://doi.org/10.1145/3033274.3085137.
  12. José R. Correa, Patricio Foncea, Dana Pizarro, and Victor Verdugo. From pricing to prophets, and back! Oper. Res. Lett., 47(1):25-29, 2019. URL: https://doi.org/10.1016/j.orl.2018.11.010.
  13. Paul Dütting, Thomas Kesselheim, and Brendan Lucier. An o(log log m) prophet inequality for subadditive combinatorial auctions. SIGecom Exch., 18(2):32–37, 2020. URL: https://doi.org/10.1145/3440968.3440972.
  14. B. Edelman, M. Ostrovsky, and M. Schwarz. Selling billions of dollars worth of keywords: The generalized second-price auction. American Economic Review, 97(1):242-259, 2007. Google Scholar
  15. Soheil Ehsani, MohammadTaghi Hajiaghayi, Thomas Kesselheim, and Sahil Singla. Prophet secretary for combinatorial auctions and matroids. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 700-714. SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975031.46.
  16. Michal Feldman, Nick Gravin, and Brendan Lucier. Combinatorial auctions via posted prices. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 123-135. SIAM, 2015. URL: https://doi.org/10.1137/1.9781611973730.10.
  17. Yiannis Giannakopoulos and Keyu Zhu. Optimal pricing for MHR distributions. In George Christodoulou and Tobias Harks, editors, Web and Internet Economics - 14th International Conference, WINE 2018, Oxford, UK, December 15-17, 2018, Proceedings, volume 11316 of Lecture Notes in Computer Science, pages 154-167. Springer, 2018. URL: https://doi.org/10.1007/978-3-030-04612-5_11.
  18. Theodore Groves. Incentives in teams. Econometrica, 41(4):617-31, 1973. URL: https://EconPapers.repec.org/RePEc:ecm:emetrp:v:41:y:1973:i:4:p:617-31.
  19. Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, and Tuomas Sandholm. Automated online mechanism design and prophet inequalities. In Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, July 22-26, 2007, Vancouver, British Columbia, Canada, pages 58-65. AAAI Press, 2007. URL: http://www.aaai.org/Library/AAAI/2007/aaai07-009.php.
  20. Theodore P Hill, Robert P Kertz, et al. Comparisons of stop rule and supremum expectations of iid random variables. The Annals of Probability, 10(2):336-345, 1982. Google Scholar
  21. Yaonan Jin, Weian Li, and Qi Qi. On the approximability of simple mechanisms for mhr distributions. In Ioannis Caragiannis, Vahab Mirrokni, and Evdokia Nikolova, editors, Web and Internet Economics, pages 228-240, Cham, 2019. Springer International Publishing. Google Scholar
  22. Ulrich Krengel and Louis Sucheston. Semiamarts and finite values. Bull. Amer. Math. Soc, 83(4), 1977. Google Scholar
  23. Brendan Lucier. An economic view of prophet inequalities. SIGecom Exchanges, 16(1):24-47, 2017. URL: https://doi.org/10.1145/3144722.3144725.
  24. Roger B. Myerson. Optimal auction design. Math. Oper. Res., 6(1):58-73, 1981. URL: https://doi.org/10.1287/moor.6.1.58.
  25. Horst Rinne. The Hazard rate : Theory and inference (with supplementary MATLAB-Programs). Justus-Liebig-Universität, 2014. URL: http://geb.uni-giessen.de/geb/volltexte/2014/10793.
  26. E. Samuel-Cahn. Comparison of threshold stop rules and maximum for independent nonnegative random variables. Annals of Probability, 12:1213-1216, 1984. Google Scholar
  27. H. Varian. Position auctions. International Journal of Industrial Organization, 25(6):1163–1178, 2007. Google Scholar
  28. William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. Journal of Finance, 16(1):8-37, 1961. URL: https://EconPapers.repec.org/RePEc:bla:jfinan:v:16:y:1961:i:1:p:8-37.
  29. Hanrui Zhang. Improved Prophet Inequalities for Combinatorial Welfare Maximization with (Approximately) Subadditive Agents. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms (ESA 2020), volume 173 of Leibniz International Proceedings in Informatics (LIPIcs), pages 82:1-82:17, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ESA.2020.82.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact