{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T15:57:37Z","timestamp":1787500657145,"version":"build-2736575974"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,1,28]],"date-time":"2020-01-28T00:00:00Z","timestamp":1580169600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGecom Exch."],"published-print":{"date-parts":[[2020,1,28]]},"abstract":"<jats:p>\n                    Consider a fundamental problem in microeconomics: selling a single item to a number of potential buyers, who independently draw their values from regular and publicly known distributions. There are four mechanisms widely studied in the literature and widely used in practice:\n                    <jats:bold>Myerson Auction (OPT), Sequential Posted Pricing (SPM), Second-Price Auction with Anonymous Reserve (AR)<\/jats:bold>\n                    , and\n                    <jats:bold>Anonymous Pricing (AP).<\/jats:bold>\n                  <\/jats:p>\n                  <jats:p>\n                    <jats:bold>OPT<\/jats:bold>\n                    is revenue-optimal but complicated, which also experiences several practical issues such as fairness.\n                    <jats:bold>AP<\/jats:bold>\n                    is the simplest mechanism, but also generates the lowest revenue among these four mechanisms.\n                    <jats:bold>SPM<\/jats:bold>\n                    and\n                    <jats:bold>AR<\/jats:bold>\n                    are of intermediate complexity and revenue. A quantitative approach to comparing the relative power of these mechanisms is to study their revenue gaps, each of which is defined as the largest ratio between the revenues from a pair of mechanisms. This letter surveys some recent developments on establishing tight revenue gaps, and highlights some open questions.\n                  <\/jats:p>","DOI":"10.1145\/3381329.3381335","type":"journal-article","created":{"date-parts":[[2020,1,28]],"date-time":"2020-01-28T15:45:40Z","timestamp":1580226340000},"page":"54-61","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Tight revenue gaps among simple and optimal mechanisms"],"prefix":"10.1145","volume":"17","author":[{"given":"Yaonan","family":"Jin","sequence":"first","affiliation":[{"name":"Columbia University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pinyan","family":"Lu","sequence":"additional","affiliation":[{"name":"Shanghai University of Finance and Economics"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Qi","family":"Qi","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhihao Gavin","family":"Tang","sequence":"additional","affiliation":[{"name":"Shanghai University of Finance and Economics"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tao","family":"Xiao","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,1,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.92"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6--8","author":"Bar-Yossef Z.","year":"2002","unstructured":"Bar-Yossef , Z. , Hildrum , K. , and Wu , F . 2002. 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. 964--970. Bar-Yossef, Z., Hildrum, K., and Wu, F. 2002. 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. 964--970."},{"key":"e_1_2_1_3_1","unstructured":"Beyhaghi H. Golrezaei N. Leme R. P. Pal M. and Sivan B. 2018. Improved approximations for free-order prophets and second-price auctions. CoRR abs\/1807.03435.  Beyhaghi H. Golrezaei N. Leme R. P. Pal M. and Sivan B. 2018. Improved approximations for free-order prophets and second-price auctions. CoRR abs\/1807.03435."},{"key":"e_1_2_1_4_1","volume-title":"SAGT 2017, L'Aquila, Italy, September 12--14, 2017, Proceedings. 16--28","author":"Birmpas G.","unstructured":"Birmpas , G. , Markakis , E. , Telelis , O. , and Tsikiridis , A . 2017. Tight welfare guarantees for pure nash equilibria of the uniform price auction. In Algorithmic Game Theory - 10th International Symposium , SAGT 2017, L'Aquila, Italy, September 12--14, 2017, Proceedings. 16--28 . Birmpas, G., Markakis, E., Telelis, O., and Tsikiridis, A. 2017. Tight welfare guarantees for pure nash equilibria of the uniform price auction. In Algorithmic Game Theory - 10th International Symposium, SAGT 2017, L'Aquila, Italy, September 12--14, 2017, Proceedings. 16--28."},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Bulow J. and Klemperer P. 1994. Auctions vs. negotiations. Tech. rep. National Bureau of Economic Research.  Bulow J. and Klemperer P. 1994. Auctions vs. negotiations. Tech. rep. National Bureau of Economic Research.","DOI":"10.3386\/w4608"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010","author":"Chawla S.","year":"2010","unstructured":"Chawla , S. , Hartline , J. D. , Malec , D. L. , and Sivan , B . 2010. 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 . 311--320. Chawla, S., Hartline, J. D., Malec, D. L., and Sivan, B. 2010. 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. 311--320."},{"key":"e_1_2_1_7_1","volume-title":"Symposium on Theory of Computing, STOC 2014","author":"Chen N.","year":"2014","unstructured":"Chen , N. , Gravin , N. , and Lu , P . 2014. Optimal competitive auctions . In Symposium on Theory of Computing, STOC 2014 , New York, NY, USA, May 31 - June 03, 2014 . 253--262. Chen, N., Gravin, N., and Lu, P. 2014. Optimal competitive auctions. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014. 253--262."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764468.2764491"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3033274.3085137"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3331033.3331039"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2018.11.010"},{"key":"e_1_2_1_12_1","unstructured":"D\u00fctting P. Fischer F. A. and Klimm M. 2016. Revenue gaps for static and dynamic posted pricing of homogeneous goods. CoRR abs\/1607.07105.  D\u00fctting P. Fischer F. A. and Klimm M. 2016. Revenue gaps for static and dynamic posted pricing of homogeneous goods. CoRR abs\/1607.07105."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764468.2764489"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, January 7--9","author":"Goldberg A. V.","year":"2001","unstructured":"Goldberg , A. V. , Hartline , J. D. , and Wright , A . 2001. Competitive auctions and digital goods . In Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, January 7--9 , 2001 , Washington, DC, USA. 735--744. Goldberg, A. V., Hartline, J. D., and Wright, A. 2001. Competitive auctions and digital goods. In Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, January 7--9, 2001, Washington, DC, USA. 735--744."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005","author":"Guruswami V.","year":"2005","unstructured":"Guruswami , V. , Hartline , J. D. , Karlin , A. R. , Kempe , D. , Kenyon , C. , and McSherry , F. 2005 . On profit-maximizing envy-free pricing . In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005 , Vancouver, British Columbia, Canada, January 23--25 , 2005. 1164--1173. Guruswami, V., Hartline, J. D., Karlin, A. R., Kempe, D., Kenyon, C., and McSherry, F. 2005. On profit-maximizing envy-free pricing. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23--25, 2005. 1164--1173."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, July 22--26","author":"Hajiaghayi M. T.","year":"2007","unstructured":"Hajiaghayi , M. T. , Kleinberg , R. D. , and Sandholm , T . 2007. 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. 58--65. Hajiaghayi, M. T., Kleinberg, R. D., and Sandholm, T. 2007. 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. 58--65."},{"key":"e_1_2_1_17_1","unstructured":"Hartline J. D. 2013. Mechanism design and approximation. Book draft. October 122.  Hartline J. D. 2013. Mechanism design and approximation. Book draft. October 122."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings 10th ACM Conference on Electronic Commerce (EC-2009)","author":"Hartline J. D.","year":"2009","unstructured":"Hartline , J. D. and Roughgarden , T . 2009. Simple versus optimal mechanisms . In Proceedings 10th ACM Conference on Electronic Commerce (EC-2009) , Stanford, California, USA, July 6--10 , 2009 . 225--234. Hartline, J. D. and Roughgarden, T. 2009. Simple versus optimal mechanisms. In Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), Stanford, California, USA, July 6--10, 2009. 225--234."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176993861"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Jin Y. Lu P. Qi Q. Tang Z. G. and Xiao T. 2019. Tight approximation ratio of anonymous pricing. In STOC. ACM 674--685.  Jin Y. Lu P. Qi Q. Tang Z. G. and Xiao T. 2019. Tight approximation ratio of anonymous pricing. In STOC. ACM 674--685.","DOI":"10.1145\/3313276.3316331"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Jin Y. Lu P. Tang Z. G. and Xiao T. 2019. Tight revenue gaps among simple mechanisms. In SODA. SIAM 209--228.  Jin Y. Lu P. Tang Z. G. and Xiao T. 2019. Tight revenue gaps among simple mechanisms. In SODA. SIAM 209--228.","DOI":"10.1137\/1.9781611975482.14"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465769.2465775"},{"key":"e_1_2_1_23_1","first-page":"197","article-title":"On semiamarts, amarts, and processes with finite value","volume":"4","author":"Krengel U.","year":"1978","unstructured":"Krengel , U. and Sucheston , L. 1978 . On semiamarts, amarts, and processes with finite value . Advances in Prob 4 , 197 -- 266 . Krengel, U. and Sucheston, L. 1978. On semiamarts, amarts, and processes with finite value. Advances in Prob 4, 197--266.","journal-title":"Advances in Prob"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3144722.3144725"},{"key":"e_1_2_1_25_1","unstructured":"Ma W. and Sivan B. 2019. Separation between second price auctions with personalized reserves and the revenue optimal auction. CoRR abs\/1906.11657.  Ma W. and Sivan B. 2019. Separation between second price auctions with personalized reserves and the revenue optimal auction. CoRR abs\/1906.11657."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.1.58"}],"container-title":["ACM SIGecom Exchanges"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3381329.3381335","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3381329.3381335","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:44:59Z","timestamp":1750189499000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3381329.3381335"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,28]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,1,28]]}},"alternative-id":["10.1145\/3381329.3381335"],"URL":"https:\/\/doi.org\/10.1145\/3381329.3381335","relation":{},"ISSN":["1551-9031"],"issn-type":[{"value":"1551-9031","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1,28]]},"assertion":[{"value":"2020-01-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}