Answer: \(\mathrm{P}\)
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximatePlurality-CCAC and Plurality-CCDC for single-crossing elections are both inP.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), unregistered candidates \(A\), a preferred candidate \(p\in C\), an integer \(k\), and rational masses \(\mu_t\) over complete ranking types \(t\) on \(C\cup A\) in a known single-crossing order, decide whether some \(S\subseteq A\) with \(|S|\le k\) makes \(p\) the unique plurality winner after \(S\) is added, using weighted plurality scores.
Given disjoint finite candidate sets \(C\) and \(A\), a preferred candidate \(p\in C\), and a binary-encoded nonnegative integer \(k\), let \(m=|C\cup A|\).
A society is given by its support: a list of \(\tau\) distinct strict complete ranking types on \(C\cup A\), each with positive binary rational mass \(\mu_t\), with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings; let \(L\) be the total input bit length.
The support comes in a known single-crossing order: for every pair of candidates, their relative ranking changes at most once along this order, on the full set \(C\cup A\).
An allowed action selects \(S\subseteq A\) with \(|S|\le k\). Rankings are restricted to \(C\cup S\), masses remain fixed, and each type contributes its mass to its highest-ranked remaining candidate under weighted plurality. Success means that \(p\)'s score strictly exceeds every other remaining candidate's score; ties do not count as success.
Is this decision problem in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\) and \(\min\{k,|A|\}\), or is it \(\mathrm{NP}\)-hard?
For explicitly listed unweighted voters with single-crossing rankings, constructive plurality control by adding or deleting candidates is in \(\mathrm{P}\) ([Magiera and Faliszewski](https://link.springer.com/article/10.1007/s10458-016-9339-3)).
No result settling this exact rational-mass, support-encoded problem was located in the literature search.
The problem is in \(\mathrm{P}\). A polynomial-time algorithm works directly with the support and binary rational masses, without expanding masses into individual voters.
The explicitly listed unweighted case is established by [Magiera and Faliszewski, Theorem 3](https://link.springer.com/article/10.1007/s10458-016-9339-3). The proof below independently establishes the support-encoded rational-mass case.
Index the ranking types by their given single-crossing order, \(\{1,\ldots,\tau\}\). Write \(x\succ_t y\) when type \(t\) ranks \(x\) above \(y\).
Write each mass as \(\mu_t=a_t/b_t\), with positive integers \(a_t,b_t\). Define \(Q=\prod_{t=1}^{\tau}b_t\) and \(w_t=a_t(Q/b_t)\). Then every \(w_t\) is a positive integer and \(\sum_t w_t=Q\). Multiplying all scores by \(Q\) preserves every strict score comparison.
For integer indices \(1\le u\le v\le\tau\), let \([u,v]=\{u,u+1,\ldots,v\}\) and \(W(u,v)=\sum_{t=u}^{v}w_t\).
Lemma 1 (vote intervals). For any nonempty remaining candidate set \(D\subseteq C\cup A\), the types whose highest-ranked candidate in \(D\) is a given candidate \(c\in D\) form an interval, possibly empty.
Proof. For each \(d\in D\setminus\{c\}\), single crossing implies that \(\{t:c\succ_t d\}\) is a prefix, a suffix, the whole index set, or the empty set. In particular, it is an interval. The types choosing \(c\) form the intersection of these sets, which is an interval. If \(D=\{c\}\), all types choose \(c\). \(\square\)
Consequently, an election partitions the type order into consecutive nonempty blocks, with a distinct candidate receiving each block’s votes. Candidates outside this list receive score zero.
An added candidate receiving score zero can be removed without changing anyone’s vote: every type’s original highest-ranked remaining candidate is still present. Thus, when seeking an action with at most \(k\) additions, we may restrict attention to added candidates receiving positive scores.
Lemma 2 (boundary comparisons). Suppose \(1\le h<\tau\), \(x\succ_h y\), and \(y\succ_{h+1}x\). Then \(x\succ_t y\) for every \(t\le h\), and \(y\succ_t x\) for every \(t\ge h+1\).
Proof. The stated comparisons already exhibit a change between indices \(h\) and \(h+1\). Any contrary comparison on either side would require another change, contradicting single crossing. \(\square\)
In particular, such a boundary implies \(x\succ_1 y\).
Consider a partition into nonempty consecutive intervals \(I_1,\ldots,I_s\), covering \([1,\tau]\), with candidate labels \(c_1,\ldots,c_s\). Suppose:
Lemma 3. Under these conditions, the labels are distinct, and in the election with candidate set \(D=C\cup\{c_1,\ldots,c_s\}\), every type in \(I_i\) votes for \(c_i\).
Proof. Lemma 2 gives \(c_i\succ_1 c_{i+1}\) at every boundary. Transitivity of the first ranking gives \(c_1\succ_1 c_2\succ_1\cdots\succ_1 c_s\). Therefore, the labels are distinct.
Fix \(t\in I_i\). Every boundary preceding \(I_i\) lies before \(t\), so Lemma 2 gives \(c_{j+1}\succ_t c_j\) for every \(j<i\). Transitivity implies that \(c_i\) beats every earlier label at type \(t\).
Every boundary following \(I_i\) lies at or after \(t\), so Lemma 2 gives \(c_j\succ_t c_{j+1}\) for every \(j\ge i\). Thus \(c_i\) also beats every later label.
Condition 1 ensures that \(c_i\) beats every other candidate in \(C\). Hence \(c_i\) is highest-ranked in \(D\) at type \(t\). \(\square\)
This lemma also handles mandatory candidates that receive no votes: they remain present through \(C\), and Condition 1 ensures they cannot disrupt the proposed blocks.
Set \(K=\min\{k,|A|\}\). Enumerate every nonempty interval \([\ell,r]\subseteq[1,\tau]\) as a guess for exactly the types voting for \(p\). There are \(\tau(\tau+1)/2\) guesses.
For a fixed guess, put \(q=W(\ell,r)\). Because all masses are positive, \(q>0\).
Construct a directed graph whose ordinary vertices are triples \((c,u,v)\), representing a block \([u,v]\) voting for \(c\). Include a triple exactly when all the following conditions hold:
Give this vertex cost \(1\) if \(c\in A\), and cost \(0\) if \(c\in C\).
Add a source \(\sigma\) and a sink \(\omega\), both of cost zero. Add an arc from \(\sigma\) to every vertex starting at index \(1\), and an arc from every vertex ending at index \(\tau\) to \(\omega\).
Between ordinary vertices, add the arc \((x,u,h)\longrightarrow(y,h+1,v)\) precisely when \(x\ne y\), \(x\succ_h y\), and \(y\succ_{h+1}x\).
Every ordinary arc strictly increases the interval’s ending index, so the graph is acyclic. Compute a minimum-cost source-to-sink path, where path cost is the sum of its vertex costs. Accept the instance if some guess has such a path of cost at most \(K\).
A source-to-sink path partitions all type indices into consecutive blocks. Since every non-\(p\) vertex avoids \([\ell,r]\), covering those indices forces the path to contain \((p,\ell,r)\).
Suppose the algorithm finds a path of cost at most \(K\). Let \(S\) be the set of its candidate labels belonging to \(A\).
The path satisfies both conditions of Lemma 3. That lemma proves that its labels are distinct and its blocks are exactly the vote blocks in the election with candidate set \(C\cup S\). Consequently, \(|S|\) equals the path cost and is at most \(K\le k\).
The candidate \(p\) receives scaled score \(q\). Every other path label receives the weight of its block, which is strictly less than \(q\) by vertex Condition 4. Every remaining candidate outside the path labels receives score zero, which is also strictly less than \(q\).
Thus \(p\) strictly defeats every other remaining candidate, and \(S\) is a successful allowed action.
Suppose an allowed action \(S\subseteq A\), with \(|S|\le k\), makes \(p\) the unique plurality winner. Remove from \(S\) every candidate receiving score zero; as established above, this preserves all votes and scores.
Because the total score is positive, a unique winner has positive score. Lemma 1 therefore gives a nonempty interval \([\ell,r]\) of types voting for \(p\). Consider the algorithm’s corresponding guess, with \(q=W(\ell,r)\).
Apply Lemma 1 to all remaining candidates. Their nonempty vote intervals partition \([1,\tau]\) into consecutive blocks with distinct labels.
Every block label beats every other candidate in \(C\) throughout its block, since it is the actual highest-ranked remaining candidate. Every non-\(p\) block is disjoint from \(p\)’s block and has weight strictly below \(q\), since \(p\) is the unique winner. Thus every block appears as a vertex of the graph.
At a boundary \(h\) between blocks labelled \(x\) and \(y\), type \(h\) votes for \(x\), so \(x\succ_h y\). Type \(h+1\) votes for \(y\), so \(y\succ_{h+1}x\). The required arc therefore exists.
These blocks form a source-to-sink path. Its cost is the number of remaining added candidates, at most both \(k\) and \(|A|\), hence at most \(K\). The algorithm accepts.
Precompute candidate positions in every ranking. For each candidate \(c\) and type \(t\), precompute whether \(c\) beats every member of \(C\setminus\{c\}\). Prefix counts of failures then allow vertex Condition 2 to be checked in constant time for any interval. Prefix weight sums likewise allow \(W(u,v)\) to be obtained with one subtraction.
For each guess:
Over all \(O(\tau^2)\) guesses, the algorithm therefore uses \(O(m^2\tau^5)\) elementary operations, apart from polynomial-time preprocessing.
The bit length of \(Q\) is at most the sum of the denominator bit lengths, hence \(O(L)\). Every weight and prefix weight sum is at most \(Q\), so all weight calculations and comparisons involve \(O(L)\)-bit integers. Every finite path cost is at most \(m\), because Lemma 3 ensures distinct candidate labels.
Consequently, the bit running time is polynomial in \(m,\tau,L\), and in particular polynomial in the requested parameters \(m,\tau,L,\min\{k,|A|\}\). No enumeration up to a binary-encoded mass or denominator is required.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The algorithm resolves the exact support-encoded rational-mass problem in polynomial time. I found no mathematical errors or gaps requiring clarification.
For each positive rational mass \(\mu_t=a_t/b_t\), the defined integer \(Q=\prod_t b_t\) is divisible by every denominator. Thus \(w_t=a_t(Q/b_t)\) is a positive integer, and normalization gives
\[
\sum_t w_t=Q.
\]
Every candidate’s scaled score is exactly its original score multiplied by \(Q>0\). Therefore all strict comparisons, including the rejection of ties, are preserved.
The representation does not expand the support into individual voters.
For any distinct candidates \(c,d\), the single-crossing promise makes the set of types preferring \(c\) to \(d\) a prefix, suffix, entire index set, or empty set.
A type chooses \(c\) from \(D\) precisely when it prefers \(c\) to every member of \(D\setminus\{c\}\). Intersecting the corresponding intervals therefore gives an interval, possibly empty. The singleton case is explicitly handled.
Strict complete rankings ensure that each type chooses exactly one remaining candidate. Consequently, the nonempty vote intervals partition the type order, and each candidate labels at most one block.
The removal of zero-score added candidates is also justified: positivity of every mass means such a candidate is chosen by no type. Removing any or all of these candidates preserves each type’s existing highest-ranked candidate.
The comparisons at indices \(h\) and \(h+1\) exhibit one change in the relative order of \(x,y\). A contrary comparison earlier or later would require an additional change.
Thus the claimed comparisons hold throughout their respective sides of the boundary. In particular, \(x\succ_1 y\). The index restrictions ensure both boundary types exist.
This is the central structural step, and it is valid.
At every consecutive boundary, Lemma 2 gives \(c_i\succ_1 c_{i+1}\). Transitivity in the first strict ranking therefore orders all labels strictly and excludes repeated labels, including nonconsecutive repetitions.
For a type \(t\in I_i\):
Together these comparisons cover every other candidate in \(D=C\cup\{c_1,\ldots,c_s\}\). Hence the proposed label is indeed the highest-ranked remaining candidate at every type in its block.
The lemma also correctly accounts for mandatory candidates receiving zero votes. They remain present and are included in Condition 1.
The vertex conditions correctly enforce:
Ordinary arcs join consecutive intervals and enforce precisely the boundary conditions of Lemma 3. Their ending indices strictly increase, so the graph is acyclic.
A source-to-sink path starts at index \(1\), joins intervals without gaps or overlaps, and ends at index \(\tau\). It therefore covers every type.
Since no non-\(p\) vertex intersects the guessed interval, a covering path must contain the vertex \((p,\ell,r)\). This argument remains valid when the guessed interval touches either endpoint or covers the entire support.
Applying Lemma 3 to an accepted path establishes both the actual vote blocks and the distinctness of their candidate labels.
Distinctness is essential here: it makes the sum of vertex costs equal to the number of selected candidates in \(A\). Thus the budget test correctly enforces \(|S|\le K\le k\).
Candidate \(p\) has scaled score \(q>0\). Each other path label has score strictly below \(q\), while every remaining candidate outside the path has score zero.
Therefore the accepted action makes \(p\) the strict plurality winner.
After removing zero-score additions from a successful action, all remaining additions label nonempty vote blocks.
The preferred candidate has positive score: total score is positive, scores are nonnegative, and a strict winner cannot have score zero. Lemma 1 therefore supplies a nonempty interval that the algorithm enumerates.
Every actual block satisfies the vertex conditions because its label is highest-ranked among all remaining candidates, including all mandatory candidates. Strict victory supplies the required strict weight inequalities.
At each actual boundary, the two adjacent types prefer their respective winning labels to the other label. These are exactly the required arc comparisons.
The resulting source-to-sink path has cost equal to the number of remaining additions, which is at most both \(k\) and \(|A|\). The algorithm therefore accepts every successful instance.
The vertex bound is correct. At boundary \(h\), there are at most \(mh\) predecessor vertices and \(m(\tau-h)\) successor vertices. The stated arc count follows from
\[
\sum_{h=1}^{\tau-1}h(\tau-h)=\frac{\tau(\tau-1)(\tau+1)}{6}.
\]
Thus each guessed interval produces a graph with polynomially many vertices and arcs. A minimum-cost path in a directed acyclic graph can be computed by processing vertices in topological order; the construction satisfies the needed acyclicity hypothesis.
The product \(Q\) has bit length bounded by the sum of denominator bit lengths, hence by \(O(L)\). Positivity and \(\sum_t w_t=Q\) bound every weight and prefix weight sum by \(Q\). Exact multiplication, division, subtraction, and comparison therefore operate on polynomially bounded integers.
The distinction between elementary operations and bit operations is explicitly addressed. Prefix failure counts, ranking positions, graph indices, and path costs also have polynomially bounded representations.
The algorithm does not iterate up to \(k\), a denominator, or a scaled mass. Its polynomial bound therefore meets the requested dependence on \(m,\tau,L,\min\{k,|A|\}\).
The supplied construction handles \(\tau=1\), \(A=\varnothing\), \(k=0\), \(k>|A|\), and \(C=\{p\}\). Positive normalized masses imply \(\tau\ge1\), while \(p\in C\) ensures a nonempty remaining candidate set.
The literature attribution is accurate: [Magiera and Faliszewski, Theorem 3](https://link.springer.com/article/10.1007/s10458-016-9339-3) states polynomial-time solvability for constructive plurality control by adding or deleting candidates in single-crossing elections; the paper uses the unique-winner model. The submitted rational-mass proof is independent of that theorem.
No repair feedback is necessary.
⟨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.