Answer: \(\mathrm{P}\); decision and construction of inserted blocks, masses, and a witnessing candidate axis take \(O(L+\tau m^2)\) word-RAM time.
Theorem 10 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThere exists an algorithm that given an election E = (C, V ) decides whether it is pre-MRSC, and, if so, constructs an MRSC election E′ = (C, V ′) such that V ⊆V ′, in time O(nm2).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), a rational distribution \(\mu\) over finitely many complete ranking types \(T\subseteq S_m\), and an order of its positive-mass type blocks, decide whether finitely many added ranking blocks with rational masses \(\eta_j>0\) can be inserted without reordering the original blocks so that the resulting measure \(\nu=\mu+\eta\) is single-crossing and minimally rich, meaning \(\sum_{t:\operatorname{top}(t)=c}\nu_t>0\) for every \(c\); if so, construct the blocks, masses, and a witnessing candidate axis.
Let \(C\) be a fixed candidate set with \(|C|=m\geq 1\). A society is given by its support: a list of \(\tau\geq 1\) distinct strict complete ranking types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings. The input also orders these types as indivisible blocks; let \(L\) be the total input bit length.
An extension inserts finitely many blocks with arbitrary strict complete rankings \(r_j\) over \(C\) and binary-rational masses \(\eta_j>0\), including before or after all original blocks, preserving every original block and its relative order. Zero insertions are allowed; repeated rankings are allowed; there is no bound on added mass or number of blocks.
The resulting finite measure is \(\nu_t=\mu_t+\sum_{j:r_j=t}\eta_j\), taking \(\mu_t=0\) outside the original support; it is not renormalized. Single-crossing is required in the resulting block order: every candidate pair changes relative preference at most once. Minimal richness means \(\sum_{t:\operatorname{top}(t)=c}\nu_t>0\) for every \(c\in C\).
A witnessing candidate axis is a linear order of \(C\) with respect to which all original and added rankings are single-peaked.
Is deciding whether such an extension exists in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? In the polynomial-time case, can the inserted blocks, their masses, and a witnessing candidate axis also be constructed in polynomial time? State running times in \(m,\tau,L\).
For finite voter lists, deciding whether an order-preserving minimally rich single-crossing extension exists and constructing one takes \(O(nm^2)\) time, where \(n\) is the number of voters ([Elkind, Faliszewski, and Skowron](https://d-nb.info/1203435991/34)).
No result explicitly treating this rational-mass extension problem was located in the literature search.
The problem is in \(\mathrm{P}\). Both a valid extension and a witnessing candidate axis can be constructed in \(O(L+\tau m^2)\) time under the usual word-RAM accounting.
If \(q\) candidates occur at the top of an original ranking, a successful construction needs only \(m-q\) inserted blocks. Every inserted block can have mass \(1\).
For \(m=1\), zero insertions already suffice. The argument below handles arbitrary \(m\).
For an ordered list \(V\) of strict complete rankings, call \(V\) extendible if it is an order-preserving sublist of a finite, minimally rich, single-crossing list.
We use two results from [Elkind, Faliszewski, and Skowron, *A characterization of the single-peaked single-crossing domain*](https://d-nb.info/1203435991/34):
The ordering in these statements is the supplied voter ordering; it is preserved by the extension.
Write the original blocks, in their supplied order, as \((r_1,\mu_1),\ldots,(r_\tau,\mu_\tau)\). Define the finite ranking list \(V=(r_1,\ldots,r_\tau)\), containing exactly one ranking per original block.
Claim. The rational-mass instance admits the requested extension if and only if \(V\) is extendible.
Proof, forward direction. Suppose a rational-mass extension exists. Erase the masses from every original and inserted block, retaining all rankings and their order. This produces a finite list \(W\) containing \(V\) as an order-preserving sublist.
For any distinct candidates \(a,b\), the relative-preference sequence along \(W\) is exactly the sequence along the extended block order. Consequently, it changes at most once, and \(W\) is single-crossing.
Moreover, all block masses are positive. For each candidate \(c\),
\(\sum_{t:\operatorname{top}(t)=c}\nu_t>0\)
holds exactly when at least one block has a ranking whose top candidate is \(c\). Indeed, the sum is the total mass of those blocks: it is zero when there are none and positive when there is at least one. Thus \(W\) is minimally rich, proving that \(V\) is extendible.
Proof, reverse direction. Suppose \(V\) is extendible, and let \(W\) be a finite minimally rich single-crossing extension. Identify the occurrences in \(W\) corresponding to the original rankings.
Replace each such occurrence of \(r_i\) by the original indivisible block \((r_i,\mu_i)\). Replace every other occurrence by an inserted block with the same ranking and mass \(1\).
This preserves every original block and its relative order. It does not split any block. The number of insertions is finite, and \(1\) is an admissible positive binary-rational mass.
The resulting ranking sequence remains \(W\), so single-crossing holds. Every candidate tops a block of positive mass, so minimal richness holds. Proposition 3 applies because \(W\) is finite, minimally rich, and single-crossing; its first ranking therefore supplies a witnessing single-peaked candidate axis. This proves the claim.
In particular, the numerical values of the positive original masses do not affect feasibility. No denominator clearing or replication of voters is required.
Apply the following procedure:
All hypotheses of Theorem 10 hold: \(V\) is a finite ordered list of strict complete rankings over the same candidate set \(C\). Its list length is \(\tau\), regardless of the masses.
If the algorithm rejects, Section 2 shows that a rational-mass extension would contradict its rejection. If it accepts, Section 2 proves that the constructed blocks satisfy every requested condition, including the existence of the output axis.
The finite construction inserts one ranking for each candidate without an original top-ranked occurrence. Hence it inserts exactly \(m-q\) blocks and produces at most \(\tau+m-q\) blocks in total. Since \(\tau\geq1\), we have \(q\geq1\), so at most \(m-1\) insertions suffice.
Use candidate indices from \(\{1,\ldots,m\}\).
Reading the input costs \(O(L)\). The finite-profile algorithm costs \(O(\tau m^2)\). Writing at most \(m-q\) inserted rankings and the axis costs \(O(m^2)\), which is absorbed by \(O(\tau m^2)\). Each inserted mass has constant encoding length.
Thus both decision and construction take \(O(L+\tau m^2)\) word-RAM time.
Under bit-cost RAM accounting, charging \(O(\log(m+\tau+2))\) for operations on candidate and position indices gives the conservative bound \(O(L+\tau m^2\log(m+\tau+2))\) bit operations. The algorithm performs no arithmetic on the original masses.
With insertion locations encoded as original-list gaps and their order within each gap, the additional witness has bit length \(O(m^2\log(m+1)+m\log(\tau+1))\). An explicit complete extended list, including the original masses, has bit length \(O(L+m^2\log(m+1)+m\log(\tau+1))\).
These bounds are polynomial in the given binary input length and depend on the support size \(\tau\), rather than any population size obtained by expanding the masses.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The reduction preserves every feasibility condition, the cited results apply to the supplied block order, and the construction and complexity bounds are justified. No major or minor issues were found.
I checked the linked paper. Its definition of a sublist preserves voter order, and its definition of single-crossing uses the given voter order. Theorem 10 decides whether an ordered profile admits a minimally rich single-crossing extension and constructs one in \(O(nm^2)\) time. Its construction adds exactly one vote for each candidate lacking an original first-place occurrence. Proposition 3 supplies the first voter’s preference order as a single-peaked axis for every minimally rich single-crossing profile. These match the prover’s uses. [Source: definitions and results in the cited paper](https://d-nb.info/1203435991/34).
The input list \(V\) satisfies the theorem’s hypotheses: it is finite, nonempty, and consists of strict complete rankings over the same candidate set. Taking one ranking per original block makes its length exactly \(\tau\). No hypothesis requires masses, distinct voters’ preferences, or an initially single-crossing profile.
An admissible extension contains finitely many blocks. Erasing their masses therefore produces a finite ranking list containing all original occurrences in their original relative order.
For each candidate pair, erasure preserves the entire relative-preference sequence. Consequently, the requirement of at most one change is preserved exactly.
The minimal-richness equivalence is also correct. Aggregating masses by ranking and then summing over rankings topped by a candidate gives precisely the sum of the masses of blocks topped by that candidate. Because every block has positive mass, this sum is positive exactly when such a block exists. Repeated inserted rankings do not invalidate this reasoning.
Thus every admissible rational-mass extension yields the required finite-profile extension.
Being an order-preserving sublist provides an identification of the original occurrences within the extended list. Restoring each original mass at its corresponding occurrence preserves its ranking, identity, indivisibility, and relative order.
Assigning mass \(1\) to every remaining occurrence is admissible: it is a positive binary-rational number. The task imposes neither normalization after extension nor an upper bound on added mass.
This operation preserves the ranking sequence, hence single-crossing. Minimal richness follows because every candidate tops at least one positive-mass block.
Proposition 3 applies to the resulting finite ranking list, since it is minimally rich and single-crossing. Its first ranking therefore supplies an axis witnessing single-peakedness for every original and inserted ranking. Masses play no role in this property.
Rejection by Theorem 10 rules out a finite-profile extension; the forward implication then rules out an admissible rational-mass extension.
Acceptance produces a finite-profile extension; the reverse implication converts it into the requested blocks and masses and supplies the output axis.
Retaining original occurrence identities is sufficient to implement this conversion. There is no need to clear denominators, expand masses into voters, or split blocks.
If \(q\) distinct candidates top original rankings, exactly \(m-q\) candidates lack such an occurrence. The cited construction inserts exactly one ranking for each of these candidates.
Since the original list is nonempty, \(q\geq1\), giving at most \(m-1\) insertions. If \(q=m\), an accepting instance needs no insertions. If \(m=1\), the original profile already satisfies all requirements, including the unique candidate axis.
Reading the input and retaining its masses costs \(O(L)\). Substituting \(n=\tau\) into the finite-profile bound gives \(O(\tau m^2)\). Writing at most \(m-q\) rankings and one axis costs \(O(m^2)\) word operations, absorbed because \(\tau\geq1\).
The stated bit-cost overhead for candidate, position, and address indices is conservative. No arithmetic on the original rational masses is required.
The additional witness contains at most \(m\) rankings of length \(m\), constant-size inserted masses, insertion-gap information, and an axis. The stated witness-size bounds cover these components; copying the original input adds \(O(L)\).
Under the explicit ranking-list representation in the task, these bounds are polynomial in the binary input length.
Repair feedback: None is required. The output resolves both decision and polynomial-time construction for the specified rational-mass problem.
⟨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.