{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:54:08Z","timestamp":1787388848328,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":58,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"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":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384267","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"1073-1085","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Separating the communication complexity of truthful and non-truthful combinatorial auctions"],"prefix":"10.1145","author":[{"given":"Sepehr","family":"Assadi","sequence":"first","affiliation":[{"name":"Rutgers University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hrishikesh","family":"Khandeparkar","sequence":"additional","affiliation":[{"name":"Princeton University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Raghuvansh R.","family":"Saxena","sequence":"additional","affiliation":[{"name":"Princeton University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S. Matthew","family":"Weinberg","sequence":"additional","affiliation":[{"name":"Princeton University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"[AS19] Sepehr Assadi and Sahil Singla. Improved truthful mechanisms for  [AS19] Sepehr Assadi and Sahil Singla. Improved truthful mechanisms for"},{"key":"e_1_3_2_1_2_1","unstructured":"Sixtieth Annual IEEE Foundations of Computer Science (FOCS) 2019. [BDF+10] David Buchfuhrer Shaddin Dughmi Hu Fu Robert Kleinberg Elchanan  Sixtieth Annual IEEE Foundations of Computer Science (FOCS) 2019. [BDF+10] David Buchfuhrer Shaddin Dughmi Hu Fu Robert Kleinberg Elchanan"},{"key":"e_1_3_2_1_3_1","unstructured":"on Discrete Algorithms (SODA) 2010. [BMW18] Mark Braverman Jieming Mao and S. Matthew Weinberg. On simultaneous  on Discrete Algorithms (SODA) 2010. [BMW18] Mark Braverman Jieming Mao and S. Matthew Weinberg. On simultaneous"},{"key":"e_1_3_2_1_4_1","volume-title":"ACM-SIAM Symposium on Discrete Algorithms, SODA","author":"Annual","year":"2018","unstructured":"Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 , New Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New"},{"key":"e_1_3_2_1_5_1","unstructured":"Orleans LA USA January 7-10 2018 pages 2256-2273 2018.  Orleans LA USA January 7-10 2018 pages 2256-2273 2018."},{"key":"e_1_3_2_1_6_1","unstructured":"[Cla71] Edward H. Clarke. Multipart Pricing of Public Goods. Public Choice [Cla71] Edward H. Clarke. Multipart Pricing of Public Goods. Public Choice"},{"key":"e_1_3_2_1_7_1","unstructured":"[CT06] Thomas M. Cover and Joy A. Thomas. Elements of information theory (2.  [CT06] Thomas M. Cover and Joy A. Thomas. Elements of information theory (2."},{"key":"e_1_3_2_1_8_1","unstructured":"ed.). Wiley 2006. [CTW20] Linda Cai Clayton Thomas and S. Matthew Weinberg. Implementation  ed.). Wiley 2006. [CTW20] Linda Cai Clayton Thomas and S. Matthew Weinberg. Implementation"},{"key":"e_1_3_2_1_9_1","volume-title":"Proceedings of the 11th Innovations","unstructured":"when demand queries are np-hard . In Proceedings of the 11th Innovations when demand queries are np-hard. In Proceedings of the 11th Innovations"},{"key":"e_1_3_2_1_10_1","volume-title":"Theoretical Computer Science Conference, (ITCS)","year":"2020","unstructured":"in Theoretical Computer Science Conference, (ITCS) , 2020 . in Theoretical Computer Science Conference, (ITCS), 2020."},{"key":"e_1_3_2_1_11_1","unstructured":"[DN11] Shahar Dobzinski and Noam Nisan. Limitations of vcg-based mechanisms.  [DN11] Shahar Dobzinski and Noam Nisan. Limitations of vcg-based mechanisms."},{"key":"e_1_3_2_1_12_1","volume-title":"379-396","author":"Combinatorica","year":"2011","unstructured":"Combinatorica , 31 ( 4 ) : 379-396 , 2011 . Combinatorica, 31 ( 4 ): 379-396, 2011."},{"key":"e_1_3_2_1_13_1","unstructured":"[DN15] Shahar Dobzinski and Noam Nisan. Multi-unit auctions: Beyond roberts. J.  [DN15] Shahar Dobzinski and Noam Nisan. Multi-unit auctions: Beyond roberts. J."},{"key":"e_1_3_2_1_14_1","volume-title":"14-44","author":"Economic Theory","year":"2015","unstructured":"Economic Theory , 156 : 14-44 , 2015 . [DNS10] Shahar Dobzinski, Noam Nisan , and Michael Schapira. Approximation Economic Theory, 156 : 14-44, 2015. [DNS10] Shahar Dobzinski, Noam Nisan, and Michael Schapira. Approximation"},{"key":"e_1_3_2_1_15_1","first-page":"1","volume":"35","author":"Oper","year":"2010","unstructured":"Oper . Res. , 35 ( 1 ): 1 - 13 , 2010 . [Dob07] Shahar Dobzinski. Two randomized mechanisms for combinatorial auctions. Oper. Res., 35 ( 1 ): 1-13, 2010. [Dob07] Shahar Dobzinski. Two randomized mechanisms for combinatorial auctions.","journal-title":"Res."},{"key":"e_1_3_2_1_16_1","volume-title":"Proceedings of the 10th International Workshop on Approximation and","author":"In","unstructured":"In Proceedings of the 10th International Workshop on Approximation and In Proceedings of the 10th International Workshop on Approximation and"},{"key":"e_1_3_2_1_17_1","volume-title":"11th International Workshop on Randomization, and Combinatorial","unstructured":"the 11th International Workshop on Randomization, and Combinatorial the 11th International Workshop on Randomization, and Combinatorial"},{"key":"e_1_3_2_1_18_1","first-page":"89","volume-title":"Algorithms and Techniques","author":"Optimization","year":"2007","unstructured":"Optimization . Algorithms and Techniques , pages 89 - 103 , 2007 . [Dob11] Shahar Dobzinski. An Impossibility Result for Truthful Combinatorial Optimization. Algorithms and Techniques, pages 89-103, 2007. [Dob11] Shahar Dobzinski. An Impossibility Result for Truthful Combinatorial"},{"key":"e_1_3_2_1_19_1","volume-title":"Submodular Valuations. In Proceedings of the 43rd ACM","author":"Auctions","unstructured":"Auctions with Submodular Valuations. In Proceedings of the 43rd ACM Auctions with Submodular Valuations. In Proceedings of the 43rd ACM"},{"key":"e_1_3_2_1_20_1","unstructured":"Symposium on Theory of Computing (STOC) 2011. [Dob16a] Shahar Dobzinski. Breaking the logarithmic barrier for truthful  Symposium on Theory of Computing (STOC) 2011. [Dob16a] Shahar Dobzinski. Breaking the logarithmic barrier for truthful"},{"key":"e_1_3_2_1_21_1","volume-title":"Annual ACM SIGACT Symposium on Theory of Computing, STOC","year":"2016","unstructured":"48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016 , 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016,"},{"key":"e_1_3_2_1_22_1","unstructured":"pages 940-948 New York NY USA 2016. ACM. [Dob16b] Shahar Dobzinski. Computational eficiency requires simple taxation. In  pages 940-948 New York NY USA 2016. ACM. [Dob16b] Shahar Dobzinski. Computational eficiency requires simple taxation. In"},{"key":"e_1_3_2_1_23_1","unstructured":"FOCS 2016. [DSS15] Amit Daniely Michael Schapira and Gal Shahaf. Inapproximability  FOCS 2016. [DSS15] Amit Daniely Michael Schapira and Gal Shahaf. Inapproximability"},{"key":"e_1_3_2_1_24_1","first-page":"401","volume-title":"STOC 2015","author":"Computing","year":"2015","unstructured":"of Computing , STOC 2015 , Portland, OR, USA , June 14-17, 2015 , pages 401 - of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 401-"},{"key":"e_1_3_2_1_25_1","unstructured":"[DV11] Shaddin Dughmi and Jan Vondrak. Limitations of Randomized Mechanisms  [DV11] Shaddin Dughmi and Jan Vondrak. Limitations of Randomized Mechanisms"},{"key":"e_1_3_2_1_26_1","volume-title":"Combinatorial Auctions. In 52nd Annual Symposium on Foundations of","unstructured":"for Combinatorial Auctions. In 52nd Annual Symposium on Foundations of for Combinatorial Auctions. In 52nd Annual Symposium on Foundations of"},{"key":"e_1_3_2_1_27_1","unstructured":"Computer Science (FOCS) 2011. [DV12a] Shahar Dobzinski and Jan Vondr\u00e1k. From query complexity to  Computer Science (FOCS) 2011. [DV12a] Shahar Dobzinski and Jan Vondr\u00e1k. From query complexity to"},{"key":"e_1_3_2_1_28_1","volume-title":"Proceedings of the 44th Symposium on Theory","unstructured":"computational complexity. In Proceedings of the 44th Symposium on Theory computational complexity. In Proceedings of the 44th Symposium on Theory"},{"key":"e_1_3_2_1_29_1","unstructured":"of Computing (STOC) 2012. [DV12b] Shahar Dobzinski and Jan Vondrak. The Computational Complexity  of Computing (STOC) 2012. [DV12b] Shahar Dobzinski and Jan Vondrak. The Computational Complexity"},{"key":"e_1_3_2_1_30_1","unstructured":"Conference on Electronic Commerce (EC) 2012.  Conference on Electronic Commerce (EC) 2012."},{"key":"e_1_3_2_1_31_1","unstructured":"[DV16] Shahar Dobzinski and Jan Vondr\u00e1k. Impossibility results for truthful  [DV16] Shahar Dobzinski and Jan Vondr\u00e1k. Impossibility results for truthful"},{"key":"e_1_3_2_1_32_1","unstructured":"combinatorial auctions with submodular valuations. J. ACM 63 ( 1 ):5: 1-5 : 19 combinatorial auctions with submodular valuations. J. ACM 63 ( 1 ):5: 1-5 : 19"},{"key":"e_1_3_2_1_33_1","unstructured":"2016. [EFN+19] Tomer Ezra Michal Feldman Eric Neyman Inbal Talgam-Cohen and  2016. [EFN+19] Tomer Ezra Michal Feldman Eric Neyman Inbal Talgam-Cohen and"},{"key":"e_1_3_2_1_34_1","volume-title":"the 60th Annual","unstructured":"combinatorial auctions with two subadditive buyers. In the 60th Annual combinatorial auctions with two subadditive buyers. In the 60th Annual"},{"key":"e_1_3_2_1_35_1","volume-title":"Symposium on Foundations of Computer Science (FOCS)","author":"IEEE","year":"2019","unstructured":"IEEE Symposium on Foundations of Computer Science (FOCS) , 2019 . IEEE Symposium on Foundations of Computer Science (FOCS), 2019."},{"key":"e_1_3_2_1_36_1","unstructured":"[Fei09] Uriel Feige. On maximizing welfare when utility functions are subadditive.  [Fei09] Uriel Feige. On maximizing welfare when utility functions are subadditive."},{"key":"e_1_3_2_1_37_1","first-page":"122","volume":"39","author":"SIAM","year":"2009","unstructured":"SIAM J. Comput. , 39 ( 1 ): 122 - 142 , 2009 . SIAM J. Comput., 39 ( 1 ): 122-142, 2009.","journal-title":"J. Comput."},{"key":"e_1_3_2_1_38_1","unstructured":"[FV10] Uriel Feige and Jan Vondr\u00e1k. The submodular welfare problem with demand  [FV10] Uriel Feige and Jan Vondr\u00e1k. The submodular welfare problem with demand"},{"key":"e_1_3_2_1_39_1","volume-title":"Theory of Computing, 6 ( 1 ): 247-290","year":"2010","unstructured":"queries. Theory of Computing, 6 ( 1 ): 247-290 , 2010 . [Gro73] Theodore Groves. Incentives in Teams. Econometrica , 41 ( 4 ): 617-631, 1973. queries. Theory of Computing, 6 ( 1 ): 247-290, 2010. [Gro73] Theodore Groves. Incentives in Teams. Econometrica, 41 ( 4 ): 617-631, 1973."},{"key":"e_1_3_2_1_40_1","unstructured":"[KV12] Piotr Krysta and Berthold V\u00f6cking. Online mechanism design (randomized  [KV12] Piotr Krysta and Berthold V\u00f6cking. Online mechanism design (randomized"},{"key":"e_1_3_2_1_41_1","unstructured":"636-647. Springer 2012. [LOS02] Daniel Lehmann Liadan O'Callaghan and Yoav Shoham. Truth revelation  636-647. Springer 2012. [LOS02] Daniel Lehmann Liadan O'Callaghan and Yoav Shoham. Truth revelation"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"crossref","unstructured":"in approximately eficient combinatorial auctions. J. ACM 49 ( 5 ): 577-602 in approximately eficient combinatorial auctions. J. ACM 49 ( 5 ): 577-602","DOI":"10.1145\/585265.585266"},{"key":"e_1_3_2_1_43_1","unstructured":"[LS05] Ron Lavi and Chaitanya Swamy. Truthful and near-optimal mechanism  [LS05] Ron Lavi and Chaitanya Swamy. Truthful and near-optimal mechanism"},{"key":"e_1_3_2_1_44_1","volume-title":"Proceedings of the 46th Annual IEEE","unstructured":"design via linear programming . In Proceedings of the 46th Annual IEEE design via linear programming. In Proceedings of the 46th Annual IEEE"},{"key":"e_1_3_2_1_45_1","unstructured":"Symposium on Foundations of Computer Science (FOCS) 2005. [MSV08] Vahab S. Mirrokni Michael Schapira and Jan Vondr\u00e1k. Tight information-  Symposium on Foundations of Computer Science (FOCS) 2005. [MSV08] Vahab S. Mirrokni Michael Schapira and Jan Vondr\u00e1k. Tight information-"},{"key":"e_1_3_2_1_46_1","volume-title":"Proceedings 9th ACM Conference on Electronic Commerce (EC-2008)","author":"In","unstructured":"In Proceedings 9th ACM Conference on Electronic Commerce (EC-2008) , In Proceedings 9th ACM Conference on Electronic Commerce (EC-2008),"},{"key":"e_1_3_2_1_47_1","unstructured":"Chicago IL USA June 8-12 2008 pages 70-77 2008.  Chicago IL USA June 8-12 2008 pages 70-77 2008."},{"key":"e_1_3_2_1_48_1","unstructured":"[NS06] Noam Nisan and Ilya Segal. The communication requirements of eficient  [NS06] Noam Nisan and Ilya Segal. The communication requirements of eficient"},{"key":"e_1_3_2_1_49_1","volume-title":"Economic Theory, 129 ( 1 ): 192-224","year":"2006","unstructured":"allocations and supporting prices. J. Economic Theory, 129 ( 1 ): 192-224 , 2006 . allocations and supporting prices. J. Economic Theory, 129 ( 1 ): 192-224, 2006."},{"key":"e_1_3_2_1_50_1","unstructured":"[PS97] Alessandro Panconesi and Aravind Srinivasan. Randomized distributed  [PS97] Alessandro Panconesi and Aravind Srinivasan. Randomized distributed"},{"key":"e_1_3_2_1_51_1","volume-title":"350-368","author":"Comput","year":"1997","unstructured":"Comput ., 26 ( 2 ) : 350-368 , 1997 . [Rag88] Prabhakar Raghavan. Probabilistic construction of deterministic algorithms: Comput., 26 ( 2 ): 350-368, 1997. [Rag88] Prabhakar Raghavan. Probabilistic construction of deterministic algorithms:"},{"key":"e_1_3_2_1_52_1","first-page":"130","volume":"37","author":"Approximating","unstructured":"Approximating packing integer programs. J. Comput. Syst. Sci. , 37 ( 2 ): 130 - Approximating packing integer programs. J. Comput. Syst. Sci., 37 ( 2 ): 130-","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_3_2_1_53_1","unstructured":"143 October 1988.  143 October 1988."},{"key":"e_1_3_2_1_54_1","unstructured":"[Vic61] William Vickrey. Counterspeculations Auctions and Competitive Sealed  [Vic61] William Vickrey. Counterspeculations Auctions and Competitive Sealed"},{"key":"e_1_3_2_1_55_1","volume-title":"Journal of Finance, 16 ( 1 ): 8-37","author":"Tenders","year":"1961","unstructured":"Tenders . Journal of Finance, 16 ( 1 ): 8-37 , 1961 . [Von08] Jan Vondr\u00e1k. Optimal approximation for the submodular welfare problem Tenders. Journal of Finance, 16 ( 1 ): 8-37, 1961. [Von08] Jan Vondr\u00e1k. Optimal approximation for the submodular welfare problem"},{"key":"e_1_3_2_1_56_1","volume-title":"Proceedings of the 40th Annual ACM Symposium","unstructured":"in the value oracle model . In Proceedings of the 40th Annual ACM Symposium in the value oracle model. In Proceedings of the 40th Annual ACM Symposium"},{"key":"e_1_3_2_1_57_1","unstructured":"on Theory of Computing Victoria British Columbia Canada May 17-20 on Theory of Computing Victoria British Columbia Canada May 17-20"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"crossref","unstructured":"2008 pages 67-74 2008.  2008 pages 67-74 2008.","DOI":"10.1016\/B978-012374215-5.50013-1"}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384267","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384267","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:12Z","timestamp":1750200072000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384267"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":58,"alternative-id":["10.1145\/3357713.3384267","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384267","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}