{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,27]],"date-time":"2026-10-27T19:55:31Z","timestamp":1793130931144,"version":"4.5.0"},"reference-count":46,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1838154"],"award-info":[{"award-number":["IIS-1838154"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1703925"],"award-info":[{"award-number":["CCF-1703925"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1814873"],"award-info":[{"award-number":["CCF-1814873"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1563155"],"award-info":[{"award-number":["CCF-1563155"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1844887"],"award-info":[{"award-number":["CCF-1844887"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Science and Technology Innovation 2030","award":["2018AAA0100903"],"award-info":[{"award-number":["2018AAA0100903"]}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["61922052"],"award-info":[{"award-number":["61922052"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["61932002"],"award-info":[{"award-number":["61932002"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"IRTSHUFE"},{"DOI":"10.13039\/501100012226","name":"Fundamental Research Funds for the Central Universities","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2022,10,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>This paper considers Bayesian revenue maximization in the [Formula: see text]-unit setting, where a monopolist seller has [Formula: see text] copies of an indivisible item and faces [Formula: see text] unit-demand buyers (whose value distributions can be nonidentical). Four basic mechanisms among others have been widely employed in practice and widely studied in the literature: Myerson auction, sequential posted-pricing, [Formula: see text]-th price auction with anonymous reserve, and anonymous pricing. Regarding a pair of mechanisms, we investigate the largest possible ratio between the two revenues (also known as the revenue gap), over all possible value distributions of the buyers. Divide these four mechanisms into two groups: (i) the discriminating mechanism group, Myerson auction and sequential posted-pricing, and (ii) the anonymous mechanism group, anonymous reserve and anonymous pricing. Within one group, the involved two mechanisms have an asymptotically tight revenue gap of [Formula: see text]. In contrast, any two mechanisms from the different groups have an asymptotically tight revenue gap of [Formula: see text].<\/jats:p>","DOI":"10.1137\/21m1456364","type":"journal-article","created":{"date-parts":[[2022,10,28]],"date-time":"2022-10-28T06:47:25Z","timestamp":1666939645000},"page":"1535-1579","source":"Crossref","is-referenced-by-count":3,"title":["Tight Revenue Gaps among Multiunit Mechanisms"],"prefix":"10.1137","volume":"51","author":[{"given":"Yaonan","family":"Jin","sequence":"first","affiliation":[{"name":"Department of Computer Science, Columbia University, New York, NY 10027 USA (, , )."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shunhua","family":"Jiang","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Columbia University, New York, NY 10027 USA (, , )."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pinyan","family":"Lu","sequence":"additional","affiliation":[{"name":"Institute for Theoretical Computer Science, Shanghai University of Finance and Economics, Shanghai, People\u2019s Republic of China ()."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hengjie","family":"Zhang","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Columbia University, New York, NY 10027 USA (, , )."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2022,10,28]]},"reference":[{"key":"ref1","doi-asserted-by":"crossref","unstructured":"Y. Azar , \nA. Chiplunkar , and \nH. Kaplan , Prophet secretary: Surpassing the 1-1\/e barrier, in  Proceedings of the 2018 ACM Conference on Economics and Computation, \n\u00c9. Tardos , \nE. Elkind , and \nR. Vohra  (eds), ACM, New York, 2018 pp. 303\u2013318.","DOI":"10.1145\/3219166.3219182"},{"key":"ref2","doi-asserted-by":"crossref","unstructured":"N. Anari , \nG. Goel , and \nA. Nikzad , Mechanism design for crowdsourcing: An optimal 1-1\/e competitive budget-feasible mechanism for large markets, in 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, IEEE, Piscataway, NJ, 2014,  pp. 266\u2013275.","DOI":"10.1109\/FOCS.2014.36"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2018.08.003"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1137\/120878422"},{"key":"ref5","doi-asserted-by":"crossref","unstructured":"M. Adamczyk  and \nM. Wlodarczyk , Random order contention resolution schemes, in  59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, \nM. Thorup , ed. IEEE, Piscataway, NJ, 2018, pp. 790\u2013801.","DOI":"10.1109\/FOCS.2018.00080"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2021.2121"},{"key":"ref7","unstructured":"Z. Bar-Yossef , \nK. Hildrum , and \nF. Wu , Incentive-compatible online auctions for digital goods, in Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002, San Francisco, CA, SIAM, Philadelphia, 2002, pp. 964\u2013970."},{"key":"ref8","first-page":"180","volume":"86","author":"Bulow J.","year":"1996","journal-title":"Amer. Econom, Revi."},{"key":"ref9","doi-asserted-by":"crossref","unstructured":"Y. Cai  and \nC. Daskalakis , Learning multi-item auctions with (or without) samples, in 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS, 2017, Berkeley, CA, 2017, pp. 516\u2013527.","DOI":"10.1109\/FOCS.2017.54"},{"key":"ref10","doi-asserted-by":"crossref","unstructured":"J. R. Correa , \nP. Foncea , \nR. Hoeksma , \nT. Oosterwijk , and \nT. Vredeveld , Posted price mechanisms for a random stream of customers, in Proceedings of the 2017 ACM Conference on Economics and Computation, EC \u201917, ACM, New York, 2017, pp. 169\u2013186.","DOI":"10.1145\/3033274.3085137"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1145\/3331033.3331039"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2018.11.010"},{"key":"ref13","doi-asserted-by":"crossref","unstructured":"N. Chen , \nN. Gravin , and \nP. Lu , On the approximability of budget feasible mechanisms, in  Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, \nD. Randall , ed. SIAM, Philadelphia, 2011, pp. 685\u2013699.","DOI":"10.1137\/1.9781611973082.54"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591855"},{"key":"ref15","doi-asserted-by":"crossref","unstructured":"N. Chen , \nN. Gravin , and \nP. Lu , Competitive analysis via benchmark decomposition, in  Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC \u201915, \nT. Roughgarden , \nM. Feldman , and \nM. Schwarz , eds, ACM, New York, 2015, pp. 363\u2013376.","DOI":"10.1145\/2764468.2764491"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2365772"},{"key":"ref17","doi-asserted-by":"crossref","unstructured":"S. Chawla , \nJ. D. Hartline , \nD. L. Malec , and \nB. Sivan , Multi-parameter mechanism design and sequential posted pricing, in Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010 ,ACM, New York, 2010, pp. 311\u2013320.","DOI":"10.1145\/1806689.1806733"},{"key":"ref18","doi-asserted-by":"crossref","unstructured":"J. Correa , \nR. Saona , and \nB. Ziliotto , Prophet secretary through blind strategies, in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, SIAM, Philadelphia, 2019, pp. 1946\u20131961.","DOI":"10.1137\/1.9781611975482.118"},{"key":"ref19","unstructured":"P. D\u00fctting , \nF. A. Fischer , and \nM. Klimm , Revenue Gaps for Static and Dynamic Posted Pricing of Homogeneous Goods, preprint, arXiv:1607.07105, 2016."},{"key":"ref20","doi-asserted-by":"crossref","unstructured":"S. Ehsani , \nM. Hajiaghayi , \nT. Kesselheim , and \nS. Singla , Prophet secretary for combinatorial auctions and matroids, in  Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, \nArtur Czumaj , ed. SIAM, Philadelphia, 2018, pp. 700\u2013714.","DOI":"10.1137\/1.9781611975031.46"},{"key":"ref21","doi-asserted-by":"crossref","unstructured":"H. Fu , \nN. Immorlica , \nB. Lucier , and \nP. Strack , Randomization beats second price as a prior-independent auction, in Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC \u201915, ACM, New York, 2015, p.323.","DOI":"10.1145\/2764468.2764489"},{"key":"ref22","unstructured":"V. Guruswami , \nJ. D. Hartline , \nA. R. Karlin , \nD. Kempe , \nC. Kenyon , and \nF. McSherry , On profit-maximizing envy-free pricing, in Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, SIAM, Philadelphia, 2005, pp. 1164\u20131173."},{"key":"ref23","doi-asserted-by":"crossref","unstructured":"A. V. Goldberg , \nJ. D. Hartline , and \nA. Wright , Competitive auctions and digital goods, in Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, \nS. R. Rao , ed. SIAM, Philadelphia, 2001, pp. 735\u2013744.","DOI":"10.1007\/3-540-44676-1_35"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1145\/3417746"},{"key":"ref25","doi-asserted-by":"crossref","unstructured":"Y. Giannakopoulos  and \nK. Zhu , Optimal pricing for MHR distributions, in Web and Internet Economics - 14th International Conference, WINE 2018, Proceedings, Oxford, UK, Springer, Cham, Switzerland, 2018, pp. 154\u2013167.","DOI":"10.1007\/978-3-030-04612-5_11"},{"key":"ref26","unstructured":"J. D. Hartline , Mechanism Design and Approximation, manuscript."},{"key":"ref27","unstructured":"M. T. Hajiaghayi , \nR. D. Kleinberg , and \nT. Sandholm , Automated online mechanism design and prophet inequalities, in Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, 2007, Vancouver, Canada, AAAI, Menlo Park, CA, 2007, pp. 58\u201365."},{"key":"ref28","doi-asserted-by":"crossref","unstructured":"J. D. Hartline  and \nT. Roughgarden . Simple versus optimal mechanisms, in Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), 2009, Stanford, California, ACM, New York, pp. 225\u2013234.","DOI":"10.1145\/1566374.1566407"},{"key":"ref29","doi-asserted-by":"crossref","unstructured":"Y. Jin , \nS. Jiang , \nP. Lu , and \nH. Zhang , Tight revenue gaps among multi-unit mechanisms. In  EC \u201921: The 22nd ACM Conference on Economics and Computation, \nP\u00e9ter Bir\u00f3 , \nShuchi Chawla , and \nFederico Echenique , eds. Budapest, Hungary, 2021, ACM, New York, 2021, pp. 654\u2013673.","DOI":"10.1145\/3465456.3467621"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2011.08.025"},{"key":"ref31","doi-asserted-by":"crossref","unstructured":"Y. Jin , \nW. Li , and \nQ. Qi , On the approximability of simple mechanisms for MHR distributions, in Web and Internet Economics - 15th International Conference, WINE 2019, Proceedings, New York, NY, Springer, Cham, Switzerland, 2019, pp. 228\u2013240.","DOI":"10.1007\/978-3-030-35389-6_17"},{"key":"ref32","doi-asserted-by":"crossref","unstructured":"Y. Jin , \nP. Lu , \nQ. Qi , \nZ. G. Tang , and \nT. Xiao , Tight approximation ratio of anonymous pricing, in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, ACM, New York, 2019 pp. 674\u2013685.","DOI":"10.1145\/3313276.3316331"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1145\/3381329.3381335"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1137\/19M126178X"},{"key":"ref35","unstructured":"Y. Jin , \nP. Lu , and \nT. Xiao , Learning Reserve Prices in Second-Price Auctions, preprint, arXiv:1912.10069, 2019."},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1145\/3144722.3144725"},{"key":"ref37","first-page":"1","volume":"17","author":"Mohri M.","year":"2016","journal-title":"J. Mach. Learn. Res."},{"key":"ref38","first-page":"1298","volume":"49","author":"Morgenstern J.","year":"2016","journal-title":"Proc. Mach. Learn. Res. (PMLR)"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2020.02.002"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1145\/1284320.1284321"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.1.58"},{"key":"ref42","volume-title":"NIST Handbook of Mathematical Functions","author":"Olver F. W. J.","year":"2010"},{"key":"ref43","volume-title":"Oxf. Grad. Texts Math. 3","author":"Oxley J. G.","year":"2006"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.2307\/2308012"},{"key":"ref45","doi-asserted-by":"crossref","unstructured":"Y. Singer , Budget feasible mechanisms, in 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, Las Vegas, IEEE Computer Society, Los Alamitos, CA, 2010, pp. 765\u2013774.","DOI":"10.1109\/FOCS.2010.78"},{"key":"ref46","doi-asserted-by":"crossref","unstructured":"Q. Yan . Mechanism design via correlation gap, in Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, SIAM, Philadelphia, 2011, pp. 710\u2013719.","DOI":"10.1137\/1.9781611973082.56"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/21M1456364","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:10:15Z","timestamp":1787339415000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/21M1456364"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,28]]},"references-count":46,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,10,31]]}},"alternative-id":["10.1137\/21M1456364"],"URL":"https:\/\/doi.org\/10.1137\/21m1456364","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,28]]}}}