The Complexity of the Nucleolus in Compact Games
- Submitting institution
-
King's College London
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 136476463
- Type
- D - Journal article
- DOI
-
10.1145/2692372.2692374
- Title of journal
- ACM Transactions on Computation Theory
- Article number
- 3
- First page
- -
- Volume
- 7
- Issue
- 1
- ISSN
- 1942-3454
- Open access status
- Out of scope for open access requirements
- Month of publication
- December
- Year of publication
- 2014
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
3
- Research group(s)
-
-
- Citation count
- 12
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- The nucleolus is a prominent coalitional game solution concept maximizing players’ social welfare. Its computational complexity was conjectured and left open more than a decade earlier in a seminal paper by Papadimitriou. This work closes the problem by proving its precise complexity via sophisticated reduction (for hardness) and algorithm (for membership). To obtain these results, an extensive investigation on linear optimization problems with exponentially many constraints represented in polynomial space is also conducted. This is an important contribution on its own, as it sheds light on an unexplored area of mathematical optimization, where optimization problems are compactly represented.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -