Answer: Polynomial-time solvable in \(m,\tau,k,L\) on each of the four promised domains.
Corollary 2 — class: algorithmic
Given candidates \(C\), committee size \(k\), finite voter types \(\Theta\), rational masses \(\mu_\theta\), and a promised restricted-domain witness, output a committee \(W\subseteq C\) with \(\lvert W\rvert=k\) such that no mass vector \(\lambda\) with \(0\leq\lambda_\theta\leq\mu_\theta\) and no candidate set \(B\subseteq C\) with \(\lvert B\rvert\leq k\sum_\theta\lambda_\theta\) satisfies that every type with \(\lambda_\theta>0\) lexicographically prefers \(B\) to \(W\).
Input: candidates \(C\), with \(m=|C|\), and an integer \(1\leq k\leq m\). A society is given by its support: the list \(\Theta\) of \(\tau\geq1\) types with positive masses \(\mu_\theta\) encoded as binary rationals, with \(\sum_\theta\mu_\theta=1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length.
Each type supplies preferences and a promised domain label with a witnessing linear order: either approval preferences that are voter-interval or candidate-interval, or strict rankings that are single-peaked or single-crossing. The witness orders types for voter-interval and single-crossing, and candidates for candidate-interval and single-peaked.
For approval preferences, each type has a nonempty approved set \(A_\theta\subseteq C\), ranked above its complement, with indifference within each set. Voter-interval means each candidate's approving types form an interval in the supplied type order; candidate-interval means each \(A_\theta\) forms an interval in the supplied candidate order.
Let \(P_{\theta,1},\ldots,P_{\theta,d_\theta}\) be the preference indifference classes, best first. Type \(\theta\) strictly prefers \(B\) to \(W\) when the first unequal coordinate of \((|B\cap P_{\theta,j}|)_{j=1}^{d_\theta}\) and \((|W\cap P_{\theta,j}|)_{j=1}^{d_\theta}\) is larger for \(B\); equal vectors imply indifference.
Output a committee \(W\subseteq C\), \(|W|=k\), for which no real mass vector \(\lambda\) with \(0\leq\lambda_\theta\leq\mu_\theta\) and \(\sum_\theta\lambda_\theta>0\), and no set \(B\subseteq C\) with \(|B|\leq k\sum_\theta\lambda_\theta\), make every type with \(\lambda_\theta>0\) strictly prefer \(B\) to \(W\).
Is this committee-search problem solvable in polynomial time in \(m,\tau,k,L\), or is it NP-hard?
For finite, explicitly listed voters, core committees exist and can be computed in polynomial time on all four domains. Fractional-committee results also concern finite voters; they do not establish complexity for binary-rational mass input with integral committees. [Source](https://arxiv.org/pdf/2108.01987)
No result settling the exact mass-input search problem was located.
The problem is polynomial-time solvable in \(m,\tau,k,L\) on each of the four promised domains.
I interpret the promise at the profile level: the society belongs to one of the four domains and comes with its witnessing order. This is the interpretation corresponding to the finite-voter result in the question.
The proof has two ingredients: an exact equivalence between mass blocking and finite-voter blocking, and a polynomial-time simulation of the finite algorithm using blocks of identical voters. The replicated election is used only in the correctness proof; it is never explicitly constructed.
Fix a committee \(W\) of size \(k\). For a set \(B\subseteq C\), define
\[ S_B(W)=\{\theta\in\Theta:\theta\text{ strictly prefers }B\text{ to }W\}, \qquad M_B(W)=\sum_{\theta\in S_B(W)}\mu_\theta. \]
Here and below, mathematical displays are written using inline delimiters:
\(\displaystyle S_B(W)=\{\theta\in\Theta:\theta\text{ strictly prefers }B\text{ to }W\},\qquad M_B(W)=\sum_{\theta\in S_B(W)}\mu_\theta.\)
Lemma 1. A nonempty set \(B\) blocks \(W\) precisely when
\(\displaystyle |B|\leq kM_B(W).\)
Proof. If \(B\) and \(\lambda\) block \(W\), every type with positive \(\lambda_\theta\) belongs to \(S_B(W)\). Consequently,
\(\displaystyle |B|\leq k\sum_\theta\lambda_\theta\leq k\sum_{\theta\in S_B(W)}\mu_\theta=kM_B(W).\)
Conversely, suppose that \(B\neq\varnothing\) and this inequality holds. Set \(\lambda_\theta=\mu_\theta\) for \(\theta\in S_B(W)\), and set \(\lambda_\theta=0\) otherwise. Its total mass is positive because \(kM_B(W)\geq |B|>0\). This vector and \(B\) satisfy every blocking condition. \(\square\)
The empty set cannot block: every type strictly prefers the nonempty committee \(W\) to the empty set. Moreover, a blocking set has size at most \(k\), since the total available mass is one.
Thus \(W\) is in the required core exactly when, for every \(B\) with \(1\leq |B|\leq k\),
\(\displaystyle kM_B(W)<|B|.\)
This equivalence includes equality at the budget threshold.
Write the input masses as \(\mu_\theta=a_\theta/b_\theta\), with positive integer denominators. Define
\(\displaystyle D=\prod_{\theta\in\Theta}b_\theta,\qquad n=kD,\qquad r_\theta=n\mu_\theta=k a_\theta(D/b_\theta).\)
Every \(r_\theta\) is a positive integer, and
\(\displaystyle \sum_\theta r_\theta=n,\qquad Q:=n/k=D.\)
Consider, conceptually, an election containing \(r_\theta\) identical copies of type \(\theta\).
Lemma 2. A committee belongs to the mass-input core if and only if it belongs to the ordinary finite-voter core of this replicated election.
Proof. For a fixed \(B\), the number of replicated voters strictly preferring \(B\) to \(W\) is
\(\displaystyle \sum_{\theta\in S_B(W)}r_\theta=nM_B(W).\)
A finite blocking coalition exists precisely when the coalition consisting of all these improving voters can afford \(B\). Indeed, any blocking coalition is a subset of these voters, and enlarging it preserves strict improvement and increases its budget. Its affordability condition is
\(\displaystyle |B|\leq k\,\frac{nM_B(W)}n=kM_B(W).\)
By Lemma 1, this is exactly the mass blocking condition. \(\square\)
The replicated election may contain exponentially many voters. Its numerical parameters nevertheless have polynomial bit length:
\(\displaystyle \log D=\sum_\theta\log b_\theta=O(L),\qquad \log n=O(L+\log k).\)
The remaining issue is therefore computational: simulate a suitable finite algorithm without iterating over its voters.
I use the following finite correctness result.
Finite algorithm theorem. Suppose \(Q=n/k\) is integral. Process voters in order, assigning each to her most preferred candidate with fewer than \(Q\) assignments. Break approval ties by the candidate order. Let \(F\) contain candidates receiving \(Q\) assignments. Delete \(F\) and their assigned voters. In the residual order, select the assigned representatives at positions \(1,Q+1,\ldots,(k-|F|-1)Q+1\), and add \(F\).
This returns a size-\(k\) core committee for approval profiles with a linearly consistent order, and for strict recursive single-top-crossing profiles; in the strict case, reorder the residual voters into a single-top-crossing order. This is the integral formulation of CommitteeCore, justified by Theorems 2–3 of [Pierczyński and Skowron](https://arxiv.org/pdf/2108.01987).
I now verify that the orders needed by this theorem can be obtained from the supplied witnesses without examining individual copies.
The required linear-consistency condition is the following. If voter \(i\) precedes voter \(j\), candidate \(a\) precedes candidate \(b\), \(j\) approves \(a\), and \(i\) approves \(b\), then \(i\) approves \(a\).
For voter-interval preferences, retain the supplied type order. Order candidates by the position of their first approving type, earliest first; put never-approved candidates last, and break ties consistently.
To verify the condition, let \(f(c)\) be the first approving position of \(c\). Under its premises,
\(\displaystyle f(a)\leq f(b)\leq i<j.\)
Candidate \(a\) is approved at both \(f(a)\) and \(j\). Its approving positions form an interval, so it is approved at \(i\).
For candidate-interval preferences, retain the supplied candidate order and order types by their leftmost approved candidate, earliest first. Write each approved interval as \([\ell_i,u_i]\) in candidate positions. Under the linear-consistency premises,
\(\displaystyle \ell_i\leq\ell_j\leq\operatorname{pos}(a)<\operatorname{pos}(b)\leq u_i.\)
Hence \(a\) belongs to \(i\)'s approved interval.
These conditions remain valid when each type is replaced by a contiguous block of identical copies. For two copies of the same type, the implication holds because their approved sets coincide.
An ordered strict profile is single-top-crossing when, for voters \(i<j<h\), writing \(p_j\) for \(j\)'s top candidate,
\(\displaystyle a\succ_i p_j\quad\Longrightarrow\quad p_j\succ_h a.\)
For single-crossing preferences, use the supplied type order. If the premise holds, the comparison between \(a\) and \(p_j\) has changed between \(i\) and \(j\), because \(p_j\succ_j a\). It cannot change again. Thus the conclusion holds. Deleting candidates or voters preserves single-crossingness.
For single-peaked preferences, order types by their peaks along the supplied candidate axis. Let their peaks satisfy \(p_i\leq p_j\leq p_h\). If \(a\succ_i p_j\), then \(a\) must lie strictly left of \(p_j\): a candidate to its right would be farther along the decreasing right side of \(i\)'s ranking. Since \(a<p_j\leq p_h\), single-peakedness gives \(p_j\succ_h a\).
Candidate deletion preserves single-peakedness. One way to verify this is through the no-valley characterization: no candidate can be ranked below two candidates flanking it on the axis. This property is inherited by restriction and implies monotonicity on both sides of the restricted top candidate. Consequently, after any candidate deletion, sorting the remaining types by their new peaks again gives a single-top-crossing order.
Thus both strict domains satisfy the recursive hypothesis. Replacing types by contiguous identical copies preserves these arguments.
We now simulate the finite algorithm exactly.
For each candidate \(c\), maintain an integer assignment count \(h_c\), initially zero, with capacity \(D\). Process types in the order established above.
For the current type \(\theta\), let \(u\) be its number of unprocessed copies, initially \(r_\theta\). While \(u>0\):
Lemma 3. Each recorded block exactly represents \(t\) consecutive steps of the finite algorithm.
Proof. Throughout these steps the voters have identical preferences. Until candidate \(c\) becomes full, the set of available candidates does not change, so every such voter chooses \(c\). The next change occurs precisely when either its capacity is exhausted or the current type's copies end. The value \(t\) is exactly the smaller of these two distances. \(\square\)
There is always an available candidate while an unprocessed voter remains. Otherwise all \(m\) candidates would already contain \(D\) assignments, requiring \(mD\) processed voters. But the total is \(kD\leq mD\); this cannot occur before processing finishes.
Every block finishes a type or fills a candidate. Each type finishes once, and each candidate fills at most once. Therefore the number of blocks is at most
\(\displaystyle \tau+m.\)
This bound is independent of the numerical value of \(D\).
After the first phase, set
\(\displaystyle F=\{c:h_c=D\},\qquad k_2=k-|F|.\)
Delete every recorded block whose representative lies in \(F\). Each member of \(F\) accounts for exactly \(D\) voters, so the remaining block lengths sum to
\(\displaystyle n_2=n-|F|D=k_2D.\)
For approval and single-crossing profiles, retain the inherited block order.
For single-peaked profiles, sort the residual blocks by their types' peaks on \(C\setminus F\). This sorting implements the required residual voter order.
To check that the recorded representatives remain appropriate in the strict case, consider a residual voter originally assigned to \(c\notin F\). Every candidate ranked above \(c\) was already full when that assignment was made, and therefore belongs to \(F\). Hence \(c\) is this voter's top candidate on \(C\setminus F\). In particular, all residual blocks of the same strict type have the same representative.
If \(k_2=0\), return \(F\). Otherwise, let the residual block lengths be \(t_1,\ldots,t_s\), and define
\(\displaystyle H_0=0,\qquad H_j=\sum_{\ell=1}^{j}t_\ell.\)
For each \(q\in\{0,\ldots,k_2-1\}\), find the unique block \(j\) satisfying
\(\displaystyle H_{j-1}<qD+1\leq H_j,\)
and select its representative. Return these representatives together with \(F\).
The position \(qD+1\) is the exact finite algorithm position. In particular, a position immediately after a block boundary is assigned to the following block.
By Lemma 3, the first phase, deletions, residual ordering, and selected positions all coincide with a permitted execution of the finite algorithm. Its correctness theorem therefore guarantees that the returned set has exactly \(k\) distinct candidates and belongs to the finite-voter core. Lemma 2 then guarantees membership in the required mass-input core.
All assignment counts are at most \(D\), and all block lengths and prefix sums are at most \(n=kD\). Thus every integer used has \(O(L+\log k)\) bits.
The algorithm performs:
Integer multiplication, exact division, addition, and comparison on these bit lengths take polynomial time. Consequently, the complete algorithm runs in polynomial time in \(m,\tau,k,L\).
The binary-rational mass representation therefore preserves polynomial-time committee search on all four domains. The essential additional argument is the polynomial-size exact simulation of CommitteeCore, together with the full-support characterization of blocking.
⟨structured verdict parsed — rendered above⟩
The argument is sound in substance and establishes polynomial-time committee search on all four domains, under the explicitly stated interpretation that the profile as a whole belongs to one promised domain. I found no false step or substantive computational gap. One minor clarification is needed to make the cited theorem’s recursive hypothesis fully explicit.
The prover explicitly adopts a profile-wide domain promise. This is the natural interpretation consistent with the finite-voter result supplied in USER_TASK. The argument does not establish a result for arbitrary mixtures of the four domains.
The cited paper uses the same lexicographic comparison of preference-class counts as the task. Thus there is no mismatch between the committee preferences used in the replication argument and those covered by the finite correctness theorem. See [the paper’s definitions and algorithm](https://arxiv.org/pdf/2108.01987).
Lemma 1 is correct.
For any blocking vector, its positive coordinates must belong to \(S_B(W)\). Consequently, its total mass cannot exceed \(M_B(W)\), giving the claimed necessary inequality.
Conversely, using the full masses of all improving types satisfies the coordinate bounds. For nonempty \(B\), the affordability inequality ensures positive coalition mass. This proves sufficiency without any assumption that coalition coordinates are rational.
The edge cases are handled correctly:
No enumeration of all \(B\) is claimed as an algorithm; this characterization is used for correctness only.
Lemma 2 is correct.
The quantities \(D\), \(n\), and \(r_\theta\) are positive integers with the stated sum and quota. Reduced rational representations are unnecessary.
For each fixed nonempty \(B\), the improving replicated voters number exactly \(nM_B(W)\). Taking all such voters is legitimate: adding improving voters preserves unanimous strict improvement and increases affordability. Therefore finite blocking and mass blocking have exactly the same threshold.
The bit-length calculation is also correct. Multiplying the denominators can produce an exponentially large value, but its binary length is bounded by the sum of their binary lengths. Replication alone would not establish polynomial time; the subsequent compressed simulation addresses that issue.
The description matches the integral CommitteeCore algorithm: capacity-limited representative assignment, removal of full candidates and their represented voters, then selection at quota-spaced residual positions. Approval tie-breaking must use the compatible candidate order, as the prover does. Theorems 2–3 and the accompanying cardinality lemmas supply core membership and exactly \(k\) distinct candidates. [Pierczyński and Skowron, Sections 4–4.2](https://arxiv.org/pdf/2108.01987).
The relevant hypotheses are met:
Minor issue: The prover names “recursive single-top-crossing” without explicitly defining its quantifier over candidate restrictions. Its subsequent verification supplies the needed substance, so this is an expositional omission rather than an unverified theorem application.
Minimum clarification: State that every restriction to a nonempty candidate subset must admit a single-top-crossing voter order, which may depend on that subset.
Both linear-consistency checks are valid.
For voter-interval preferences, the premises ensure that both first-approval positions exist. The displayed inequalities place \(i\) between an approving position of \(a\) and the approving position \(j\), so interval membership gives the conclusion. Never-approved candidates cannot satisfy the relevant approval premises.
For candidate-interval preferences, nonempty approved sets ensure that left endpoints exist. The displayed inequalities place \(a\) inside \(i\)’s approved interval. Equal left endpoints do not invalidate the argument.
Replacing types by contiguous identical copies preserves these conditions, including comparisons between copies of the same type.
The single-crossing implication is correct: the comparison changes before the middle voter and cannot change back afterward. Restrictions preserve this property.
The single-peaked implication is also correct. Under its premise, \(a\) must lie strictly left of the middle peak; monotonicity on the later voter’s left side then gives the conclusion. Equal peaks cause no failure.
The discussion of candidate restriction correctly justifies sorting by the restricted peaks. The no-valley characterization invoked here is equivalent to strict single-peakedness, and restriction preserves its condition.
Lemma 3 and the batch bound are correct.
Within a batch, identical preferences and unchanged availability force the same representative. Its length stops exactly when the current type ends or the selected candidate fills.
Availability is guaranteed by total capacity. Before all voters are processed, all \(m\) capacities cannot already be exhausted because \(k\leq m\).
Every batch exhausts a type or fills a candidate. These events occur at most \(\tau\) and \(m\) times respectively, so the claimed \(\tau+m\) bound is valid.
Deleting full-candidate blocks removes exactly \(|F|D\) voters. The residual mass count and quota are therefore correct.
For strict preferences, every candidate ranked above a surviving representative was already full when that assignment occurred. Such candidates remain full and are removed. Thus surviving representatives are indeed restricted top candidates, making the residual reordering compatible with the finite algorithm.
The prefix-sum inequalities locate the exact residual positions, including positions immediately following a block boundary. Distinctness of selected representatives is legitimately supplied by the cited finite cardinality result.
The case \(k_2=0\) is handled directly, avoiding an undefined residual quota.
All multiplicities, batch lengths, capacities, and position counters have polynomial binary length. The number of batches, candidate scans, sorting operations, and selected positions is polynomial in the stated parameters. Exact arithmetic on these integers therefore yields the claimed polynomial running time.
The prover resolves the intended mass-input search problem. The only requested repair is an explicit definition of the recursive hypothesis; no new mathematical argument 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.