Research map / Learning theory and algorithms / Submodular and game algorithms
Refining Tournament Solutions via Margin of Victory
Markus Brill, Ulrike Schmidt-Kraepelin, Warut Suksompong
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use minimum edge reversals to quantify how robust each alternative's winner status is | Tournament solutions · Pairwise-comparison tournaments | MoV | Improved |
| Compute winner MoV via minimum length-bounded cuts | Uncovered Set, 3-kings, and Top Cycle · Weighted tournaments | computational complexity | Improved |
| Use length-bounded cut reductions for k ≥ 4 | k-kings winners · Unweighted tournaments | computational complexity | Hurt |
| Use the weighted MoV framework | Uncovered Set non-winners · Weighted tournaments | computational complexity | Hurt |
| Use the weighted MoV framework | Top Cycle non-winners · Weighted tournaments | computational complexity | Improved |
| Use minimum dominating sets to construct reversals | Uncovered Set non-winners · Unweighted tournaments | reversal count: -\lceil \log_2 n\rceil | Mixed |
| Use a Copeland-score comparison to find the cheapest destructive reversals | Copeland winners · Weighted tournaments | computational complexity | Improved |
| Use a network-flow construction to find constructive reversals | Copeland non-winners · Weighted tournaments | computational complexity | Improved |
| Allow arbitrary weighted reversal costs | k-kings non-winners · Weighted tournaments | computational complexity | Hurt |
| Use Banks-set membership to define winner robustness | Banks Set winners · Unweighted tournaments | computational complexity | Hurt |
| Use Banks-set membership to define entry robustness | Banks Set non-winners · Unweighted tournaments | computational complexity | Hurt |
| Use a winner-separation perspective for all considered tournament solutions | Winners · Unweighted tournaments | maximum reversal count: \lfloor n/2 \rfloor | Improved |
Closest papers by meaning
- Margin of Victory in Tournaments: Structural and Experimental Results (AAAI 2021 · similarity 0.95)
- An Exercise in Tournament Design: When Some Matches Must Be Scheduled (AAAI 2024 · similarity 0.86)
- Adaptive Manipulation for Coalitions in Knockout Tournaments (AAAI 2025 · similarity 0.84)
- Smooth Partial Lotteries for Stable Randomized Selection (NeurIPS 2026 · similarity 0.84)
- Safe and Robust Subgame Exploitation in Imperfect Information Games (ICML 2024 · similarity 0.83)
- Competition among Pairwise Lottery Contests (AAAI 2024 · similarity 0.83)
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.
