Faster Algorithms for the Least-Core value and the Nucleolus in Convex Games
This work addresses a computational bottleneck in cooperative game theory for researchers and practitioners, offering a faster alternative to existing methods, though it is incremental as it builds on known polynomial-time solvability.
The authors tackled the problem of computing the nucleolus in convex games, which is NP-hard in general but polynomial-time solvable, and developed a combinatorial algorithm that improves oracle complexity by a factor of n^3 over previous methods, leading to a new strongly polynomial-time algorithm for the nucleolus.
The nucleolus is a central solution concept in cooperative game theory. While its computation is NP-hard in general, it can be computed in polynomial time for convex games; however, the only published polynomial-time algorithm relies on the ellipsoid method. We develop a combinatorial alternative based on reduced games and iterative least-core value computations. Leveraging submodular function minimization and polyhedral structure in a novel way, we obtain a faster combinatorial algorithm for computing the least-core value, improving the oracle complexity by a factor $n^3$ over previous approaches. As a consequence, we obtain a new strongly polynomial-time and combinatorial algorithm for computing the nucleolus in convex games. Preliminary analysis indicates an improved oracle complexity compared to the ellipsoid-based algorithm.