Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2509.02380 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917349197611008 |
|---|---|
| author | Maggiorano, Giacomo Sosso, Alessandro Stauffer, Gautier |
| author_facet | Maggiorano, Giacomo Sosso, Alessandro Stauffer, Gautier |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_02380 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Faster Algorithms for the Least-Core value and the Nucleolus in Convex Games Maggiorano, Giacomo Sosso, Alessandro Stauffer, Gautier Computer Science and Game Theory 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. |
| title | Faster Algorithms for the Least-Core value and the Nucleolus in Convex Games |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2509.02380 |