{"ID":2875473,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.02380","arxiv_id":"2509.02380","title":"Faster Algorithms for the Least-Core value and the Nucleolus in Convex Games","abstract":"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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2509.02380","url_pdf":"https://arxiv.org/pdf/2509.02380v3","authors":"[\"Giacomo Maggiorano\",\"Alessandro Sosso\",\"Gautier Stauffer\"]","published":"2025-09-02T14:46:24Z","proceeding":"cs.GT","tasks":"[\"cs.GT\"]","methods":"[]","has_code":false}