Unambiguous Problems in $\Sigma_2^P$

Matan Gilboa ( University of Oxford )

We study the computational complexity of problems that have at most one solution, namely {\em unambiguous} problems. We focus mainly on problems syntactically in $\Sigma_2^P$, typically of the form: ``Does there {\em exist} an item that beats {\em all} others?'' Motivated by questions in social choice and game theory, we study 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 (sink) in a tournament. We classify these problems, showing the first is $P^{NP}$-complete, the second and third are complete for a class we term PCW (Polynomial Condorcet Winner), and the fourth for a class we term PTW (Polynomial Tournament Winner). We define another unambiguous class PMA (Polynomial Majority Argument), seemingly incomparable to PTW. We show that with randomization, PCW and PTW collapse to $P^{NP}$, and PMA is contained in $P^{NP}$. Specifically, we prove: $P^{NP} \subseteq PCW \subseteq PTW \subseteq S_2P$, and $\coNP{} \subseteq PMA \subseteq S_2P$ (and it is known that $S_2P\subseteq ZPP^{NP} \subseteq \Sigma_2^P \cap \Pi_2^P$).