d4-conf-ecai-2024-0151

The strongest mirror I see is the Young bribery result, because Young’s rule already asks how much of a profile must be removed to restore a consistent majority. In a population model, “how many members?” has a natural counterpart: “what fraction of the population?”

My anchor is Theorem 1, specifically its Young-bribery case. The theorem states that for each of Kemeny, Slater, MaxHamming, Young, and Dodgson, both manipulation and bribery are \(\Sigma_2^p\)-complete, even when the desired outcome is a single literal. For Young, the paper proves manipulation hardness by reducing from \(\exists\forall\)-QBF-SAT, then obtains bribery hardness by reducing manipulation to bribery with one corruptible agent and budget \(k=1\). The theorem’s Kemeny result has prior hardness work behind it; the Young result is part of this paper’s extension.

Here is the continuous problem I would hand to a prover. Call it Young Mass Bribery. Fix an agenda \(\Phi\) and integrity constraint \(\Gamma\), and let \(T\) be the complete \(\Gamma\)-consistent judgment sets. The input gives two distributions over \(T\): \(\mu^{\mathrm{fixed}}\) for members who cannot be bribed, and \(\mu^{\mathrm{eligible}}\) for those who can. Their total mass is \(1\); the distributions have rational masses and combined support size \(\tau\). Eligibility is part of a member’s type, since it affects what intervention is possible. The input also gives a target literal \(\ell\in\Phi\) and a rational budget \(\beta\).

Choose transfers \(x_{J,J'}\geq 0\) from eligible mass of judgment type \(J\) to reported type \(J'\in T\), with \(\sum_{J'}x_{J,J'}=\mu^{\mathrm{eligible}}_J\). The resulting distribution is
\[ \mu'_K=\mu^{\mathrm{fixed}}_K+\sum_{J\in T}x_{J,K}. \]
The changed mass is \(\sum_{J\ne J'}x_{J,J'}\). The question is whether there is a transfer plan changing at most \(\beta\) mass such that every outcome selected by continuous Young aggregation on \(\mu'\) contains \(\ell\). Equivalently, the optimization version minimizes changed mass subject to that guarantee.

For clarity, continuous Young aggregation here retains a subdistribution \(\rho\leq\mu'\) of maximum total mass whose strict-majority judgment set is \(\Gamma\)-consistent. A literal \(l\) is in that majority set when the retained mass supporting \(l\) exceeds half of \(\sum_J\rho_J\). The rule returns every complete \(\Gamma\)-consistent judgment set extending the majority set of some maximum-mass retained subdistribution. Thus the guarantee is robust to ties among optimal retentions, just as the paper requires the target to occur in every selected outcome.

A plausible regime is a large public consultation or membership vote on a fixed set of linked policy propositions. Many participants may share the same complete, coherent position and the same eligibility for contact by an outside campaign. The type is that full position plus eligibility; mass is the fraction of participants with that type. In the intended regime, the number of participants is very large while the number \(\tau\) of represented types is moderate. A campaign’s budget is naturally a share of the eligible population. This preserves the paper’s central question—whether an outside party can make a desired judgment unavoidable under Young aggregation—while expressing both the electorate and the intervention in population shares.

I would expect hardness to survive, most plausibly as Class B, because the paper’s Young reduction puts substantial combinatorics in the agenda and integrity constraint, not just in the number of voters. But Theorem 1 does not establish that transfer: fractional mass can split a type, and the discrete proof may rely on indivisible votes. An answer-preserving reduction, or a rounding result showing when fractional plans can be converted to discrete ones, is a key next question. Others are whether the problem has an algorithm polynomial in \(m,\tau\), and the input bit length; whether fixing \(m\) or \(\tau\) changes its complexity; and whether the nested optimization over minimum-mass deletions can be handled by LP duality or separation.

The weakest point is exactly that fractional split. A finite profile maps naturally to rational proportions, but continuous bribery permits changes involving less than one voter’s share. That can alter the Young outcome and break the paper’s hardness gadget. I would still expect the authors to recognize Young Mass Bribery as their problem’s continuous-population analogue: the types, target, rule, and guarantee are preserved, while the count of altered members becomes altered mass. This case covers the Young bribery result only; it does not claim to mirror the paper’s manipulation results, its other aggregation rules, or its CEGAR experiments.