Faster Algorithms for the Least-Core value and the Nucleolus in Convex Games

A team of researchers—Giacomo Maggiorano, Alessandro Sosso, and Gautier Stauffer—has published a paper introducing significantly faster algorithms for computing two central solution concepts in cooperative game theory: the least-core value and the nucleolus. While computing the nucleolus is generally NP-hard, it becomes polynomial-time solvable for convex games, a class where cooperation becomes more valuable as groups grow. Previously, the only known polynomial-time algorithm relied on the theoretically powerful but practically complex ellipsoid method. The new work provides a combinatorial alternative based on constructing reduced games and performing iterative least-core computations.

The breakthrough comes from a novel application of submodular function minimization and careful exploitation of polyhedral structure. This approach achieves an improvement in oracle complexity by a factor of n³ (where 'n' is the number of players) over prior methods for finding the least-core value. As a direct consequence, the researchers derive a new, strongly polynomial-time combinatorial algorithm for computing the nucleolus itself. Preliminary analysis indicates this method also improves upon the oracle complexity of the ellipsoid-based algorithm, offering a more intuitive and potentially more implementable pathway to solving these complex allocation problems.