{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,23]],"date-time":"2026-10-23T04:32:05Z","timestamp":1792729925184,"version":"4.5.0"},"reference-count":60,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>We consider a fundamental problem in microeconomics: selling a single item to a number of potential buyers, whose values are drawn from known independent and regular (not necessarily identical) distributions. There are four widely used and widely studied mechanisms in the literature: Myerson Auction (OPT), Sequential Posted-Pricing (SPM), Second-Price Auction with Anonymous Reserve (AR), and Anonymous Pricing (AP). OPT is revenue-optimal but complicated and also experiences several issues in practice such as fairness; AP is the simplest mechanism but also generates the lowest revenue among these four mechanisms; SPM and AR are of intermediate complexity and revenue. We explore revenue gaps among these mechanisms, each of which is defined as the largest ratio between revenues from a pair of mechanisms. We establish two tight bounds and one tighter bound: 1. SPM vs. AP: this ratio studies the power of discrimination in pricing schemes. We obtain the tight ratio of constant ${\\cal{C}}^* \\approx {2.62}$, closing the gap between $[\\frac{e}{e - 1}, e]$ left before. 2. AR vs. AP: this ratio measures the relative power of auction scheme vs. pricing scheme, when no discrimination is allowed. We attain the tight ratio of $\\frac{\\pi^2}{6} \\approx 1.64$, closing the previously known bounds $[\\frac{e}{e - 1}, e]$. 3. OPT vs. AR: this ratio quantifies the power of discrimination in auction schemes and is previously known to be somewhere between [2, e]. The lower bound of 2 was conjectured to be tight by Hartline and Roughgarden [ Proceedings of the 10th ACM Conference on Electronic Commerce, 2009, pp. 225--234] and Alaei et al. [ Games Econom. Behav., 118 (2019), pp. 494--510]. We acquire a better lower bound of 2.15 and thus disprove this conjecture.<\/jats:p>","DOI":"10.1137\/19m126178x","type":"journal-article","created":{"date-parts":[[2020,9,9]],"date-time":"2020-09-09T09:50:56Z","timestamp":1599645056000},"page":"927-958","source":"Crossref","is-referenced-by-count":14,"title":["Tight Revenue Gaps Among Simple Mechanisms"],"prefix":"10.1137","volume":"49","author":[{"given":"Yaonan","family":"Jin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pinyan","family":"Lu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhihao Gavin","family":"Tang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tao","family":"Xiao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2020,9,9]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"M. Abolhassani, S. Ehsani, H. Esfandiari, M.T. Hajiaghayi, R. D. Kleinberg, and B. Lucier (2017),\n                      Beating 1-1\/e for ordered prophets\n                      , in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, Montreal, QC, Canada, pp. 61-71,http:\/\/doi.acm.org\/10.1145\/3055399.3055479.","DOI":"10.1145\/3055399.3055479"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/120878422"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2018.08.003"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"N. Anari, R. Niazadeh, A. Saberi, and A. Shameli (2019),\n                      Nearly optimal pricing algorithms for production constrained and laminar Bayesian selection\n                      , in Proceedings of the ACM Conference on Economics and Computation, Phoenix, AZ, pp. 91-92,https:\/\/doi.org\/10.1145\/3328526.3329652.","DOI":"10.1145\/3328526.3329652"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"E. Anshelevich and S. Sekar (2017),\n                      Price doubling and item halving: Robust revenue guarantees for item pricing\n                      , in Proceedings of the ACM Conference on Economics and Computation, Cambridge, MA, pp. 325-342,http:\/\/doi.acm.org\/10.1145\/3033274.3085117.","DOI":"10.1145\/3033274.3085117"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"Y. Azar, A. Chiplunkar, and H. Kaplan (2018),\n                      Prophet secretary: Surpassing the 1-1\/e barrier\n                      , in Proceedings of the ACM Conference on Economics and Computation, Ithaca, NY, pp. 303-318,http:\/\/doi.acm.org\/10.1145\/3219166.3219182.","DOI":"10.1145\/3219166.3219182"},{"key":"atypb7","unstructured":"M. Babaioff, N. Immorlica, and R. Kleinberg (2007),\n                      Matroids, secretary problems, and online mechanisms\n                      , in Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, pp. 434-443,http:\/\/dl.acm.org\/citation.cfm?id=1283383.1283429."},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"M. Babaioff, N. Immorlica, B. Lucier, and S. M. Weinberg (2014),\n                      A simple and approximately optimal mechanism for an additive buyer\n                      , in Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, Philadelphia, PA, pp. 21-30,https:\/\/doi.org\/10.1109\/FOCS.2014.11.","DOI":"10.1109\/FOCS.2014.11"},{"key":"atypb9","unstructured":"Z. Bar-Yossef, K. Hildrum, and F. Wu (2002),\n                      Incentive-compatible online auctions for digital goods\n                      , in Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, pp. 964-970,http:\/\/dl.acm.org\/citation.cfm?id=545381.545506."},{"key":"atypb10","unstructured":"H. Beyhaghi, N. Golrezaei, R. P. Leme, M. Pal, and B. Sivan (2018),\n                      Improved Approximations for Free-order Prophets and Second-price Auctions\n                      , CoRR abs\/1807.03435,http:\/\/arxiv.org\/abs\/1807.03435."},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"G. Birmpas, E. Markakis, O. Telelis, and A. Tsikiridis (2017),\n                      Tight welfare guarantees for pure Nash equilibria of the uniform price auction\n                      , in Proceedings of the 10th International Symposium on Algorithmic Game Theory, L'Aquila, Italy, pp. 16-28,https:\/\/doi.org\/10.1007\/978-3-319-66700-3_2.","DOI":"10.1007\/978-3-319-66700-3_2"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"J. Bulow and P. Klemperer (1994),\n                      Auctions vs. Negotiations\n                      , Technical report, National Bureau of Economic Research, Cambridge, MA.","DOI":"10.3386\/w4608"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2015.02.003"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"Y. Cai and M. Zhao (2017),\n                      Simple mechanisms for subadditive buyers via duality\n                      , in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, Montreal, QC, Canada, pp. 170-183,http:\/\/doi.acm.org\/10.1145\/3055399.3055465.","DOI":"10.1145\/3055399.3055465"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"Y. Cai, N. R. Devanur, and S. M. Weinberg (2016),\n                      A duality based unified approach to Bayesian mechanism design\n                      , in Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, Cambridge, MA, pp. 926-939,http:\/\/doi.acm.org\/10.1145\/2897518.2897645.","DOI":"10.1145\/2897518.2897645"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2365772"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"S. Chawla and J. B. Miller (2016),\n                      Mechanism design for subadditive agents via an ex ante relaxation\n                      , in Proceedings of the ACM Conference on Economics and Computation, Maastricht, The Netherlands, pp. 579-596,http:\/\/doi.acm.org\/10.1145\/2940716.2940756.","DOI":"10.1145\/2940716.2940756"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"S. Chawla, J. D. Hartline, and R. D. Kleinberg (2007),\n                      Algorithmic pricing via virtual valuations\n                      , in Proceedings of the 8th ACM Conference on Electronic Commerce, San Diego, CA, pp. 243-251,http:\/\/doi.acm.org\/10.1145\/1250910.1250946.","DOI":"10.1145\/1250910.1250946"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"S. Chawla, J. D. Hartline, D. L. Malec, and B. Sivan (2010),\n                      Multi-parameter mechanism design and sequential posted pricing\n                      , in Proceedings of the 42nd ACM Symposium on Theory of Computing, Cambridge, MA, pp. 311-320,http:\/\/doi.acm.org\/10.1145\/1806689.1806733.","DOI":"10.1145\/1806689.1806733"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2012.08.010"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"N. Chen, N. Gravin, and P. Lu (2014),\n                      Optimal competitive auctions\n                      , in Proceedings of the Symposium on Theory of Computing, New York, pp. 253-262,http:\/\/doi.acm.org\/10.1145\/2591796.2591855.","DOI":"10.1145\/2591796.2591855"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"N. Chen, N. Gravin, and P. Lu (2015),\n                      Competitive analysis via benchmark decomposition\n                      , in Proceedings of the 16th ACM Conference on Economics and Computation, Portland, OR, pp. 363-376,http:\/\/doi.acm.org\/10.1145\/2764468.2764491.","DOI":"10.1145\/2764468.2764491"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"X. Chen, G. Hu, P. Lu, and L. Wang (2011),\n                      On the approximation ratio of k-lookahead auction\n                      , in International Workshop on Internet and Network Economics, Lecture Notes in Comput. Sci. 7090, Springer, New York, pp. 61-71.","DOI":"10.1007\/978-3-642-25510-6_6"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"J. Correa, R. Saona, and B. Ziliotto (2019),\n                      Prophet secretary through blind strategies\n                      , in Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, San Diego, CA, pp. 1946-1961,https:\/\/doi.org\/10.1137\/1.9781611975482.118.","DOI":"10.1137\/1.9781611975482.118"},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"J. R. Correa, P. Foncea, R. Hoeksma, T. Oosterwijk, and T. Vredeveld (2017),\n                      Posted price mechanisms for a random stream of customers\n                      , in Proceedings of the ACM Conference on Economics and Computation, Cambridge, MA, pp. 169-186,http:\/\/doi.acm.org\/10.1145\/3033274.3085137.","DOI":"10.1145\/3033274.3085137"},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"J. R. Correa, P. D\u00fctting, F. A. Fischer, and Ke. Schewior (2019),\n                      Prophet inequalities for I.I.D. random variables from an unknown distribution\n                      , in Proceedings of the ACM Conference on Economics and Computation, Phoenix, AZ, pp. 3-17,https:\/\/doi.org\/10.1145\/3328526.3329627.","DOI":"10.1145\/3328526.3329627"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.2307\/1913096"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2013.03.010"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"P. Duetting, M. Feldman, T. Kesselheim, and B. Lucier (2017),\n                      Prophet inequalities made easy: Stochastic optimization by pricing non-stochastic inputs\n                      , in Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, Berkeley, CA, pp. 540-551,https:\/\/doi.org\/10.1109\/FOCS.2017.56.","DOI":"10.1109\/FOCS.2017.56"},{"key":"atypb30","doi-asserted-by":"crossref","unstructured":"P. D\u00fctting and T. Kesselheim (2019),\n                      Posted pricing and prophet inequalities with inaccurate priors\n                      , in Proceedings of the ACM Conference on Economics and Computation, Phoenix, AZ, pp. 111-129,https:\/\/doi.org\/10.1145\/3328526.3329576.","DOI":"10.1145\/3328526.3329576"},{"key":"atypb31","unstructured":"P. D\u00fctting, F. A. Fischer, and M. Klimm (2016),\n                      Revenue Gaps for Static and Dynamic Posted Pricing of Homogeneous Goods\n                      , CoRR abs\/1607.07105,http:\/\/arxiv.org\/abs\/1607.07105."},{"key":"atypb32","doi-asserted-by":"crossref","unstructured":"A. Eden, M. Feldman, O. Friedler, I. Talgam-Cohen, and S. M. Weinberg (2017),\n                      The competition complexity of auctions: A Bulow-Klemperer result for multi-dimensional bidders\n                      , in Proceedings of the ACM Conference on Economics and Computation, Cambridge, MA, p. 343,http:\/\/doi.acm.org\/10.1145\/3033274.3085115.","DOI":"10.1145\/3033274.3085115"},{"key":"atypb33","doi-asserted-by":"crossref","unstructured":"S. Ehsani, M.T. Hajiaghayi, T. Kesselheim, and S. Singla (2019),\n                      Prophet secretary for combinatorial auctions and matroids\n                      , in Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, pp. 700-714,https:\/\/doi.org\/10.1137\/1.9781611975031.46.","DOI":"10.1137\/1.9781611975031.46"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1137\/15M1029394"},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"M. Feldman, N. Gravin, and B. Lucier (2015),\n                      Combinatorial auctions via posted prices\n                      , in Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, San Diego, CA, pp. 123-135,https:\/\/doi.org\/10.1137\/1.9781611973730.10.","DOI":"10.1137\/1.9781611973730.10"},{"key":"atypb36","doi-asserted-by":"crossref","unstructured":"H. Fu, N. Immorlica, B. Lucier, and P. Strack (2015),\n                      Randomization beats second price as a prior-independent auction\n                      , in Proceedings of the 16th ACM Conference on Economics and Computation, Portland, OR, p. 323,http:\/\/doi.acm.org\/10.1145\/2764468.2764489.","DOI":"10.1145\/2764468.2764489"},{"key":"atypb37","unstructured":"A. V. Goldberg, J. D. Hartline, and A. Wright (2001),\n                      Competitive auctions and digital goods\n                      , in Proceedings of the 12th Annual Symposium on Discrete Algorithms, Washington, DC, pp. 735-744,http:\/\/dl.acm.org\/citation.cfm?id=365411.365768."},{"key":"atypb38","unstructured":"V. Guruswami, J. D. Hartline, A. R. Karlin, D. Kempe, C. Kenyon, and F. McSherry (2005),\n                      On profit-maximizing envy-free pricing\n                      , in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, Vancouver, BC, Canada, pp. 1164-1173,http:\/\/dl.acm.org\/citation.cfm?id=1070432.1070598."},{"key":"atypb39","unstructured":"M. T. Hajiaghayi, R. D. Kleinberg, and T. Sandholm (2007),\n                      Automated online mechanism design and prophet inequalities\n                      , in Proceedings of the 22nd AAAI Conference on Artificial Intelligence, Vancouver, BC, Canada, pp. 58-65,http:\/\/www.aaai.org\/Library\/AAAI\/2007\/aaai07-009.php."},{"key":"atypb40","doi-asserted-by":"crossref","unstructured":"S. Hart and N. Nisan (2012),\n                      Approximate revenue maximization with multiple items\n                      , in Proceedings of the ACM Conference on Electronic Commerce, Valencia, Spain, p. 656,http:\/\/doi.acm.org\/10.1145\/2229012.2229061.","DOI":"10.1145\/2229012.2229061"},{"key":"atypb41","doi-asserted-by":"crossref","unstructured":"J. D. Hartline (2013),\n                      Mechanism Design and Approximation\n                      , manuscript,http:\/\/www.jasonhartline.com\/MDnA\/.","DOI":"10.1561\/9781601986719"},{"key":"atypb42","doi-asserted-by":"crossref","unstructured":"J. D. Hartline and T. Roughgarden (2009),\n                      Simple versus optimal mechanisms\n                      , in Proceedings of the 10th ACM Conference on Electronic Commerce, Stanford, CA, pp. 225-234,http:\/\/doi.acm.org\/10.1145\/1566374.1566407.","DOI":"10.1145\/1566374.1566407"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176993861"},{"key":"atypb44","doi-asserted-by":"crossref","unstructured":"Y. Jin, P. Lu, Q. Qi, Z. G. Tang, and T. Xiao (2019a),\n                      Tight approximation ratio of anonymous pricing\n                      , in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, Phoenix, AZ, pp. 674-685,https:\/\/doi.org\/10.1145\/3313276.3316331.","DOI":"10.1145\/3313276.3316331"},{"key":"atypb45","doi-asserted-by":"crossref","unstructured":"Y. Jin, P. Lu, Z. G. Tang, and T. Xiao (2019b),\n                      Tight revenue gaps among simple mechanisms\n                      , in Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, San Diego, CA, pp. 209-228,https:\/\/doi.org\/10.1137\/1.9781611975482.14.","DOI":"10.1137\/1.9781611975482.14"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1016\/0047-259X(86)90095-3"},{"key":"atypb47","doi-asserted-by":"crossref","unstructured":"R. Kleinberg and S. M. Weinberg (2012),\n                      Matroid prophet inequalities\n                      , in Proceedings of the 44th Symposium on Theory of Computing Conference, New York, pp. 123-136,http:\/\/doi.acm.org\/10.1145\/2213977.2213991.","DOI":"10.1145\/2213977.2213991"},{"key":"atypb48","volume":"1","author":"Koutsoupias E.","year":"2013","journal-title":"ACM Trans. Econom. Comput."},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1977-14378-4"},{"key":"atypb50","first-page":"197","volume":"4","author":"Krengel U.","year":"1978","journal-title":"Adv. Probab."},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1309533110"},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1145\/3144722.3144725"},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.1.58"},{"key":"atypb54","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2013.08.009"},{"key":"atypb55","doi-asserted-by":"crossref","unstructured":"A. Ronen (2001),\n                      On approximating optimal auctions\n                      , in Proceedings of the 3rd ACM Conference on Electronic Commerce, pp. 11-17.","DOI":"10.1145\/501158.501160"},{"key":"atypb56","doi-asserted-by":"crossref","unstructured":"A. Rubinstein (2016),\n                      Beyond matroids: Secretary problem and prophet inequality with general constraints\n                      , in Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, Cambridge, MA, pp. 324-332,http:\/\/doi.acm.org\/10.1145\/2897518.2897540.","DOI":"10.1145\/2897518.2897540"},{"key":"atypb57","doi-asserted-by":"crossref","unstructured":"A. Rubinstein and S. Singla (2017),\n                      Combinatorial prophet inequalities\n                      , in Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain, pp. 1671-1687,https:\/\/doi.org\/10.1137\/1.9781611974782.110.","DOI":"10.1137\/1.9781611974782.110"},{"key":"atypb58","doi-asserted-by":"crossref","unstructured":"A. Rubinstein and S. M. Weinberg (2015),\n                      Simple mechanisms for a subadditive buyer and applications to revenue monotonicity\n                      , in Proceedings of the 16th ACM Conference on Economics and Computation, Portland, OR, pp. 377-394,http:\/\/doi.acm.org\/10.1145\/2764468.2764510.","DOI":"10.1145\/2764468.2764510"},{"key":"atypb59","doi-asserted-by":"crossref","unstructured":"Q. Yan (2011),\n                      Mechanism design via correlation gap\n                      , in Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, pp. 710-719,https:\/\/doi.org\/10.1137\/1.9781611973082.56.","DOI":"10.1137\/1.9781611973082.56"},{"key":"atypb60","doi-asserted-by":"crossref","unstructured":"A. C.C. Yao (2015),\n                      An n-to-$1$ bidder reduction for multi-item auctions and its applications\n                      , in Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, San Diego, CA, pp. 92-109,https:\/\/doi.org\/10.1137\/1.9781611973730.8.","DOI":"10.1137\/1.9781611973730.8"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M126178X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:01:46Z","timestamp":1787338906000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M126178X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":60,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1137\/19M126178X"],"URL":"https:\/\/doi.org\/10.1137\/19m126178x","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}