{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:43:19Z","timestamp":1773481399871,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":35,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"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":[],"published-print":{"date-parts":[[2022,6,9]]},"DOI":"10.1145\/3519935.3520029","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"704-717","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Computing simple mechanisms: Lift-and-round over marginal reduced forms"],"prefix":"10.1145","author":[{"given":"Yang","family":"Cai","sequence":"first","affiliation":[{"name":"Yale University, USA"}]},{"given":"Argyris","family":"Oikonomou","sequence":"additional","affiliation":[{"name":"Yale University, USA"}]},{"given":"Mingfei","family":"Zhao","sequence":"additional","affiliation":[{"name":"Google Research, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.90"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229017"},{"key":"e_1_3_2_1_3_1","volume-title":"the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS).","author":"Babaioff Moshe","unstructured":"Moshe Babaioff , Nicole Immorlica , Brendan Lucier , and S. Matthew Weinberg . 2014. A Simple and Approximately Optimal Mechanism for an Additive Buyer . In the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS). Moshe Babaioff, Nicole Immorlica, Brendan Lucier, and S. Matthew Weinberg. 2014. A Simple and Approximately Optimal Mechanism for an Additive Buyer. In the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS)."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3391403.3399541"},{"key":"e_1_3_2_1_5_1","volume-title":"Extreme-Value Theorems for Optimal Multidimensional Pricing. In the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS).","author":"Cai Yang","year":"2011","unstructured":"Yang Cai and Constantinos Daskalakis . 2011 . Extreme-Value Theorems for Optimal Multidimensional Pricing. In the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS). Yang Cai and Constantinos Daskalakis. 2011. Extreme-Value Theorems for Optimal Multidimensional Pricing. In the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS)."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.54"},{"key":"e_1_3_2_1_7_1","volume-title":"Recommender Systems meet Mechanism Design. arXiv preprint arXiv:2110","author":"Cai Yang","year":"2021","unstructured":"Yang Cai and Constantinos Daskalakis . 2021 . Recommender Systems meet Mechanism Design. arXiv preprint arXiv:2110 .12558. Yang Cai and Constantinos Daskalakis. 2021. Recommender Systems meet Mechanism Design. arXiv preprint arXiv:2110.12558."},{"key":"e_1_3_2_1_8_1","volume-title":"An Algorithmic Characterization of Multi-Dimensional Mechanisms. In the 44th Annual ACM Symposium on Theory of Computing (STOC).","author":"Cai Yang","unstructured":"Yang Cai , Constantinos Daskalakis , and S. Matthew Weinberg . 2012 . An Algorithmic Characterization of Multi-Dimensional Mechanisms. In the 44th Annual ACM Symposium on Theory of Computing (STOC). Yang Cai, Constantinos Daskalakis, and S. Matthew Weinberg. 2012. An Algorithmic Characterization of Multi-Dimensional Mechanisms. In the 44th Annual ACM Symposium on Theory of Computing (STOC)."},{"key":"e_1_3_2_1_9_1","volume-title":"the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS).","author":"Cai Yang","unstructured":"Yang Cai , Constantinos Daskalakis , and S. Matthew Weinberg . 2012. Optimal Multi-Dimensional Mechanism Design: Reducing Revenue to Welfare Maximization . In the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS). Yang Cai, Constantinos Daskalakis, and S. Matthew Weinberg. 2012. Optimal Multi-Dimensional Mechanism Design: Reducing Revenue to Welfare Maximization. In the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS)."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Yang Cai Constantinos Daskalakis and S. Matthew Weinberg. 2012. Optimal Multi-Dimensional Mechanism Design: Reducing Revenue to Welfare Maximization. arxiv report http:\/\/arxiv.org\/abs\/1207.5518  Yang Cai Constantinos Daskalakis and S. Matthew Weinberg. 2012. Optimal Multi-Dimensional Mechanism Design: Reducing Revenue to Welfare Maximization. arxiv report http:\/\/arxiv.org\/abs\/1207.5518","DOI":"10.1109\/FOCS.2012.88"},{"key":"e_1_3_2_1_11_1","volume-title":"the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).","author":"Cai Yang","unstructured":"Yang Cai , Constantinos Daskalakis , and S. Matthew Weinberg . 2013. Reducing Revenue to Welfare Maximization : Approximation Algorithms and other Generalizations . In the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Yang Cai, Constantinos Daskalakis, and S. Matthew Weinberg. 2013. Reducing Revenue to Welfare Maximization : Approximation Algorithms and other Generalizations. In the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)."},{"key":"e_1_3_2_1_12_1","volume-title":"the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS).","author":"Cai Yang","unstructured":"Yang Cai , Constantinos Daskalakis , and S. Matthew Weinberg . 2013. Understanding Incentives: Mechanism Design becomes Algorithm Design . In the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS). Yang Cai, Constantinos Daskalakis, and S. Matthew Weinberg. 2013. Understanding Incentives: Mechanism Design becomes Algorithm Design. In the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS)."},{"key":"e_1_3_2_1_13_1","volume-title":"the 48th Annual ACM Symposium on Theory of Computing (STOC).","author":"Cai Yang","unstructured":"Yang Cai , Nikhil R. Devanur , and S. Matthew Weinberg . 2016. A Duality Based Unified Approach to Bayesian Mechanism Design . In the 48th Annual ACM Symposium on Theory of Computing (STOC). Yang Cai, Nikhil R. Devanur, and S. Matthew Weinberg. 2016. A Duality Based Unified Approach to Bayesian Mechanism Design. In the 48th Annual ACM Symposium on Theory of Computing (STOC)."},{"key":"e_1_3_2_1_14_1","volume-title":"Simple and Nearly Optimal Multi-Item Auctions. In the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).","author":"Cai Yang","year":"2013","unstructured":"Yang Cai and Zhiyi Huang . 2013 . Simple and Nearly Optimal Multi-Item Auctions. In the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Yang Cai and Zhiyi Huang. 2013. Simple and Nearly Optimal Multi-Item Auctions. In the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3465456.3467643"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.81"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055465"},{"key":"e_1_3_2_1_18_1","volume-title":"Sequential Posted Pricing and Multi-parameter Mechanism Design. CoRR, abs\/0907.2435","author":"Chawla Shuchi","year":"2010","unstructured":"Shuchi Chawla , Jason Hartline , David Malec , and Balasubramanian Sivan . 2010. Sequential Posted Pricing and Multi-parameter Mechanism Design. CoRR, abs\/0907.2435 ( 2010 ), arxiv:0907.2435. Shuchi Chawla, Jason Hartline, David Malec, and Balasubramanian Sivan. 2010. Sequential Posted Pricing and Multi-parameter Mechanism Design. CoRR, abs\/0907.2435 (2010), arxiv:0907.2435."},{"key":"e_1_3_2_1_19_1","volume-title":"the 8th ACM Conference on Electronic Commerce (EC).","author":"Chawla Shuchi","unstructured":"Shuchi Chawla , Jason D. Hartline , and Robert D. Kleinberg . 2007. Algorithmic Pricing via Virtual Valuations . In the 8th ACM Conference on Electronic Commerce (EC). Shuchi Chawla, Jason D. Hartline, and Robert D. Kleinberg. 2007. Algorithmic Pricing via Virtual Valuations. In the 8th ACM Conference on Electronic Commerce (EC)."},{"key":"e_1_3_2_1_20_1","volume-title":"Multi-Parameter Mechanism Design and Sequential Posted Pricing. In the 42nd ACM Symposium on Theory of Computing (STOC).","author":"Chawla Shuchi","year":"2010","unstructured":"Shuchi Chawla , Jason D. Hartline , David L. Malec , and Balasubramanian Sivan . 2010 . Multi-Parameter Mechanism Design and Sequential Posted Pricing. In the 42nd ACM Symposium on Theory of Computing (STOC). Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan. 2010. Multi-Parameter Mechanism Design and Sequential Posted Pricing. In the 42nd ACM Symposium on Theory of Computing (STOC)."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2012.08.010"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2940716.2940756"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.93"},{"key":"e_1_3_2_1_24_1","volume-title":"The Complexity of Optimal Mechanism Design. In the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).","author":"Daskalakis Constantinos","year":"2014","unstructured":"Constantinos Daskalakis , Alan Deckelbaum , and Christos Tzamos . 2014 . The Complexity of Optimal Mechanism Design. In the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Constantinos Daskalakis, Alan Deckelbaum, and Christos Tzamos. 2014. The Complexity of Optimal Mechanism Design. In the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.130"},{"key":"e_1_3_2_1_26_1","volume-title":"Symmetries and Optimal Multi-Dimensional Mechanism Design. In the 13th ACM Conference on Electronic Commerce (EC).","author":"Daskalakis Constantinos","unstructured":"Constantinos Daskalakis and S. Matthew Weinberg . 2012 . Symmetries and Optimal Multi-Dimensional Mechanism Design. In the 13th ACM Conference on Electronic Commerce (EC). Constantinos Daskalakis and S. Matthew Weinberg. 2012. Symmetries and Optimal Multi-Dimensional Mechanism Design. In the 13th ACM Conference on Electronic Commerce (EC)."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00037"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177728174"},{"key":"e_1_3_2_1_29_1","volume-title":"Approximate Revenue Maximization with Multiple Items. In the 13th ACM Conference on Electronic Commerce (EC).","author":"Hart Sergiu","year":"2012","unstructured":"Sergiu Hart and Noam Nisan . 2012 . Approximate Revenue Maximization with Multiple Items. In the 13th ACM Conference on Electronic Commerce (EC). Sergiu Hart and Noam Nisan. 2012. Approximate Revenue Maximization with Multiple Items. In the 13th ACM Conference on Electronic Commerce (EC)."},{"key":"e_1_3_2_1_30_1","volume-title":"Matroid Prophet Inequalities. In the 44th Annual ACM Symposium on Theory of Computing (STOC).","author":"Kleinberg Robert","unstructured":"Robert Kleinberg and S. Matthew Weinberg . 2012 . Matroid Prophet Inequalities. In the 44th Annual ACM Symposium on Theory of Computing (STOC). Robert Kleinberg and S. Matthew Weinberg. 2012. Matroid Prophet Inequalities. In the 44th Annual ACM Symposium on Theory of Computing (STOC)."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00023"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.1.58"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2840728.2840736"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764468.2764510"},{"key":"e_1_3_2_1_35_1","unstructured":"Andrew Chi-Chih Yao. 2015. An n-to-1 Bidder Reduction for Multi-item Auctions and its Applications. In SODA. CoRR arxiv:1406.3278  Andrew Chi-Chih Yao. 2015. An n-to-1 Bidder Reduction for Multi-item Auctions and its Applications. In SODA. CoRR arxiv:1406.3278"}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","location":"Rome Italy","acronym":"STOC '22","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520029","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3520029","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:31:15Z","timestamp":1750188675000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520029"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":35,"alternative-id":["10.1145\/3519935.3520029","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3520029","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}