Research map / Learning theory and algorithms / Submodular and game algorithms
Adaptive Manipulation for Coalitions in Knockout Tournaments
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces adaptive constructive coalition manipulation in probabilistic knockout tournaments, proving PH/PSPACE/W[1]-hardness and giving FPT and polynomial-time algorithms for constant coalition size.
Problem
Determining whether a coalition of players can manipulate a probabilistic knockout tournament by adaptively throwing games so a favorite player wins with at least a threshold probability.
Approach
Coalition players decide which games to lose round by round based on the observed current seeding (adaptive strategies), rather than fixing all manipulations before the tournament; the paper analyzes the resulting complexity, including generalized (imbalanced) tournament trees.
Key results
- ACCM-KT is hard for every class in the polynomial hierarchy even when the threshold t equals one.
- ACCM-GKT is PSPACE-complete and NP- and W[1]-hard parameterized by coalition size even with random game cover of size two.
- ACCM-KT is solvable in (|C|+x)^{O(|C|+x)} n^{O(1)} time and BR-ACCM-KT is NP-hard; CCM-KT (non-adaptive) is shown NP-hard, resolving an open case of Mattei et al.
Surprising findings
- Adaptive coalition manipulation is much harder than the classical setting, lying across the polynomial hierarchy and PSPACE for generalized trees.
Limitations
- Problems are intractable in general; algorithms only tractable under restrictive parameters.
- Model assumes non-coalition players do not act strategically and probabilities are known.
Experimental setup
Builds on: Russell and Walsh coalition manipulation Mattei et al. probabilistic coalition manipulation tournament fixing problem
Closest papers by meaning
- Rigging Nearly Acyclic Tournaments Is Fixed-Parameter Tractable (AAAI 2017 · similarity 0.92)
- An Exercise in Tournament Design: When Some Matches Must Be Scheduled (AAAI 2024 · similarity 0.90)
- How to Make Knockout Tournaments More Popular? (AAAI 2024 · similarity 0.86)
- A Matching-Based Algorithm for the Traveling Tournament Problem (AAAI 2025 · similarity 0.84)
- Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size (AAAI 2025 · similarity 0.84)
- Team-Fictitious Play for Reaching Team-Nash Equilibrium in Multi-team Games (NeurIPS 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.