Answer: Polynomial-time solvable: the problem is in \(\mathrm{P}\) for fixed \(m=3\).
Theorem 8 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor the cup rule on weighted votes, \ConstructiveManipulation\ is polynomial irrespective of the number of candidates, but \PreferenceManipulation\ with 3 or more candidates is NP-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(A,B,C\), the cup agenda, a target, and the paper’s target-favourable tie rule, let each type \(t\) have rational mass \(\mu_t\), initial ranking \(r_t\), and a set \(M_t\) of comparisons the campaign may change. Let \(R_t\) be the total rankings that preserve all comparisons outside \(M_t\). Does there exist an allocation \(x_{t,r}\ge 0\), for \(r\in R_t\), with \(\sum_{r\in R_t}x_{t,r}=\mu_t\) for every type, such that the resulting population elects the target?
The candidate set is \(\{A,B,C\}\), with \(m=3\); the input includes a target \(p\) and a fixed cup agenda, a binary tree with each candidate appearing once as a leaf.
A society is given by its support: a list of \(\tau\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type specifies an initial strict total ranking \(r_t\) and a set \(M_t\) of unordered candidate pairs whose comparisons may change. Let \(R_t\) contain exactly the strict total rankings agreeing with \(r_t\) on every pair outside \(M_t\).
An allocation consists of real masses \(x_{t,r}\geq0\) for \(r\in R_t\), with \(\sum_{r\in R_t}x_{t,r}=\mu_t\). Changes have no costs or budget, and allowed comparisons may remain unchanged.
Each cup match advances the candidate preferred by greater population mass. A tied match involving \(p\) advances \(p\); in other tied matches the chair may choose either candidate, with choices favouring an overall victory for \(p\).
The decision problem asks whether an allocation and permitted chair choices make \(p\) the cup winner. Let \(L\) be the total binary input length; state running times in \(m,\tau,L\), with \(m=3\) fixed.
Is this continuous preference-manipulation decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
For indivisible positive-integer-weight votes, changing specified comparisons while preserving total rankings is \(\mathrm{NP}\)-complete already with three candidates and a fixed balanced cup; changing entire coalition votes is polynomial-time solvable for any number of candidates. [Walsh](https://arxiv.org/pdf/0903.1137)
No published result settling this exact divisible-mass problem was located in the literature search.
The decision problem is in \(\mathrm{P}\) for fixed \(m=3\). The proof uses at most two rational linear-programming feasibility problems and handles the stated tie rules exactly.
For each type \(t\), enumerate all \(m!\) strict total rankings and retain precisely those agreeing with \(r_t\) on every pair outside \(M_t\). This constructs \(R_t\) exactly. Since \(m=3\), each \(R_t\) contains at most six rankings. Moreover, \(r_t\in R_t\), so \(R_t\) is nonempty.
Introduce one real variable \(x_{t,r}\) for each \(r\in R_t\), with constraints
\[ x_{t,r}\geq 0,\qquad \sum_{r\in R_t}x_{t,r}=\mu_t \quad\text{for every }t. \]
These constraints describe exactly the permitted allocations: each type’s mass can be divided arbitrarily among its allowed total rankings.
For distinct candidates \(u,v\), define
\[ \sigma_r(u,v)= \begin{cases} 1,&\text{if }r\text{ ranks }u\text{ above }v,\\ -1,&\text{if }r\text{ ranks }v\text{ above }u, \end{cases} \qquad D_{uv}(x)=\sum_t\sum_{r\in R_t}\sigma_r(u,v)x_{t,r}. \]
Every ranking is strict and total, so \(D_{uv}(x)\) is exactly the mass preferring \(u\) to \(v\) minus the mass preferring \(v\) to \(u\).
Consequently:
The first statement uses the mandatory tie rule favouring \(p\). The second uses the chair’s freedom to choose either candidate at equality.
A binary cup with three leaves has one preliminary match and one final. There are two cases.
Let \(a,b\) be the other candidates; they contest the preliminary match.
For each \(w\in\{a,b\}\), let \(\ell\) be the other candidate. Construct a linear feasibility problem consisting of the allocation constraints and
\[ D_{w\ell}(x)\geq 0,\qquad D_{pw}(x)\geq 0. \]
Accept if at least one of these two systems is feasible.
Necessity. Suppose an allocation and permitted chair choices make \(p\) win. Let \(w\) be the actual preliminary winner. Its advancement implies \(D_{w\ell}(x)\geq 0\): a negative margin would force \(\ell\) to advance. Since \(p\) wins the final against \(w\), we also have \(D_{pw}(x)\geq 0\). Thus the system indexed by \(w\) is feasible.
Sufficiency. Suppose the system indexed by \(w\) is feasible. Its solution is a permitted allocation. If \(D_{w\ell}(x)>0\), then \(w\) wins the preliminary match outright. If \(D_{w\ell}(x)=0\), the chair chooses \(w\); this choice favours an overall victory for \(p\), because the second constraint guarantees that \(p\) wins the final against \(w\). Therefore \(p\) becomes the cup winner.
Let \(a\) be \(p\)’s preliminary opponent and \(b\) the candidate entering directly into the final.
Construct one linear feasibility problem consisting of the allocation constraints and
\[ D_{pa}(x)\geq 0,\qquad D_{pb}(x)\geq 0. \]
Necessity. To win the cup, \(p\) must win both its preliminary match against \(a\) and its final against \(b\). The two inequalities therefore hold.
Sufficiency. The first inequality makes \(p\) advance from the preliminary match, and the second makes \(p\) win the final. Equality in either match advances \(p\) by the specified tie rule.
These cases exhaust all three-candidate agendas, proving correctness of the algorithm.
We use the standard polynomial-time theorem for rational linear programming: feasibility of a finite system of non-strict linear inequalities with rational coefficients, over real variables, is decidable in time polynomial in its binary encoding length.
Its hypotheses hold here:
In particular, exact ties require no numerical tolerance. The theorem decides feasibility over real allocations directly.
Constructing the allowed rankings takes \(O(\tau m!m^2)\) elementary comparison operations, which is \(O(\tau)\) for \(m=3\).
Each feasibility problem has at most \(6\tau\) variables. Expressing every equality as two inequalities and counting nonnegativity constraints gives at most
\[ 6\tau+2\tau+2=8\tau+2 \]
inequalities. A dense binary encoding of one system has length \(O(L+\tau^2)\): its matrix has \(O(\tau^2)\) constant-size coefficients, and the masses contribute \(O(L)\) bits.
Writing \(T_{\mathrm{LP}}(N,H,B)\) for a polynomial bound for rational feasibility with \(N\) variables, \(H\) inequalities, and encoding length \(B\), the running time is bounded by
\[ O(\tau m!m^2) + 2T_{\mathrm{LP}}\!\left(6\tau,8\tau+2,O(L+\tau^2)\right), \qquad m=3. \]
Thus the running time is \(\operatorname{poly}(\tau,L)\). Since the input explicitly lists the \(\tau\) types, \(\tau=O(L)\), so this is also \(\operatorname{poly}(L)\).
Walsh’s three-candidate hardness construction uses indivisible weighted votes to enforce a partition of their weights. [Walsh, Section 8](https://arxiv.org/pdf/0903.1137)
Here, a type’s mass may be divided among several allowed rankings. That division is represented exactly by the continuous variables above. For each possible preliminary winner, the remaining conditions are linear inequalities, so the indivisible-choice obstruction does not apply.
Therefore the stated divisible-mass problem is polynomial-time solvable. It could also be \(\mathrm{NP}\)-hard under polynomial-time many-one reductions only if \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly: the continuous decision problem is in \(\mathrm{P}\) for fixed \(m=3\). No major or minor mathematical issues were found.
Enumerating all strict total rankings and retaining those that preserve every comparison outside \(M_t\) produces exactly the specified set \(R_t\). This does not impose unintended restrictions on comparisons inside \(M_t\), which may either change or remain unchanged.
The assertion \(r_t\in R_t\) is correct: the initial ranking agrees with itself on every fixed comparison. Thus every type has a nonempty allowed set. For \(m=3\), the bound \(|R_t|\leq 6\) is correct.
The variables \(x_{t,r}\geq 0\), together with \(\sum_{r\in R_t}x_{t,r}=\mu_t\), impose exactly the permitted division of each type’s mass among its allowed rankings.
There are no missing integrality, cost, or budget constraints: the task explicitly allows real allocations and unrestricted changes within the specified comparisons. The formulation also permits zero mass on an allowed ranking and permits retaining the initial ranking.
Every strict total ranking contributes either \(+x_{t,r}\) or \(-x_{t,r}\) to \(D_{uv}(x)\), according to its comparison of \(u\) and \(v\). Consequently, this expression is precisely the difference between the two supporting population masses.
For a match involving \(p\), the condition \(D_{pv}(x)\geq 0\) is necessary and sufficient for \(p\) to advance, including equality under the mandatory tie rule.
For a match between the other candidates, \(D_{uv}(x)\geq 0\) is necessary and sufficient for the chair to be able to advance \(u\). A negative margin cannot be overridden, and equality permits either choice. There is no incorrect replacement of a strict inequality by a non-strict one.
Under the cup interpretation, internal nodes represent matches between two children. A three-leaf agenda therefore has one preliminary match and one final. The target either receives the bye or participates in the preliminary match.
In Case I, necessity correctly selects the actual preliminary winner \(w\). Both required margins must then be nonnegative under the same allocation.
Sufficiency also holds: the first constraint permits \(w\) to advance, and the second guarantees that \(p\) defeats \(w\). When the preliminary match is tied, selecting \(w\) is a permitted choice favouring an overall victory for \(p\). Enumerating both possible preliminary winners covers every successful allocation and chair choice.
In Case II, the final opponent is necessarily the candidate receiving the bye. Both inequalities concern the same allocation and are exactly the conditions for \(p\) to win its two matches. Equality in either match is handled correctly.
The invoked theorem concerns feasibility over real variables of finite systems of non-strict rational linear inequalities, with running time polynomial in their binary encoding length. This is the appropriate standard rational linear-programming feasibility theorem.
Every coefficient is rational, every right-hand side is rational, and replacing the allocation equalities with two inequalities yields the required form. Real variables are within the theorem’s scope. No strict inequalities, numerical tolerances, or irrational input constants enter the systems.
Thus the appeal to exact feasibility is justified, including instances whose successful allocations require tied matches.
Let \(N=\sum_t|R_t|\). Then \(N\leq 6\tau\). There are \(N\) nonnegativity inequalities, \(2\tau\) inequalities expressing the allocation equalities, and two match inequalities. Hence the stated bound \(8\tau+2\) is valid.
A dense matrix has \(O(\tau^2)\) entries of constant coefficient bit length. Encoding the masses, including their repeated appearance after converting equalities, requires \(O(L)\) bits. The total bound \(O(L+\tau^2)\) is therefore valid.
The enumeration bound \(O(\tau m!m^2)\) correctly counts checking all pair comparisons for all rankings and types. The displayed algorithm uses at most two feasibility calls. With \(m=3\), its running time is polynomial in \(\tau,L\); because the support is explicitly listed, \(\tau=O(L)\), giving polynomial time in the total input length.
The attribution to Walsh’s Section 8 is supported: its three-candidate cup reduction uses a partition of indivisible vote weights, and the constructed cup is balanced. [Walsh, Section 8](https://arxiv.org/pdf/0903.1137)
The prover correctly explains why that obstruction does not establish hardness for divisible allocations. More importantly, its polynomial-time conclusion follows independently from the verified algorithm. The qualification that polynomial-time many-one NP-hardness would imply \(\mathrm{P}=\mathrm{NP}\) is correct.
No additional clarification or repair is needed. The result is restricted appropriately to the assigned setting with fixed \(m=3\).
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.