Answer: Both the co-winner and unique-winner continuous manipulation problems are in \(\mathrm{P}\). The algorithm runs in \(3^{\binom m2}\operatorname{poly}(m!,m,\tau,L)\) bit operations, hence in \(\operatorname{poly}(\tau,L)\) time for \(m=4\).
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateCopeland1-WCM for four candidates can be solved in polynomial time both in the nonunique-winner model and in the unique-winner model. The general idea of our algorithm is as follows. First, we let all the manipulators rank the preferred candidate p in the top position in their votes. Based on that, we compute the Copeland1 score of the preferred candidate as well as lower bounds on the scores of the remaining three candidates.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Fix \(C=\{p,a,b,c\}\). An instance gives binary-rational masses \(\mu_{\succ,w}\) of sincere voter types, each with ranking \(\succ\) and positive integer weight \(w\), and masses \(\nu_w\) of manipulable types with weight \(w\); the masses together sum to \(1\), and the input has support size \(\tau\). For each weight \(w\) and reported ranking \(\pi\), choose \(x_{w,\pi}\ge 0\) with \(\sum_{\pi}x_{w,\pi}=\nu_w\). Define \(M_x(i,j)=\sum_{\succ,w}w\mu_{\succ,w}\sigma_{\succ}(i,j)+\sum_{w,\pi}w x_{w,\pi}\sigma_{\pi}(i,j)\), where \(\sigma_{\rho}(i,j)=1\) if \(\rho\) ranks \(i\) above \(j\), and \(-1\) otherwise. Decide whether a feasible \(x\) makes \(p\) a Copeland\(_1\) co-winner, or, in the unique-winner variant, the sole winner.
Fix \(C=\{p,a,b,c\}\), with \(m=4\). All sincere and reported rankings are strict total orders on \(C\); weights \(w\) are positive integers encoded in binary.
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational. Sincere types \((\succ,w)\) have masses \(\mu_{\succ,w}\); manipulable types \(w\) have masses \(\nu_w\). Their combined mass is \(1\). The support size \(\tau\) counts listed types, not possible types; \(L\) is the total input bit length.
A manipulation chooses real masses \(x_{w,\pi}\geq0\) for every listed manipulable weight and every strict ranking \(\pi\), satisfying \(\sum_\pi x_{w,\pi}=\nu_w\). Each type's mass may be split arbitrarily among reports, with its weight preserved.
For distinct candidates define \(\sigma_\rho(i,j)=1\) when \(i\) precedes \(j\) in \(\rho\), and \(-1\) otherwise, and \(M_x(i,j)=\sum_{\succ,w}w\mu_{\succ,w}\sigma_\succ(i,j)+\sum_{w,\pi}wx_{w,\pi}\sigma_\pi(i,j)\).
Use Copeland\(_1\) (Llull), retaining all candidates with maximum score and applying no final tie-breaking. The co-winner decision problem asks whether some feasible manipulation makes \(p\) a winner; the unique-winner variant requires \(p\) to be the sole winner.
For each of these two continuous decision problems, is it in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? State running times in \(m\), \(\tau\), and \(L\), with \(m=4\) fixed.
Discrete weighted coalitional manipulation with four candidates and binary integer weights is polynomial-time solvable in both winner models ([Faliszewski, Hemaspaandra, and Schnoor](https://ebooks.iospress.nl/pdf/doi/10.3233/978-1-61499-098-7-318)). No result settling exactly the continuous decision problems above was identified in the literature search.
Both the co-winner and unique-winner problems are in \(\mathrm{P}\).
More generally, the algorithm below takes
\(3^{\binom m2}\operatorname{poly}(m!,m,\tau,L)\) bit operations. For \(m=4\), it solves at most \(3^6=729\) rational linear programs, each with \(25\) variables and a constant number of constraints. Thus its running time is \(\operatorname{poly}(\tau,L)\).
Let \(\Pi\) be the set of all \(m!\) strict rankings. Define the sincere margins and total manipulable weighted mass by
\(A(i,j)=\sum_{\succ,w}w\mu_{\succ,w}\sigma_\succ(i,j),\qquad W=\sum_w w\nu_w.\)
For a feasible manipulation, define
\(y_\pi=\sum_w wx_{w,\pi}\qquad(\pi\in\Pi).\)
Then
\(y_\pi\geq0,\qquad \sum_{\pi\in\Pi}y_\pi=W,\)
and the resulting margins are
\(M_y(i,j)=A(i,j)+\sum_{\pi\in\Pi}y_\pi\sigma_\pi(i,j).\)
Conversely, every vector satisfying these nonnegativity and total-weight constraints comes from a feasible manipulation.
Indeed, if \(W>0\), set, for each listed manipulable weight,
\(x_{w,\pi}=\nu_w\frac{y_\pi}{W}.\)
These masses are nonnegative and satisfy
\(\sum_\pi x_{w,\pi}=\nu_w\frac{\sum_\pi y_\pi}{W}=\nu_w.\)
Moreover,
\(\sum_w wx_{w,\pi}=\frac{y_\pi}{W}\sum_w w\nu_w=y_\pi.\)
If \(W=0\), positivity of the listed weights and masses implies that there are no manipulable types. The constraints on \(y\) force every coordinate to be zero, which represents that case correctly.
Consequently, the attainable margin vectors are exactly those generated by the simplex
\(\{y\in\mathbb R_{\geq0}^{m!}:\sum_\pi y_\pi=W\}\).
This equivalence preserves every type’s weight and mass.
Fix an arbitrary ordering of the candidates and put \(d=\binom m2\). Enumerate all \(3^d\) assignments
\(s(i,j)\in\{-1,0,1\}\qquad(i<j),\)
where a positive sign means that \(i\) defeats \(j\), zero means a pairwise tie, and a negative sign means that \(i\) loses. Extend each assignment antisymmetrically by \(s(j,i)=-s(i,j)\).
Under Copeland\(_1\), a candidate receives one point for either a victory or a tie and zero points for a defeat. Therefore the score determined by a sign assignment is
\(S_s(i)=\sum_{j\neq i}\mathbf 1\{s(i,j)\geq0\}.\)
For the co-winner problem, retain precisely those assignments satisfying
\(S_s(p)\geq S_s(c)\qquad\text{for every }c\neq p.\)
For the unique-winner problem, retain precisely those satisfying
\(S_s(p)>S_s(c)\qquad\text{for every }c\neq p.\)
These tests take \(O(m^2)\) time per assignment. What remains is to decide whether a retained assignment is attainable.
For a retained assignment \(s\), introduce the variables \(y_\pi\) and one additional variable \(\delta\). Solve the following rational linear program:
Maximize \(\delta\), subject to
\(y_\pi\geq0\quad(\pi\in\Pi),\qquad \sum_{\pi\in\Pi}y_\pi=W,\qquad 0\leq\delta\leq1,\)
and, for each \(i<j\), the appropriate constraint:
| Prescribed sign | Constraint |
|---|---|
| \(s(i,j)=1\) | \(A(i,j)+\sum_\pi y_\pi\sigma_\pi(i,j)\geq\delta\) |
| \(s(i,j)=0\) | \(A(i,j)+\sum_\pi y_\pi\sigma_\pi(i,j)=0\) |
| \(s(i,j)=-1\) | \(A(i,j)+\sum_\pi y_\pi\sigma_\pi(i,j)\leq-\delta\) |
Reject an infeasible program. Otherwise, accept this assignment exactly when its optimum satisfies \(\delta^*>0\).
Suppose first that some feasible aggregate vector \(y\) realizes the prescribed signs. If at least one prescribed sign is nonzero, define
\(\varepsilon=\min_{\substack{i<j\\s(i,j)\neq0}}|M_y(i,j)|.\)
Every quantity in this finite minimum is strictly positive, so \(\varepsilon>0\). Taking \(\delta=\min\{1,\varepsilon\}\) satisfies every constraint. Thus \(\delta^*>0\).
If all prescribed signs are zero, the same aggregate vector satisfies the program with \(\delta=1\), so again \(\delta^*>0\).
Conversely, any feasible solution with \(\delta>0\) has strictly positive margins on the prescribed positive pairs, strictly negative margins on the prescribed negative pairs, and exactly zero margins on the prescribed ties. It therefore realizes precisely \(s\). Section 1 converts its aggregate vector into a feasible manipulation.
Finally, the program’s feasible region is closed and bounded: each \(y_\pi\) belongs to \([0,W]\), and \(\delta\) belongs to \([0,1]\). Hence every feasible program attains its optimum. This proves the claimed equivalence.
If a successful manipulation exists, its margins define one of the enumerated sign assignments. Its scores satisfy the applicable winner test, so that assignment is retained. Its attainability program has positive optimum by Section 3, and the algorithm accepts.
Conversely, if the algorithm accepts, an accepted program supplies an attainable sign assignment satisfying the applicable winner test. The reconstruction in Section 1 yields a feasible manipulation with exactly those margins. Thus \(p\) is a co-winner or the unique winner, respectively.
Both directions hold also when there are no manipulable types.
Computing \(A\) and \(W\) requires \(O(\tau m^2)\) rational arithmetic operations. Their encoding lengths remain polynomial in \(L\). Explicitly, a common denominator can be obtained by multiplying the denominators of all input masses; its bit length is at most their total input bit length. After clearing that denominator, multiplication by the binary weights and summation over the support produce integers of bit length \(O(L+\log\tau)\).
Each attainability program has \(m!+1\) variables and \(O(m!+m^2)\) constraints. All coefficients are rational, and its total encoding length is polynomial in \(m!,m,L\). Rational linear programming permits exact feasibility determination and exact optimization in time polynomial in the binary encoding length; see [Trevisan’s linear-programming notes, Section 5.2.5](https://theory.stanford.edu/~trevisan/books/cs261.pdf#page=44). The programs here meet these hypotheses, and feasible instances have bounded objectives. Consequently, comparing the exact rational optimum with zero is a polynomial-time operation.
Including preprocessing, enumeration, and optimization gives the bound
\(3^{\binom m2}\operatorname{poly}(m!,m,\tau,L).\)
For \(m=4\), there are at most \(729\) programs with \(25\) variables each, so both decision problems are polynomial-time solvable in the stated binary input model.
⟨structured verdict parsed — rendered above⟩
The prover resolves both assigned decision problems correctly. Both are in \(\mathrm{P}\) for fixed \(m=4\). I found no mathematical errors, unjustified applications of theorems, or gaps requiring clarification.
From any feasible manipulation, the definition \(y_\pi=\sum_w wx_{w,\pi}\) gives nonnegative coordinates and
\(\sum_\pi y_\pi=\sum_w w\nu_w=W\). Substitution into the margin formula is valid because all sums are finite.
The converse is also correct. When \(W>0\), the proposed reconstruction \(x_{w,\pi}=\nu_w y_\pi/W\) preserves every listed type’s mass, uses only its original weight, and reproduces each aggregate coordinate. Arbitrary splitting among all strict rankings is explicitly permitted by the task, so there are no additional report restrictions to invalidate this reconstruction.
The case \(W=0\) is handled correctly: positive weights and positive listed masses exclude any manipulable type, and nonnegativity together with total aggregate mass zero forces \(y_\pi=0\) for every ranking. No division by zero occurs.
Each unordered pair has exactly three possible margin signs, giving \(3^{\binom m2}\) assignments. Antisymmetric extension correctly determines the outcome from either candidate’s perspective.
Under the specified rule, a victory and a tie each contribute one point. Consequently, \(S_s(i)=\sum_{j\ne i}\mathbf 1\{s(i,j)\geq0\}\) is correct, including tied pairs, where both candidates receive a point.
Comparing \(p\)’s score weakly against every opponent characterizes co-winning. Comparing it strictly against every opponent characterizes unique winning because the task applies no final tie-breaking. The stated \(O(m^2)\) work per assignment is valid.
Some enumerated assignments may be unattainable; the algorithm does not assume otherwise and tests their attainability separately.
For an aggregate vector realizing an assignment with nonzero signs, every corresponding absolute margin is positive. There are finitely many such pairs, so their minimum \(\varepsilon\) is positive. The specified choice \(\delta=\min\{1,\varepsilon\}\) satisfies every signed inequality and all tie equalities.
The all-zero assignment is explicitly covered: its pair constraints are equalities independent of \(\delta\), so a realizing vector permits \(\delta=1\).
Conversely, a feasible solution with \(\delta>0\) enforces precisely the prescribed positive, negative, and zero margins. Thus neither a zero margin masquerading as a strict outcome nor an unintended nonzero margin on a prescribed tie can cause acceptance.
The optimum exists whenever the LP is feasible. The aggregate constraints imply \(0\leq y_\pi\leq W\), and the auxiliary variable lies in \([0,1]\). All constraints are closed, so the feasible region is compact, and the linear objective attains its maximum. Therefore acceptance based on \(\delta^*>0\) is justified.
A successful manipulation determines an enumerated assignment that passes the appropriate score test and has a positive LP optimum.
Conversely, an accepted assignment has a realizing aggregate vector, and Section 1 reconstructs a feasible manipulation preserving the prescribed margins. Its score comparison then gives the requested winner status.
These implications apply separately to both winner models and remain valid with no manipulable types. The argument does not confuse existence of real masses with existence of integral allocations.
The \(O(\tau m^2)\) preprocessing bound counts rational arithmetic operations, as stated. The accompanying bit-length analysis justifies polynomial bit cost: multiplying the input denominators gives a common denominator whose bit length is bounded by their total encoding length. Multiplication by encoded weights and summation over at most \(\tau\) terms give the claimed \(O(L+\log\tau)\) numerator bound. Cancellation or reduction of fractions cannot increase these bounds.
Each LP has \(m!+1\) variables and \(O(m!+m^2)\) constraints, with rational coefficients of polynomial encoding length. The cited theorem supplies polynomial-time feasibility determination and exact optimization for rational LPs; its binary encoding assumptions and boundedness requirements are satisfied here. The cited [Trevisan notes, Section 5.2.5](https://theory.stanford.edu/~trevisan/books/cs261.pdf#page=44) support this application.
Exact rational optimization makes comparison with zero legitimate even when the positive optimum is very small. No numerical tolerance assumption is needed.
The resulting bound \(3^{\binom m2}\operatorname{poly}(m!,m,\tau,L)\) accounts for preprocessing, enumeration, and optimization. For \(m=4\), the counts \(3^6=729\) and \(4!+1=25\) are correct, and the running time is polynomial in \(\tau\) and \(L\).
No repair or additional clarification is needed. The proof establishes the continuous classification directly and does not rely on the supplied discrete manipulation result.
⟨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.