Tournament equilibrium set membership is PSPACE-complete under uniqueness
The Tournament Equilibrium Set Is PSPACE-Complete, Even under Hereditary Uniqueness
Computer Science and Game TheoryComputational Complexity
Summary
The paper studies a voting rule that selects winners based on who beats whom in pairwise comparisons. Determining if a specific candidate is part of this special winning set is very computationally hard — so hard that it requires complex reasoning steps that can grow very quickly. The authors show this difficulty remains even in cases where each smaller group of candidates has a unique special subset, a well-known conjecture in the field. Interestingly, while finding all winners is generally hard, picking one winner can be much faster under certain conditions.
What this means in practice
- •For voting system designers: Identify when membership tests in tournament-based winner selection rules are computationally infeasible, guiding design towards efficient approximations or special cases.
- •For decision support developers: Use special conditions with limited dominators to compute winners efficiently in pairwise comparison methods, improving performance in automated decision aids.
A theory result. No direct application yet.
Authors
Ethan Dickey, Athina Terzoglou
Abstract
The tournament equilibrium set (TEQ), proposed by Schwartz in 1990, is a classical voting rule based on pairwise majority comparisons. Its definition is recursive: an alternative is judged by the alternatives that beat it, called its dominators, and by which of those dominators TEQ itself selects. Deciding whether a given alternative belongs to TEQ was known to be NP-hard and to lie in PSPACE. We close this gap by proving that the problem is PSPACE-complete. To our knowledge, this is the first PSPACE-completeness result for membership in a tournament solution. The hardness persists even when every nonempty subtournament has a unique minimal retentive set, the property conjectured by Schwartz to hold for all tournaments. Moreover, every such subtournament in our hard instances contains an alternative with at most three dominators. We prove that a single alternative with at most four dominators suffices both to guarantee uniqueness and to find a TEQ winner in $O(N^2)$ time. Thus, on our hard instances, finding one winner is efficient even though recognizing a specified winner is PSPACE-complete. We also study how the complexity changes with the dominator bound. If every nonempty subtournament has an alternative with at most one dominator, the entire TEQ can be computed in quadratic time; allowing two dominators makes membership NP-hard. Under the same condition with four dominators, all $t$ winners can be computed in $O(2^t N^2)$ time, where $N$ is the number of alternatives.