{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,27]],"date-time":"2026-10-27T19:55:30Z","timestamp":1793130930443,"version":"4.5.0"},"publisher-location":"New York, NY, USA","reference-count":45,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T00:00:00Z","timestamp":1561248000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Innovation Program of Shanghai Municipal Education Commission"},{"name":"Fundamental Research Funds for the Central Universities"},{"name":"Research Grant Council of Hong Kong, GRF Project","award":["16215717, 16243516"],"award-info":[{"award-number":["16215717, 16243516"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,6,23]]},"DOI":"10.1145\/3313276.3316331","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T08:19:08Z","timestamp":1561018748000},"page":"674-685","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Tight approximation ratio of anonymous pricing"],"prefix":"10.1145","author":[{"given":"Yaonan","family":"Jin","sequence":"first","affiliation":[{"name":"Columbia University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pinyan","family":"Lu","sequence":"additional","affiliation":[{"name":"Shanghai University of Finance and Economics, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Qi","family":"Qi","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhihao Gavin","family":"Tang","sequence":"additional","affiliation":[{"name":"Shanghai University of Finance and Economics, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tao","family":"Xiao","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,6,23]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055479"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.73"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.92"},{"key":"e_1_3_2_1_4_1","unstructured":"Yossi Azar Ashish Chiplunkar and Haim Kaplan. 2018.  Yossi Azar Ashish Chiplunkar and Haim Kaplan. 2018."},{"key":"e_1_3_2_1_5_1","volume-title":"Proceedings of the 2018 ACM Conference on Economics and Computation","author":"Secretary Prophet","year":"2018","unstructured":"Prophet Secretary : Surpassing the 1-1\/e Barrier . In Proceedings of the 2018 ACM Conference on Economics and Computation , Ithaca, NY, USA , June 18-22, 2018 . 303\u2013318. Prophet Secretary: Surpassing the 1-1\/e Barrier. In Proceedings of the 2018 ACM Conference on Economics and Computation, Ithaca, NY, USA, June 18-22, 2018. 303\u2013318."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055426"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.11"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1386790.1386801"},{"key":"e_1_3_2_1_9_1","unstructured":"1386801 STOC \u201919 June 23\u201326 2019 Phoenix AZ USA Jin etal  1386801 STOC \u201919 June 23\u201326 2019 Phoenix AZ USA Jin et al."},{"key":"e_1_3_2_1_10_1","unstructured":"Patrick Briest. 2008.  Patrick Briest. 2008."},{"key":"e_1_3_2_1_11_1","volume-title":"35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games. 808\u2013819","author":"Uniform","unstructured":"Uniform Budgets and the Envy-Free Pricing Problem. In Automata, Languages and Programming , 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games. 808\u2013819 . 978- 3- 540- 70575- 8_66 Uniform Budgets and the Envy-Free Pricing Problem. In Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games. 808\u2013819. 978- 3- 540- 70575- 8_66"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2015.02.003"},{"key":"e_1_3_2_1_13_1","volume-title":"Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016","author":"Cai Yang","year":"2016","unstructured":"Yang Cai , Nikhil R. Devanur , and S. Matthew Weinberg . 2016. A duality based unified approach to Bayesian mechanism design . In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016 , Cambridge, MA, USA , June 18-21, 2016 . 926\u2013939. Yang Cai, Nikhil R. Devanur, and S. Matthew Weinberg. 2016. A duality based unified approach to Bayesian mechanism design. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016. 926\u2013939."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055465"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2365772"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250910.1250946"},{"key":"e_1_3_2_1_17_1","unstructured":"Shuchi Chawla Jason D. Hartline David L. Malec and Balasubramanian Sivan. 2010.  Shuchi Chawla Jason D. Hartline David L. Malec and Balasubramanian Sivan. 2010."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806733"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2012.08.010"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.93"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2018.03.016"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175438"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3033274.3085137"},{"key":"e_1_3_2_1_24_1","unstructured":"3085137  3085137"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2018.11.010"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634170"},{"key":"e_1_3_2_1_27_1","volume-title":"Revenue Gaps for Static and Dynamic Posted Pricing of Homogeneous Goods. CoRR abs\/1607.07105","author":"D\u00fctting Paul","year":"2016","unstructured":"Paul D\u00fctting , Felix A. Fischer , and Max Klimm . 2016. Revenue Gaps for Static and Dynamic Posted Pricing of Homogeneous Goods. CoRR abs\/1607.07105 ( 2016 ). Paul D\u00fctting, Felix A. Fischer, and Max Klimm. 2016. Revenue Gaps for Static and Dynamic Posted Pricing of Homogeneous Goods. CoRR abs\/1607.07105 (2016)."},{"key":"e_1_3_2_1_28_1","unstructured":"arXiv: 1607.07105 http:\/\/arxiv.org\/abs\/1607.07105  arXiv: 1607.07105 http:\/\/arxiv.org\/abs\/1607.07105"},{"key":"e_1_3_2_1_29_1","volume-title":"Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005","author":"Guruswami Venkatesan","year":"2005","unstructured":"Venkatesan Guruswami , Jason D. Hartline , Anna R. Karlin , David Kempe , Claire Kenyon , and Frank McSherry . 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\u20131173. http:\/\/dl.acm.org\/citation.cfm?id=1070432.1070598 Venkatesan Guruswami, Jason D. Hartline, Anna R. Karlin, David Kempe, Claire Kenyon, and Frank McSherry. 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\u20131173. http:\/\/dl.acm.org\/citation.cfm?id=1070432.1070598"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764468.2764498"},{"key":"e_1_3_2_1_31_1","unstructured":"2764498  2764498"},{"key":"e_1_3_2_1_32_1","unstructured":"Mohammad Taghi Hajiaghayi Robert D. Kleinberg and Tuomas Sandholm. 2007.  Mohammad Taghi Hajiaghayi Robert D. Kleinberg and Tuomas Sandholm. 2007."},{"key":"e_1_3_2_1_33_1","volume-title":"Online Mechanism Design and Prophet Inequalities. In Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence","author":"Automated","year":"2007","unstructured":"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\u201365. http:\/\/www.aaai.org\/Library\/AAAI\/ 2007\/aaai07- 009.php 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\u201365. http:\/\/www.aaai.org\/Library\/AAAI\/ 2007\/aaai07- 009.php"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229061"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492002.2482544"},{"key":"e_1_3_2_1_36_1","volume-title":"Mechanism design and approximation. Book draft. October 122","author":"Hartline Jason D","year":"2013","unstructured":"Jason D Hartline . 2013. Mechanism design and approximation. Book draft. October 122 ( 2013 ). Jason D Hartline. 2013. Mechanism design and approximation. Book draft. October 122 (2013)."},{"key":"e_1_3_2_1_37_1","volume-title":"Proceedings 10th ACM Conference on Electronic Commerce (EC-2009)","author":"Jason","year":"2009","unstructured":"Jason D. Hartline and Tim Roughgarden. 2009. Simple versus optimal mechanisms . In Proceedings 10th ACM Conference on Electronic Commerce (EC-2009) , Stanford, California, USA, July 6\u201310 , 2009 . 225\u2013234. 1566374.1566407 Jason D. Hartline and Tim Roughgarden. 2009. Simple versus optimal mechanisms. In Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), Stanford, California, USA, July 6\u201310, 2009. 225\u2013234. 1566374.1566407"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.14"},{"key":"e_1_3_2_1_39_1","unstructured":"Brendan Lucier. 2017.  Brendan Lucier. 2017."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3144722.3144725"},{"key":"e_1_3_2_1_41_1","unstructured":"Mehryar Mohri and Andres Mu\u00f1oz Medina. 2016.  Mehryar Mohri and Andres Mu\u00f1oz Medina. 2016."},{"key":"e_1_3_2_1_42_1","volume-title":"Journal of Machine Learning Research 17","author":"Second-Price Learning Algorithms","year":"2016","unstructured":"Learning Algorithms for Second-Price Auctions with Reserve . Journal of Machine Learning Research 17 ( 2016 ), 74:1\u201374:25. http:\/\/jmlr.org\/papers\/v17\/14- 499.html Learning Algorithms for Second-Price Auctions with Reserve. Journal of Machine Learning Research 17 (2016), 74:1\u201374:25. http:\/\/jmlr.org\/papers\/v17\/14- 499.html"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.1.58"},{"key":"e_1_3_2_1_44_1","unstructured":"Aviad Rubinstein. 2016.  Aviad Rubinstein. 2016."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2840728.2840736"}],"event":{"name":"STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing","location":"Phoenix AZ USA","acronym":"STOC '19","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316331","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316331","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:54:32Z","timestamp":1750190072000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316331"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,23]]},"references-count":45,"alternative-id":["10.1145\/3313276.3316331","10.1145\/3313276"],"URL":"https:\/\/doi.org\/10.1145\/3313276.3316331","relation":{},"subject":[],"published":{"date-parts":[[2019,6,23]]},"assertion":[{"value":"2019-06-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}