Parameterized Analysis of Bribery in Challenge the Champ Tournaments

My strongest honest case is anchored on Theorem 2, proved in this paper: CBCCT is weakly NP-hard and W[1]-hard when parameterized by the number \(n\) of non-initial players. I would use this as the lead anchor because the paper itself supplies the right bridge to a population model: its campaign-management interpretation treats \(e^\star\) as a candidate, product, or proposal, and each \(e_i\) as a voter or group whose support is required.

The scenario is a large approval campaign. There are \(N\) voters or local gatekeepers, with \(N\gg\tau\) distinct response types. A type records the complete information relevant to bribery: its baseline probability of rejecting \(e^\star\), its finite menu of campaign interventions, the cost of each intervention, and the resulting probability that the type accepts \(e^\star\). The \(\tau\) types might be recurring combinations of sector, jurisdiction, professional role, and baseline support. The original sports story is not the right regime—thirty boxers are not a continuum—but the paper’s own candidate/product interpretation scales naturally to millions of repeated voter or approval-gate types.

I would call the continuous problem Mass-CBCCT\(_\infty\). An instance consists of a finite type set \(T\), rational masses \(\mu_t\ge 0\) with \(\sum_{t\in T}\mu_t=1\), and, for each type \(t\), a bribe vector \(C_t=\{(b_{t,j},p_{t,j}) : j\in J_t\}\), where \(b_{t,j}\ge0\) is cost per unit mass and \(p_{t,j}\in(0,1]\) is the probability that \(e^\star\) defeats an agent receiving option \(j\). There is also a per-capita budget \(\beta\) and a target \(\theta\in(0,1]\).

A solution is a mass allocation \(x_{t,j}\ge0\). The quantity \(x_{t,j}\) is the fraction of type \(t\) receiving bribe option \(j\), so it must satisfy \(\sum_{j\in J_t}x_{t,j}=\mu_t\) for every \(t\). It is feasible when \(\sum_{t,j}b_{t,j}x_{t,j}\le\beta\). Its normalized winning probability is the continuous product \(G(x)=\exp\!\left(\sum_{t,j}x_{t,j}\ln p_{t,j}\right)\). The decision question is whether some feasible \(x\) has \(G(x)\ge\theta\). Zero-probability options can be handled as having log-loss \(+\infty\), or excluded when \(\theta>0\).

This is not an arbitrary replacement of a product by an average. If \(\mu_t=a_t/N\) and \(x_{t,j}=a_{t,j}/N\), then cloning the population gives \(a_t\) players of type \(t\), and the original winning probability is exactly \(G(x)^N=\prod_{t,j}p_{t,j}^{a_{t,j}}\). Likewise, the original budget is recovered by taking \(B=N\beta\). Thus clearing denominators recovers the finite CBCCT instance, with the same feasible bribe allocations and the same ordering of solutions after taking the \(N\)-th root of the probability threshold.

I expect Mass-CBCCT\(_\infty\) to be Class A. Taking logarithms turns the objective into the linear expression \(\sum_{t,j}x_{t,j}\ln p_{t,j}\), while the mass-conservation constraints and budget constraint are linear. The explicit formulation has \(\sum_t|J_t|\) variables and is solvable by linear programming, with running time polynomial in the number of types, menu entries, and encoding length under the usual computable-real or log-loss representation. The paper’s own proof of Theorem 5 already works with logarithms of probabilities and groups players by probability profiles and bribe-value sets; the continuous formulation makes those grouped quantities genuine masses and removes the need to recover an integral optimum.

The resulting interpretation of Theorem 2 is informative rather than disappointing. Its weak NP-hardness and W[1]-hardness arise from choosing one discrete menu entry for every individual player, via product-knapsack-style combinatorics. In the high-multiplicity regime, fractions of a type can receive different options, so that combinatorics becomes a transportation/knapsack LP. The hardness is therefore population-multiplicity hardness that continuization can dissolve. This directly illustrates the programme’s Class A mechanism.

The mirror covers only CBCCT and Theorem 2. I would not claim it covers Theorem 3 on cup tournaments: cross-player matches and seeding introduce identity and bracket structure that are not determined by type masses. Natural follow-up questions are whether the LP admits an exact bit-model algorithm when probabilities are rational but \(\ln p\) is not explicitly encoded; how to round an optimal mass solution to a finite \(N\)-agent campaign with an additive loss bound; and what happens if every type must receive one uniform campaign package rather than being splittable. That last variant would preserve more of the product-knapsack choice structure and might be Class B or W[1]-hard.

The weakest point is the normalization. The raw probability that \(e^\star\) defeats every member of an atomless population is either \(0\) or degenerate, since \(\prod_i p_i\) collapses as \(N\) grows. The geometric-mean, or per-capita log-probability, objective is therefore an extension of the paper’s literal threshold question. I think it is defensible because it exactly preserves every finite rational-clone instance after taking an \(N\)-th root, and because the paper already treats the product through its logarithm. But I would present Mass-CBCCT\(_\infty\) as an author-recognizable high-multiplicity continuation of CBCCT, not pretend that the unnormalized probability has a nontrivial continuum limit.