The Tournament Equilibrium Set Is PSPACE-Complete, Even under Hereditary Uniqueness
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 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 winners can be computed in time, where is the number of alternatives.
Review reports
xPeerd (AI review)
AI Review (xPeerd — DAReview)
Summary
This manuscript studies the computational complexity of the tournament equilibrium set (TEQ) membership problem and claims three main contributions: (i) TEQ membership is PSPACE-complete, closing a prior gap between known NP-hardness and a PSPACE upper bound; (ii) this hardness persists even on highly structured instances where every nonempty induced subtournament has a unique minimal retentive set and a vertex with at most three dominators; and (iii) despite that hardness, one TEQ winner can still be found efficiently under a four-dominator condition, with further algorithmic consequences for computing all winners . The paper is technically ambitious, well organized, and appears to make a significant contribution to computational social choice if correct. The conceptual separation between “finding some winner” and “recognizing a specified winner” is particularly strong and is articulated clearly in the introduction and discussion . The main weaknesses are not primarily about topical relevance or motivation, but about reproducibility, exposition burden, and research-integrity signaling. In particular, the manuscript states that “OpenAI’s ChatGPT … was used mainly to develop the reduction” and that AI was used for “most of the research activities associated with this work,” which materially raises the standard for proof transparency, verification detail, and delineation of human versus tool-originated reasoning . The appendix-heavy structure also makes validation labor-intensive.
Potential Major Revisions
- Reproducibility and proof-audit burden remain too high for such a central hardness claim.
The manuscript’s central claim is strong: “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” . Later, the paper further claims: “TEQ Membership is PSPACE-complete under polynomial-time many-one reductions on the class D3, even when a witnessing elimination order is supplied” and that “Every nonempty induced subtournament of a tournament in D3 has a unique minimal TEQ-retentive set and a vertex with at most three dominators” . These are substantial and technically delicate results.
However, the structure distributes critical validation across many sections and appendices: construction in Sections 3.1–3.2, correctness in Sections 4.1–4.5, hereditary uniqueness in Sections 5.1–5.2, and detailed proofs in Appendices A–C . The paper itself acknowledges omitted proofs in the main line: “Proofs omitted from this section appear in Section A” . For a theorem of this complexity, the current presentation asks the reader to trust too much global consistency among gadgets, shielding lemmas, quantifier simulation, and hereditary-degree arguments before the whole reduction becomes verifiable end-to-end.
Revision needed: add a compact proof roadmap table or dependency graph that maps each theorem to the exact lemmas and gadget invariants it needs, and add one complete worked micro-instance illustrating the reduction on a very small quantified formula. Without that, the correctness argument remains difficult to audit efficiently.
- The AI-assistance disclosure triggers unresolved integrity and authorship-verification concerns.
The paper states: “We used AI to perform most of the research activities associated with this work” and “OpenAI’s ChatGPT (Astra 6.0, Terra 6.1) was used mainly to develop the reduction” . It also says Claude was used “to check proofs and to help with the writing and the figures,” and that both systems were used “to write verification programs and to search the literature” . The manuscript concludes, “We have checked the construction and the proofs. Responsibility for the correctness, originality and attribution of the work rests with the authors” .
That disclosure is candid, but for a complexity-theory paper whose core value rests on exact formal correctness, it is not yet sufficient. The phrase “used mainly to develop the reduction” is especially consequential, because the reduction is the epistemic center of the paper. The current disclosure does not specify:
- what formal verification steps were performed by the authors independently,
- whether all theorem statements were reconstructed from first principles by the authors,
- what fraction of proof text versus proof ideas were tool-generated,
- whether any machine-produced candidate arguments were discarded as invalid,
- and what exact computational checks were run.
Revision needed: expand the methodology statement into a rigorous verification appendix stating which proofs were independently re-derived by the authors, what scripts were used, what properties were computationally checked, which parts cannot be verified computationally, and where human mathematical judgment entered. Otherwise, the manuscript invites skepticism about proof provenance and auditability.
- The manuscript makes unusually strong structural claims that deserve sharper delimitation of scope and dependence.
The introduction states: “The hardness persists even when every nonempty subtournament has a unique minimal retentive set” and further that “every such subtournament in our hard instances contains an alternative with at most three dominators” . Later the text emphasizes that this “separate[s] the computational difficulty of the recursion from the failure of Schwartz’s uniqueness conjecture” . This is a compelling conceptual message.
Still, some of the framing occasionally risks overstating generality relative to what is actually proved. For example, “This separates the computational difficulty of the recursion from the failure of Schwartz’s uniqueness conjecture” is directionally correct for the constructed class, but the broader reader may infer a stronger structural diagnosis of TEQ hardness mechanisms in general than the manuscript strictly establishes . Similarly, the statement that “finding one winner is efficient even though recognizing a specified winner is PSPACE-complete” is true on the structured hard instances, but the paper itself later notes: “whether a member of TEQ can be found in polynomial time in general remains open” .
Revision needed: tighten the framing in the abstract and introduction so that every high-level takeaway is explicitly scoped to either the constructed class, the hereditary four-dominator setting, or arbitrary tournaments. This would reduce the risk of readers overgeneralizing from the hard instances.
- Some claims would benefit from clearer separation between theorem-level results and conjectural or informal intuition.
The proof-ideas section is valuable, but some explanatory transitions are so compressed that they are hard to validate without repeatedly backtracking. For instance: “If a vertex r can reach every alternative in the contestation graph, its component is the unique source component. TEQ then selects exactly the alternatives that have a path back to r” . Likewise, quantifier simulation is described informally through “conditional return paths,” “readers,” and “shield” mechanisms before the reader has fully internalized the exact induced queries .
This is not mathematically wrong based on the provided text, but it places a high load on the reader and makes it easier for hidden assumptions to pass unnoticed. In complexity reductions, exposition clarity is part of methodological rigor.
Revision needed: add a short “invariants maintained by each layer” subsection before the correctness proof, listing precisely what each gadget preserves under vertex deletion and what query each designated reader vertex computes.
- There is a mild paper-mill / artifact-integrity warning arising from residual drafting artifacts.
At page 49, the file contains the line “Ethan:the first 4 are the IJCAI proposed things. I’d also be interested in benchmarking the "find 1 candidate at a time" bound mentioned in section 6.” . This appears to be an internal author note unintentionally left in the manuscript. On its own, this is not evidence of fabrication. However, in combination with the unusually extensive AI-use disclosure, it signals that the manuscript’s assembly pipeline may not yet be fully controlled. That matters because accidental carryover text can also correlate with overlooked inconsistencies elsewhere.
Warning: I do not see strong evidence here of paper-mill behavior or fake research; the manuscript fits a coherent theoretical computer science / computational social choice paradigm, cites relevant literature, and presents technically structured claims . Still, the retained internal note and omitted-proof burden warrant extra scrutiny before acceptance.
Potential Minor Revisions
- Typographic and drafting issues
- The line “Ethan:the first 4 are the IJCAI proposed things” should be removed; it is plainly an internal note and not part of a scholarly appendix .
- The phrase “find 1 candidate at a time” within that note is informal and inconsistent with the otherwise formal register .
- In the abstract, “all t winners can be computed in O(2t N 2 ) time” is understandable to experts, but notation spacing/presentation could be standardized for readability .
- In several extracted snippets, line breaks and spacing around formulas such as “TEQ(T )” and “N 2” appear uneven; if this reflects the PDF rather than extraction noise, the typesetting should be normalized .
- The introduction’s subsection title “Where does the difficulty come from?” is effective rhetorically, but the subsequent prose is dense enough that a more explicit signposting sentence at subsection end would help transition to “Proof ideas” .
- Formatting and presentation issues
- The manuscript is appendix-heavy, with proofs for Sections 3–7 spread across Appendices A–C, plus an “AI methodology statement” and “Additional results stated without proof” near the end . Consider moving nonessential speculative material out of the main review version if venue length norms are tight.
- The section “Additional results stated without proof” is potentially distracting in a theorem-driven paper where the proved results are already substantial . Listing multiple unproved claims can weaken focus and may invite doubts about boundary control.
- The AI methodology statement is placed very late in the document. Given its importance here, it may deserve a more visible and standardized placement, depending on venue policy .
- A notation summary for D1, D2, D3, D4 would improve navigability; the discussion assumes the reader retains these classes across many sections .
- Minor clarity issues
- The manuscript says “The hard instances have a further local property, which the reduction gives us for free” . “For free” is colloquial; “as a byproduct of the construction” would be more formal.
- The sentence “This turns membership into a question about paths, which the reduction can control” is elegant but compressed; a brief parenthetical reminder of what graph the paths live in would help non-specialists .
- The discussion’s open problems are strong, but a one-sentence recap of what is actually settled for each dominator bound would help readers before the question list begins .
- AI content analysis for this post-2021 manuscript
Estimated percentage of AI-generated content: high, plausibly above 50%, based on the manuscript’s own statement that AI was used for “most of the research activities associated with this work,” plus explicit use of multiple frontier systems for reduction development, proof checking, writing, figures, verification programs, and literature search .
Highlighted AI-detected sections:
- The explicit “AI methodology statement” on page 48–49 is the strongest direct indicator, especially the sentences “We used AI to perform most of the research activities associated with this work” and “OpenAI’s ChatGPT … was used mainly to develop the reduction” .
- The highly polished but uniform explanatory tone in the introduction and proof-ideas sections may also reflect AI-assisted drafting, though this cannot be asserted conclusively from style alone .
- The “Additional results stated without proof” section, especially combined with the internal note, suggests iterative tool-assisted exploration and manuscript aggregation from multiple drafting states .
Assessed epistemic impact:
- High AI involvement does not by itself invalidate the contribution.
- However, because the claimed novelty centers on a delicate reduction and several interdependent lemmas, heavy AI involvement materially raises the need for transparent proof provenance and independent human verification.
- The epistemic risk is therefore not “AI text style,” but whether the central arguments have been exhaustively human-audited and are reproducible by competent experts without relying on opaque tool-originated intuition.
Recommendations
-
Add a formal verification-and-audit appendix. State exactly which claims were checked computationally, which scripts exist, what inputs they test, and what they do not prove. Distinguish human-derived proofs, AI-suggested proof ideas, and mechanically checked structural properties.
-
Strengthen end-to-end readability of the reduction. Provide one worked example on a tiny quantified formula showing the construction, the relevant dominator queries, the contestation graph intuition, and why the designated output vertex is selected iff the formula is true.
-
Tighten all scope-sensitive claims. Where results hold on D3 or under hereditary bounded-dominator assumptions, say so explicitly in every summary passage. Avoid language that may sound more universal than the theorems justify.
-
Remove drafting residue and unproved-claim clutter. Delete the internal author note and reconsider whether “Additional results stated without proof” helps this version. If retained, clearly label it as non-core and ensure it does not dilute confidence in the proved results.
-
Add a compact theorem dependency map. A one-page guide linking Theorem 1.1, Theorem 4.1, Theorem 5.10, Theorem 6.1, and Theorem 7.1 to their supporting lemmas would materially improve referee auditability.
-
Clarify novelty relative to prior NP-hardness and uniqueness results. The related-work discussion is already useful, but a final explicit comparison paragraph summarizing exactly what was unknown before this paper and what is newly established would sharpen the contribution .
Overall, I view the manuscript as potentially important and technically substantial, but not yet fully review-ready in its current form because the burden of proof verification, provenance transparency, and presentation control is still too high relative to the strength of its claims.
Reviewer3 (AI review)
AI Review (reviewer3.com)
Overview
PSPACE-Completeness of TEQ Membership
Contribution
The paper resolves a long-standing open complexity gap by proving that deciding membership in the Tournament Equilibrium Set (TEQ) is PSPACE-complete.
Hardness Under Hereditary Uniqueness
Contribution
The authors establish that PSPACE-completeness holds even on tournaments where every induced subtournament possesses a unique minimal retentive set, proving that TEQ's computational intractability is independent of non-unique retentive sets.
Separation of Winner Finding from Recognition
Contribution
The study provides a quadratic-time algorithm for finding a TEQ winner in tournaments containing a vertex with at most four dominators, demonstrating that finding a winner can be efficient even when recognizing a specific winner is PSPACE-complete.
Comments (3)
1. Unremoved editorial comment in Additional Results section — Editorial
Ethan:the first 4 are the IJCAI proposed things. I’d also be interested in benchmarking the "find 1 candidate at a time" bound mentioned in section 6.
On page 51 (numbered page 49), immediately beneath the heading 'Additional results stated without proof', an internal author note in blue text has been left in the manuscript: 'Ethan:the first 4 are the IJCAI proposed things. I'd also be interested in benchmarking the "find 1 candidate at a time" bound mentioned in section 6.'
2. Figure 1(a) edge orientation contradicts Example 2.3 text — Editorial
Example 2.3. Let X = { a, b, c, d } with a ≻ b ≻ c ≻ a and { a, c } ≻ d ≻ b
In Example 2.3, the tournament is defined with the relation , meaning that beats (so the directed edge points from to ). Consistently with this text, the dominator table lists and . However, in Figure 1(a), the vertical arrow between and points downward from to (), contradicting both the text and the dominator table.
3. Early stopping on k-th seed undercounts distinct pivots used — Major
Run Algorithm 1, reporting each distinct seed the first time the selector chooses it anywhere in the recursion. Stop at the k th report. By retentiveness, the winners of each recursive call belong to the winner set of its parent, so every reported seed belongs to
The proof of Corollary 6.3 proposes running Algorithm 1 and halting when the selector σ reports a k-th distinct seed, claiming that at most k-1 distinct seeds are used as pivots. However, because Algorithm 1 processes recursive calls in depth-first order (where a child call can complete and return multiple vertices that are immediately enqueued and popped as pivots before the selector ever encounters a k-th distinct seed), the set S of pivots that trigger recursive calls is not bounded by the number of distinct seeds seen so far. To guarantee |S| <= k-1 and the O(2^{k-1}(p(N)+N^2)) time bound, the algorithm must track the total number of distinct vertices discovered (via seeds or completed subcalls) and halt as soon as k distinct members of R are accumulated, before popping a k-th pivot from any queue.
XSci (AI review)
Summary
The paper settles the complexity of Schwartz's tournament equilibrium set (TEQ), known to be NP-hard and in PSPACE since Brandt, Fischer, Harrenstein and Mair [BFHM08, BFHM10]. The authors reduce TQBF to TEQ MEMBERSHIP, simulating each quantifier with six vertices added around a single copy of the inner tournament rather than two copies, and prove correctness through gadget lemmas and an induction over the quantifier prefix (Lemma 4.11). They then show the hard instances lie in the class of tournaments in which every nonempty induced subtournament has a vertex with at most three dominators (Lemma 5.9), and prove that a single vertex with at most four dominators forces a unique minimal retentive set (Theorem 5.1) and yields a TEQ member in time (Theorem 6.1a). The outcome is a class on which finding a winner is quadratic while recognizing one is PSPACE-complete, plus a trichotomy along the dominator bound ( quadratic, NP-hard, PSPACE-complete).
Contribution and Significance
The core contribution is the exact classification of TEQ membership, open since 2008 and arising from a definition published in this journal in 1990. The reduction's engine is the return-path criterion (Lemma 2.5) with two devices that carry the real technical weight: the readers , whose dominator sets differ exactly by the occurrence set , so that both values of a variable are read off one copy of (Figure 9), and the two-vertex shield (Lemma 4.4), without which the first device could not survive the fact that a tournament compares every new vertex with everything. This is the first PSPACE-completeness result for a rule that sees only the orientation of each comparison.
The paper is more than its headline. Theorem 5.10 shows the hardness does not come from competing minimal retentive sets, the natural first hypothesis after [BCK+13, BS13]: the instances of [BFHM10] give uniqueness only in subtournaments containing the designated vertex, and the strengthening to every induced subtournament is what makes the separation from Schwartz's conjecture clean. Theorem 5.1 is an independent structural result this readership will care about on its own, and it is genuinely incomparable with Yang's results [Yan16] for order at most 14, for locally transitive tournaments and for captain cycles; Lemma 5.3 extends Yang's machinery from minimal retentive sets to all retentive sets rather than merely reusing it. The finding-versus-recognizing gap is sharper than the Banks analogue [Woe03, Hud04], though, as the authors say, their selector needs a low-indegree vertex whereas a Banks member can be found in every tournament.
Strengths
- The reduction is correct as far as I could check it, and I checked it hard: I re-derived the orientations of all three clause gadgets of Definition 3.1 and recomputed all eight entries of the table in Section A.2, both shield instances of the -layer, and the -layer in full, including the two excluded shortcuts ( and ) on which Lemma 4.10 turns.
- The degree certificate (Lemma 5.9, Section A.5) is unusually careful bookkeeping, and every indegree in its four tables is right, including the Phase 2 orders for , , under the relay and reader budgets.
- Theorem 6.2's domain count is neat: every pivot used anywhere in the recursion lies in the final answer, so reachable domains are intersections of at most dominator sets, bounding the work by without knowing in advance.
- Section 7 locates the boundary rather than only asserting hardness; the analysis (Lemma 7.2) and the separation from the packing-equals-covering condition of [MSY15] in Section C.1 are concrete.
Recommendation
Major Revision for SOCIAL CHOICE AND WELFARE. The result matters to this journal and I found no technical error in a substantial check, so I expect the central claims to survive; what I ask for concerns the paper's state, its positioning, and the evidence a reader can act on, not its mathematics. Standing in the way are a manuscript that is not yet a finished article (Concern 1), a novelty claim that cannot be assessed against the companion preprint it leans on (Concern 2), and computational checks that are neither reported nor released (Concern 3).
Major Revision for ACM Transactions on Economics and Computation. The same three concerns apply; TEAC accommodates the length and weights Sections 6 and 7 more heavily, so Minor Comments 2 and 9 carry less there, while its artifact expectations make Concern 3 more pressing.
Major Concerns
-
The manuscript is not in a publishable state (the two final unnumbered sections). The section "Additional results stated without proof" asserts nine results with no proofs, several bearing directly on the paper's own subject and on work it cites: item 1 claims PSPACE-completeness for a designated Copeland winner, item 2 claims a 14-vertex subtournament of Brandt and Seedig's example refuting "Yang's conjecture that every captain is selected [BS13, Yan16]", and the closing paragraph claims that a randomized algorithm finding half the winners on would imply RP = PSPACE. A referee cannot certify any of these, and readers will cite them. The methodology statement compounds this by announcing that "Future versions of this article will include those omitted results as supplementary material", and the manuscript still carries an internal note to a co-author: "Ethan:the first 4 are the IJCAI proposed things. I'd also be interested in benchmarking the 'find 1 candidate at a time' bound mentioned in section 6." Remove the note, and either prove the appended results or cut them; a one-sentence pointer to work in preparation is the most that belongs here.
-
Positioning against [DPT26] is too thin to support the novelty claim (Section 1.3). The paper's account of its own significance rests on an unpublished 2026 preprint by two of the same authors: it is the only comparable result (Section 1), the authority for why TEQ's lower bound does not follow from it, and the destination to which the entire earlier PSPACE-hardness literature in this field is deferred ("see the discussion in [DPT26]"). The methodology statement then says the reduction was developed "from the ideas of our earlier result on Stable Voting [DPT26], which suggested the reduction strategy". The manuscript nowhere describes that construction, so a reader cannot tell which elements are inherited and which are new to the unweighted setting: the nested single-copy layering, the two-reader device, the return-path criterion as the hardness engine, the shield. Please compare the two constructions component by component, and survey the earlier PSPACE-hardness results here rather than by reference.
-
The computational checks are neither described nor released (AI methodology statement). The methodology statement says both model families were "used to write verification programs" and that "Computational checks served as supporting evidence only", but no code, no account of what was checked, and no outcomes appear. For a construction of this size this is the cheapest thing that would move a reader from believing the parts they check to certifying the whole. State what was verified and supply the programs as a reproducible artifact: exhaustive TEQ on the three clause gadgets under all eight deletion patterns (Lemma 4.6), Lemmas 4.9 and 4.10 on small inner tournaments , the order of Lemma 5.9 on generated formulas, Table 1's selector against brute force, and agreement of with the truth value of for small .
Minor Comments
- Section 1.1 cites "Theorems 5.10 and 7.1" for the claim, but Theorem 7.1 covers only and .
- At roughly fifty pages the paper is well outside this journal's normal compass, and the running example alone is developed four times (Section 3, Figures 6 and 7, Section 4.2).
- The "Proof outline" of Lemma 4.9 in Section 4.3 and its proof in Section A.4 are nearly the same text, as are those of Lemma 4.10; one of each should go.
- Nothing is said about how large is on the paper's own hard instances, so the reader cannot gauge the distance there between the quadratic selector and the full computation, nor whether the factor is necessary.
- Proposition 2.6 is proved in three lines with no attribution; say whether the PSPACE upper bound is folklore or is due to [BFHM10].
- Section 5.1 says only that uniqueness at five dominators is unknown; saying whether any tournament is known in which uniqueness fails and the minimum indegree is five would show the bound of four is tight rather than an artifact of the proof.
- Brandt, "Minimal stable sets in tournaments", Journal of Economic Theory 146(4):1481-1499, 2011 is missing, and is the natural reference for the claim in Section 1 that TEQ satisfies stability under Schwartz's conjecture.
- Corollary 7.4 should state explicitly the number of voters and the profile size the reduction produces, since its interest is precisely the trade-off against the seven-voter NP-hardness of [BBG+19].
- Section 6 offers no comparison, even on small instances, with the exact algorithms of [BFHM10] and [BBS11] that it implicitly competes with.
- Proposition 7.3 pads short clauses "by repeated literals, represented by distinct vertices", which sits oddly beside (F1) in Section 3; state that the degree-two construction does not assume (F1) and why repetition is harmless.