Unambiguous Problems in Σ₂P

We study the computational complexity of problems that have at most one solution, namely unambiguous problems. We focus mainly on problems syntactically in Σ₂^P, typically of the form: “Does there exist an item that beats 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 ⊆ PCW ⊆ PTW ⊆ S₂^P, and coNP ⊆ PMA ⊆ S₂^P (and it is known that S₂^P ⊆ ZPP^NP ⊆ Σ₂^P ∩ Π₂^P).