The Tournament Equilibrium Set Is PSPACE-Complete, Even under Hereditary Uniqueness
summary
The gist
The Tournament Equilibrium Set (TEQ), proposed by Schwartz in 1990, is a voting rule based on pairwise majority comparisons, defined recursively: an alternative is judged by its dominators…
In short
The Tournament Equilibrium Set (TEQ) is a voting rule based on pairwise majority comparisons. The paper proves that deciding if a specific alternative belongs to TEQ is PSPACE-complete, even when every recursive subproblem has a unique minimal retentive set. This shows the complexity arises purely from the comparison structure.
Key concepts
- Tournament Equilibrium Set (TEQ)
- A voting rule defined recursively where an alternative is judged by its dominators, and TEQ selects among those dominators. The complexity of membership in this set is studied based on structural properties of the tournament.
- Hereditary Dominator Bound ($D_k$)
- This bound relates to the maximum number of dominators an alternative can have within any induced subtournament. The paper shows that TEQ membership hardness changes depending on whether this bound is 1, 2, 3, or 4.
- Minimal Retentive Set
- A specific set of vertices within a tournament structure that plays a crucial role in the recursive definition of TEQ. Analyzing the uniqueness and properties of these sets helps prove the PSPACE-completeness results.
Terminology used across episodes
This episode discusses
- The Tournament Equilibrium Set Is PSPACE-Complete, Even under Hereditary Uniqueness · Paper Radio
- A tournament of order 24 with two disjoint TEQ-retentive sets
- Stable Voting is PSPACE-Complete
- A Further Step Towards an Understanding of the Tournament Equilibrium Set
The paper
The Tournament Equilibrium Set Is PSPACE-Complete, Even under Hereditary Uniqueness · Read on arXiv
Ethan Dickey, Athina Terzoglou
Department of Computer Science, Purdue University
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "The Tournament Equilibrium Set Is PSPACE-Complete, Even under Hereditary Uniqueness".
Jane: Here's the gist of the paper. The Tournament Equilibrium Set (TEQ), proposed by Schwartz in 1990, is a voting rule based on pairwise majority comparisons, defined recursively: an alternative is judged by its dominators, and TEQ selects among those dominators.
Tom: The paper establishes the PSPACE-completeness of deciding whether a designated vertex belongs to TEQ under polynomial-time many-one reductions (Theorem 1.1).
Jane: This result closes a gap, showing that this complexity arises solely from the directions of pairwise comparisons, even when every recursive subproblem possesses a unique minimal retentive set.
Tom: The complexity of TEQ membership is intricately linked to the hereditary dominator bound (D k).
Title and authors: Tom: Ethan Dickey and Athina Terzoglou are the authors of this paper, and the title really tells you what's coming: The Tournament Equilibrium Set Is PSPACE-Complete, Even under Hereditary Uniqueness. It sets a very high bar for complexity results in this area.
Jane: When you hear PSPACE-complete, it’s a big computational class that usually means the problem requires a lot of memory to solve, even if the time taken isn't exponentially long. It implies we can't just use simple fast algorithms to find an answer for these tournaments.
Lu: The paper is making a claim that this PSPACE-completeness holds even when you have that extra property of hereditary uniqueness you mentioned earlier, which was considered a strong assumption by Schwartz.
Meng: That’s interesting because if it's hard even under those nice structural conditions, it suggests the difficulty isn't just about the general structure but about the recursive way TEQ is defined through those comparisons.
Lalam: It really highlights how deeply tied this complexity is to the underlying logic of pairwise majority decisions, not just some arbitrary configuration of vertices.
The paper's summary: Tom: So, what’s the core mechanism they are describing here? They define TEQ recursively: an alternative is judged by its dominators, and then TEQ selects among those dominators. This recursive definition is where the complexity seems to explode.
Jane: It’s like a chain of voting decisions, where each step depends on the results of the previous ones, and this nesting creates that PSPACE hardness for membership testing.
Lu: The paper proves they can reduce problems from TQBF, which is Quantified Boolean Formula satisfiability—that’s a very powerful class—to deciding TEQ membership in tournaments using clause gadgets and layers for the quantifiers.
Meng: So they’re essentially showing that you can encode complex logical structures like nested "for all" and "there exists" statements directly into a tournament structure.
Lalam: And they do this even when the tournament has a very specific property called hereditary uniqueness, which is what makes this result particularly noteworthy for the field.
The paper's improvements: Tom: Now, they don't just stop at proving it’s PSPACE-complete; they actually provide some constructive results that show how to deal with these hard instances in practice. They mention a single alternative with at most four dominators being enough for both uniqueness and finding a winner in quadratic time.
Jane: That’s a bit of a relief, because if we only cared about finding *one* member, they give us an O(N two) algorithm under certain conditions—specifically when every induced subtournament has at most four dominators <ref:2611.17312#pg2>.
Lu: They also have a certified closure algorithm that can compute the entire set in time related to two t times N squared plus some other polynomial function of N. This is what allows them to find the whole set deterministically on structured tournaments like D3 and D4.
Meng: But I gotta ask, what does it cost for me? If I have a massive tournament, running an algorithm that takes time related to N squared is fine for a small instance, but if N is huge and we need the full set computation...
Lalam: The paper points out that on structured tournaments in D4, finding all winners can be done in time related to N squared. And they also show that for fixed k, it’s O of N cubed. These are concrete performance bounds based on the structure of the tournament class.
Conclusion: Tom: So to wrap up, this paper proves that even with unique minimal retentive sets, deciding if something belongs to TEQ is PSPACE-complete because it can encode quantified logic very effectively. It closes a gap in understanding the complexity of this voting rule.
Jane: The main implication for us is that we have to be careful not to assume simple structural properties guarantee easy solutions; the recursive nature of TEQ keeps it hard, even when things look nice on the surface.
Lu: For future work, they leave open some questions about degree two tournaments and whether having five dominators still forces uniqueness. They are clearly pushing the boundaries of what we think is computationally feasible for these types of selection rules.
Meng: From a deployment standpoint, if we’re building a system that needs to check TEQ membership on massive real-world data, this result tells us upfront that we need to expect polynomial space requirements and potentially slow computation times unless the tournament structure is very restricted.
Lalam: Overall, the paper "The Tournament Equilibrium Set Is PSPACE-Complete, Even under Hereditary Uniqueness" solidifies that the complexity of TEQ is fundamentally tied to its pairwise comparison structure, and it points us toward needing more specific structural constraints to get tractable solutions.
More episodes
- 2505.16254-Human-AI Writing as Distributed Cognition: Reassessing Collaborative Writing Theories in the Age of LLMs
- 2506.10913-Choreographic Quick Changes: First-Class Location (Set) Polymorphism
- 2507.14812-A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation
- 2507.15448-Frames over finite fields with respect to the Galois inner product and their connections to self-orthogonal and LCD codes
- 2508.21572-NewsReX: An Open-Source Multi-Framework for Neural News Recommendation
- 2509.17028-Impact of Packetization on Network Calculus Analysis
- 2510.17342-AoA Services in 5G Networks: A Framework for Real-World Implementation and Systematic Testing
- 2511.04088-Efficient and rate-optimal list-decoding in the presence of minimal feedback
- 2511.17264-Notes on Stack Machines and Quantum Stack Machines
- 2601.15318-On the closest balanced game