Polynomial-Time Algorithms for Computing the Nucleolus: An Assessment

Meinhardt, Holger Ingmar (2025): Polynomial-Time Algorithms for Computing the Nucleolus: An Assessment.

Abstract

Recently, Maggiorano et al. (2025) claimed that they have developed a strongly polynomial-time combinatorial algorithm for the nucleolus in convex games that is based on the reduced game approach and submodular function minimization method. Thereby, avoiding the ellipsoid method with its negative side effects in numerical computation completely. However, we shall argue that this is a fallacy based on an incorrect application of the Davis/Maschler reduced game property (RGP). Ignoring the fact that despite the pre-nucleolus, other solutions like the core, pre-kernel, and semi-reactive pre-bargaining set possess this property as well. This causes a severe selection issue, leading to the failure to compute the nucleolus of convex games using the reduced games approach. In order to assess this finding in its context, the ellipsoid method of Faigle et al. (2001) and the Fenchel-Moreau conjugation-based approach from convex analysis of Meinhardt (2013) to compute a pre-kernel element were resumed. In the latter case, it was exploited that for TU games with a single-valued pre-kernel, both solution concepts coincide. Implying that one has computed the pre-nucleolus if one has found the sole pre-kernel element of the game. Though it is a specialized and highly optimized algorithm for the pre-kernel, it assures runtime complexity of O(n^3) for computing the pre-nucleolus whenever the pre-kernel is a single point, which indicates a polynomial-time algorithm for this class of games.

• Item Type: MPRA Paper
• Language: English
• Keywords: Transferable Utility Game, Pre-Kernel, Pre-Nucleolus, Single-Valuedness of the Pre-Kernel, Fenchel-Moreau Conjugation, Indirect Function, Runtime Complexity, Polynomial-Time Algorithm, Stability Analysis
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C71 - Cooperative Games

References

J. Arin and V. Feltkamp. The Nucleolus and Kernel of Veto-Rich Transferable Utility Games. International Journal of Game Theory, 26:61–73, 1997. URL https://doi.org/10.1007/BF01262513.

D. Chakrabarty, Y. T. Lee, A. Sidford, S. Singla, and S. C.-W. Wong. Faster Matroid Intersection, 2019. URL https://arxiv.org/abs/1911.10765.

M. Davis and M. Maschler. The Kernel of a Cooperative Game. Naval Research Logistic Quarterly, 12:223–259, 1965.

U. Faigle, W. Kern, and J. Kuipers. Note: Computing the nucleolus of min-cost spanning tree games is NP-hard. International Journal of Game Theory, 27(3):443450, 1998. doi: 10.1007/s001820050083. URL https://doi.org/10.1007/s001820050083.

U. Faigle, W. Kern, and J. Kuipers. On the Computation of the Nucleolus of a Cooperative Game. International Journal of Game Theory, 30(1):7998, 2001. doi: 10.1007/s001820100065. URL https://doi.org/10.1007/s001820100065.

D. Granot, M. Maschler, G. Owen, and W.R. Zhu. The kernel/nucleolus of a standard tree game. International Journal of Game Theory, 25(3):219–244, 1996. URL https://doi.org/10.1007/BF01247104.

M. Grötschel, L. Lovász, and A. Schrijver. The Ellipsoid Method and its consequences in Combinatorial Optimization. Combinatorica, 1:169197, 1981. doi: 10.1007/BF02579273. URL https://doi.org/10.1007/BF02579273.

M. Grötschel, L. Lovász, and A. Schrijver, editors. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, Berlin, 2 edition, 2012. doi: 10.1007/978-3-642-78240-4. URL https://doi.org/10.1007/978-3-642-78240-4.

W. Kern and D. Paulusma. Matching games: The least core and the nucleolus. Mathematics of Operations Research, 28(2):294–308, 2003. ISSN 0364765X, 15265471. URL http://www.jstor.org/stable/4127022.

L. Khachiyan. A polynomial time Algorithm in Linear Programming. Doklady Akademii Nauk SSR, 244:1093–1096, 1979. English Translation: Soviet Mathematics Doklady 20: 191–194.

K. Kido. A nonlinear Approximation of the Nucleolus. In W. Takahashi and T. Tanaka, editors, Proceedings of the International Conference on Nonlinear Analysis and Convex Analysis, pages 307–317, Tokyo, 2004. Yokohama Publishers, Yokohama, Japan.

K. Kido. Convergence Theorems for lp-Norm Minimizers with respect to p. Journal of Optimization Theory and Applications, 125:577–589, 2005.

K. Kido. A Modified Kohlberg Criterion and a Nonlinear Method to compute the Nucleolus of a Cooperative Game. Taiwanese Journal of Mathematics, 12:1581–1590, 2008.

E. Kohlberg. The Nucleolus as a Solution of a Minimization Problem. SIAM, Journal of Applied Mathematics, 23:34–39, 1972.

A Kopelowitz. Computation of the Kernels of Simple Games and the Nucleolus of N -Person Games. Technical report, RM 31, Research Program in Game Theory and Mathematical Economics, The Hebrew University of Jerusalem, 1967. mimeo.

Y. T. Lee, A. Sidford, and S. C.-W. Wong. A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization, 2015. URL https://arxiv.org/abs/1508.04874.

G. Maggiorano, A. Sosso, and G. Stauffer. A Strongly Polynomial-Time Combinatorial Algorithm for the Nucleolus in Convex Games, 2025. URL https://arxiv.org/abs/2509.02380.

J-E. Martinez-Legaz. Dual Representation of Cooperative Games based on Fenchel-Moreau Conjugation. Optimization, 36:291–319, 1996.

M. Maschler, B. Peleg, and L.S. Shapley. The Kernel and Bargaining Set for Convex Games. International Journal of Game Theory, 1:73–93, 1972.

M. Maschler, B. Peleg, and L. S. Shapley. Geometric Properties of the Kernel, Nucleolus, and Related Solution Concepts. Mathematics of Operations Research, 4:303–338, 1979.

N. Megiddo. Computational Complexity of the Game Theory Approach to Cost Allocation for a Tree. Mathematics of Operations Research, 3(3):189–196, 1978. URL https://doi.org/10.1287/moor.3.3.189

H. I. Meinhardt. The Pre-Kernel as a Tractable Solution for Cooperative Games: An Exercise in Algorithmic Game Theory, volume 45 of Theory and Decision Library: Series C. Springer Publisher, Heidelberg/Berlin, 2013. ISBN 978-3-642-39548-2. doi: 10.1007/978-3-642-39549-9. URL https://doi.org/10.1007/978-3-642-39549-9.

H. I. Meinhardt. A Note on the Computation of the Pre-Kernel for Permutation Games. Technical Report MPRA-59365, Karlsruhe Institute of Technology (KIT), May 2014. URL http://mpra.ub.uni-muenchen.de/59365/.

H. I. Meinhardt. The Pre-Kernel as a Fair Division Rule for Some Cooperative Game Models, pages 235–266. Springer International Publishing, Cham, 2018. ISBN 978-3-319-61603-2. doi: 10.1007/978-3-319-61603-2_11. URL https://doi.org/10.1007/978-3-319-61603-2_11.

H. I. Meinhardt. Deduction Theorem: The Problematic Nature of Common Practice in Game Theory. arXiv e-prints, art. arXiv:1908.00409, Aug 2021. URL https://arxiv.org/abs/1908.00409v2.

H. I. Meinhardt. TuGames: A Mathematica Package for Cooperative Game Theory, 2023. URL https://github.com/himeinhardt/TuGames.

H. I. Meinhardt. On the Replication of the Pre-Kernel and Related Solutions. Computational Economics, 64:871946, 2024. URL http://dx.doi.org/10.1007/s10614-023-10428-w. Online available 2023.

H. I. Meinhardt. MatTuGames: A Matlab Toolbox for Cooperative Game Theory, 2025a. URL http://www.mathworks.com/matlabcentral/fileexchange/35933-mattugames.

H. I. Meinhardt. Analysis of Cooperative Games with Matlab and Mathematica. Technical report, Karlsruhe Institute of Technology (KIT), Karlsruhe, Germany, 2025b. mimeo.

A. Meseguer-Artola. Using the Indirect Function to characterize the Kernel of a TU-Game. Technical report, Departament d’Economia i d’Història Econòmica, Universitat Autònoma de Barcelona, Nov. 1997. mimeo.

G. Owen. A Note on the Nucleolus. International Journal of Game Theory, 3(2):101–103, 1974. URL https://doi.org/10.1007/BF01766395.

B. Peleg. On the Reduced Game Property and its Converse. International Journal of Game Theory, 15:187–200, 1986.

B. Peleg and P. Sudhölter. Introduction to the Theory of Cooperative Games, volume 34 of Theory and Decision Library: Series C. Springer-Verlag, Heidelberg, 2 edition, 2007.

R. Rockafellar. Convex Analysis. Princeton University Press, Princeton, 1970. L. S. Shapley. Cores of Convex Games,. International Journal of Game Theory, 1:11–26, 1971.

A. J. Sobolev. The Characterization of Optimality Principles in Cooperative Games by Functional Equations. In N. N. Vorobjev, editor, Matematicheskie Metody v Sotsial’nykh Naukakh, Proceedings of the Seminar, pages 94–151, Vilnius, 1975. Institute of Physics and Mathematics, Academy of Sciences of the Lithuanian SSR. (in Russian, English summary).

T. Solymosi. The Kernel is in the Least Core for Permutation Games. Central European Journal of Operations Research, pages 1–15, March 2014. ISSN 1435-246X. doi: 10.1007/s10100-014-0342-y. URL http://dx.doi.org/10.1007/ s10100-014-0342-y.

T. Solymosi and T.E.S Raghavan. An Algorithm for Finding the Nucleolus of Assignment Games. International Journal of Game Theory, 6:94–151, 1994.

R.E. Stearns. Convergent Transfer Schemes for N -Person Games. Transaction of the American Mathematical Society, 134:449–459, 1968.

P. Sudhölter and J. A. M. Potters. The semireactive Bargaining Set of a Cooperative Game. International Journal of Game Theory, 30:117–139, 2001. doi: 10.1007/s001820100068. URL https://doi.org/10.1007/s001820100068.

J. F. Traub and H. Woniakowski. Complexity of linear programming. Operations Research Letters, 1(2):59–62, 1982. ISSN 0167-6377. doi: https://doi.org/10.1016/0167-6377(82)90047-5. URL https://www.sciencedirect.com/science/article/pii/0167637782900475.

J. van den Brand. A Deterministic Linear Program Solver in Current Matrix Multiplication Time, 2020. URL https://arxiv.org/abs/1910.11957.