Answer: polynomial-time solvable
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateCCRA is NP-hard when R is union function or approval function or GreedyMRC function, #delegations = 1 even when (1) the delegation graph satisfies one of the following conditions: (a) the maximum length of a path in the delegation graph is at most one and the cost of all the arcs is 1 (b) every vertex in the delegation graph has in-degree at most one (2) size of approval set is at most three (3) only one voter approves 𝑐★ Furthermore, it is W[2]-hard with respect to 𝑘+#redirections even when #delegations = 1 and condition 1 and 3 holds.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), preferred candidate \(c^\star\), active approval types \(\mathcal A\subseteq 2^C\) with \(|A|\le3\), rational active masses \(a_A\) and passive masses \(p_A\) satisfying \(\sum_{A\in\mathcal A}(a_A+p_A)=1\), where \(p_A\) currently delegates directly to an active voter of type \(A\), and a normalized unit-redirection budget \(K\), choose \(x_{A,B}\ge0\) with \(\sum_B x_{A,B}\le p_A\) and \(\sum_{A,B}x_{A,B}\le K\). Define \(q_A=a_A+p_A-\sum_Bx_{A,B}+\sum_Dx_{D,A}\). Decide whether \(c^\star\) can be made the unique approval winner, i.e. whether \(\sum_Aq_A\mathbf 1[c^\star\in A]>\sum_Aq_A\mathbf 1[c\in A]\) for every \(c\ne c^\star\).
Given finite sets of active types \(A\) and passive types \(P\), rational masses \(\alpha_a,\beta_p\ge0\) with \(\sum_{a\in A}\alpha_a+\sum_{p\in P}\beta_p=1\), approval sets \(B_a\subseteq C\) of size at most \(3\), an initial delegate \(a_0(p)\in A\), redirection prices \(w_p\), a preferred candidate \(c^\star\), and a rational budget \(K\), choose \(x_{p,a}\ge0\) with \(\sum_{a\in A}x_{p,a}=\beta_p\). The score of \(c\) is \(S_c(x)=\sum_{a\in A}(\alpha_a+\sum_{p\in P}x_{p,a})\mathbf{1}[c\in B_a]\), and the redirection cost is \(\sum_{p\in P}w_p(\beta_p-x_{p,a_0(p)})\).
Is deciding whether there is an \(x\) of cost at most \(K\) such that \(S_{c^\star}(x)>S_c(x)\) for every \(c\ne c^\star\) solvable in polynomial time, or is it NP-hard?
For discrete CCRA, where each passive voter redirects a single delegation arc, the problem is NP-hard even when every approval ballot has size at most \(3\), delegation paths have length at most \(1\), all arc costs are \(1\), and only one voter approves \(c^\star\). No result for the fractional-mass formulation above is established here.
Under the standard explicit encoding of \(A\), \(P\), \(C\), and all rational numbers in binary, the fractional-mass problem is polynomial-time solvable by linear programming. The bound \(\lvert B_a\rvert\le 3\) is not needed.
For every active type \(a\) and candidate \(c\), define
\(q_{a,c}:=\mathbf 1[c\in B_a]\).
For each opponent \(c\in C\setminus\{c^\star\}\), the winning margin of \(c^\star\) over \(c\) is
\(D_c(x):=S_{c^\star}(x)-S_c(x)\).
Expanding the scores gives
\(D_c(x)=\sum_{a\in A}\alpha_a(q_{a,c^\star}-q_{a,c})+\sum_{p\in P}\sum_{a\in A}x_{p,a}(q_{a,c^\star}-q_{a,c})\).
Thus every \(D_c(x)\) is an affine function of \(x\), with variable coefficients in \(\{-1,0,1\}\).
For any feasible assignment, put
\(\gamma_a:=\alpha_a+\sum_{p\in P}x_{p,a}\).
Then \(\gamma_a\ge 0\) and
\(\sum_{a\in A}\gamma_a=\sum_{a\in A}\alpha_a+\sum_{p\in P}\beta_p=1\).
Consequently \(0\le S_c(x)\le 1\) for every candidate \(c\), and hence \(-1\le D_c(x)\le 1\).
Introduce one additional variable \(\delta\), representing the minimum winning margin. Consider the following rational linear program:
The upper bound on \(\delta\) is valid because every positive winning margin is at most \(1\). It also makes the formulation work when \(c^\star\) is the only candidate.
Let \(\delta^\star\) denote the optimal value, provided the linear program is feasible.
Suppose first that there is an assignment \(x\) of cost at most \(K\) such that \(S_{c^\star}(x)>S_c(x)\) for every \(c\ne c^\star\). If there is at least one opponent, define
\(\widehat\delta:=\min_{c\in C\setminus\{c^\star\}}D_c(x)\).
The candidate set is finite, and every term in this minimum is strictly positive. Therefore \(\widehat\delta>0\). Moreover, \(\widehat\delta\le 1\), so \((x,\widehat\delta)\) is feasible for the linear program. Hence \(\delta^\star>0\).
If there are no opponents, the victory condition is vacuous. Any budget-feasible \(x\), together with \(\delta=1\), is feasible for the linear program.
Conversely, if the linear program has a feasible solution with \(\delta>0\), then for every opponent \(c\),
\(S_{c^\star}(x)-S_c(x)=D_c(x)\ge\delta>0\).
Thus \(c^\star\) strictly defeats every opponent, and the linear program already enforces the budget and mass-conservation conditions.
Therefore the original instance is a yes-instance exactly when the linear program is feasible and its optimal value satisfies \(\delta^\star>0\).
The linear program has \(\lvert P\rvert\lvert A\rvert+1\) variables and polynomially many constraints. All coefficients are rational numbers whose binary encoding lengths are polynomial in the input length.
Rational linear programming, including exact comparison of the optimal value with \(0\), is solvable in polynomial time in the Turing model. We can therefore reject if the program is infeasible and otherwise accept exactly when \(\delta^\star>0\).
Hence fractional divisibility removes the discrete selection responsible for the stated CCRA hardness result. The fractional formulation belongs to \(\mathsf P\), even without the restriction \(\lvert B_a\rvert\le 3\).
⟨structured verdict parsed — rendered above⟩
The prover correctly classifies the fractional-mass problem as polynomial-time solvable under the stated explicit rational encoding. The linear program exactly captures mass conservation, budget feasibility, and strict victory through maximization of a common margin variable. No substantive gap or false statement was found.
Defining \(q_{a,c}=\mathbf 1[c\in B_a]\), the displayed expansion of
\(D_c(x)=S_{c^\star}(x)-S_c(x)\) is correct. Each margin is affine in the variables \(x_{p,a}\).
From nonnegativity and the mass constraints,
\[
\sum_{a\in A}\left(\alpha_a+\sum_{p\in P}x_{p,a}\right)=1.
\]
Therefore every approval score lies in \([0,1]\), and every pairwise margin lies in \([-1,1]\). The constraint \(0\le\delta\le1\) is consequently valid.
All original feasibility constraints appear unchanged. The inequalities \(D_c(x)\ge\delta\) correctly make \(\delta\) a lower bound on every winning margin.
If an assignment strictly defeats every opponent, finiteness of \(C\) implies that the minimum of its finitely many positive margins is positive. Conversely, any feasible solution with \(\delta>0\) gives strict victory against every opponent. This correctly converts the strict feasibility question into testing whether the optimal LP value is positive.
When \(C\setminus\{c^\star\}\) is empty, the victory requirement is vacuous. The LP is feasible exactly when a budget-feasible mass assignment exists, and then \(\delta=1\) is allowed. The special case is handled correctly.
The criterion “the LP is feasible and \(\delta^\star>0\)” remains correct if the added condition \(\delta\ge0\) makes the LP infeasible because every attainable minimum margin is negative: such an instance is necessarily a no-instance.
There are \(\lvert P\rvert\lvert A\rvert+1\) variables and polynomially many rational constraints. The constructed coefficients have polynomial binary encoding length. Polynomial-time rational linear programming permits exact determination of infeasibility and of whether the rational optimum is greater than \(0\).
Nothing in the formulation depends on \(\lvert B_a\rvert\le3\); with explicitly encoded approval sets, removing this restriction does not invalidate the polynomial-size claim.
No major or minor issues were identified.
⟨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.