{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T03:08:34Z","timestamp":1767236914741,"version":"3.41.0"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2015,1,13]],"date-time":"2015-01-13T00:00:00Z","timestamp":1421107200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004895","name":"European Social Fund","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004895","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000780","name":"European Commission","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100009877","name":"Calabria Region","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100009877","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2015,1,13]]},"abstract":"<jats:p>\n            The nucleolus is a well-known solution concept for coalitional games to fairly distribute the total available worth among the players. The nucleolus is known to be\n            <jats:italic>NP<\/jats:italic>\n            -hard to compute over compact coalitional games, that is, over games whose functions specifying the worth associated with each coalition are encoded in terms of polynomially computable functions over combinatorial structures. In particular, hardness results have been exhibited over minimum spanning tree games, threshold games, and flow games. However, due to its intricate definition involving reasoning over exponentially many coalitions, a nontrivial upper bound on its complexity was missing in the literature and looked for.\n          <\/jats:p>\n          <jats:p>This article faces this question and precisely characterizes the complexity of the nucleolus, by exhibiting an upper bound that holds on any class of compact games, and by showing that this bound is tight even on the (structurally simple) class of graph games. The upper bound is established by proposing a variant of the standard linear-programming based algorithm for nucleolus computation and by studying a framework for reasoning about succinctly specified linear programs, which are contributions of interest in their own. The hardness result is based on an elaborate combinatorial reduction, which is conceptually relevant for it provides a \u201cmeasure\u201d of the computational cost to be paid for guaranteeing voluntary participation to the distribution process. In fact, the pre-nucleolus is known to be efficiently computable over graph games, with this solution concept being defined as the nucleolus but without guaranteeing that each player is granted with it at least the worth she can get alone, that is, without collaborating with the other players.<\/jats:p>\n          <jats:p>Finally, this article identifies relevant tractable classes of coalitional games, based on the notion of type of a player. Indeed, in most applications where many players are involved, it is often the case that such players do belong in fact to a limited number of classes, which is known in advance and may be exploited for computing the nucleolus in a fast way.<\/jats:p>","DOI":"10.1145\/2692372.2692374","type":"journal-article","created":{"date-parts":[[2015,1,16]],"date-time":"2015-01-16T14:29:58Z","timestamp":1421418598000},"page":"1-52","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["The Complexity of the Nucleolus in Compact Games"],"prefix":"10.1145","volume":"7","author":[{"given":"Gianluigi","family":"Greco","sequence":"first","affiliation":[{"name":"University of Calabria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Enrico","family":"Malizia","sequence":"additional","affiliation":[{"name":"University of Calabria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luigi","family":"Palopoli","sequence":"additional","affiliation":[{"name":"University of Calabria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Francesco","family":"Scarcello","sequence":"additional","affiliation":[{"name":"University of Calabria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,1,13]]},"reference":[{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2008.08.004"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s001820050018"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(85)90102-4"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201910)","author":"Bachrach Yoram","year":"2010","unstructured":"Yoram Bachrach and Ely Porat . 2010 . Path disruption games . In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201910) , Michael Luck, Sandip Sen, Wiebe van der Hoek, and Gal A. Kaminka (Eds.), 1123--1130. Yoram Bachrach and Ely Porat. 2010. Path disruption games. In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201910), Michael Luck, Sandip Sen, Wiebe van der Hoek, and Gal A. Kaminka (Eds.), 1123--1130."},{"volume-title":"Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201908)","author":"Bachrach Yoram","key":"e_1_2_1_6_1","unstructured":"Yoram Bachrach and Jeffrey S. Rosenschein . 2008. Coalitional skill games . In Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201908) , Lin Padgham, David C. Parkes, J\u00f6rg M\u00fcller, and Simon Parsons (Eds.), 1023--1030. Yoram Bachrach and Jeffrey S. Rosenschein. 2008. Coalitional skill games. In Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201908), Lin Padgham, David C. Parkes, J\u00f6rg M\u00fcller, and Simon Parsons (Eds.), 1023--1030."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201908)","author":"Bachrach Yoram","year":"2008","unstructured":"Yoram Bachrach , Jeffrey S. Rosenschein , and Ely Porat . 2008 . Power and stability in connectivity games . In Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201908) , Lin Padgham, David C. Parkes, J\u00f6rg M\u00fcller, and Simon Parsons (Eds.), 999--1006. Yoram Bachrach, Jeffrey S. Rosenschein, and Ely Porat. 2008. Power and stability in connectivity games. In Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201908), Lin Padgham, David C. Parkes, J\u00f6rg M\u00fcller, and Simon Parsons (Eds.), 999--1006."},{"volume-title":"Complexity and Real Computation","author":"Blum Lenore","key":"e_1_2_1_8_1","unstructured":"Lenore Blum , Felipe Cucker , Michael Shub , and Steve Smale . 1998. Complexity and Real Computation . Springer-Verlag New York, Inc. , Secaucus, NJ . Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale. 1998. Complexity and Real Computation. Springer-Verlag New York, Inc., Secaucus, NJ."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00182-006-0019-4"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00182-005-0213-9"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 26th National Conference on Artificial Intelligence (AAAI-12)","author":"Chen Ning","year":"2012","unstructured":"Ning Chen , Pinyan Lu , and Hongyang Zhang . 2012 . Computing the nucleolus of matching, cover and clique games . In Proceedings of the 26th National Conference on Artificial Intelligence (AAAI-12) , Bart Selman and J\u00f6rg Hoffmann (Eds.), 1319--1325. Ning Chen, Pinyan Lu, and Hongyang Zhang. 2012. Computing the nucleolus of matching, cover and clique games. In Proceedings of the 26th National Conference on Artificial Intelligence (AAAI-12), Bart Selman and J\u00f6rg Hoffmann (Eds.), 1319--1325."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1597148.1597185"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2006.01.005"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-008-9138-0"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.19.2.257"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01919297"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-009-9162-5"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.200810021"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s001820050083"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-008-0252-2"},{"volume-title":"Contributions to the Theory of Games","author":"Gillies Donald B.","key":"e_1_2_1_22_1","unstructured":"Donald B. Gillies . 1959. Solutions to general non-zero-sum games . In Contributions to the Theory of Games , Volume IV , Albert William Tucker and R. Duncan Luce (Eds.), Annals of Mathematics Studies, Vol. 40, Princeton University Press , Princeton, NJ, 47--85. Donald B. Gillies. 1959. Solutions to general non-zero-sum games. In Contributions to the Theory of Games, Volume IV, Albert William Tucker and R. Duncan Luce (Eds.), Annals of Mathematics Studies, Vol. 40, Princeton University Press, Princeton, NJ, 47--85."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.17.4.792"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s001820050078"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01247104"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1892211.1892227"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2011.06.002"},{"key":"e_1_2_1_28_1","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"Gr\u00f6tschel Martin","unstructured":"Martin Gr\u00f6tschel , L\u00e1szl\u00f3 Lov\u00e1sz , and Alexander Schrijver . 1993. Geometric Algorithms and Combinatorial Optimization ( 2 nd Ed.). Algorithms and Combinatorics, Vol . 2,Springer-Verlag, Berlin\/Heidelberg, Germany . Martin Gr\u00f6tschel, L\u00e1szl\u00f3 Lov\u00e1sz, and Alexander Schrijver. 1993. Geometric Algorithms and Combinatorial Optimization (2nd Ed.). Algorithms and Combinatorics, Vol. 2,Springer-Verlag, Berlin\/Heidelberg, Germany.","edition":"2"},{"key":"e_1_2_1_29_1","first-page":"175","article-title":"\u00dcber Mengen konvexer K\u00f6rper mit gemeinschaftlichen Punkten","volume":"32","author":"Helly Eduard","year":"1923","unstructured":"Eduard Helly . 1923 . \u00dcber Mengen konvexer K\u00f6rper mit gemeinschaftlichen Punkten . Jahresbericht der Deutschen Mathematiker-Vereinigung 32 , 175 -- 176 . Eduard Helly. 1923. \u00dcber Mengen konvexer K\u00f6rper mit gemeinschaftlichen Punkten. Jahresbericht der Deutschen Mathematiker-Vereinigung 32, 175--176.","journal-title":"Jahresbericht der Deutschen Mathematiker-Vereinigung"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064009.1064030"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1134707.1134726"},{"volume-title":"Handbook of Theoretical Computer Science","author":"Johnson David S.","key":"e_1_2_1_32_1","unstructured":"David S. Johnson . 1990. A catalog of complexity classes . In Handbook of Theoretical Computer Science , Volume A: Algorithms and Complexity, Jan van Leeuwen (Ed.), The MIT Press, Cambridge, MA, 67-- 161 . David S. Johnson. 1990. A catalog of complexity classes. In Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, Jan van Leeuwen (Ed.), The MIT Press, Cambridge, MA, 67--161."},{"volume-title":"On totally balanced games and games of flow. Discussion Paper 413","author":"Kalai Ehud","key":"e_1_2_1_33_1","unstructured":"Ehud Kalai and Eitan Zemel . 1980. On totally balanced games and games of flow. Discussion Paper 413 . Northwestern University , Center for Mathematical Studies in Economics and Management Science, Evanston, IL. Ehud Kalai and Eitan Zemel. 1980. On totally balanced games and games of flow. Discussion Paper 413. Northwestern University, Center for Mathematical Studies in Economics and Management Science, Evanston, IL."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.28.2.294.14477"},{"key":"e_1_2_1_35_1","first-page":"34","article-title":"The nucleolus as a solution of a minimization problem.SIAM","volume":"23","author":"Kohlberg Elon","year":"1972","unstructured":"Elon Kohlberg . 1972 . The nucleolus as a solution of a minimization problem.SIAM J. Appl. Math. 23 , 1, 34 -- 39 . Elon Kohlberg. 1972. The nucleolus as a solution of a minimization problem.SIAM J. Appl. Math. 23, 1, 34--39.","journal-title":"J. Appl. Math."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12138"},{"volume-title":"A polynomial time algorithm for computing the nucleolus of convex games.Report M 96-12","author":"Kuipers Jeroen","key":"e_1_2_1_38_1","unstructured":"Jeroen Kuipers . 1996. A polynomial time algorithm for computing the nucleolus of convex games.Report M 96-12 . Maastricht University , Maastricht, The Netherlands. Jeroen Kuipers. 1996. A polynomial time algorithm for computing the nucleolus of convex games.Report M 96-12. Maastricht University, Maastricht, The Netherlands."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01766216"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.2307\/3003493"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.16"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.4.303"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.3.3.189"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2013.03.014"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00182-005-0199-3"},{"key":"e_1_2_1_46_1","volume-title":"Osborne and Ariel Rubinstein","author":"Martin","year":"1994","unstructured":"Martin J. Osborne and Ariel Rubinstein . 1994 . A Course in Game Theory. The MIT Press , Cambridge, MA. Martin J. Osborne and Ariel Rubinstein. 1994. A Course in Game Theory. The MIT Press, Cambridge, MA."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01766395"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01681356"},{"key":"e_1_2_1_49_1","volume-title":"Papadimitriou and Kenneth Steiglitz","author":"Christos","year":"1998","unstructured":"Christos H. Papadimitriou and Kenneth Steiglitz . 1998 . Combinatorial Optimization : Algorithms and Complexity (2nd Ed.).Dover Publications . Christos H. Papadimitriou and Kenneth Steiglitz. 1998. Combinatorial Optimization: Algorithms and Complexity (2nd Ed.).Dover Publications."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.21.3.757"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1955.5.363"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1997.0629"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01766424"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1137\/0117107"},{"volume-title":"Theory of Linear and Integer Programming","author":"Schrijver Alexander","key":"e_1_2_1_57_1","unstructured":"Alexander Schrijver . 1998. Theory of Linear and Integer Programming . John Wiley & Sons , New York, NY . Alexander Schrijver. 1998. Theory of Linear and Integer Programming. John Wiley & Sons, New York, NY."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01753437"},{"key":"e_1_2_1_59_1","volume-title":"Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201910)","author":"Shrot Tammar","year":"2010","unstructured":"Tammar Shrot , Yonatan Aumann , and Sarit Kraus . 2010 . On agent types in coalition formation problems . In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201910) , Michael Luck, Sandip Sen, Wiebe van der Hoek, and Gal A. Kaminka (Eds.), 757--764. Tammar Shrot, Yonatan Aumann, and Sarit Kraus. 2010. On agent types in coalition formation problems. In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201910), Michael Luck, Sandip Sen, Wiebe van der Hoek, and Gal A. Kaminka (Eds.), 757--764."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.23.4.983"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01240179"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2003.02.003"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.5555\/2283396.2283461"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.5555\/22101.22108"},{"key":"e_1_2_1_67_1","volume-title":"Theory of Games and Economic Behavior","author":"von Neumann John","unstructured":"John von Neumann and Oskar Morgenstern . 1953. Theory of Games and Economic Behavior ( 3 rd Ed.). Princeton University Press, Princeton , NJ. John von Neumann and Oskar Morgenstern. 1953. Theory of Games and Economic Behavior (3rd Ed.). Princeton University Press, Princeton, NJ.","edition":"3"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1029\/WR018i003p00463"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2692372.2692374","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2692372.2692374","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:19:40Z","timestamp":1750231180000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2692372.2692374"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1,13]]},"references-count":61,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1,13]]}},"alternative-id":["10.1145\/2692372.2692374"],"URL":"https:\/\/doi.org\/10.1145\/2692372.2692374","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2015,1,13]]},"assertion":[{"value":"2013-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-01-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}