Answer: Polynomial-time solvable: in \(\mathrm P\), with running time polynomial in \(m,\tau,L\).
Theorem 16 — class: algorithmic
Given alternatives \(C\), a support \(\mathcal B \subseteq 2^C\) of approval types, and positive rational masses \(\mu_A\) summing to \(1\), does there exist a measurable assignment on \([0,1]\) of a type \(A(x)\in\mathcal B\) and a strict ranking \(\succ_x\) that places every member of \(A(x)\) above every alternative outside it, with \(\lambda(\{x:A(x)=A\})=\mu_A\) for each \(A\), such that for every pair \(a,b\in C\), the indicator of \(a\succ_x b\) is monotone in \(x\), in a direction that may depend on the pair?
Let \(C\) be a finite set of \(m\) alternatives. A society is given by its support: a list \(\mathcal B\subseteq 2^C\) of \(\tau\) distinct approval types with positive binary rational masses \(\mu_A\) satisfying \(\sum_{A\in\mathcal B}\mu_A=1\). Here \(\tau\) is the support size, not the number of possible approval types; let \(L\) be the total input bit length. Empty and full approval sets are allowed.
A feasible realization consists of Lebesgue-measurable maps \(x\mapsto A(x)\in\mathcal B\) and \(x\mapsto\succ_x\), where \(\succ_x\) is a strict total ranking of \(C\), such that \(\lambda(\{x\in[0,1]:A(x)=A\})=\mu_A\) for every \(A\in\mathcal B\). At every \(x\), every member of \(A(x)\) must rank above every member of \(C\setminus A(x)\).
For each distinct pair \(a,b\in C\), the function \(x\mapsto\mathbf 1\{a\succ_x b\}\) must be either nondecreasing or nonincreasing on all of \([0,1]\), with the direction chosen separately for each pair. Types may occupy arbitrary measurable sets, and individuals of the same type may receive different rankings.
Is deciding whether a feasible realization exists in \(\mathrm P\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
For a finite list of approval ballots, recognition of the existence of compatible single-crossing strict rankings, and construction of such rankings and a voter axis, are polynomial-time solvable ([Constantinescu and Wattenhofer](https://arxiv.org/pdf/2310.03736)).
No result settling this exact continuous recognition problem was located in the literature search.
The recognition problem is in \(\mathrm P\), with running time polynomial in \(m,\tau,L\). In fact, feasibility depends only on the support \(\mathcal B\): whenever a realization exists, one also exists in which each type occupies one interval and receives one constant ranking.
The key is an exact equivalence with finite recognition on one ballot per support type.
Call an ordering \(A_1,\ldots,A_\tau\) of \(\mathcal B\), together with strict total rankings \(R_1,\ldots,R_\tau\) of \(C\), a finite witness if:
The second condition is precisely finite single-crossing for strict rankings: a binary sequence changes value at most once exactly when it is monotone in one of these two directions.
We prove that a continuous realization exists if and only if a finite witness exists.
Suppose a feasible realization \(x\mapsto(A(x),\succ_x)\) exists.
For each \(A\in\mathcal B\), define \(E_A=\{x\in[0,1]:A(x)=A\}\). Since \(\lambda(E_A)=\mu_A>0\), the set \(E_A\) is nonempty. Choose one point \(x_A\in E_A\).
These selected points are distinct: if \(A\ne B\), then \(E_A\cap E_B=\varnothing\), because \(A(x)\) is a function. Order them as \(x_{A_1}<\cdots<x_{A_\tau}\), and let \(R_i=\succ_{x_{A_i}}\).
Each \(R_i\) is a strict total ranking compatible with \(A_i\), by pointwise compatibility in the continuous realization.
Now fix distinct alternatives \(a,b\). By hypothesis, \(f_{a,b}(x)=\mathbf 1\{a\succ_x b\}\) is nondecreasing or nonincreasing on all of \([0,1]\). Restricting a monotone function to an increasing sequence of points preserves its direction of monotonicity. Consequently, \(\bigl(f_{a,b}(x_{A_i})\bigr)_{i=1}^{\tau}\) is monotone.
Thus the selected rankings and ordered types form a finite witness. This argument allows the original type sets to be arbitrary measurable sets and the original rankings to vary within a type.
Conversely, suppose \(A_1,\ldots,A_\tau\) and \(R_1,\ldots,R_\tau\) form a finite witness.
Set \(s_0=0\) and \(s_i=\sum_{j=1}^{i}\mu_{A_j}\) for \(1\le i\le\tau\). Positivity and normalization give \(0=s_0<s_1<\cdots<s_\tau=1\).
Partition \([0,1]\) into the intervals \(I_i=[s_{i-1},s_i)\) for \(1\le i<\tau\), and \(I_\tau=[s_{\tau-1},1]\). Define \(A(x)=A_i\) and \(\succ_x=R_i\) whenever \(x\in I_i\).
We check every requirement.
Measurability and masses. Both maps are constant on finitely many Borel intervals, hence measurable. Since each support type occurs exactly once, its preimage is its assigned interval, and \(\lambda(I_i)=s_i-s_{i-1}=\mu_{A_i}\). Including the final endpoint does not change this measure.
Pointwise compatibility. Every \(x\in I_i\) receives the compatible pair \(A_i,R_i\), including all interval endpoints.
Pointwise monotonicity. Fix distinct \(a,b\), and write \(v_i=\mathbf 1\{a\succ_{R_i}b\}\). Let \(h(x)\) be the unique interval index containing \(x\). The interval construction makes \(h\) nondecreasing on all of \([0,1]\), and the comparison function is \(v_{h(x)}\).
If \((v_i)\) is nondecreasing, then for every \(x\le y\), we have \(h(x)\le h(y)\) and hence \(v_{h(x)}\le v_{h(y)}\). If \((v_i)\) is nonincreasing, the corresponding inequality reverses. Thus the required monotonicity holds everywhere, including at each boundary.
This proves the equivalence.
Constantinescu and Wattenhofer’s finite recognition theorem gives a polynomial-time algorithm that, for approval ballots over a finite alternative set, constructs compatible single-crossing strict rankings and a voter axis, or correctly reports impossibility. This is Theorem 16 of [*Recovering Single-Crossing Preferences From Approval Ballots*](https://arxiv.org/pdf/2310.03736).
Apply that algorithm to exactly \(\tau\) voters, giving one voter ballot \(A\) for each \(A\in\mathcal B\). Its hypotheses hold: compatibility is exactly the requirement that approved alternatives precede disapproved alternatives. Empty and full ballots impose no comparisons and are allowed as weak orders with one indifference class. If \(m\le1\), feasibility is immediate.
Accept precisely when the finite algorithm accepts. Sections 2 and 3 prove correctness in both directions. The finite instance has an approval matrix of size \(m\tau\), so recognition runs in time polynomial in \(m,\tau,L\). There is no expansion of rational masses into replicated voters.
A continuous witness also has a polynomial-size description. To verify the arithmetic bound, write the masses as \(\mu_A=p_A/q_A\) and use the common denominator \(Q=\prod_{A\in\mathcal B}q_A\). Its bit length is at most one plus the sum of the input denominator bit lengths, hence is \(O(L)\). Each cumulative endpoint has denominator \(Q\) and a numerator between \(0\) and \(Q\). All endpoints can therefore be computed exactly in polynomial time.
Consequently, the stated continuous recognition problem is completely resolved in \(\mathrm P\).
⟨structured verdict parsed — rendered above⟩
The prover’s claim is correct. The continuous problem is equivalent to finite recognition on one ballot per support type, and the cited theorem applies. No mathematical gaps or errors were found.
Restriction to an increasing finite sequence preserves either direction of monotonicity. Thus every pairwise comparison sequence satisfies the finite witness condition. This argument requires neither interval-shaped type sets nor constant rankings within a type. There is no exceptional-point issue: the task explicitly imposes compatibility and monotonicity everywhere.
The resulting maps are measurable because they are constant on finitely many Borel sets. Compatibility holds at every point, including endpoints. The interval-index function is nondecreasing, so composing it with each monotone finite comparison sequence preserves that sequence’s direction of monotonicity everywhere.
The construction also covers \(\tau=1\): the sole interval is \([0,1]\). Normalization rules out \(\tau=0\) for a valid input.
The prover states the invoked theorem sufficiently precisely and verifies its relevant hypotheses. No stronger, unstated variant is needed.
For construction, the proposed common denominator \(Q=\prod_A q_A\) has bit length bounded by one plus the sum of denominator bit lengths. Every cumulative numerator lies between \(0\) and \(Q\), so all endpoints have polynomial-length exact representations and can be computed in polynomial time. The stated treatment of \(m\leq1\) is valid because there are no distinct-alternative comparisons to constrain.
The support-only feasibility claim and the polynomial-size interval realization are both established. No additional clarification is needed.
⟨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.