2025/10/21 by Matan Gilboa, Paul W. Goldberg, Gilboa, Matan +6 · 1 citation
Computer Science · Economics, Econometrics and Finance · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #F.0 #F.2 #FOS: Computer and information sciences #Formal Methods in Verification #Game Theory and Voting Systems #cs.CC #cs.GT
paper · pdf · doi:10.48550/arxiv.2510.19084
Earlier versions of this work included a preliminary version of the results in arXiv:2607.27277, when the two works formed a single manuscript. 43 pages, 1 figures
openalex publication_date 2025/10/21 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28 · arxiv created 2026/07/31 · arxiv updated 2026/08/03
Various practical problems within the class Σ2P possess an unambiguity property, meaning that yes-instances correspond with a unique witness. The semantic class containing all unambiguous Σ2P problems is denoted UΣ2P. Examples include the existence of (1) a dominating strategy in a game, (2) a Condorcet winner, (3) a strongly popular partition in hedonic games, and (4) a winner (source) in a tournament. The computational complexity of unambiguous problems is not well understood, leaving many questions unresolved. We address this gap in a broad complexity-theoretic sense; our main contributions consist of the following. - We identify three syntactic subclasses of UΣ2P associated with general properties of problems that guarantee uniqueness: Polynomial Tournament Winner (PTW), Polynomial Condorcet Winner (PCW), and Polynomial Majority Argument (PMA). - We establish complexity upper and lower bounds for our proposed classes. In particular, we show that they are all contained in S2P and are thus significantly easier than the immediate Σ2P upper bound. - We characterize the complexity of various practical problems using this framework.