{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:43:12Z","timestamp":1773481392108,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":32,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"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":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585176","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"672-685","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["A Proof of the Nisan-Ronen Conjecture"],"prefix":"10.1145","author":[{"given":"George","family":"Christodoulou","sequence":"first","affiliation":[{"name":"Aristotle University of Thessaloniki, Greece \/ RC Athena, Greece"}]},{"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 am Main, Germany"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Proc. of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS). 482\u2013491","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\u2013491 . 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\u2013491."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1110.0534"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-015-9625-5"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1468-0262.2006.00695.x"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Shuchi Chawla Jason D. Hartline David L. Malec and Balasubramanian Sivan. 2013. Prior-independent mechanisms for scheduling. In STOC. ACM 51\u201360. \t\t\t\t  Shuchi Chawla Jason D. Hartline David L. Malec and Balasubramanian Sivan. 2013. Prior-independent mechanisms for scheduling. In STOC. ACM 51\u201360.","DOI":"10.1145\/2488608.2488616"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-014-9601-5"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721854"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"George Christodoulou Elias Koutsoupias and Annam\u00e1ria Kov\u00e1cs. 2020. On the Nisan-Ronen conjecture for submodular valuations. In STOC. ACM 1086\u20131096. (Full version arXiv:1907.12733) \t\t\t\t  George Christodoulou Elias Koutsoupias and Annam\u00e1ria Kov\u00e1cs. 2020. On the Nisan-Ronen conjecture for submodular valuations. In STOC. ACM 1086\u20131096. (Full version arXiv:1907.12733)","DOI":"10.1145\/3357713.3384299"},{"key":"e_1_3_2_1_9_1","volume-title":"On the Nisan-Ronen conjecture","author":"Christodoulou George","unstructured":"George Christodoulou , Elias Koutsoupias , and Annam\u00e1ria Kov\u00e1cs . 2021. On the Nisan-Ronen conjecture . In FOCS. IEEE , 839\u2013850. George Christodoulou, Elias Koutsoupias, and Annam\u00e1ria Kov\u00e1cs. 2021. On the Nisan-Ronen conjecture. In FOCS. IEEE, 839\u2013850."},{"key":"e_1_3_2_1_10_1","first-page":"1","article-title":"Truthful Allocation in Graphs and Hypergraphs. In ICALP (LIPIcs, Vol. 198)","volume":"56","author":"Christodoulou George","year":"2021","unstructured":"George Christodoulou , Elias Koutsoupias , and Annam\u00e1ria Kov\u00e1cs . 2021 . Truthful Allocation in Graphs and Hypergraphs. In ICALP (LIPIcs, Vol. 198) . Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik , 56 : 1 \u2013 56 :20. George Christodoulou, Elias Koutsoupias, and Annam\u00e1ria Kov\u00e1cs. 2021. Truthful Allocation in Graphs and Hypergraphs. In ICALP (LIPIcs, Vol. 198). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 56:1\u201356:20.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87744-8_25"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1668926.1668927"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/120866038"},{"key":"e_1_3_2_1_14_1","volume-title":"Multipart pricing of public goods. Public Choice, 8","author":"Clarke Edward H.","year":"1971","unstructured":"Edward H. Clarke . 1971. Multipart pricing of public goods. Public Choice, 8 ( 1971 ). Edward H. Clarke. 1971. Multipart pricing of public goods. Public Choice, 8 (1971)."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1971.11992852"},{"key":"e_1_3_2_1_16_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 \u20131952. isbn:978-1-61197-373-0 Constantinos Daskalakis and S. Matthew Weinberg. 2015. Bayesian truthful mechanisms for job scheduling from bi-criterion approximation algorithms. In SODA. SIAM, 1934\u20131952. isbn:978-1-61197-373-0"},{"key":"e_1_3_2_1_17_1","unstructured":"Shahar Dobzinski and Ariel Shaulker. 2020. Improved Lower Bounds for Truthful Scheduling. arxiv:2007.04362v2. \t\t\t\t  Shahar Dobzinski and Ariel Shaulker. 2020. Improved Lower Bounds for Truthful Scheduling. arxiv:2007.04362v2."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Shahar Dobzinski and Mukund Sundararajan. 2008. On characterizations of truthful mechanisms for combinatorial auctions and scheduling. In EC. ACM 38\u201347. \t\t\t\t  Shahar Dobzinski and Mukund Sundararajan. 2008. On characterizations of truthful mechanisms for combinatorial auctions and scheduling. In EC. ACM 38\u201347.","DOI":"10.1145\/1386790.1386798"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-57980-7_15"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3105968"},{"key":"e_1_3_2_1_21_1","volume-title":"Spencer","author":"Graham Ronald L.","year":"1990","unstructured":"Ronald L. Graham , Bruce L. Rothschild , and Joel H . Spencer . 1990 . Ramsey Theory, 2 nd Edition. Wiley Series in Discrete Mathematics and Optimization. Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer. 1990. Ramsey Theory, 2nd Edition. Wiley Series in Discrete Mathematics and Optimization.","edition":"2"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.2307\/1914085"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Elias Koutsoupias and Angelina Vidali. 2012. A Lower Bound of 1+\u03c6 for Truthful Scheduling Mechanisms. Algorithmica 1\u201313. \t\t\t\t  Elias Koutsoupias and Angelina Vidali. 2012. A Lower Bound of 1+\u03c6 for Truthful Scheduling Mechanisms. Algorithmica 1\u201313.","DOI":"10.1007\/s00453-012-9634-6"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2008.08.001"},{"key":"e_1_3_2_1_25_1","first-page":"527","article-title":"An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines","volume":"1","author":"Lu Pinyan","year":"2008","unstructured":"Pinyan Lu and Changyuan Yu . 2008 . An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines . In STACS. 1 , 527 \u2013 538 . Pinyan Lu and Changyuan Yu. 2008. An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines. In STACS. 1, 527\u2013538.","journal-title":"STACS."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92185-1_46"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2018.02.001"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0790"},{"key":"e_1_3_2_1_29_1","volume-title":"Saks and Lan Yu","author":"Michael","year":"2005","unstructured":"Michael E. Saks and Lan Yu . 2005 . Weak monotonicity suffices for truthfulness on convex domains. In EC. ACM , 286\u2013293. Michael E. Saks and Lan Yu. 2005. Weak monotonicity suffices for truthfulness on convex domains. In EC. ACM, 286\u2013293."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1540-6261.1961.tb02789.x"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10841-9_31"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.02.001"}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","location":"Orlando FL USA","acronym":"STOC '23","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585176","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585176","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:00Z","timestamp":1750178820000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585176"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":32,"alternative-id":["10.1145\/3564246.3585176","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585176","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}