Tournaments in Computational Social Choice: Recent Developments

Warut SuksompongIJCAI 2021 · DOI

TL;DR

This survey provides a comprehensive overview of recent advancements in computational social choice, focusing on two key areas: tournament solutions and single-elimination tournaments. It highlights how computational social choice has introduced novel frameworks and analytical perspectives to these long-standing problems, particularly in understanding tournament fixing, algorithmic solutions, and structural properties.

What Problem Does This Paper Address?

The paper addresses the challenge of selecting a socially desirable outcome from a set of alternatives when decisions are based on pairwise comparisons, a scenario modeled by "tournaments." This is a fundamental problem in social choice theory with applications ranging from sports competitions and political elections to biological interactions. Specifically, the survey delves into two major lines of research:

  1. Tournament Solutions: These are methods designed to identify "winners" from a tournament graph, where vertices represent alternatives and edges represent pairwise dominance. The challenge lies in defining and computing these solutions efficiently and understanding their properties.
  2. Single-Elimination Tournaments (SE Tournaments): These are a specific format for competitions (like sports tournaments) where players are eliminated after a single loss. Key problems include determining if a specific player can win the tournament by strategically setting up the bracket ("tournament fixing") and understanding the complexity and tractability of these problems.

The paper aims to synthesize recent developments, particularly those emerging from computational social choice research in the last five years, offering fresh insights and new questions.

Methods

The survey covers a range of methods and theoretical frameworks, including:

  • Algorithmic Approaches: For tournament fixing problems (#TFP), algorithms are presented that, while not polynomial-time (due to NP-completeness), offer significant improvements over brute-force methods. These include recursive algorithms based on subset convolution and dynamic programming approaches for parameterized versions of the problem.
  • Complexity Theory: The paper discusses the NP-completeness of tournament fixing and its variants (like bribery), as well as the development of fixed-parameter tractable (FPT) algorithms for certain parameters (e.g., the size of a feedback arc set).
  • Structural Results: Theoretical conditions are explored that guarantee a player can win a single-elimination tournament, often based on concepts like "kings" and their relationships within the tournament graph.
  • Probabilistic Models: The survey examines models where tournament outcomes are not deterministic but are generated probabilistically (e.g., Condorcet random model). This allows for analysis of robustness and expected outcomes.
  • Query Complexity: For tournament solutions, the paper investigates the minimum number of queries an algorithm needs to determine the set of winners, showing that for many common solutions, Ω(n²) queries are unavoidable.
  • Margin of Victory (MoV): A novel framework is introduced to refine tournament solutions by quantifying how "close" a winner is to losing, measured by the number of edge reversals needed. This concept is analyzed computationally and structurally.
  • Randomized Tournament Solutions: The paper discusses solutions that output probability distributions over alternatives, focusing on properties like Condorcet-consistency and strategyproofness (resistance to manipulation).

Datasets

Not discussed in the paper. The paper focuses on theoretical frameworks and algorithmic analysis rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Tournament Fixing is Hard, but Tractable in Specific Cases: While the general tournament fixing problem (TFP) is NP-complete, significant progress has been made in identifying parameters (like the size of a feedback arc set) that make it fixed-parameter tractable (FPT). This means that for certain types of tournaments, efficient solutions exist.
  • Structural Properties Guarantee Wins: Concepts like "kings" and specific structural conditions on the tournament graph can guarantee that a player can win a single-elimination tournament, even if the bracket isn't explicitly known beforehand.
  • Bribery Adds Complexity: Allowing players to be bribed to lose matches makes the tournament fixing problem computationally harder, though still FPT with respect to certain parameters.
  • Query Complexity is Often High: For many standard tournament solutions, determining the winners requires querying almost all pairwise comparisons, even if the tournament graph itself is not explicitly given as input.
  • Margin of Victory Offers Finer-Grained Analysis: The "margin of victory" concept provides a more nuanced way to compare winners beyond simply identifying them, capturing their "closeness" to defeat and offering insights into tournament stability.
  • Randomized SE Tournaments are Surprisingly Robust: Even simple randomized approaches to setting up single-elimination tournament brackets exhibit strong resistance to manipulation, a desirable property for fair competition.
  • SE Winners Don't Always Align with Traditional Strength Measures: A player who wins a single-elimination tournament doesn't necessarily have the highest "Copeland score" (number of wins against all other players), suggesting that tournament format can significantly influence outcomes independent of raw strength.

Key Results

  • TFP is NP-complete: This was a significant theoretical result, establishing the inherent difficulty of the tournament fixing problem.
  • #TFP Solvable in O(2^n poly(n)) time: While still exponential, this is a substantial improvement over brute-force enumeration for counting winning brackets.
  • FPT Results for TFP: Algorithms exist with running times like $2^{O(k \log k)} n^{O(1)}$ where $k$ is the size of the smallest feedback arc set, demonstrating tractability for certain tournament structures.
  • Bribery-TFP is NP-hard for $b < (1-\epsilon) \log_2 n$: This quantifies the difficulty of rigging tournaments with limited bribery.
  • Query Complexity for Tournament Solutions is $\Omega(n^2)$: For common solutions like Copeland set, top cycle, and uncovered set, nearly all pairwise comparisons must be queried.
  • MoV Computation is Polynomial for CO, TC, UC, but NP-hard for BA: This differentiates the computational difficulty of analyzing winners using the margin of victory concept.
  • Condorcet-consistent randomized SE brackets are 2-SNM-1/3: This shows a strong resistance to manipulation for a simple randomized tournament format.
  • Any alternative in the Copeland set is a SE winner: This establishes a direct link between a traditional tournament solution and the possibility of winning a single-elimination tournament.

Limitations and Future Work

  • Limitations:
    • The survey focuses on work published in the last five years or so, meaning it might not cover all relevant developments.
  • While NP-completeness is established for many problems, finding more efficient algorithms for specific, practical instances remains an ongoing challenge.
  • The analysis of probabilistic tournaments is complex, and further work is needed to fully understand the implications of various probability models.
  • Future Work:
    • Investigating other tournament formats (e.g., double-elimination, round-robin, stepladder, Swiss-system, multi-stage tournaments) in greater depth.
  • Performing empirical studies on real-world tournaments to validate theoretical models.
  • Examining the effects of tournament structure on fairness and exploring new parameters for fixed-parameter tractability.
  • Developing more efficient algorithms for computing tournament solutions and analyzing their properties, especially for large-scale tournaments.
  • Further exploring randomized tournament solutions and their strategic properties.

Summary updated

BibTeX
@inproceedings{suksompong2021tournaments,
  author = {Warut Suksompong},
  title = {{Tournaments in Computational Social Choice: Recent Developments}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/626},
}
Figure