{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T20:21:12Z","timestamp":1767990072883,"version":"3.49.0"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T00:00:00Z","timestamp":1739232000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T00:00:00Z","timestamp":1739232000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003825","name":"Magyar Tudom\u00e1nyos Akad\u00e9mia","doi-asserted-by":"publisher","award":["LP2021-2"],"award-info":[{"award-number":["LP2021-2"]}],"id":[{"id":"10.13039\/501100003825","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100011019","name":"Nemzeti Kutat\u00e1si Fejleszt\u00e9si \u00e9s Innov\u00e1ci\u00f3s Hivatal","doi-asserted-by":"publisher","award":["K138945"],"award-info":[{"award-number":["K138945"]}],"id":[{"id":"10.13039\/501100011019","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100011019","name":"Nemzeti Kutat\u00e1si Fejleszt\u00e9si \u00e9s Innov\u00e1ci\u00f3s Hivatal","doi-asserted-by":"publisher","award":["K143858"],"award-info":[{"award-number":["K143858"]}],"id":[{"id":"10.13039\/501100011019","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2025,11]]},"abstract":"Abstract<\/jats:title>\n \n We introduce partitioned matching games as a suitable model for international kidney exchange programmes, where in each round the total number of available kidney transplants needs to be distributed amongst the participating countries in a \u201cfair\u201d way. A partitioned matching game (\n N<\/jats:italic>\n ,\u00a0\n v<\/jats:italic>\n ) is defined on a graph\n \n \n $$G=(V,E)$$<\/jats:tex-math>\n \n \n G<\/mml:mi>\n =<\/mml:mo>\n (<\/mml:mo>\n V<\/mml:mi>\n ,<\/mml:mo>\n E<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n with an edge weighting\n w<\/jats:italic>\n and a partition\n \n \n $$V=V_1 \\cup \\dots \\cup V_n$$<\/jats:tex-math>\n \n \n V<\/mml:mi>\n =<\/mml:mo>\n \n V<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n \u222a<\/mml:mo>\n \u22ef<\/mml:mo>\n \u222a<\/mml:mo>\n \n V<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . The player set is\n \n \n $$N = \\{ 1, \\dots , n\\}$$<\/jats:tex-math>\n \n \n N<\/mml:mi>\n =<\/mml:mo>\n {<\/mml:mo>\n 1<\/mml:mn>\n ,<\/mml:mo>\n \u22ef<\/mml:mo>\n ,<\/mml:mo>\n n<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , and player\n \n \n $$p \\in N$$<\/jats:tex-math>\n \n \n p<\/mml:mi>\n \u2208<\/mml:mo>\n N<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n owns the vertices in\n \n \n $$V_p$$<\/jats:tex-math>\n \n \n V<\/mml:mi>\n p<\/mml:mi>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . The value\n v<\/jats:italic>\n (\n S<\/jats:italic>\n ) of a coalition\u00a0\n \n \n $$S \\subseteq N$$<\/jats:tex-math>\n \n \n S<\/mml:mi>\n \u2286<\/mml:mo>\n N<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is the maximum weight of a matching in the subgraph of\n G<\/jats:italic>\n induced by the vertices owned by the players in\u00a0\n S<\/jats:italic>\n . If\n \n \n $$|V_p|=1$$<\/jats:tex-math>\n \n \n \n |<\/mml:mo>\n <\/mml:mrow>\n \n V<\/mml:mi>\n p<\/mml:mi>\n <\/mml:msub>\n \n |<\/mml:mo>\n =<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n for all\n \n \n $$p\\in N$$<\/jats:tex-math>\n \n \n p<\/mml:mi>\n \u2208<\/mml:mo>\n N<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , then we obtain the classical matching game. Let\n \n \n $$c=\\max \\{|V_p| \\; |\\; 1\\le p\\le n\\}$$<\/jats:tex-math>\n \n \n c<\/mml:mi>\n =<\/mml:mo>\n max<\/mml:mo>\n {<\/mml:mo>\n |<\/mml:mo>\n \n V<\/mml:mi>\n p<\/mml:mi>\n <\/mml:msub>\n |<\/mml:mo>\n \n |<\/mml:mo>\n \n 1<\/mml:mn>\n \u2264<\/mml:mo>\n p<\/mml:mi>\n \u2264<\/mml:mo>\n n<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n be the width of (\n N<\/jats:italic>\n ,\u00a0\n v<\/jats:italic>\n ). We prove that checking core non-emptiness is polynomial-time solvable if\n \n \n $$c\\le 2$$<\/jats:tex-math>\n \n \n c<\/mml:mi>\n \u2264<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n but co--hard if\n \n \n $$c\\le 3$$<\/jats:tex-math>\n \n \n c<\/mml:mi>\n \u2264<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . We do this via pinpointing a relationship with the known class of\n b<\/jats:italic>\n -matching games and completing the complexity classification on testing core non-emptiness for\n b<\/jats:italic>\n -matching games. With respect to our application, we prove a number of complexity results on choosing, out of possibly many optimal solutions, one that leads to a kidney transplant distribution that is as close as possible to some prescribed fair distribution.\n <\/jats:p>","DOI":"10.1007\/s10107-025-02200-9","type":"journal-article","created":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T07:22:37Z","timestamp":1739258557000},"page":"723-758","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Partitioned matching games for international kidney exchange"],"prefix":"10.1007","volume":"214","author":[{"given":"M\u00e1rton","family":"Benedek","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7011-3463","authenticated-orcid":false,"given":"P\u00e9ter","family":"Bir\u00f3","sequence":"additional","affiliation":[]},{"given":"Walter","family":"Kern","sequence":"additional","affiliation":[]},{"given":"D\u00f6m\u00f6t\u00f6r","family":"P\u00e1lv\u00f6lgyi","sequence":"additional","affiliation":[]},{"given":"Daniel","family":"Paulusma","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,2,11]]},"reference":[{"key":"2200_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, D.J., Blum, A., Sandholm, T.: Clearing algorithms for barter exchange markets: enabling nationwide kidney exchanges. In: Proceedings of EC 2007, pp. 295\u2013304 (2007)","DOI":"10.1145\/1250910.1250954"},{"key":"2200_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2019.05.011","volume":"790","author":"H Aziz","year":"2019","unstructured":"Aziz, H., Bir\u00f3, P., Lang, J., Lesca, J., Monnot, J.: Efficient reallocation under additive and responsive preferences. Theor. Comput. Sci. 790, 1\u201315 (2019)","journal-title":"Theor. Comput. Sci."},{"key":"2200_CR3","doi-asserted-by":"crossref","unstructured":"Aziz, H., Cseh, \u00c1., Dickerson, J.P., McElfresh, D.C.: Optimal kidney exchange with immunosuppressants. In: Proceedings of AAAI 2021, pp. 21\u201329 (2021)","DOI":"10.1609\/aaai.v35i1.16073"},{"key":"2200_CR4","doi-asserted-by":"crossref","unstructured":"Bateni, M., Hajiaghayi, M., Immorlica, N., Mahini, H.: The cooperative game theory foundations of network bargaining games. In: Proceedings of ICALP 2010, LNCS 6198, pp. 67\u201378 (2010)","DOI":"10.1007\/978-3-642-14165-2_7"},{"key":"2200_CR5","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1613\/jair.1.14281","volume":"77","author":"M Benedek","year":"2023","unstructured":"Benedek, M., Bir\u00f3, P., Johnson, M., Paulusma, D., Ye, X.: The complexity of matching games: a survey. J. Artif. Intell. Res. 77, 459\u2013485 (2023)","journal-title":"J. Artif. Intell. Res."},{"key":"2200_CR6","doi-asserted-by":"crossref","unstructured":"Benedek, M., Bir\u00f3, P., Kern, W., Paulusma, D.: Computing balanced solutions for large international kidney exchange schemes. In: Proceedings of AAMAS 2022, pp. 82\u201390 (2022)","DOI":"10.21203\/rs.3.rs-2621065\/v1"},{"key":"2200_CR7","doi-asserted-by":"crossref","unstructured":"Bir\u00f3, P., Gyetvai, M., Klimentova, X., Pedroso, J.P., Pettersson, W., Viana, A.: Compensation scheme with Shapley value for multi-country kidney exchange programmes. In: Proceedings of ECMS 2020, pp. 129\u2013136 (2020)","DOI":"10.7148\/2020-0129"},{"key":"2200_CR8","doi-asserted-by":"publisher","first-page":"1514","DOI":"10.1097\/TP.0000000000002432","volume":"103","author":"P Bir\u00f3","year":"2019","unstructured":"Bir\u00f3, P., Haase-Kromwijk, B., Andersson, T., et al.: Building kidney exchange programmes in Europe\u2014an overview of exchange practice and activities. Transplantation 103, 1514\u20131522 (2019)","journal-title":"Transplantation"},{"key":"2200_CR9","unstructured":"Bir\u00f3, P., Kern, W., P\u00e1lv\u00f6lgyi, D., Paulusma, D.: Generalized matching games for international kidney exchange. In: Proceedings of AAMAS 2019, pp. 413\u2013421 (2019)"},{"key":"2200_CR10","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/s00182-011-0273-y","volume":"41","author":"P Bir\u00f3","year":"2012","unstructured":"Bir\u00f3, P., Kern, W., Paulusma, D.: Computing solutions for matching games. Int. J. Game Theory 41, 75\u201390 (2012)","journal-title":"Int. J. Game Theory"},{"key":"2200_CR11","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/j.geb.2017.02.002","volume":"108","author":"P Bir\u00f3","year":"2018","unstructured":"Bir\u00f3, P., Kern, W., Paulusma, D., Wojuteczky, P.: The stable fixtures problem with payments. Games Econom. Behav. 108, 245\u2013268 (2018)","journal-title":"Games Econom. Behav."},{"key":"2200_CR12","doi-asserted-by":"publisher","first-page":"638","DOI":"10.1111\/tri.12945","volume":"30","author":"GA B\u00f6hmig","year":"2017","unstructured":"B\u00f6hmig, G.A., Fronek, J., Slavcev, A., Fischer, G.F., Berlakovich, G., Viklicky, O.: Czech-Austrian kidney paired donation: first European cross-border living donor kidney exchange. Transpl. Int. 30, 638\u2013639 (2017)","journal-title":"Transpl. Int."},{"key":"2200_CR13","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1016\/j.ejor.2022.05.027","volume":"305","author":"M Carvalho","year":"2023","unstructured":"Carvalho, M., Lodi, A.: A theoretical and computational equilibria analysis of a multi-player kidney exchange program. Eur. J. Oper. Res. 305, 373\u2013385 (2023)","journal-title":"Eur. J. Oper. Res."},{"key":"2200_CR14","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/s10107-016-1013-7","volume":"161","author":"M Carvalho","year":"2017","unstructured":"Carvalho, M., Lodi, A., Pedroso, J.P., Viana, A.: Nash equilibria in the two-player kidney exchange game. Math. Program. 161, 389\u2013417 (2017)","journal-title":"Math. Program."},{"key":"2200_CR15","doi-asserted-by":"publisher","first-page":"751","DOI":"10.1287\/moor.24.3.751","volume":"24","author":"X Deng","year":"1999","unstructured":"Deng, X., Ibaraki, T., Nagamochi, H.: Algorithmic aspects of the core of combinatorial optimization games. Math. Oper. Res. 24, 751\u2013766 (1999)","journal-title":"Math. Oper. Res."},{"key":"2200_CR16","doi-asserted-by":"publisher","first-page":"125","DOI":"10.6028\/jres.069B.013","volume":"69B","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Maximum matching and a polyhedron with $$0,1$$-vertices. J. Res. Natl. Bur. Stand. Sect. B 69B, 125\u2013130 (1965)","journal-title":"J. Res. Natl. Bur. Stand. Sect. B"},{"key":"2200_CR17","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. H. Freeman & Co., New York (1979)"},{"key":"2200_CR18","first-page":"111","volume":"7","author":"L Gourv\u00e8s","year":"2013","unstructured":"Gourv\u00e8s, L., Monnot, J., Pascual, F.: Cooperation in multiorganization matching. Algorithmic Oper. Res. 7, 111\u2013124 (2013)","journal-title":"Algorithmic Oper. Res."},{"key":"2200_CR19","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 169\u2013197 (1981)","journal-title":"Combinatorica"},{"key":"2200_CR20","doi-asserted-by":"publisher","first-page":"8:1","DOI":"10.1145\/3041402","volume":"9","author":"R Gurjar","year":"2017","unstructured":"Gurjar, R., Korwar, A., Messner, J., Thierauf, T.: Exact perfect matching in complete graphs. ACM Trans. Comput. Theory 9, 8:1-8:20 (2017)","journal-title":"ACM Trans. Comput. Theory"},{"key":"2200_CR21","first-page":"191","volume":"20","author":"LG Khachiyan","year":"1979","unstructured":"Khachiyan, L.G.: A polynomial algorithm in linear programming. Soviet Math. Doklady 20, 191\u2013194 (1979)","journal-title":"Soviet Math. Doklady"},{"key":"2200_CR22","doi-asserted-by":"publisher","first-page":"102333","DOI":"10.1016\/j.omega.2020.102333","volume":"102","author":"X Klimentova","year":"2021","unstructured":"Klimentova, X., Viana, A., Pedroso, J. a P., Santos, N.: Fairness models for multi-agent kidney exchange programmes. Omega 102, 102333 (2021)","journal-title":"Omega"},{"key":"2200_CR23","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/s10107-020-01483-4","volume":"183","author":"J K\u00f6nemann","year":"2020","unstructured":"K\u00f6nemann, J., Pashkovich, K., Toth, J.: Computing the nucleolus of weighted cooperative matching games in polynomial time. Math. Program. 183, 555\u2013581 (2020)","journal-title":"Math. Program."},{"key":"2200_CR24","doi-asserted-by":"crossref","unstructured":"K\u00f6nemann, J., Toth, J.: A general framework for computing the nucleolus via dynamic programming. In: Proceedings of SAGT 2020, LNCS 12283, pp. 307\u2013321 (2020)","DOI":"10.1007\/978-3-030-57980-7_20"},{"key":"2200_CR25","doi-asserted-by":"crossref","unstructured":"K\u00f6nemann, J., Toth, J., Zhou, F.: On the complexity of nucleolus computation for bipartite $$b$$-matching games. In: Proceedings of SAGT 2021, LNCS 12885, 171\u2013185 (2021)","DOI":"10.1007\/978-3-030-85947-3_12"},{"key":"2200_CR26","doi-asserted-by":"publisher","first-page":"53","DOI":"10.2307\/1907742","volume":"25","author":"TC Koopmans","year":"1957","unstructured":"Koopmans, T.C., Beckmann, M.: Assignment problems and the location of economic activities. Econometrica 25, 53\u201376 (1957)","journal-title":"Econometrica"},{"key":"2200_CR27","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02579206","volume":"7","author":"K Mulmuley","year":"1987","unstructured":"Mulmuley, K., Vazirani, U.V., Vazirani, V.V.: Matching is as easy as matrix inversion. Combinatorica 7, 105\u2013113 (1987)","journal-title":"Combinatorica"},{"key":"2200_CR28","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1145\/322307.322309","volume":"29","author":"CH Papadimitriou","year":"1982","unstructured":"Papadimitriou, C.H., Yannakakis, M.: The complexity of restricted spanning tree problems. J. ACM 29, 285\u2013309 (1982)","journal-title":"J. ACM"},{"key":"2200_CR29","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/S0166-218X(99)00052-9","volume":"92","author":"J Plesn\u00edk","year":"1999","unstructured":"Plesn\u00edk, J.: Constrained weighted matchings and edge coverings in graphs. Discrete Appl. Math. 92, 229\u2013241 (1999)","journal-title":"Discrete Appl. Math."},{"key":"2200_CR30","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF01753437","volume":"1","author":"LS Shapley","year":"1972","unstructured":"Shapley, L.S., Shubik, M.: The assignment game I: the core. Int. J. Game Theory 1, 111\u2013130 (1972)","journal-title":"Int. J. Game Theory"},{"key":"2200_CR31","doi-asserted-by":"crossref","unstructured":"Sotomayor, M.: The multiple partners game. In: Equilibrium and Dynamics: Essays in Honor of David Gale. Macmillan Press Ltd, New York (1992)","DOI":"10.1007\/978-1-349-11696-6_17"},{"key":"2200_CR32","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/0012-365X(95)00324-P","volume":"163","author":"IA Stewart","year":"1997","unstructured":"Stewart, I.A.: On locating cubic subgraphs in bounded-degree connected bipartite graphs. Discrete Math. 163, 319\u2013324 (1997)","journal-title":"Discrete Math."},{"key":"2200_CR33","doi-asserted-by":"crossref","unstructured":"Sun, Z., Todo, T., Walsh, T.: Fair pairwise exchange among groups. In: Proceedings of IJCAI 2021, pp. 419\u2013425 (2021)","DOI":"10.24963\/ijcai.2021\/59"},{"key":"2200_CR34","doi-asserted-by":"publisher","first-page":"347","DOI":"10.4153\/CJM-1954-033-3","volume":"6","author":"WT Tutte","year":"1954","unstructured":"Tutte, W.T.: A short proof of the factor theorem for finite graphs. Can. J. Math. 6, 347\u2013352 (1954)","journal-title":"Can. J. Math."},{"key":"2200_CR35","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1097\/TP.0000000000002664","volume":"103","author":"MO Valent\u00edn","year":"2019","unstructured":"Valent\u00edn, M.O., Garcia, M., Costa, A.N., Bolotinha, C., Guirado, L., Vistoli, F., Breda, A., Fiaschetti, P., Dominguez-Gil, B.: International cooperation for kidney exchange success. Transplantation 103, 180\u2013181 (2019)","journal-title":"Transplantation"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-025-02200-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-025-02200-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-025-02200-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T07:51:01Z","timestamp":1764575461000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-025-02200-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,11]]},"references-count":35,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2025,11]]}},"alternative-id":["2200"],"URL":"https:\/\/doi.org\/10.1007\/s10107-025-02200-9","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,11]]},"assertion":[{"value":"2 February 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 January 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 February 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declared that they have no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}