Introduction
Presented at IJCAI 2015, this research explores the mathematical foundations of collective decision-making, specifically focusing on the boundaries of Schwartz’s Conjecture in social choice theory. While the conjecture—which posits that every tournament has a unique "best" set of winners called the Tournament Equilibrium Set ($\tau$)—was recently disproved, this paper identifies specific infinite classes of tournaments where the conjecture still holds. The authors also provide polynomial-time algorithms to calculate these winners for these classes, offering a "safe harbor" for a theory that is otherwise computationally hard and theoretically elusive.
Problem Statement
In social choice theory, majority preferences are represented as a tournament: a directed graph where an edge from $a$ to $b$ means a majority of people prefer candidate $a$ over $b$. Ideally, a "Condorcet winner" (someone who beats everyone else) would exist, but the Condorcet Paradox often creates cycles. Thomas Schwartz proposed the Tournament Equilibrium Set ($\tau$) in 1990 as a stable way to pick winners, conjecturing its uniqueness. However, recent counterexamples—ranging from 24 to $10^{136}$ vertices—have shown this uniqueness can fail. This paper investigates which structural properties of tournaments guarantee that the conjecture holds.
Methodology
As a theoretical work in discrete mathematics, the authors use combinatorial graph theory to analyze specific "well-behaved" families of tournaments rather than empirical datasets. They define and prove results for:
- Triangle Packing and Covering: Tournaments where the maximum number of vertex-disjoint triangles equals the minimum number of vertices needed to hit all triangles.
- Forbidden Subtournaments: Tournaments that do not contain specific small, troublesome patterns, such as the 5-vertex tournament $U_5$.
- Critical Tournaments: Prime tournaments that become non-prime if any single vertex is removed.
The proofs rely on composition-consistency, allowing researchers to decompose large tournaments into smaller components, solve them, and recombine the results.
Key Insights and Ideas
The paper identifies that any counterexample to Schwartz’s Conjecture must contain certain structures, such as the tournaments $W_5$, $U_5$, or specific configurations labeled $F_1$ and $F_2$. By avoiding these configurations, "clean" tournaments maintain a regular structure that guarantees the conjecture holds.
Furthermore, the authors prove a complexity breakthrough: while determining if a vertex is in $\tau$ is generally NP-hard, it can be computed in polynomial time for the identified classes, such as critical tournaments or those with equal triangle packing and covering numbers.
Key Results
- Theorem 1: Schwartz’s Conjecture holds for all tournaments where the triangle packing number equals the triangle covering number.
- Theorem 2: The conjecture holds for all $U_5$-free tournaments.
- Theorem 3: The conjecture holds for all "critical" tournaments.
- Corollary: Due to composition-consistency, if a large tournament can be decomposed into these "safe" components, the conjecture holds for the entire structure.
Conclusion and Future Work
Although the identified sufficient conditions are restrictive, they provide a roadmap for hunting the smallest possible counterexample. Currently known to lie between 12 and 24 vertices, understanding these forbidden structures allows researchers to narrow the gap and find the simplest case where Schwartz’s elegant theory fails.
Summary updated