{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,27]],"date-time":"2026-04-27T10:34:05Z","timestamp":1777286045449,"version":"3.51.4"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T00:00:00Z","timestamp":1591401600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T00:00:00Z","timestamp":1591401600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/M50662X\/1"],"award-info":[{"award-number":["EP\/M50662X\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/P021042\/1"],"award-info":[{"award-number":["EP\/P021042\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012550","name":"National Research, Development and Innovation Fund","doi-asserted-by":"crossref","award":["TUDFO\/51757\/2019-ITM, Thematic Excellence Program"],"award-info":[{"award-number":["TUDFO\/51757\/2019-ITM, Thematic Excellence Program"]}],"id":[{"id":"10.13039\/501100012550","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2021,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The nucleolus offers a desirable payoff-sharing solution in cooperative games, thanks to its attractive properties\u2014it always exists and lies in the core (if the core is non-empty), and it is unique. The nucleolus is considered as the most \u2018stable\u2019 solution in the sense that it lexicographically minimizes the dissatisfactions among all coalitions. Although computing the nucleolus is very challenging, the Kohlberg criterion offers a powerful method for verifying whether a solution is the nucleolus in relatively small games (i.e. with the number of players <jats:inline-formula><jats:alternatives><jats:tex-math>$$n \\le 15$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>\u2264<\/mml:mo>\n                    <mml:mn>15<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>). This approach, however, becomes more challenging for larger games because of the need to form and check a criterion involving possibly exponentially large collections of coalitions, with each collection potentially of an exponentially large size. The aim of this work is twofold. First, we develop an improved version of the Kohlberg criterion that involves checking the \u2018balancedness\u2019 of at most <jats:inline-formula><jats:alternatives><jats:tex-math>$$(n-1)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> sets of coalitions. Second, we exploit these results and introduce a novel descent-based constructive algorithm to find the nucleolus efficiently. We demonstrate the performance of the new algorithms by comparing them with existing methods over different types of games. Our contribution also includes the first open-source code for computing the nucleolus for games of moderately large sizes.\n<\/jats:p>","DOI":"10.1007\/s10107-020-01527-9","type":"journal-article","created":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T10:02:31Z","timestamp":1591437751000},"page":"135-170","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":23,"title":["Finding and verifying the nucleolus of cooperative games"],"prefix":"10.1007","volume":"190","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7492-1174","authenticated-orcid":false,"given":"M\u00e1rton","family":"Benedek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00f6rg","family":"Fliege","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tri-Dung","family":"Nguyen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,6,6]]},"reference":[{"issue":"6","key":"1527_CR1","doi-asserted-by":"publisher","first-page":"1163","DOI":"10.1137\/0117107","volume":"17","author":"D Schmeidler","year":"1969","unstructured":"Schmeidler, D.: The nucleolus of a characteristic function game. SIAM J. Appl. Math. 17(6), 1163\u20131170 (1969). https:\/\/doi.org\/10.1137\/0117107","journal-title":"SIAM J. Appl. Math."},{"issue":"2","key":"1527_CR2","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/BF01240179","volume":"23","author":"T Solymosi","year":"1994","unstructured":"Solymosi, T., Raghavan, T.E.S.: An algorithm for finding the nucleolus of assignment games. Int. J. Game Theory 23(2), 119\u2013143 (1994)","journal-title":"Int. J. Game Theory"},{"issue":"1","key":"1527_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0377-2217(02)00240-0","volume":"146","author":"H Hamers","year":"2003","unstructured":"Hamers, H., Klijn, F., Solymosi, T., Tijs, S., Vermeulen, D.: On the nucleolus of neighbor games. Eur. J. Oper. Res. 146(1), 1\u201318 (2003)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"1527_CR4","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/j.ejor.2003.02.003","volume":"162","author":"T Solymosi","year":"2005","unstructured":"Solymosi, T., Raghavan, T., Tijs, S.: Computing the nucleolus of cyclic permutation games. Eur. J. Oper. Res. 162(1), 270\u2013280 (2005)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"1527_CR5","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/j.geb.2004.08.008","volume":"54","author":"J Potters","year":"2006","unstructured":"Potters, J., Reijnierse, H., Biswas, A.: The nucleolus of balanced simple flow networks. Games Econ. Behav. 54(1), 205\u2013225 (2006)","journal-title":"Games Econ. Behav."},{"issue":"1","key":"1527_CR6","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1007\/s10878-008-9138-0","volume":"18","author":"X Deng","year":"2009","unstructured":"Deng, X., Fang, Q., Sun, X.: Finding nucleolus of flow game. J. Comb. Optim. 18(1), 64\u201386 (2009)","journal-title":"J. Comb. Optim."},{"issue":"4","key":"1527_CR7","doi-asserted-by":"publisher","first-page":"981","DOI":"10.1287\/moor.1090.0405","volume":"34","author":"W Kern","year":"2009","unstructured":"Kern, W., Paulusma, D.: On the core and f-nucleolus of flow games. Math. Oper. Res. 34(4), 981\u2013991 (2009)","journal-title":"Math. Oper. Res."},{"key":"1527_CR8","unstructured":"Elkind, E., Goldberg, L.A., Goldberg, P., Wooldridge, M.: Computational complexity of weighted threshold games. In: Proceeding of the National Conference on Artificial Intelligence, vol. 22, p. 718 (2007)"},{"issue":"20","key":"1527_CR9","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1137\/0120009","volume":"1","author":"E Kohlberg","year":"1971","unstructured":"Kohlberg, E.: On the nucleolus of a characteristic function game. SIAM J. Appl. Math. 1(20), 62\u201366 (1971)","journal-title":"SIAM J. Appl. Math."},{"key":"1527_CR10","unstructured":"Kopelowitz, A.: Computation of the kernels of simple games and the nucleolus of n-person games. Technical report, DTIC Document (1967)"},{"key":"1527_CR11","doi-asserted-by":"publisher","first-page":"1581","DOI":"10.11650\/twjm\/1500405041","volume":"12","author":"K Kido","year":"2008","unstructured":"Kido, K.: A modified Kohlberg criterion and a nonlinear method to compute the nucleolus of a cooperative game. Taiwan. J. Math. 12, 1581\u20131590 (2008)","journal-title":"Taiwan. J. Math."},{"issue":"1","key":"1527_CR12","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1137\/0123004","volume":"23","author":"E Kohlberg","year":"1972","unstructured":"Kohlberg, E.: The nucleolus as a solution of a minimization problem. SIAM J. Appl. Math. 23(1), 34\u201339 (1972)","journal-title":"SIAM J. Appl. Math."},{"issue":"2","key":"1527_CR13","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/BF01766395","volume":"3","author":"G Owen","year":"1974","unstructured":"Owen, G.: A note on the nucleolus. Int. J. Game Theory 3(2), 101\u2013103 (1974)","journal-title":"Int. J. Game Theory"},{"issue":"10","key":"1527_CR14","doi-asserted-by":"publisher","first-page":"2308","DOI":"10.1016\/j.cor.2013.03.011","volume":"40","author":"J Puerto","year":"2013","unstructured":"Puerto, J., Perea, F.: Finding the nucleolus of any n-person cooperative game by a single linear program. Comput. Oper. Res. 40(10), 2308\u20132313 (2013)","journal-title":"Comput. Oper. Res."},{"issue":"4","key":"1527_CR15","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1287\/moor.4.4.303","volume":"4","author":"M Maschler","year":"1979","unstructured":"Maschler, M., Peleg, B., Shapley, L.S.: Geometric properties of the kernel, nucleolus, and related solution concepts. Math. Oper. Res. 4(4), 303\u2013338 (1979)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"1527_CR16","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/BF01766424","volume":"19","author":"JK Sankaran","year":"1991","unstructured":"Sankaran, J.K.: On finding the nucleolus of an n-person cooperative game. Int. J. Game Theory 19(4), 329\u2013338 (1991)","journal-title":"Int. J. Game Theory"},{"key":"1527_CR17","unstructured":"Solymosi, T.: On computing the nucleolus of cooperative games. Ph.D. Thesis, University of Illinois (1993). https:\/\/doi.org\/10.13140\/RG.2.2.28952.80642"},{"issue":"3","key":"1527_CR18","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1287\/moor.21.3.757","volume":"21","author":"JAM Potters","year":"1996","unstructured":"Potters, J.A.M., Reijnierse, J.H., Ansing, M.: Computing the nucleolus by solving a prolonged simplex algorithm. Math. Oper. Res. 21(3), 757\u2013768 (1996)","journal-title":"Math. Oper. Res."},{"key":"1527_CR19","unstructured":"Derks, J., Kuipers, J.: Implementing the simplex method for computing the prenucleolus of transferable utility games (1997)"},{"issue":"248","key":"1527_CR20","doi-asserted-by":"publisher","first-page":"1078","DOI":"10.1016\/j.ejor.2015.08.017","volume":"3","author":"T Nguyen","year":"2016","unstructured":"Nguyen, T., Thomas, L.: Finding the nucleoli of large cooperative games. Eur. J. Oper. Res. 3(248), 1078\u20131092 (2016)","journal-title":"Eur. J. Oper. Res."},{"key":"1527_CR21","unstructured":"Benedek, M.: Nucleolus. https:\/\/github.com\/blrzsvrzs\/nucleolus (2018)"},{"key":"1527_CR22","doi-asserted-by":"crossref","unstructured":"Benedek, M., Fliege, J., Nguyen, T.D.: Finding and verifying the nucleolus of cooperative games. Technical report (2019)","DOI":"10.1007\/s10107-020-01527-9"},{"issue":"3","key":"1527_CR23","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/s001820050078","volume":"27","author":"D Granot","year":"1998","unstructured":"Granot, D., Granot, F., Zhu, W.R.: Characterization sets for the nucleolus. Int. J. Game Theory 27(3), 359\u2013374 (1998)","journal-title":"Int. J. Game Theory"},{"issue":"4","key":"1527_CR24","doi-asserted-by":"publisher","first-page":"520","DOI":"10.1016\/j.orl.2016.05.014","volume":"44","author":"T Solymosi","year":"2016","unstructured":"Solymosi, T., Sziklai, B.: Characterization sets for the nucleolus in balanced games. Oper. Res. Lett. 44(4), 520\u2013524 (2016)","journal-title":"Oper. Res. Lett."},{"issue":"1\u20132","key":"1527_CR25","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1006\/game.1997.0629","volume":"24","author":"Hans Reijnierse","year":"1998","unstructured":"Reijnierse, Hans, Potters, Jos: The b-nucleolus of tu-games. Games Econ. Behav. 24(1\u20132), 77\u201396 (1998)","journal-title":"Games Econ. Behav."},{"issue":"1","key":"1527_CR26","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/BF01240254","volume":"21","author":"M Maschler","year":"1992","unstructured":"Maschler, M., Potters, J.A.M., Tijs, S.H.: The general nucleolus and the reduced game property. Int. J. Game Theory 21(1), 85\u2013106 (1992)","journal-title":"Int. J. Game Theory"},{"issue":"2","key":"1527_CR27","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/BF01247104","volume":"25","author":"D Granot","year":"1996","unstructured":"Granot, D., Maschler, M., Owen, G., Zhu, W.R.: The kernel\/nucleolus of a standard tree game. Int. J. Game Theory 25(2), 219\u2013244 (1996)","journal-title":"Int. J. Game Theory"},{"key":"1527_CR28","unstructured":"Reijnierse, J.H.: Games, graphs and algorithms. Ph.D. Thesis, Nijmegen (1995)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01527-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-020-01527-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01527-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,10]],"date-time":"2021-10-10T02:40:06Z","timestamp":1633833606000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-020-01527-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,6]]},"references-count":28,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2021,11]]}},"alternative-id":["1527"],"URL":"https:\/\/doi.org\/10.1007\/s10107-020-01527-9","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,6]]},"assertion":[{"value":"19 December 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 May 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 June 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}