{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:06:50Z","timestamp":1750309610886,"version":"3.41.0"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T00:00:00Z","timestamp":1747180800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Recovery and Resilience Plan Greece 2.0 funded by the European Union under the NextGenerationEU Program","award":["MIS 5154714"],"award-info":[{"award-number":["MIS 5154714"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2025,6,30]]},"abstract":"<jats:p>\n            We study truthful mechanisms for allocation problems in graphs, both for the minimization (i.e., scheduling) and maximization (i.e., auctions) setting. The minimization problem is a special case of the well-studied unrelated machines scheduling problem, in which every given task can be executed only by two pre-specified machines in the case of graphs or a given subset of machines in the case of hypergraphs. This corresponds to a multigraph whose nodes are the machines and its hyperedges are the tasks. This class of problems belongs to multidimensional mechanism design, for which there are no known general mechanisms other than the VCG and its generalization to affine minimizers. We propose a new class of truthful mechanisms that have significantly better performance than affine minimizers in many settings. Specifically, we provide upper and lower bounds for truthful mechanisms for general multigraphs, as well as special classes of graphs such as stars, trees, planar graphs,\n            <jats:italic>k<\/jats:italic>\n            -degenerate graphs, and graphs of a given treewidth. We also consider the objective of minimizing or maximizing the\n            <jats:italic>\n              L\n              <jats:sup>p<\/jats:sup>\n            <\/jats:italic>\n            -norm of the values of the players, a generalization of the makespan minimization that corresponds to\n            <jats:italic>p<\/jats:italic>\n            = \u221e, and extend the results to any\n            <jats:italic>p<\/jats:italic>\n            &gt; 0.\n          <\/jats:p>","DOI":"10.1145\/3718360","type":"journal-article","created":{"date-parts":[[2025,3,15]],"date-time":"2025-03-15T11:47:06Z","timestamp":1742039226000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Truthful Allocation in Graphs and Hypergraphs"],"prefix":"10.1145","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9623-7461","authenticated-orcid":false,"given":"George","family":"Christodoulou","sequence":"first","affiliation":[{"name":"Aristotle University of Thessaloniki, Thessaloniki, Greece and Archimedes, Athena Research Center, Athens, Greece"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2226-6737","authenticated-orcid":false,"given":"Elias","family":"Koutsoupias","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, United Kingdom of Great Britain and Northern Ireland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8852-7231","authenticated-orcid":false,"given":"Annamaria","family":"Kovacs","sequence":"additional","affiliation":[{"name":"Goethe-Universitat Frankfurt am Main, Frankfurt, Germany"}]}],"member":"320","published-online":{"date-parts":[[2025,5,14]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"crossref","first-page":"482","DOI":"10.1109\/SFCS.2001.959924","volume-title":"42nd IEEE Symposium on Foundations of Computer Science (FOCS\u201901)","author":"Archer Aaron","year":"2001","unstructured":"Aaron Archer and \u00c9va Tardos. 2001. Truthful mechanisms for one-parameter agents. In 42nd IEEE Symposium on Foundations of Computer Science (FOCS\u201901). 482\u2013491."},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054111008246"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2010.11.003"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1110.0534"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-015-9625-5"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132522"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1111\/j.1468-0262.2006.00695.x"},{"key":"e_1_3_3_9_2","first-page":"51","volume-title":"Symposium on Theory of Computing Conference (STOC\u201913)","author":"Chawla Shuchi","year":"2013","unstructured":"Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan. 2013. Prior-independent mechanisms for scheduling. In Symposium on Theory of Computing Conference (STOC\u201913). ACM, 51\u201360."},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-014-9601-5"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3580507.3597764"},{"key":"e_1_3_3_12_2","doi-asserted-by":"crossref","unstructured":"George Christodoulou Elias Koutsoupias and Annam\u00e1ria Kov\u00e1cs. 2010. Mechanism design for fractional scheduling on unrelated machines. ACM Transactions on Algorithms 6 2 (2010) 1\u201318.","DOI":"10.1145\/1721837.1721854"},{"key":"e_1_3_3_13_2","article-title":"On the Nisan-Ronen conjecture","volume":"2011","author":"Christodoulou George","year":"2020","unstructured":"George Christodoulou, Elias Koutsoupias, and Annam\u00e1ria Kov\u00e1cs. 2020. On the Nisan-Ronen conjecture. CoRR abs\/2011.14434 (2020).","journal-title":"CoRR"},{"key":"e_1_3_3_14_2","first-page":"1086","volume-title":"Symposium on Theory of Computing Conference (STOC\u201920)","author":"Christodoulou George","year":"2020","unstructured":"George Christodoulou, Elias Koutsoupias, and Annam\u00e1ria Kov\u00e1cs. 2020. On the Nisan-Ronen conjecture for submodular valuations. In Symposium on Theory of Computing Conference (STOC\u201920). ACM, 1086\u20131096."},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2021.56"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585176"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.5555\/1668926.1668927"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1137\/120866038"},{"key":"e_1_3_3_19_2","article-title":"Multipart pricing of public goods","volume":"8","author":"Clarke Edward H.","year":"1971","unstructured":"Edward H. Clarke. 1971. Multipart pricing of public goods. Pub. Choice 8 (1971), 17\u201333.","journal-title":"Pub. Choice"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1137\/15m1053682"},{"key":"e_1_3_3_21_2","first-page":"1934","volume-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915)","author":"Daskalakis Constantinos","year":"2015","unstructured":"Constantinos Daskalakis and S. Matthew Weinberg. 2015. Bayesian truthful mechanisms for job scheduling from bi-criterion approximation algorithms. In ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915). SIAM, 1934\u20131952."},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/080744992"},{"key":"e_1_3_3_23_2","volume-title":"Graph Theory (4th ed.)","author":"Diestel Reinhard","year":"2012","unstructured":"Reinhard Diestel. 2012. Graph Theory (4th ed.). Springer."},{"key":"e_1_3_3_24_2","article-title":"Improved lower bounds for truthful scheduling","volume":"2007","author":"Dobzinski Shahar","year":"2020","unstructured":"Shahar Dobzinski and Ariel Shaulker. 2020. Improved lower bounds for truthful scheduling. CoRR abs\/2007.04362 (2020).","journal-title":"CoRR"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9668-9"},{"key":"e_1_3_3_26_2","first-page":"1243","volume-title":"24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201913)","author":"Epstein Leah","year":"2013","unstructured":"Leah Epstein, Asaf Levin, and Rob van Stee. 2013. A unified approach to truthful scheduling on related machines. In 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201913). 1243\u20131252."},{"issue":"1","key":"e_1_3_3_27_2","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/BF02020444","article-title":"On chromatic number of graphs and set-systems","volume":"17","author":"Erd\u0151s Paul","year":"1966","unstructured":"Paul Erd\u0151s and Andr\u00e1s Hajnal. 1966. On chromatic number of graphs and set-systems. Acta Math. Hungar. 17, 1-2 (1966), 61\u201399.","journal-title":"Acta Math. Hungar."},{"key":"e_1_3_3_28_2","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1007\/978-3-030-57980-7_15","volume-title":"13th International Symposium on Algorithmic Game Theory (SAGT\u201920)","author":"Giannakopoulos Yiannis","year":"2020","unstructured":"Yiannis Giannakopoulos, Alexander Hammerl, and Diogo Po\u00e7as. 2020. A new lower bound for deterministic truthful scheduling. In 13th International Symposium on Algorithmic Game Theory (SAGT\u201920). 226\u2013240."},{"issue":"4","key":"e_1_3_3_29_2","first-page":"19:1\u201319:16","article-title":"The VCG mechanism for Bayesian scheduling","volume":"5","author":"Giannakopoulos Yiannis","year":"2017","unstructured":"Yiannis Giannakopoulos and Maria Kyropoulou. 2017. The VCG mechanism for Bayesian scheduling. ACM Trans. Econ. Comput. 5, 4 (2017), 19:1\u201319:16.","journal-title":"ACM Trans. Econ. Comput."},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.2307\/1914085"},{"key":"e_1_3_3_31_2","first-page":"49:1\u201349:15","volume-title":"24th Annual European Symposium on Algorithms (ESA\u201916)","author":"Huang Chien-Chung","year":"2016","unstructured":"Chien-Chung Huang and Sebastian Ott. 2016. A combinatorial approximation algorithm for graph balancing with light hyper edges. In 24th Annual European Symposium on Algorithms (ESA\u201916). 49:1\u201349:15."},{"key":"e_1_3_3_32_2","first-page":"74:1\u201374:14","volume-title":"46th International Colloquium on Automata, Languages, and Programming (ICALP\u201919)","author":"Jansen Klaus","year":"2019","unstructured":"Klaus Jansen and Lars Rohwedder. 2019. Local search breaks 1.75 for graph balancing. In 46th International Colloquium on Automata, Languages, and Programming (ICALP\u201919). 74:1\u201374:14."},{"key":"e_1_3_3_33_2","first-page":"211","article-title":"A lower bound of 1+ \\(\\phi\\)  for truthful scheduling mechanisms","author":"Koutsoupias Elias","year":"2012","unstructured":"Elias Koutsoupias and Angelina Vidali. 2012. A lower bound of 1+ \\(\\phi\\) for truthful scheduling mechanisms. Algorithmica 66 (2012), 211\u2013223.","journal-title":"Algorithmica"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2008.08.001"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2009.09.015"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/bf01585745"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2018.05.003"},{"key":"e_1_3_3_38_2","series-title":"Lecture Notes in Computer Science","first-page":"30","volume-title":"International Workshop on Internet and Network Economics (WINE\u201909)","author":"Lu Pinyan","year":"2009","unstructured":"Pinyan Lu. 2009. On 2-player randomized mechanisms for scheduling. In International Workshop on Internet and Network Economics (WINE\u201909)(Lecture Notes in Computer Science, Vol. 5929). Springer, 30\u201341."},{"key":"e_1_3_3_39_2","series-title":"LIPIcs","first-page":"527","volume-title":"Symposium on Theoretical Aspects of Computer Science (STACS\u201908)","author":"Lu Pinyan","year":"2008","unstructured":"Pinyan Lu and Changyuan Yu. 2008. An improved randomized truthful mechanism for scheduling unrelated machines. In Symposium on Theoretical Aspects of Computer Science (STACS\u201908)(LIPIcs, Vol. 1). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 527\u2013538."},{"key":"e_1_3_3_40_2","first-page":"402","volume-title":"4th International Workshop on Internet and Network Economics (WINE\u201908)","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\u201908). 402\u2013413."},{"key":"e_1_3_3_41_2","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1007\/978-3-642-35311-6_33","volume-title":"8th International Workshop on Internet and Network Economics (WINE\u201912)","author":"Minooei Hadi","year":"2012","unstructured":"Hadi Minooei and Chaitanya Swamy. 2012. Truthful mechanism design for multidimensional covering problems. In 8th International Workshop on Internet and Network Economics (WINE\u201912). 448\u2013461."},{"key":"e_1_3_3_42_2","first-page":"1143","volume-title":"18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907)","author":"Mu\u2019alem Ah\u2019uva","year":"2007","unstructured":"Ah\u2019uva Mu\u2019alem and Michael Schapira. 2007. Setting lower bounds on truthfulness. In 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907). 1143\u20131152."},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2018.02.001"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0790"},{"key":"e_1_3_3_45_2","doi-asserted-by":"crossref","unstructured":"Noam Nisan Tim Roughgarden \u00c9va Tardos and Vijay V. Vazirani. 2007. Algorithmic Game Theory Chapter 9: Introduction to Mechanism Design (for Computer Scientists). Cambridge University Press.","DOI":"10.1017\/CBO9780511800481"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(74)90042-9"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/1064009.1064040"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-013-0359-4"},{"key":"e_1_3_3_49_2","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1111\/j.1540-6261.1961.tb02789.x","article-title":"Counterspeculations, auctions and competitive sealed tenders","volume":"16","author":"Vickrey William","year":"1961","unstructured":"William Vickrey. 1961. Counterspeculations, auctions and competitive sealed tenders. J. Finan. 16 (1961), 8\u201337.","journal-title":"J. Finan."},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2016.06.007"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.02.001"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3718360","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3718360","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:57:35Z","timestamp":1750298255000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3718360"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,14]]},"references-count":50,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,30]]}},"alternative-id":["10.1145\/3718360"],"URL":"https:\/\/doi.org\/10.1145\/3718360","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2025,5,14]]},"assertion":[{"value":"2024-03-28","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-01-17","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-05-14","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}