Recognizing Members of the Tournament Equilibrium Set is NP-hard

Felix Brandt, Felix A. Fischer, Paul Harrenstein

TL;DR

This paper tackles the computational complexity of identifying "desirable" alternatives within a tournament, a common model in social choice theory. The authors prove that determining if an alternative belongs to the Tournament Equilibrium Set (TEQ), a complex but potentially attractive solution concept, is NP-hard. This finding implies that efficiently finding TEQ members is likely impossible for large tournaments, highlighting a significant computational barrier.

What Problem Does This Paper Address?

In social sciences, we often deal with situations where alternatives are compared pairwise, leading to a "dominance relation." Think of voting systems or preference rankings. A tournament is a mathematical model for this, where every pair of alternatives has a clear winner. The challenge arises when we want to identify the "best" or "most desirable" alternatives. Unlike simple cases, cycles (A beats B, B beats C, C beats A) make standard notions of "maximum" problematic.

To address this, various "tournament solution concepts" have been proposed, each aiming to single out desirable outcomes. The Tournament Equilibrium Set (TEQ) is one such concept, introduced by Schwartz. It's known for its intricate, recursive definition, which has made it difficult to analyze. Despite its complexity, TEQ has desirable properties if certain conjectures hold, potentially refining other established solutions like the Banks set and the minimal covering set. However, a major hurdle has been understanding its computational tractability. This paper specifically addresses the question: how hard is it to determine if a given alternative is part of the TEQ for a given tournament?

Methods

The core of this paper is a proof of NP-hardness for the TEQ membership problem. The authors achieve this by constructing a reduction from 3SAT, a well-known NP-complete problem. This means they show how to transform any 3SAT problem into a tournament problem such that solving the tournament problem is equivalent to solving the original 3SAT problem.

Specifically, they first present an alternative NP-completeness proof for the Banks set, building on a construction from 3SAT. This construction involves creating a special class of tournaments, denoted $T^*$, designed to encode the logical structure of a 3SAT formula. They then adapt this construction to create a new tournament for the TEQ problem. The key idea is to design the dominance relations within these tournaments in such a way that the satisfiability of the 3SAT formula directly corresponds to whether a specific node (representing the decision to be made) belongs to the TEQ.

The proof for TEQ relies on a lemma that establishes a connection between the TEQ of a subset of the tournament and the dominance relations within that subset. This lemma, combined with the specific tournament construction, allows them to demonstrate the equivalence between 3SAT satisfiability and the membership of a particular node in the TEQ.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and proofs rather than empirical evaluation on existing datasets. The "datasets" are effectively the constructed tournaments based on 3SAT instances.

Key Insights and Ideas

  • TEQ is computationally challenging: The most significant insight is that determining membership in the TEQ is NP-hard. This means that for large tournaments, finding TEQ members is likely to be computationally infeasible, requiring exponential time in the worst case.
  • Recursive definition's complexity: The paper highlights that the unwieldy recursive definition of TEQ is a major reason for its enigmatic nature and computational difficulty.
  • Connection to 3SAT: The successful reduction from 3SAT demonstrates a deep connection between logical satisfiability and social choice theory concepts, suggesting that problems in one domain can shed light on the complexity of the other.
  • Refinement of Banks set proof: The paper offers a new, arguably simpler, NP-completeness proof for the Banks set, which then serves as a foundation for the TEQ proof.
  • TEQ vs. Banks Set: The paper illustrates with an example that TEQ and the Banks set can differ, with TEQ being a subset of the Banks set. The NP-hardness of TEQ membership is a stronger result than the NP-completeness of Banks set membership.

Key Results

  • TEQ Membership is NP-hard: The paper proves that deciding whether a given alternative is in the Tournament Equilibrium Set (TEQ) of a tournament is NP-hard. This is the paper's main theoretical contribution.
  • Banks Set Membership is NP-complete: The paper provides an alternative proof for the NP-completeness of deciding membership in the Banks set, using a reduction from 3SAT.
  • Construction of specific tournaments: The authors introduce a class of tournaments ($T^*$) and specific constructions (TBA and TTEQ) that encode 3SAT formulas, which are crucial for their reduction proofs.

Limitations and Future Work

  • P vs. NP: The paper proves NP-hardness for TEQ membership. It does not prove that TEQ membership is in NP. The authors suggest that TEQ membership might even be harder than NP-complete problems, as there's "no obvious reason to suppose that the TEQ membership problem is in NP." This leaves open the possibility of it being PSPACE-complete or even harder.
  • Monotonicity of TEQ: The paper mentions that the monotonicity of TEQ remains an open problem. If TEQ were monotonic, it would be a more attractive solution concept. The NP-hardness result might imply that proving or disproving monotonicity is also computationally difficult.
  • Heuristic for TEQ computation: While the paper focuses on theoretical hardness, it briefly mentions a heuristic algorithm for computing TEQ. However, it acknowledges that this heuristic still has exponential worst-case running time, reinforcing the difficulty of exact computation.
  • Practical implications: The NP-hardness result implies that for large, real-world tournaments, finding the exact TEQ might be computationally prohibitive. Future work could explore approximation algorithms or more efficient heuristics for practical applications.

Summary updated

Abstract

A recurring theme in the mathematical social sciences is how to select the "most desirable" elements given a binary dominance relation on a set of alternatives. Schwartz's tournament equilibrium set (TEQ) ranks among the most intriguing, but also among the most enigmatic, tournament solutions that have been proposed so far in this context. Due to its unwieldy recursive definition, little is known about TEQ. In particular, its monotonicity remains an open problem up to date. Yet, if TEQ were to satisfy monotonicity, it would be a very attractive tournament solution concept refining both the Banks set and Dutta's minimal covering set. We show that the problem of deciding whether a given alternative is contained in TEQ is NP-hard.
BibTeX
@inproceedings{brandt2008recognizing,
  author = {Felix Brandt and Felix A. Fischer and Paul Harrenstein},
  title = {{Recognizing Members of the Tournament Equilibrium Set is NP-hard}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
  url = {https://openreview.net/forum?id=SJ-RG0luWS},
}
Figure