Rigging a Knockout Bracket When Match Outcomes Are Uncertain

Most theory about rigging a knockout tournament assumes that the organizer knows, for every pair of players, who will win. Under that assumption, choosing the bracket so that a favored player wins is NP-complete. Recent algorithms nonetheless solve it fast when only a few players break an otherwise clean ranking. Real matches are uncertain, though. A bracket that is "safe" when every match is treated as certain may still give its target only a coin-flip chance of winning. And a player who cannot win any bracket in the certain-outcome model may win some bracket with real probability. This note proposes to carry the fast, structure-exploiting algorithms over to uncertain outcomes. The key step is a reformulation: with independent matches, choosing the best bracket for a target player is an exact-cover problem over a hypergraph of candidate opponent groups. Near-transitive structure then collapses that hypergraph to a manageable size.

Concretely, the target's chance of winning splits into one factor per round. Each factor depends only on the group of players who fill the opposite half of the bracket in that round. So the organizer's job is to split everyone else into groups of sizes 1, 2, 4, …, n/2 that are as harmless as possible. That is a covering problem over "candidate groups", which are hyperedges, meaning connections among many players at once rather than pairs. There are exponentially many such hyperedges. The claim is that when the probability matrix is close to a ranking, apart from a small set of $k$ players, only about $2^{k}\cdot\mathrm{poly}(n)$ of them are genuinely different. That yields an algorithm whose cost grows exponentially only in $k$, with an explicit error bound tied to how uncertain the "easy" matches are.

Core Claim

Let $p(u,v)$ be the probability that $u$ beats $v$, and let $v^*$ be the target in a balanced bracket of $n = 2^r$ players. Any bracket in which $v^*$ can win assigns to $v^*$ a sequence of disjoint opponent blocks $S_1,\dots,S_r$ with $|S_i| = 2^{i-1}$. These blocks are the sibling subtrees it faces in round $i$. If matches are independent, the outcomes inside different blocks are independent. Hence

$$\Pr[v^* \text{ wins}] \;=\; \prod_{i=1}^{r} \sum_{u \in S_i} q_{S_i}(u)\, p(v^*,u),$$

where $q_{S_i}(u)$ is the probability that $u$ emerges as winner of block $S_i$ under that block's internal arrangement. Maximizing this is therefore a weighted exact cover of $V\setminus\{v^*\}$ by hyperedges of prescribed sizes. Each hyperedge's weight is $-\log$ of the best achievable per-round survival probability against that block. This is the hypergraph that Fixing a Tournament implicitly used when it proved hardness by reduction from Exact Cover by 4-Sets. Here it becomes the algorithmic object rather than a hardness gadget.

The proposal is to define an "$\eta$-core": a smallest set $K$ of players such that, among the remaining players, every match goes the ranking's way with probability at least $1-\eta$. Write $k = |K|$. Outside the core, a block's threat to $v^*$ is determined, up to an error of order $|S_i|\eta$, by two things: which core members it contains and which non-core player in it ranks highest. Candidate hyperedges therefore fall into at most $2^{k}\cdot n$ equivalence classes per size level.

This leads to the target theorem. Risk-bounded tournament fixing asks whether some bracket gives $v^*$ win probability at least $\tau$. We conjecture it can be decided in $2^{O(k\log k)}\,n^{O(1)}$ time, up to an additive slack of $(n-1)\eta$. The slack form comes from a union bound over the at most $n-1$ non-core matches whose outcome is near-certain but not certain. When $\eta = 0$ and probabilities are in $\{0,1\}$, the problem specializes to the deterministic feedback-vertex-set setting.

Relation to Prior Work

The method comes from the deterministic parameterized line of work. Rigging Nearly Acyclic Tournaments Is Fixed-Parameter Tractable showed that fixing is tractable when few match outcomes need reversing to obtain a ranking, using integer programming. When Rigging a Tournament, Let Greediness Blind You replaced the integer program with a small skeleton built around the upset arcs, plus greedy filling of the remaining slots. Tournament Fixing Parameterized by Feedback Vertex Set Number Is FPT extended this to the stronger parameter of few cycle-breaking players. All three operate on a certain-outcome win matrix. The Gupta et al. paper names "Expected Tournament Fixing" as future work, and that is the closest existing pointer to this proposal. We reuse their skeleton-guessing idea for the core. What is new is the per-round factorization, the block-class compression of the candidate-group hypergraph, and the explicit error accounting for near-certain matches.

The motivation comes from the probabilistic line. Who Can Win a Single-Elimination Tournament? proved that in a model with uniform upset probability $p \ge C\ln n/n$, every player can be made to win with high probability. That result covers random instances and gives no algorithm for a given heterogeneous matrix. Fixing a Balanced Knockout Tournament supplies a constraint: the maximum win probability cannot be approximated within any constant factor in general. Our error is therefore additive and parameterized, not a general approximation ratio. The strategyproofness results of Condorcet-Consistent and Approximately Strategyproof Tournament Rules and Approximately Strategyproof Tournament Rules in the Probabilistic Setting study participants colluding against a randomized bracket, not an organizer choosing one. We use them only as context. Both also assume independent matches, which is the assumption our factorization depends on.

The hypergraph line plays a narrower role than its methods might suggest. Densest Subhypergraph: Negative Supermodular Functions and Strongly Localized Methods shows that flattening group structure into pairs loses information, and our objective is likewise not a sum over pairs. Anchor-guided Hypergraph Condensation with Dual-level Discrimination compresses large hypergraphs into learned proxies. By contrast, our compression is an exact equivalence of hyperedges with a provable error bound, because we need certificates rather than accuracy on average.

Research Program

The first piece is the reformulation. We will state the block-cover formulation formally and prove the factorization. We will then characterize exactly which correlations preserve it. Shocks local to a single player, such as one player's form on the day, keep blocks independent, because each player sits in exactly one block. Shocks shared by a group of players, such as a session or a venue, form a "shock hypergraph". Each such shock breaks the factorization in proportion to how many of $v^*$'s blocks it spans. We will prove a bound on the factorization error in terms of that crossing number. This addresses the independence assumption flagged as open by Ding and Weinberg.

The second piece is the parameterized algorithm. We will guess where the $k$ core players sit relative to $v^*$'s blocks and to each other, in the style of Zehavi's skeleton. For each block-size level, we enumerate equivalence classes of the form (core subset, top non-core rank). We then fill non-core slots with a dynamic program over ranks, which is exact for the compressed objective. We will prove the $(n-1)\eta$ slack. We will also try to sharpen it to depend only on matches along $v^*$'s path. The latter is plausible because non-core upsets far from $v^*$ change a block's winner only among players ranked below the presumed winner, which can only help $v^*$.

The third piece is a matching hardness result. We will show that if the error-free problem is solved exactly with uncertain matches outside the core, it stays hard even for small $k$. Otherwise, a slack depending on $\eta$ would be unnecessary.

Baselines

The naive reference point is rank-based standard seeding: top seeds are kept apart, and $v^*$ is placed in its natural slot. A second naive reference is the best of many uniformly random brackets under the same wall-clock budget as our method. Both are evaluated exactly with the factorized formula, which takes polynomial time for a fixed bracket.

The first strong baseline rounds every probability to the more likely outcome, runs the deterministic feedback-vertex-set algorithm of Tournament Fixing Parameterized by Feedback Vertex Set Number Is FPT to obtain a bracket, and evaluates that bracket's true win probability. Where that algorithm is impractical, we substitute the greedy skeleton method of When Rigging a Tournament, Let Greediness Blind You. This is the strongest existing structured method. When probabilities are close to 0 or 1, it is exactly what a practitioner would do.

The second strong baseline is simulated annealing over brackets, using pairwise slot swaps and the same exact evaluator. It gets the same wall-clock budget as our method, and its schedule is tuned on held-out synthetic instances with the same number of tuning trials we spend on our own constants.

For $n \le 16$, there are at most about $6.4\times 10^8$ distinct brackets, so exhaustive search gives the true optimum.

The ablation that isolates the key ingredient keeps our skeleton enumeration but scores blocks by their rounded deterministic winner instead of the probability-aware threat. This separates "structure" from "uncertainty-aware objective."

I found no reported result on Lacuna for the win probability achieved by any bracket-optimization method on a heterogeneous probability matrix. The only tournament-quality number in the file is ArenaRL's Spearman correlation of 0.961 between a seeded knockout ranking and full round-robin (ArenaRL), which measures ranking fidelity rather than rigging. Beating a baseline therefore means one of three outcomes. Our method attains a higher exact win probability for $v^*$ on matched instances. Or it attains equal probability with a certificate the baseline lacks. Or, for $n \le 16$, it stays within the proven slack of the exhaustive optimum, while rounding demonstrably does not.

Why not just…?

Why not just round probabilities and use the deterministic algorithms? Rounding ignores that survival multiplies across rounds. A path of seven matches each won with probability 0.9 succeeds less than half the time. So the bracket rounding calls safe can be far from the best risk-aware bracket. Rounding also declares players unwinnable when Who Can Win a Single-Elimination Tournament? shows that modest noise makes almost everyone winnable. This alternative is a genuine threat when $\eta$ is tiny, because our method then reduces to it. The experiments sweep $\eta$ to locate where the two diverge. If they never diverge by more than a few points of win probability on real matrices, the proposal's practical case collapses to its theoretical one.

Why not just run local search with the exact evaluator? This is the most serious competitor. Because a fixed bracket is cheap to score, annealing may find excellent brackets on realistic sizes. The inapproximability result of Fixing a Balanced Knockout Tournament says it must fail on some instances, but those instances may be unnatural. Our answer is twofold. First, our method returns a certificate: no bracket exceeds the returned value by more than the slack. Local search cannot provide this, and it matters when the organizer must claim fairness or optimality. Second, the decisive check below tests whether annealing ever beats us. If it does on near-transitive instances, the compression claim is wrong.

Why not just simulate brackets by Monte Carlo? Sampling random draws from $n!/2^{n-1}$ possibilities finds good brackets only by luck. Evaluation, meanwhile, needs no sampling under independence, because the factorization is exact. Monte Carlo is useful only for correlated outcomes. We do use it there, as the ground-truth evaluator when testing our crossing-number error bound.

Proposed Experiments

We will use three instance sources. The first is the chess game collections in Waterhorse/chess_data. From CCRL engine games and Lichess games among frequent opponents, we fit pairwise win probabilities with a strength model plus pair-specific residuals. These matrices are mostly ranked but contain a non-transitive core. The second is the caption ratings in yguooo/newyorker_caption_ranking. From these we derive pairwise preference probabilities among captions for a single contest, giving dense, near-parity matrices. The third is synthetic instances from the uniform-upset model of Kim et al., with planted cores of size $k$ and controlled $\eta$.

Sizes range over $n \in \{8, 16, 32, 64, 128\}$. Each instance takes several targets $v^*$, spread across strength quantiles.

The metrics are the exact win probability achieved for $v^*$; the gap to the exhaustive optimum for $n \le 16$; the fraction of players reaching a threshold $\tau$, compared with the fraction rounding deems winnable; and wall-clock time as a function of $k$.

The first decisive check is falsification of the compression claim. On every instance with $n \le 16$, our value must lie within the proven slack of the exhaustive optimum. On larger instances, annealing must never exceed our value by more than the slack. Any violation means the equivalence classes are too coarse.

The second check measures where rounding fails. We plot rounding's shortfall against $\eta$ and against core size. We expect the shortfall to grow with the number of near-certain matches on $v^*$'s path. If it stays negligible on the chess matrices, we will report that the practical gain is confined to near-parity regimes like the caption data.

The third check tests the independence boundary. We inject shared shocks spanning chosen players, measure the factorization error against Monte Carlo ground truth, and compare it with the predicted crossing-number bound. Player-level shocks should give zero error by construction, and group shocks should give error that scales with the number of blocks crossed.