On the complexity of nucleolus computation for bipartite \(b\)-matching games. (English) Zbl 1541.91015
Summary: We explore the complexity of nucleolus computation in \(b\)-matching games on bipartite graphs. We show that computing the nucleolus of a simple \(b\)-matching game is \(\mathcal{NP}\)-hard when \(b \equiv 3\) even on bipartite graphs of maximum degree 7. We complement this with partial positive results in the special case where \(b\) values are bounded by 2. In particular, we describe an efficient algorithm when a constant number of vertices satisfy \(b_v = 2\) as well as an efficient algorithm for computing the non-simple \(b\)-matching nucleolus when \(b \equiv 2\).
MSC:
| 91A12 | Cooperative games |
| 91A43 | Games involving graphs |
| 91A68 | Algorithmic game theory and complexity |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
Keywords:
algorithmic game theory; combinatorial optimization; matching games; cooperative game theory; linear programming; complexity theoryReferences:
| [1] | Aumann, Robert J.; Maschler, Michael, Game theoretic analysis of a bankruptcy problem from the Talmud, J. Econ. Theory, 36, 2, 195-213, 1985 · Zbl 0578.90100 |
| [2] | Bateni, Mohammad Hossein; Hajiaghayi, Mohammad Taghi; Immorlica, Nicole; Mahini, Hamid, The cooperative game theory foundations of network bargaining games, (International Colloquium on Automata, Languages, and Programming, 2010, Springer), 67-78 · Zbl 1287.91008 |
| [3] | Biró, Péter; Kern, Walter; Paulusma, Daniël; Wojuteczky, Péter, The stable fixtures problem with payments, Games Econ. Behav., 108, 245-268, 2018 · Zbl 1400.91014 |
| [4] | Biró, Péter; Kern, Walter; Pálvölgyi, Dömötör; Paulusma, Daniel, Generalized matching games for international kidney exchange, (Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, 2019), 413-421 |
| [5] | Biró, Péter; Kern, Walter; Paulusma, Daniël, Computing solutions for matching games, Int. J. Game Theory, 41, 1, 75-90, 2012 · Zbl 1232.91026 |
| [6] | Brânzei, Rodica; Solymosi, Tamás; Tijs, Stef, Strongly essential coalitions and the nucleolus of peer group games, Int. J. Game Theory, 33, 3, 447-460, 2005 · Zbl 1121.91009 |
| [7] | Cook, Karen S.; Yamagishi, Toshio, Power in exchange networks: a power-dependence formulation, Soc. Netw., 14, 3-4, 245-265, 1992 |
| [8] | Deng, Xiaotie; Fang, Qizhi, Algorithmic cooperative game theory, (Pareto Optimality, Game Theory and Equilibria, 2008, Springer), 159-185 · Zbl 1152.91322 |
| [9] | Deng, Xiaotie; Fang, Qizhi; Sun, Xiaoxun, Finding nucleolus of flow game, J. Comb. Optim., 18, 1, 64-86, 2009 · Zbl 1188.91024 |
| [10] | Diestel, Reinhard, Graph Theory, GTM, vol. 173, 2016 |
| [11] | Deng, Xiaotie; Ibaraki, Toshihide; Nagamochi, Hiroshi, Algorithmic aspects of the core of combinatorial optimization games, Math. Oper. Res., 24, 3, 751-766, 1999 · Zbl 1064.91505 |
| [12] | Drechsel, Julia; Kimms, Alf, Computing core allocations in cooperative games with an application to cooperative procurement, Int. J. Prod. Econ., 128, 1, 310-321, 2010 |
| [13] | Davis, Morton; Maschler, Michael, The kernel of a cooperative game, Nav. Res. Logist. Q., 12, 3, 223-259, 1965 · Zbl 0204.20202 |
| [14] | Easley, David; Kleinberg, Jon, Networks, crowds, and markets: reasoning about a highly connected world, Significance, 9, 1, 43-44, 2012 |
| [15] | Elkind, Edith; Goldberg, Leslie Ann; Goldberg, Paul; Wooldridge, Michael, Computational complexity of weighted threshold games, (AAAI, 2007), 718-723 |
| [16] | Elkind, Edith; Goldberg, Leslie Ann; Goldberg, Paul W.; Wooldridge, Michael, On the computational complexity of weighted voting games, Ann. Math. Artif. Intell., 56, 2, 109-131, 2009 · Zbl 1185.91081 |
| [17] | Faigle, Ulrich; Kern, Walter; Kuipers, Jeroen, On the computation of the nucleolus of a cooperative game, Int. J. Game Theory, 30, 1, 79-98, 2001 · Zbl 1060.91011 |
| [18] | Faigle, Ulrich; Kern, Walter; Kuipers, Jeroen, Computing an element in the lexicographic kernel of a game, Math. Methods Oper. Res., 63, 3, 427-433, 2006 · Zbl 1133.91005 |
| [19] | Faigle, Ulrich; Kern, Walter; Kuipers, Jeroen, Note computing the nucleolus of min-cost spanning tree games is NP-hard, Int. J. Game Theory, 27, 3, 443-450, 1998 · Zbl 1058.91511 |
| [20] | Faigle, Ulrich; Kern, Walter; Paulusma, Daniël, Note on the computational complexity of least core concepts for min-cost spanning tree games, Math. Methods Oper. Res., 52, 1, 23-38, 2000 · Zbl 1054.91010 |
| [21] | Granot, Daniel; Granot, Frieda; Zhu, Weiping R., Characterization sets for the nucleolus, Int. J. Game Theory, 27, 3, 359-374, 1998 · Zbl 0960.91009 |
| [22] | Gonzalez, Teofilo F., Clustering to minimize the maximum intercluster distance, Theor. Comput. Sci., 38, 293-306, 1985 · Zbl 0567.62048 |
| [23] | Granot, Daniel; Maschler, Michael; Owen, Guillermo; Zhu, Weiping R., The kernel/nucleolus of a standard tree game, Int. J. Game Theory, 25, 2, 219-244, 1996 · Zbl 0846.90136 |
| [24] | Hardwick, John, Graphical Algorithms for Finding the Nucleolus of Binary-Valued Matching Games, 2017, University of Illinois at Chicago, PhD thesis |
| [25] | Khachiyan, Leonid Genrikhovich, A polynomial algorithm in linear programming, Dokl. Akad. Nauk, 244, 5, 1093-1096, 1979 · Zbl 0414.90086 |
| [26] | Kopelowitz, Alexander, Computation of the kernels of simple games and the nucleolus of n-person games, 1967, Hebrew University of Jerusalem (Israel), Department of Mathematics, Tech. Rep. |
| [27] | Kern, Walter; Paulusma, Daniël, Matching games: the least core and the nucleolus, Math. Oper. Res., 28, 2, 294-308, 2003 · Zbl 1082.91016 |
| [28] | Könemann, Jochen; Pashkovich, Kanstantsin; Toth, Justin, Computing the nucleolus of weighted cooperative matching games in polynomial time, Math. Program., 1-27, 2020 |
| [29] | Kuipers, Jeroen; Solymosi, Tamás; Aarts, Harry, Computing the nucleolus of some combinatorially-structured games, Math. Program., 88, 3, 541-563, 2000 · Zbl 1034.91021 |
| [30] | Könemann, Jochen; Toth, Justin, A general framework for computing the nucleolus via dynamic programming, (International Symposium on Algorithmic Game Theory, 2020, Springer), 307-321 · Zbl 1503.91019 |
| [31] | Lemaire, Jean, An application of game theory: cost allocation, ASTIN Bull., 14, 1, 61-81, 1984 |
| [32] | Maschler, Michael; Peleg, Bezalel; Shapley, Lloyd S., Geometric properties of the kernel, nucleolus, and related solution concepts, Math. Oper. Res., 4, 4, 303-338, 1979 · Zbl 0426.90097 |
| [33] | Nash, John F., The bargaining problem, Econometrica, 155-162, 1950 · Zbl 1202.91122 |
| [34] | Paulusma, Daniël, Complexity Aspects of Cooperative Games, 2001, Citeseer |
| [35] | Plesník, Ján, A note on the complexity of finding regular subgraphs, Discrete Math., 49, 2, 161-167, 1984 · Zbl 0567.05029 |
| [36] | Potters, Jos; Reijnierse, Hans; Biswas, Amit, The nucleolus of balanced simple flow networks, Games Econ. Behav., 54, 1, 205-225, 2006 · Zbl 1129.91006 |
| [37] | Schrijver, Alexander, Combinatorial Optimization: Polyhedra and Efficiency, vol. 24, 2003, Springer Science & Business Media · Zbl 1041.90001 |
| [38] | Schmeidler, David, The nucleolus of a characteristic function game, SIAM J. Appl. Math., 17, 6, 1163-1170, 1969 · Zbl 0191.49502 |
| [39] | Sziklai, Balázs; Fleiner, Tamás; Solymosi, Tamás, On the core and nucleolus of directed acyclic graph games, Math. Program., 163, 1-2, 243-271, 2017 · Zbl 1366.91038 |
| [40] | Solymosi, Tamás; Raghavan, Tirukkannamangai E. S., An algorithm for finding the nucleolus of assignment games, Int. J. Game Theory, 23, 2, 119-143, 1994 · Zbl 0811.90128 |
| [41] | Solymosi, Tamás; Sziklai, Balázs, Characterization sets for the nucleolus in balanced games, Oper. Res. Lett., 44, 4, 520-524, 2016 · Zbl 1380.91019 |
| [42] | Shapley, Lloyd S.; Shubik, Martin, The assignment game I: the core, Int. J. Game Theory, 1, 1, 111-130, 1971 · Zbl 0236.90078 |
| [43] | Stearns, Richard Edwin, Convergent transfer schemes for n-person games, Trans. Am. Math. Soc., 134, 3, 449-459, 1968 · Zbl 0175.47402 |
| [44] | Willer, David, Network Exchange Theory, 1999, Greenwood Publishing Group |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
