{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T11:36:28Z","timestamp":1770896188876,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":38,"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"}],"funder":[{"name":"ERC","award":["321171"],"award-info":[{"award-number":["321171"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384299","type":"proceedings-article","created":{"date-parts":[[2021,6,28]],"date-time":"2021-06-28T21:48:36Z","timestamp":1624916916000},"page":"1086-1096","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["On the Nisan-Ronen conjecture for submodular valuations"],"prefix":"10.1145","author":[{"given":"George","family":"Christodoulou","sequence":"first","affiliation":[{"name":"University of Liverpool, UK"}]},{"given":"Elias","family":"Koutsoupias","sequence":"additional","affiliation":[{"name":"University of Oxford, UK"}]},{"given":"Annam\u00e1ria","family":"Kov\u00e1cs","sequence":"additional","affiliation":[{"name":"Goethe University Frankfurt, Germany"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Truthful germs are contagious: A local-to-global characterization of truthfulness. Games and Economic Behavior 86 (","author":"Archer Aaron","year":"2014","unstructured":"Aaron Archer and Robert Kleinberg . 2014. Truthful germs are contagious: A local-to-global characterization of truthfulness. Games and Economic Behavior 86 ( Jul 2014 ), 340-366. Aaron Archer and Robert Kleinberg. 2014. Truthful germs are contagious: A local-to-global characterization of truthfulness. Games and Economic Behavior 86 ( Jul 2014 ), 340-366."},{"key":"e_1_3_2_1_2_1","volume-title":"Proc. of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS). 482-491","author":"Aaron","unstructured":"Aaron Archer and \u00c9va Tardos. 2001. Truthful Mechanisms for One-Parameter Agents .. In Proc. of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS). 482-491 . Aaron Archer and \u00c9va Tardos. 2001. Truthful Mechanisms for One-Parameter Agents.. In Proc. of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS). 482-491."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Itai Ashlagi Shahar Dobzinski and Ron Lavi. 2012. Optimal Lower Bounds for Anonymous Scheduling Mechanisms. Mathematics of Operations Research 37 2 ( 2012 ) 244-258.  Itai Ashlagi Shahar Dobzinski and Ron Lavi. 2012. Optimal Lower Bounds for Anonymous Scheduling Mechanisms. Mathematics of Operations Research 37 2 ( 2012 ) 244-258.","DOI":"10.1287\/moor.1110.0534"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Vincenzo Auletta George Christodoulou and Paolo Penna. 2015. Mechanisms for Scheduling with Single-Bit Private Values. Theory Comput. Syst. 57 3 ( 2015 ) 523-548.  Vincenzo Auletta George Christodoulou and Paolo Penna. 2015. Mechanisms for Scheduling with Single-Bit Private Values. Theory Comput. Syst. 57 3 ( 2015 ) 523-548.","DOI":"10.1007\/s00224-015-9625-5"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1468-0262.2006.00695.x"},{"key":"e_1_3_2_1_6_1","first-page":"51","article-title":"Prior-independent mechanisms for scheduling","author":"Chawla Shuchi","year":"2013","unstructured":"Shuchi Chawla , Jason D. Hartline , David L. Malec , and Balasubramanian Sivan . 2013 . Prior-independent mechanisms for scheduling . In STOC. ACM , 51 - 60 . Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan. 2013. Prior-independent mechanisms for scheduling. In STOC. ACM, 51-60.","journal-title":"STOC. ACM"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Xujin Chen Donglei Du and Luis Fernando Zuluaga. 2015. Copula-based Randomized Mechanisms for Truthful Scheduling on Two Unrelated Machines. Theory Comput. Syst. 57 3 ( 2015 ) 753-781.  Xujin Chen Donglei Du and Luis Fernando Zuluaga. 2015. Copula-based Randomized Mechanisms for Truthful Scheduling on Two Unrelated Machines. Theory Comput. Syst. 57 3 ( 2015 ) 753-781.","DOI":"10.1007\/s00224-014-9601-5"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721854"},{"key":"e_1_3_2_1_9_1","volume-title":"On the Nisan-Ronen conjecture for submodular valuations. arXiv","author":"Christodoulou George","year":"1907","unstructured":"George Christodoulou , Elias Koutsoupias , and Annamaria Kovacs . 2019. On the Nisan-Ronen conjecture for submodular valuations. arXiv : 1907 . 12733v1 [cs.GT] George Christodoulou, Elias Koutsoupias, and Annamaria Kovacs. 2019. On the Nisan-Ronen conjecture for submodular valuations. arXiv: 1907. 12733v1 [cs.GT]"},{"key":"e_1_3_2_1_10_1","unstructured":"George Christodoulou Elias Koutsoupias and Annam\u00e1ria Kov\u00e1cs. 2020. Truthful graph balancing. ( 2020 ). Manuscript.  George Christodoulou Elias Koutsoupias and Annam\u00e1ria Kov\u00e1cs. 2020. Truthful graph balancing. ( 2020 ). Manuscript."},{"key":"e_1_3_2_1_11_1","volume-title":"ESA (Lecture Notes in Computer Science)","author":"Christodoulou George","unstructured":"George Christodoulou , Elias Koutsoupias , and Angelina Vidali . 2008. A Characterization of 2-Player Mechanisms for Scheduling . In ESA (Lecture Notes in Computer Science) , Vol. 5193 . Springer , 297-307. George Christodoulou, Elias Koutsoupias, and Angelina Vidali. 2008. A Characterization of 2-Player Mechanisms for Scheduling. In ESA (Lecture Notes in Computer Science), Vol. 5193. Springer, 297-307."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"crossref","unstructured":"George Christodoulou Elias Koutsoupias and Angelina Vidali. 2009. A Lower Bound for Scheduling Mechanisms. Algorithmica 55 4 ( 2009 ) 729-740.  George Christodoulou Elias Koutsoupias and Angelina Vidali. 2009. A Lower Bound for Scheduling Mechanisms. Algorithmica 55 4 ( 2009 ) 729-740.","DOI":"10.1007\/s00453-008-9165-3"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/120866038"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01726210"},{"key":"e_1_3_2_1_15_1","volume-title":"Bayesian Truthful Mechanisms for Job Scheduling from Bi-criterion Approximation Algorithms","author":"Daskalakis Constantinos","year":"1934","unstructured":"Constantinos Daskalakis and S. Matthew Weinberg . 2015. Bayesian Truthful Mechanisms for Job Scheduling from Bi-criterion Approximation Algorithms . In SODA. SIAM , 1934 -1952. Constantinos Daskalakis and S. Matthew Weinberg. 2015. Bayesian Truthful Mechanisms for Job Scheduling from Bi-criterion Approximation Algorithms. In SODA. SIAM, 1934-1952."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/080744992"},{"key":"e_1_3_2_1_17_1","first-page":"940","article-title":"Breaking the logarithmic barrier for truthful combinatorial auctions with submodular bidders","author":"Dobzinski Shahar","year":"2016","unstructured":"Shahar Dobzinski . 2016 . Breaking the logarithmic barrier for truthful combinatorial auctions with submodular bidders . In STOC. ACM , 940 - 948 . Shahar Dobzinski. 2016. Breaking the logarithmic barrier for truthful combinatorial auctions with submodular bidders. In STOC. ACM, 940-948.","journal-title":"STOC. ACM"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Shahar Dobzinski and Noam Nisan. 2015. Multi-unit auctions: Beyond Roberts. J. Econ. Theory 156 ( 2015 ) 14-44.  Shahar Dobzinski and Noam Nisan. 2015. Multi-unit auctions: Beyond Roberts. J. Econ. Theory 156 ( 2015 ) 14-44.","DOI":"10.1016\/j.jet.2014.04.006"},{"key":"e_1_3_2_1_19_1","first-page":"38","article-title":"On characterizations of truthful mechanisms for combinatorial auctions and scheduling","author":"Dobzinski Shahar","year":"2008","unstructured":"Shahar Dobzinski and Mukund Sundararajan . 2008 . On characterizations of truthful mechanisms for combinatorial auctions and scheduling . In EC. ACM , 38 - 47 . Shahar Dobzinski and Mukund Sundararajan. 2008. On characterizations of truthful mechanisms for combinatorial auctions and scheduling. In EC. ACM, 38-47.","journal-title":"EC. ACM"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786754"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Leah Epstein Asaf Levin and Rob van Stee. 2016. A Unified Approach to Truthful Scheduling on Related Machines. Math. Oper. Res. 41 1 ( 2016 ) 332-351.  Leah Epstein Asaf Levin and Rob van Stee. 2016. A Unified Approach to Truthful Scheduling on Related Machines. Math. Oper. Res. 41 1 ( 2016 ) 332-351.","DOI":"10.1287\/moor.2015.0730"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3105968"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Theodore Groves. 1973. Incentives in teams. Econometrica 41 4 ( 1973 ) 617-631.  Theodore Groves. 1973. Incentives in teams. Econometrica 41 4 ( 1973 ) 617-631.","DOI":"10.2307\/1914085"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Elias Koutsoupias and Angelina Vidali. 2012. A Lower Bound of 1+ for Truthful Scheduling Mechanisms. Algorithmica ( 2012 ) 1-13.  Elias Koutsoupias and Angelina Vidali. 2012. A Lower Bound of 1+ for Truthful Scheduling Mechanisms. Algorithmica ( 2012 ) 1-13.","DOI":"10.1007\/s00453-012-9634-6"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Ron Lavi and Chaitanya Swamy. 2009. Truthful mechanism design for multidimensional scheduling via cycle monotonicity. Games Econ. Behav. 67 1 ( 2009 ) 99-124.  Ron Lavi and Chaitanya Swamy. 2009. Truthful mechanism design for multidimensional scheduling via cycle monotonicity. Games Econ. Behav. 67 1 ( 2009 ) 99-124.","DOI":"10.1016\/j.geb.2008.08.001"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Benny Lehmann Daniel Lehmann and Noam Nisan. 2006. Combinatorial auctions with decreasing marginal utilities. Games Econ. Behav. 55 2 ( 2006 ) 270-296.  Benny Lehmann Daniel Lehmann and Noam Nisan. 2006. Combinatorial auctions with decreasing marginal utilities. Games Econ. Behav. 55 2 ( 2006 ) 270-296.","DOI":"10.1016\/j.geb.2005.02.006"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Jan Karel Lenstra David B Shmoys and Eva Tardos. 1990. Approximation algorithms for scheduling unrelated parallel machines. Mathematical programming 46 1-3 ( 1990 ) 259-271.  Jan Karel Lenstra David B Shmoys and Eva Tardos. 1990. Approximation algorithms for scheduling unrelated parallel machines. Mathematical programming 46 1-3 ( 1990 ) 259-271.","DOI":"10.1007\/BF01585745"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Stefano Leucci Akaki Mamageishvili and Paolo Penna. 2018. No truthful mechanism can be better than n approximate for two natural problems. Games Econ. Behav. 111 ( 2018 ) 64-74.  Stefano Leucci Akaki Mamageishvili and Paolo Penna. 2018. No truthful mechanism can be better than n approximate for two natural problems. Games Econ. Behav. 111 ( 2018 ) 64-74.","DOI":"10.1016\/j.geb.2018.05.003"},{"key":"e_1_3_2_1_29_1","volume-title":"WINE (Lecture Notes in Computer Science)","author":"Pinyan Lu.","unstructured":"Pinyan Lu. 2009. On 2-Player Randomized Mechanisms for Scheduling . In WINE (Lecture Notes in Computer Science) , Vol. 5929 . Springer , 30-41. Pinyan Lu. 2009. On 2-Player Randomized Mechanisms for Scheduling. In WINE (Lecture Notes in Computer Science), Vol. 5929. Springer, 30-41."},{"key":"e_1_3_2_1_30_1","first-page":"527","volume-title":"An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines. In 25th Annual Symposium on Theoretical Aspects of Computer Science (STACS) (LIPIcs)","volume":"1","author":"Lu Pinyan","year":"2008","unstructured":"Pinyan Lu and Changyuan Yu . 2008 . An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines. In 25th Annual Symposium on Theoretical Aspects of Computer Science (STACS) (LIPIcs) , Vol. 1 . 527 - 538 . Pinyan Lu and Changyuan Yu. 2008. An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines. In 25th Annual Symposium on Theoretical Aspects of Computer Science (STACS) (LIPIcs), Vol. 1. 527-538."},{"key":"e_1_3_2_1_31_1","volume-title":"Randomized Truthful Mechanisms for Scheduling Unrelated Machines. In 4th International Workshop on Internet and Network Economics (WINE). 402-413","author":"Lu Pinyan","year":"2008","unstructured":"Pinyan Lu and Changyuan Yu . 2008 . Randomized Truthful Mechanisms for Scheduling Unrelated Machines. In 4th International Workshop on Internet and Network Economics (WINE). 402-413 . Pinyan Lu and Changyuan Yu. 2008. Randomized Truthful Mechanisms for Scheduling Unrelated Machines. In 4th International Workshop on Internet and Network Economics (WINE). 402-413."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Ahuva Mu 'alem and Michael Schapira. 2018. Setting lower bounds on truthfulness. Games Econ. Behav. 110 ( 2018 ) 174-193.  Ahuva Mu 'alem and Michael Schapira. 2018. Setting lower bounds on truthfulness. Games Econ. Behav. 110 ( 2018 ) 174-193.","DOI":"10.1016\/j.geb.2018.02.001"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Noam Nisan and Amir Ronen. 2001. Algorithmic Mechanism Design. Games and Economic Behavior 35 ( 2001 ) 166-196.  Noam Nisan and Amir Ronen. 2001. Algorithmic Mechanism Design. Games and Economic Behavior 35 ( 2001 ) 166-196.","DOI":"10.1006\/game.1999.0790"},{"key":"e_1_3_2_1_34_1","unstructured":"Kevin Roberts. 1979. The characterization of implementable choice rules. Aggregation and Revelation of Preferences ( 1979 ) 321-348.  Kevin Roberts. 1979. The characterization of implementable choice rules. Aggregation and Revelation of Preferences ( 1979 ) 321-348."},{"key":"e_1_3_2_1_35_1","first-page":"286","article-title":"Weak monotonicity sufices for truthfulness on convex domains","author":"Saks Michael E.","year":"2005","unstructured":"Michael E. Saks and Lan Yu . 2005 . Weak monotonicity sufices for truthfulness on convex domains . In EC. ACM , 286 - 293 . Michael E. Saks and Lan Yu. 2005. Weak monotonicity sufices for truthfulness on convex domains. In EC. ACM, 286-293.","journal-title":"EC. ACM"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"crossref","unstructured":"William Vickrey. 1961. Counterspeculations auctions and competitive sealed tenders. Journal of Finance 16 ( 1961 ) 8-37.  William Vickrey. 1961. Counterspeculations auctions and competitive sealed tenders. Journal of Finance 16 ( 1961 ) 8-37.","DOI":"10.1111\/j.1540-6261.1961.tb02789.x"},{"key":"e_1_3_2_1_37_1","volume-title":"The Geometry of Truthfulness. In 5th Workshop on Internet and Network Economics (WINE'09)","author":"Vidali Angelina","year":"2009","unstructured":"Angelina Vidali . 2009 . The Geometry of Truthfulness. In 5th Workshop on Internet and Network Economics (WINE'09) , Springer. 340-350. Angelina Vidali. 2009. The Geometry of Truthfulness. In 5th Workshop on Internet and Network Economics (WINE'09), Springer. 340-350."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.02.001"}],"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.3384299","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384299","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.3384299"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":38,"alternative-id":["10.1145\/3357713.3384299","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384299","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"}}]}}