Answer: \(\mathrm{NP}\)-complete
Theorem 11 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateM-Multiwinner is NP-hard for single-peaked input profiles and an integer- valued misrepresentation function even if the maximum misrepresentation value of every voter is polynomial in the number of candidates (and every winner represents exactly three voters).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), a common societal axis, voter types \(T\) with rational masses \(\mu_t\) summing to \(1\), single-peaked type profiles, misrepresentations \(r_t(c)\), integer \(k\), and threshold \(\rho\), decide whether there exist \(W\subseteq C\) with \(|W|=k\) and \(x_{t,c}\ge 0\) such that \(\sum_{c\in W}x_{t,c}=\mu_t\), \(\sum_{t\in T}x_{t,c}=1/k\) for every \(c\in W\), and \(\sum_{t\in T}\sum_{c\in W}r_t(c)x_{t,c}\le \rho\).
A type profile consists of a finite candidate set \(C\) with a common linear axis \(\prec\), finite types \(T\), and rational masses \(\mu_t\ge 0\) with \(\sum_{t\in T}\mu_t=1\). Each type has a \(\prec\)-single-peaked ranking, and its rational misrepresentation function \(r_t\) is compatible with that ranking.
Given \(k\) and \(\rho\), does there exist \(W\subseteq C\) with \(|W|=k\) and fractional assignments \(x_{t,c}\ge0\) such that \(\sum_{c\in W}x_{t,c}=\mu_t\), \(\sum_{t\in T}x_{t,c}=1/k\) for every \(c\in W\), and \(\sum_{t\in T}\sum_{c\in W}r_t(c)x_{t,c}\le\rho\)?
Target. Is this continuous single-peaked Monroe winner-determination problem solvable in polynomial time, or is it NP-hard?
Known results. The discrete analogue is NP-hard for single-peaked profiles and integer-valued misrepresentation functions, even when every winner represents exactly three voters. That result uses integral voter-to-winner assignments rather than fractional mass assignments.
The problem is \(\mathrm{NP}\)-complete. The stated discrete hardness result transfers because, for a fixed winner set, fractional assignments with integer supply and capacity have an integral optimum.
We use the stated hardness result as a premise and prove the required integrality property explicitly.
1. Integrality of assignments.
Let \(I,J\) be finite sets, with nonnegative integer supplies \(a_i\) and capacities \(b_j\). Suppose a nonnegative real matrix \(y\) satisfies
\( \sum_{j\in J}y_{i,j}=a_i \) and \( \sum_{i\in I}y_{i,j}=b_j \).
For arbitrary real costs \(d_{i,j}\), there exists a nonnegative integer matrix \(z\) with the same margins and with
\( \sum_{i,j}d_{i,j}z_{i,j}\leq\sum_{i,j}d_{i,j}y_{i,j} \).
To prove this, form a bipartite graph on \(I\) and \(J\), including precisely those edges whose matrix entries are noninteger. Every vertex incident to an edge has degree at least two: otherwise its prescribed integer margin would be a sum of integers and exactly one noninteger, which is impossible.
If this graph is nonempty, it therefore contains a cycle. Since the graph is bipartite, the cycle has even length. Alternately increase and decrease the entries around this cycle by a common amount \(\varepsilon\). This preserves every margin. There are two choices of direction, and their changes in cost are opposites, so choose a direction whose cost change is nonpositive.
For each increased entry, consider its distance to the next larger integer; for each decreased entry, consider its distance to the next smaller integer. All these distances are strictly positive. Choose \(\varepsilon\) to be their minimum. No entry becomes negative, at least one becomes integer, and every entry previously integer remains unchanged. Thus the number of noninteger entries strictly decreases without increasing cost.
Repeating finitely many times produces the required integer matrix. This proves the claim.
2. Reduction from the stated discrete hard problem.
Take an instance of the stated \(\mathrm{NP}\)-hard discrete restriction. Write its explicitly listed voters as \(V\), with \(n=|V|=3k\). Its question is whether one can select \(k\) winners and assign each voter to one winner, with exactly three voters per winner and total misrepresentation at most \(B\).
Construct the continuous instance as follows:
All single-peakedness and ranking-compatibility conditions are preserved because neither rankings nor misrepresentation functions change. Distinct type labels may have identical data; alternatively, identical types can be combined by adding their masses.
The construction is polynomial in the explicitly represented discrete input: it introduces one type per voter, and its new rational numbers have polynomial encoding length.
For the forward implication, take a feasible discrete assignment and give mass \(1/n\) from each type to its assigned winner. Every winner receives \(3/n=1/k\), and the continuous cost is the discrete cost divided by \(n\), hence at most \(B/n\).
For the reverse implication, suppose the constructed continuous instance has a feasible committee \(W\) and assignments \(x_{t_v,c}\). Define
\( y_{v,c}=n x_{t_v,c} \).
Then, for every voter and every selected winner, respectively,
\( \sum_{c\in W}y_{v,c}=1 \) and \( \sum_{v\in V}y_{v,c}=n/k=3 \).
Its total cost satisfies
\( \sum_{v\in V}\sum_{c\in W}r_v(c)y_{v,c}\leq B \).
Apply the integrality claim with row margins one, column margins three, and costs \(r_v(c)\). It gives an integer matrix \(z\) with the same margins and cost at most \(B\). Nonnegativity and row sum one imply that every row contains exactly one entry equal to one and all other entries zero. Thus \(z\) assigns each voter to exactly one winner, and every winner receives exactly three voters.
This is a feasible discrete solution. The reduction therefore proves \(\mathrm{NP}\)-hardness.
3. Membership in \(\mathrm{NP}\).
Assume \(1\leq k\leq |C|\), since selecting a committee is impossible when \(k>|C|\), and the stated capacities require positive \(k\).
Write each input mass as \(\mu_t=p_t/q_t\), with positive integer denominator \(q_t\), and choose
\( D=k\prod_{t\in T}q_t \).
Its binary encoding length is polynomial in the input length because
\( \log D=\log k+\sum_{t\in T}\log q_t \).
Suppose the instance is feasible, with committee \(W\) and assignments \(x\). The scaled matrix \(y=Dx\) has integer row margins \(D\mu_t\) and integer column margins \(D/k\). By the integrality claim, there exists an integer matrix \(z\) with these margins and
\( \sum_{t,c}r_t(c)z_{t,c}\leq D\rho \).
Every entry satisfies \(0\leq z_{t,c}\leq D\), since the sum of all entries is \(D\). Consequently, \(W\) and the integers \(z_{t,c}\) form a polynomial-size certificate. A verifier checks nonnegativity, all margins, and the cost inequality using exact rational arithmetic in polynomial time. Conversely, any certificate passing these checks yields a feasible assignment \(x=z/D\).
Thus the problem belongs to \(\mathrm{NP}\), completing the proof of \(\mathrm{NP}\)-completeness.
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the target: the continuous problem is \(\mathrm{NP}\)-complete, using the discrete hardness result supplied in USER_TASK as a premise. No major or minor issues were found.
The rounding argument is valid for arbitrary real costs and any feasible matrix with nonnegative integer margins.
The argument establishes existence; it need not provide a polynomial-time rounding algorithm for either subsequent use.
The reduction uses precisely the supplied discrete restriction: explicitly listed voters, integer-valued compatible misrepresentation functions, single-peaked rankings, and exactly three voters assigned to each selected winner. Thus \(\lvert V\rvert=n=3k\).
Creating one type per voter with mass \(\mu_{t_v}=1/n\) gives nonnegative rational masses summing to one. Retaining the rankings, axis, and costs preserves all the structural restrictions. Separate type labels with identical data are permitted by the stated definition, so the optional aggregation remark is unnecessary to the reduction.
The output size is polynomial: the voter data are copied, and the rational quantities \(1/n\) and \(B/n\) have polynomial encoding length.
Replacing each discrete assignment by mass \(1/n\) satisfies every type’s supply constraint. Each winner receives \(3/n=1/k\), exactly the required capacity. The total cost is divided by \(n\), so a discrete cost at most \(B\) yields continuous cost at most \(\rho=B/n\).
All feasibility conditions are checked correctly.
For a feasible continuous assignment, scaling by \(n\) yields row margins \(1\), column margins \(3\), and total cost at most \(B\).
These are exactly the hypotheses of the proved integrality claim. Its application preserves the chosen committee and produces a nonnegative integer matrix of no greater cost. An integer row with sum one has exactly one entry equal to one and all other entries zero. Column sums of three therefore give exactly three voters per winner.
This establishes both directions of the reduction. Fractional assignments do not introduce additional yes-instances on the constructed inputs.
The denominator choice \(D=k\prod_{t\in T}q_t\) is valid. Each \(q_t\) divides \(D\), and \(k\) divides \(D\), so both \(D\mu_t\) and \(D/k\) are integers. The binary length of \(D\) is polynomial in the input length, even though its numerical value may be large.
Applying the integrality claim to \(Dx\) gives an integer certificate satisfying the scaled margins and cost bound. Its entries sum to \(D\), so nonnegativity implies that every entry is at most \(D\). There are at most \(\lvert T\rvert\lvert C\rvert\) entries, each with polynomial binary length.
Checking the committee size, margins, nonnegativity, and rational cost inequality requires polynomial-time exact arithmetic. Dividing a valid certificate by \(D\) recovers a feasible continuous assignment, proving certificate soundness as well as completeness.
Zero-mass types cause no difficulty: their rows must be zero throughout. The write-up correctly handles \(k>\lvert C\rvert\) as infeasible and identifies positive \(k\) as necessary for the expression \(1/k\) to be defined. No additional domain assumption affects the reduction or certificate argument.
No repair or 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.