Document Open Access Logo

Learning Reserve Prices in Second-Price Auctions

Authors Yaonan Jin , Pinyan Lu, Tao Xiao

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.75.pdf
  • Filesize: 0.96 MB
  • 24 pages

Document Identifiers

Author Details

Yaonan Jin
  • Columbia University, New York, NY, USA
Pinyan Lu
  • Shanghai University of Finance and Economics, China
Tao Xiao
  • Huawei TCS Lab, Shanghai, China

Funding

  • Jin, Yaonan: NSF grants IIS-1838154, CCF-1563155, CCF-1703925, CCF-1814873, CCF-2106429, and CCF-2107187.
  • Lu, Pinyan: Science and Technology Innovation 2030 – "New Generation of Artificial Intelligence" Major Project No.(2018AAA0100903), NSFC grant 61922052 and 61932002, Innovation Program of Shanghai Municipal Education Commission, Program for Innovative Research Team of Shanghai University of Finance and Economics, and Fundamental Research Funds for Central Universities.

Acknowledgements

We would like to thank Zhiyi Huang, Xi Chen, Rocco Servedio, and anonymous reviewers for many helpful discussions and comments.

Cite As Get BibTex

Yaonan Jin, Pinyan Lu, and Tao Xiao. Learning Reserve Prices in Second-Price Auctions. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 75:1-75:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ITCS.2023.75

Abstract

This paper proves the tight sample complexity of Second-Price Auction with Anonymous Reserve, up to a logarithmic factor, for each of all the value distribution families studied in the literature: [0,1]-bounded, [1,H]-bounded, regular, and monotone hazard rate (MHR). Remarkably, the setting-specific tight sample complexity poly(ε^{-1}) depends on the precision ε ∈ (0, 1), but not on the number of bidders n ≥ 1. Further, in the two bounded-support settings, our learning algorithm allows correlated value distributions.
In contrast, the tight sample complexity Θ̃(n) ⋅ poly(ε^{-1}) of Myerson Auction proved by Guo, Huang and Zhang (STOC 2019) has a nearly-linear dependence on n ≥ 1, and holds only for independent value distributions in every setting.
We follow a similar framework as the Guo-Huang-Zhang work, but replace their information theoretical arguments with a direct proof.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic mechanism design
  • Theory of computation → Computational pricing and auctions
  • Theory of computation → Sample complexity and generalization bounds
  • Theory of computation → Bayesian analysis
Keywords
  • Revenue Maximization
  • Sample Complexity
  • Anonymous Reserve

Metrics

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

Related Versions

References

  1. Saeed Alaei, Jason D. Hartline, Rad Niazadeh, Emmanouil Pountourakis, and Yang Yuan. Optimal auctions vs. anonymous pricing. Games Econ. Behav., 118:494-510, 2019. URL: https://doi.org/10.1016/j.geb.2018.08.003.
  2. Amine Allouah, Achraf Bahamou, and Omar Besbes. Pricing with samples. Oper. Res., 70(2):1088-1104, 2022. URL: https://doi.org/10.1287/opre.2021.2200.
  3. Lawrence M Ausubel and Paul Milgrom. The lovely but lonely vickrey auction. Combinatorial auctions, 17:22-26, 2006. Google Scholar
  4. Moshe Babaioff, Yannai A. Gonczarowski, Yishay Mansour, and Shay Moran. Are two (samples) really better than one? In Proceedings of the 2018 ACM Conference on Economics and Computation, Ithaca, NY, USA, June 18-22, 2018, page 175, 2018. URL: https://doi.org/10.1145/3219166.3219187.
  5. Maria-Florina Balcan, Avrim Blum, Jason D. Hartline, and Yishay Mansour. Reducing mechanism design to algorithm design via machine learning. J. Comput. Syst. Sci., 74(8):1245-1270, 2008. URL: https://doi.org/10.1016/j.jcss.2007.08.002.
  6. Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. Sample complexity of automated mechanism design. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 2083-2091, 2016. URL: http://papers.nips.cc/paper/6351-sample-complexity-of-automated-mechanism-design.
  7. Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. A general theory of sample complexity for multi-item profit maximization. In Proceedings of the 2018 ACM Conference on Economics and Computation, Ithaca, NY, USA, June 18-22, 2018, pages 173-174, 2018. URL: https://doi.org/10.1145/3219166.3219217.
  8. Ziv Bar-Yossef, Kirsten Hildrum, and Felix Wu. Incentive-compatible online auctions for digital goods. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6-8, 2002, San Francisco, CA, USA., pages 964-970, 2002. URL: http://dl.acm.org/citation.cfm?id=545381.545506.
  9. Richard E. Barlow, Albert W. Marshall, and Frank Proschan. Properties of probability distributions with monotone hazard rate. The Annals of Mathematical Statistics, 34(2):375-389, 1963. URL: http://www.jstor.org/stable/2238381.
  10. Xiaohui Bei, Nick Gravin, Pinyan Lu, and Zhihao Gavin Tang. Correlation-robust analysis of single item auction. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 193-208, 2019. URL: https://doi.org/10.1137/1.9781611975482.13.
  11. Avrim Blum and Jason D. Hartline. Near-optimal online auctions. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005, pages 1156-1163, 2005. URL: http://dl.acm.org/citation.cfm?id=1070432.1070597.
  12. Avrim Blum, Vijay Kumar, Atri Rudra, and Felix Wu. Online learning in online auctions. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 12-14, 2003, Baltimore, Maryland, USA., pages 202-204, 2003. URL: http://dl.acm.org/citation.cfm?id=644108.644143.
  13. Sébastien Bubeck, Nikhil R. Devanur, Zhiyi Huang, and Rad Niazadeh. Multi-scale online learning: Theory and applications to online auctions and pricing. J. Mach. Learn. Res., 20:62:1-62:37, 2019. URL: http://jmlr.org/papers/v20/17-498.html.
  14. Yang Cai and Constantinos Daskalakis. Extreme value theorems for optimal multidimensional pricing. Games and Economic Behavior, 92:266-305, 2015. URL: https://doi.org/10.1016/j.geb.2015.02.003.
  15. Yang Cai and Constantinos Daskalakis. Learning multi-item auctions with (or without) samples. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 516-527, 2017. URL: https://doi.org/10.1109/FOCS.2017.54.
  16. Andrew Caplin and Barry Nalebuff. Aggregation and social choice: a mean voter theorem. Econometrica: Journal of the Econometric Society, pages 1-23, 1991. Google Scholar
  17. Nicolò Cesa-Bianchi, Claudio Gentile, and Yishay Mansour. Regret minimization for reserve prices in second-price auctions. IEEE Trans. Information Theory, 61(1):549-564, 2015. URL: https://doi.org/10.1109/TIT.2014.2365772.
  18. Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan. Multi-parameter mechanism design and sequential posted pricing. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 311-320, 2010. URL: https://doi.org/10.1145/1806689.1806733.
  19. Xi Chen, Ilias Diakonikolas, Anthi Orfanou, Dimitris Paparas, Xiaorui Sun, and Mihalis Yannakakis. On the complexity of optimal lottery pricing and randomized mechanisms for a unit-demand buyer. SIAM J. Comput., 51(3):492-548, 2022. URL: https://doi.org/10.1137/17m1136481.
  20. Xi Chen, Ilias Diakonikolas, Dimitris Paparas, Xiaorui Sun, and Mihalis Yannakakis. The complexity of optimal multidimensional pricing for a unit-demand buyer. Games and Economic Behavior, 110:139-164, 2018. URL: https://doi.org/10.1016/j.geb.2018.03.016.
  21. Xi Chen, George Matikas, Dimitris Paparas, and Mihalis Yannakakis. On the complexity of simple and optimal deterministic mechanisms for an additive buyer. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 2036-2049, 2018. URL: https://doi.org/10.1137/1.9781611975031.133.
  22. Xue Chen, Guangda Hu, Pinyan Lu, and Lei Wang. On the approximation ratio of k-lookahead auction. In Internet and Network Economics - 7th International Workshop, WINE 2011, Singapore, December 11-14, 2011. Proceedings, pages 61-71, 2011. URL: https://doi.org/10.1007/978-3-642-25510-6_6.
  23. Richard Cole and Shravas Rao. Applications of α-strongly regular distributions to bayesian auctions. ACM Trans. Economics and Comput., 5(4):18:1-18:29, 2017. URL: https://doi.org/10.1145/3157083.
  24. Richard Cole and Tim Roughgarden. The sample complexity of revenue maximization. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 243-252, 2014. URL: https://doi.org/10.1145/2591796.2591867.
  25. Constantinos Daskalakis, Alan Deckelbaum, and Christos Tzamos. The complexity of optimal mechanism design. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1302-1318, 2014. URL: https://doi.org/10.1137/1.9781611973402.96.
  26. Constantinos Daskalakis and Vasilis Syrgkanis. Learning in auctions: Regret is hard, envy is easy. Games Econ. Behav., 134:308-343, 2022. URL: https://doi.org/10.1016/j.geb.2022.03.001.
  27. Nikhil R. Devanur, Zhiyi Huang, and Christos-Alexandros Psomas. The sample complexity of auctions with side information. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 426-439, 2016. URL: https://doi.org/10.1145/2897518.2897553.
  28. Peerapong Dhangwatnotai, Tim Roughgarden, and Qiqi Yan. Revenue maximization with a single sample. Games Econ. Behav., 91:318-333, 2015. URL: https://doi.org/10.1016/j.geb.2014.03.011.
  29. Shahar Dobzinski, Hu Fu, and Robert Kleinberg. Approximately optimal auctions for correlated bidders. Games and Economic Behavior, 92:349-369, 2015. URL: https://doi.org/10.1016/j.geb.2013.03.010.
  30. Hu Fu, Nicole Immorlica, Brendan Lucier, and Philipp Strack. Randomization beats second price as a prior-independent auction. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC '15, Portland, OR, USA, June 15-19, 2015, page 323, 2015. URL: https://doi.org/10.1145/2764468.2764489.
  31. Hu Fu and Tao Lin. Learning utilities and equilibria in non-truthful auctions. In Hugo Larochelle, Marc'Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL: https://proceedings.neurips.cc/paper/2020/hash/a3c788c57e423fa9c177544a4d5d1239-Abstract.html.
  32. Yannai A. Gonczarowski and Noam Nisan. Efficient empirical revenue maximization in single-parameter auction environments. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 856-868, 2017. URL: https://doi.org/10.1145/3055399.3055427.
  33. Yannai A. Gonczarowski and S. Matthew Weinberg. The sample complexity of up-to-ε multi-dimensional revenue maximization. J. ACM, 68(3):15:1-15:28, 2021. URL: https://doi.org/10.1145/3439722.
  34. Chenghao Guo, Zhiyi Huang, Zhihao Gavin Tang, and Xinzhi Zhang. Generalizing complex hypotheses on product distributions: Auctions, prophet inequalities, and pandora’s problem. In Mikhail Belkin and Samory Kpotufe, editors, Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pages 2248-2288. PMLR, 2021. URL: http://proceedings.mlr.press/v134/guo21a.html.
  35. Chenghao Guo, Zhiyi Huang, and Xinzhi Zhang. Settling the sample complexity of single-parameter revenue maximization. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019., pages 662-673, 2019. URL: https://doi.org/10.1145/3313276.3316325.
  36. Jason D Hartline. Mechanism design and approximation. Book draft. October, 122, 2013. Google Scholar
  37. Jason D. Hartline and Tim Roughgarden. Simple versus optimal mechanisms. In Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), Stanford, California, USA, July 6-10, 2009, pages 225-234, 2009. URL: https://doi.org/10.1145/1566374.1566407.
  38. Jason D. Hartline and Samuel Taggart. Sample complexity for non-truthful mechanisms. In Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019., pages 399-416, 2019. URL: https://doi.org/10.1145/3328526.3329632.
  39. Zhiyi Huang, Yishay Mansour, and Tim Roughgarden. Making the most of your samples. SIAM J. Comput., 47(3):651-674, 2018. URL: https://doi.org/10.1137/16M1065719.
  40. Yaonan Jin, Shunhua Jiang, Pinyan Lu, and Hengjie Zhang. Tight revenue gaps among multiunit mechanisms. SIAM Journal on Computing, 51(5):1535-1579, 2022. URL: https://doi.org/10.1137/21M1456364.
  41. Yaonan Jin, Weian Li, and Qi Qi. On the approximability of simple mechanisms for MHR distributions. In Ioannis Caragiannis, Vahab S. Mirrokni, and Evdokia Nikolova, editors, Web and Internet Economics - 15th International Conference, WINE 2019, New York, NY, USA, December 10-12, 2019, Proceedings, volume 11920 of Lecture Notes in Computer Science, pages 228-240. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-35389-6_17.
  42. Yaonan Jin, Pinyan Lu, Qi Qi, Zhihao Gavin Tang, and Tao Xiao. Tight approximation ratio of anonymous pricing. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019., pages 674-685, 2019. URL: https://doi.org/10.1145/3313276.3316331.
  43. Yaonan Jin, Pinyan Lu, Zhihao Gavin Tang, and Tao Xiao. Tight revenue gaps among simple mechanisms. SIAM J. Comput., 49(5):927-958, 2020. URL: https://doi.org/10.1137/19M126178X.
  44. Jinyan Liu, Zhiyi Huang, and Xiangning Wang. Learning optimal reserve price against non-myopic bidders. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montréal, Canada., pages 2042-2052, 2018. URL: http://papers.nips.cc/paper/7474-learning-optimal-reserve-price-against-non-myopic-bidders.
  45. Mehryar Mohri and Andres Muñoz Medina. Learning algorithms for second-price auctions with reserve. Journal of Machine Learning Research, 17:74:1-74:25, 2016. URL: http://jmlr.org/papers/v17/14-499.html.
  46. Jamie Morgenstern and Tim Roughgarden. On the pseudo-dimension of nearly optimal auctions. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages 136-144, 2015. URL: http://papers.nips.cc/paper/5766-on-the-pseudo-dimension-of-nearly-optimal-auctions.
  47. Jamie Morgenstern and Tim Roughgarden. Learning simple auctions. In Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016, pages 1298-1318, 2016. URL: http://jmlr.org/proceedings/papers/v49/morgenstern16.html.
  48. Roger B. Myerson. Optimal auction design. Math. Oper. Res., 6(1):58-73, 1981. URL: https://doi.org/10.1287/moor.6.1.58.
  49. Christos H. Papadimitriou and George Pierrakos. Optimal deterministic auctions with correlated priors. Games and Economic Behavior, 92:430-454, 2015. URL: https://doi.org/10.1016/j.geb.2013.08.009.
  50. Amir Ronen. On approximating optimal auctions. In Proceedings 3rd ACM Conference on Electronic Commerce (EC-2001), Tampa, Florida, USA, October 14-17, 2001, pages 11-17, 2001. URL: https://doi.org/10.1145/501158.501160.
  51. Tim Roughgarden and Okke Schrijvers. Ironing in the dark. In Proceedings of the 2016 ACM Conference on Economics and Computation, EC '16, Maastricht, The Netherlands, July 24-28, 2016, pages 1-18, 2016. URL: https://doi.org/10.1145/2940716.2940723.
  52. Vasilis Syrgkanis. A sample complexity measure with applications to learning optimal auctions. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pages 5352-5359, 2017. URL: http://papers.nips.cc/paper/7119-a-sample-complexity-measure-with-applications-to-learning-optimal-auctions.
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 About DROPS Imprint Privacy Contact