Answer: Both \(\mathrm{CC}\) and \(\mathrm{Monroe}\) continuous winner-determination problems are \(\mathrm{NP}\)-complete when \(k\) is part of the input, already for \(B=0\).
Theorem 5 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe WINNER-DETERMINATION problem in Monroe’s scheme and in the Chamberlin-Courant scheme is NP-complete, even when the misrepresentation values are binary.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), \(k\), a listed support \(T\) with positive rational masses \(w_t\) summing to \(1\), binary costs \(d(t,c)\), a threshold \(B\), and a scheme \(R\in\{\mathrm{CC},\mathrm{Monroe}\}\), decide whether there are a committee \(S\subseteq C\), \(|S|=k\), and assigned masses \(x_{tc}\ge 0\) such that \(\sum_{c\in S}x_{tc}=w_t\) for each \(t\), and \(\sum_{t\in T,c\in S}d(t,c)x_{tc}\le B\). For Monroe also require \(\sum_{t\in T}x_{tc}=1/k\) for every \(c\in S\); CC has no such quota.
A society is given by its support: a list \(T\) of \(\tau\) types with positive binary rational masses \(w_t\), where \(\sum_{t\in T}w_t=1\). Here \(\tau\) is the support size, not the number of possible types.
The input also contains candidates \(C\), \(m=|C|\ge1\), an integer \(1\le k\le m\), arbitrary misrepresentation costs \(d:T\times C\to\{0,1\}\), a nonnegative binary rational threshold \(B\), and a scheme \(R\in\{\mathrm{CC},\mathrm{Monroe}\}\). Each type is specified by its cost vector; no ranking restrictions apply.
Decide whether there exist a committee \(S\subseteq C\), \(|S|=k\), and divisible assigned masses \(x_{tc}\in\mathbb R_{\ge0}\) for \(t\in T,c\in S\), satisfying \(\sum_{c\in S}x_{tc}=w_t\) for every \(t\) and \(\sum_{t\in T}\sum_{c\in S}d(t,c)x_{tc}\le B\).
For Monroe additionally require \(\sum_{t\in T}x_{tc}=1/k\) for every \(c\in S\); Chamberlin–Courant (CC) imposes no quota. Committee selection is discrete, and feasibility is existential, so no tie-breaking is needed. Let \(L\) denote the total input bit length; state running times in \(m,\tau,k,L\).
For each scheme separately, is this continuous winner-determination problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard, when \(k\) is part of the input?
Discrete winner determination is \(\mathrm{NP}\)-complete for both schemes even with binary costs, and is polynomial-time solvable for constant \(k\) ([Procaccia, Rosenschein and Zohar](https://www.avivz.net/pubs/12/scw_fpr_final.pdf)).
Fractional voter assignments have been studied ([Potthoff and Brams](https://journals.sagepub.com/doi/10.1177/0951692898010002001)); the search identified no complexity classification explicitly covering the normalized rational-support problem stated here.
Both continuous winner-determination problems are \(\mathrm{NP}\)-complete when \(k\) is part of the input. Hardness already holds at threshold \(B=0\). Thus, either problem is polynomial-time solvable only if \(\mathrm P=\mathrm{NP}\).
The proof below handles normalized rational masses, divisible assignments, and support types specified by distinct cost vectors. Rational numbers are understood to have numerators and denominators encoded in binary.
Fix a committee \(S\subseteq C\) with \(|S|=k\).
Define \(a_t=\min_{c\in S}d(t,c)\). Every feasible assignment satisfies
\[ \sum_{c\in S}d(t,c)x_{tc}\ge a_t\sum_{c\in S}x_{tc}=a_tw_t. \]
Equality is attainable by assigning all of type \(t\)'s mass to a candidate attaining the minimum. Consequently, the optimal committee cost is
\[ \operatorname{OPT}_{\mathrm{CC}}(S) =\sum_{t\in T}w_t\min_{c\in S}d(t,c) =\sum_{\substack{t\in T:\\ d(t,c)=1\text{ for all }c\in S}}w_t. \]
Computing this rational sum and comparing it with \(B\) takes polynomial time in \(\tau,k,L\).
Construct a directed network with source \(s\), one vertex for each type, one vertex for each candidate in \(S\), and sink \(z\). Its arcs and capacities are:
Let \(F(S)\) be the maximum flow value. We prove the exact formula
\[ \operatorname{OPT}_{\mathrm{Monroe}}(S)=1-F(S). \]
First, take any feasible Monroe assignment and let \(Z\) be its total mass on zero-cost pairs. Its zero-cost entries form a feasible flow: their type totals are at most \(w_t\), and their candidate totals are at most \(1/k\). Hence \(Z\le F(S)\). Since total assigned mass is \(1\) and costs are binary, the assignment cost is \(1-Z\ge1-F(S)\).
Conversely, take a maximum flow and write \(f_{tc}\) for its type-to-candidate entries, setting \(f_{tc}=0\) on missing arcs. Define residual masses
\[ r_t=w_t-\sum_{c\in S}f_{tc}, \qquad s_c=\frac1k-\sum_{t\in T}f_{tc}. \]
These are nonnegative, and both total \(H=1-F(S)\).
If \(H=0\), the flow itself is a feasible assignment of cost zero. If \(H>0\), extend it by setting
\[ x_{tc}=f_{tc}+\frac{r_ts_c}{H}. \]
The added entries have row totals \(r_t\) and column totals \(s_c\), so this is a feasible Monroe assignment.
Moreover, if \(r_t>0\), \(s_c>0\), and \(d(t,c)=0\), the maximum flow could be increased along \(s\to t\to c\to z\). Indeed, its first and last arcs have positive residual capacity, while \(f_{tc}<w_t\le1\) gives positive residual capacity on the middle arc. This contradicts maximality. Thus every positive added entry has cost \(1\), and the extension has cost exactly \(H=1-F(S)\). The formula follows.
The network has \(\tau+k+2\) vertices and at most \(\tau k+\tau+k\) arcs. Its rational capacities can be scaled to integers of polynomial bit length, so maximum flow is computable in polynomial time.
For either scheme, a certificate need contain only the \(k\) selected candidate indices. The verifier computes the fixed committee's optimal cost as above and compares it with \(B\). Therefore both decision problems belong to \(\mathrm{NP}\); no certificate consisting of arbitrary real assignment entries is needed.
We reduce from the standard \(\mathrm{NP}\)-complete Exact Cover by 3-Sets problem: given a universe \(U\) of size \(3q\), with \(q\ge1\), and a family \(\mathcal A\) of three-element subsets of \(U\), decide whether \(q\) members partition \(U\). This source problem and its complexity are stated in [Felsner's dissertation, Section 2.6](https://page.math.tu-berlin.de/~felsner/Paper/diss.pdf).
Create one candidate \(c_A\) for every \(A\in\mathcal A\), and set \(k=q\) and \(B=0\).
If \(|\mathcal A|<q\), the source instance is necessarily negative. In that case output the fixed negative election with one type of mass \(1\), one candidate, \(k=1\), cost \(1\), and threshold \(0\). This is negative under either scheme. Hence assume \(q\le|\mathcal A|\), ensuring the required condition \(1\le k\le m\).
For each element \(u\in U\), define its binary cost vector by
\[ d_u(c_A)= \begin{cases} 0,&u\in A,\\ 1,&u\notin A. \end{cases} \]
Elements may have identical vectors. To obtain a support with distinct types, partition \(U\) into equivalence classes \(G\) of identical vectors. For each class create one type \(t_G\), with that common cost vector and mass
\[ w_{t_G}=\frac{|G|}{3q}. \]
Every mass is positive, and
\[ \sum_Gw_{t_G}=\frac{|U|}{3q}=1. \]
The support size is \(\tau\le3q\), and each mass has numerator and denominator of bit length \(O(\log q)\). Constructing and grouping the vectors takes polynomial time in the source input size. Thus this is a polynomial reduction to the stated support representation.
Suppose \(\mathcal A'\subseteq\mathcal A\) is an exact cover with \(|\mathcal A'|=q\). Select \(S=\{c_A:A\in\mathcal A'\}\), and define
\[ x_{t_G,c_A}=\frac{|G\cap A|}{3q} \qquad(A\in\mathcal A'). \]
Because the selected sets partition \(U\), the row total for type \(t_G\) is \(|G|/(3q)=w_{t_G}\).
Every positive entry has zero cost: if \(G\cap A\) is nonempty, its elements' common vector has cost zero at \(c_A\). Therefore the total cost is \(0\), establishing CC feasibility.
For Monroe, each selected candidate also receives exactly
\[ \sum_Gx_{t_G,c_A}=\frac{|A|}{3q}=\frac{3}{3q}=\frac1q=\frac1k. \]
Thus the same assignment establishes Monroe feasibility.
Conversely, suppose a committee \(S\) of size \(q\) admits a feasible assignment of cost at most \(B=0\), under either scheme.
All terms in the cost are nonnegative. Consequently, any entry \(x_{t_G,c_A}>0\) must have \(d(t_G,c_A)=0\). Each type has positive mass, so its row constraint guarantees at least one such positive entry. The common cost-vector definition then implies that every element of \(G\) belongs to at least one selected set.
Hence the \(q\) selected triples cover \(U\). Let \(r(u)\) count the selected triples containing \(u\). Coverage gives \(r(u)\ge1\), while
\[ \sum_{u\in U}r(u) =\sum_{c_A\in S}|A| =3q =|U|. \]
These equalities force \(r(u)=1\) for every \(u\): any larger value would make the sum exceed \(|U|\). The selected triples therefore form an exact cover.
This implication uses only the row constraints and zero total cost, so it applies separately to both CC and Monroe. Together with the forward implication, it proves \(\mathrm{NP}\)-hardness for each scheme.
For clarity, the fixed-committee algorithms yield explicit, non-optimized bit bounds.
Write each mass as \(w_t=a_t/b_t\), with positive integer denominator \(b_t\), and define
\[ D=k\prod_{t\in T}b_t. \]
Its bit length is \(O(L)\). Multiplying every Monroe network capacity by \(D\) gives integers: \(Dw_t\), \(D\), and \(D/k\), each of bit length \(O(L)\). Computing these integers takes \(O(L^3)\) bit operations using elementary arithmetic.
The Edmonds–Karp maximum-flow algorithm uses \(O(VE^2)\) elementary graph and arithmetic operations; its capacities here are finite nonnegative integers, as required. See [Edmonds and Karp's original paper](https://ftp.eecs.umich.edu/~pettie/matching/Edmonds-Karp-network-flow.pdf). Additions, comparisons, and residual-capacity updates cost \(O(L)\) bit operations here.
Consequently, exhaustive committee enumeration gives the following valid bounds:
These bounds depend on the listed support size \(\tau\), without expanding rational masses into individual voters. For constant \(k\), \(\binom{m}{k}\le m^k\), so both bounds are polynomial.
Combining the reduction with polynomial verification proves the claimed \(\mathrm{NP}\)-completeness for both schemes.
⟨structured verdict parsed — rendered above⟩
The claimed classification is proved. Both schemes are \(\mathrm{NP}\)-complete when \(k\) is part of the input, already at \(B=0\). I found no major or minor mathematical issues.
Since \(k\ge1\), the minimum \(a_t=\min_{c\in S}d(t,c)\) exists. Nonnegativity of the assignment entries justifies the displayed lower bound, and assigning all of a type’s mass to a minimizing candidate attains it. CC has no column constraints that could obstruct this assignment.
Because costs are binary, the resulting optimum is exactly the total mass of types having no zero-cost candidate in \(S\). Exact rational summation and comparison with \(B\) take polynomial time in the stated encoding.
The zero-cost part of any feasible assignment induces a feasible flow: its row and column totals obey the source and sink capacities. Each type-to-candidate entry is also at most \(w_t\le1\), so the middle-arc capacity is respected. Consequently, \(Z\le F(S)\), and the assignment cost is at least \(1-F(S)\).
For the reverse inequality, flow conservation gives nonnegative residual masses with \(\sum_t r_t=\sum_c s_c=H\). When \(H=0\), every row and column requirement is already satisfied.
When \(H>0\), the displayed extension has precisely the claimed row and column totals. The argument excluding a positive added entry on a zero-cost pair is valid: \(r_t>0\) and \(s_c>0\) leave positive residual capacity on the first and last arcs, and \(f_{tc}<w_t\le1\) leaves positive residual capacity on the middle arc. Increasing flow along this path would contradict maximality.
Thus every positive added entry costs one. Their total mass is \(H\), establishing \(\operatorname{OPT}_{\mathrm{Monroe}}(S)=1-F(S)\) exactly. The division by \(H\) is used only in the explicitly separated case \(H>0\).
A committee is a certificate of polynomial length. Its cardinality and candidate indices can be checked, and the fixed-committee algorithms decide whether an assignment meeting the threshold exists. The argument correctly avoids any need to certify arbitrary real numbers.
The stated X3C problem has an explicitly listed universe of size \(3q\), positive integer \(q\), and three-element sets. The cited source states this formulation and its \(\mathrm{NP}\)-completeness. [Felsner, Section 2.6](https://page.math.tu-berlin.de/~felsner/Paper/diss.pdf)
Setting \(k=q\) is legal whenever \(|\mathcal A|\ge q\). The separate branch for \(|\mathcal A|<q\) correctly maps necessarily negative source instances to a legal election that is negative under both schemes.
Grouping elements with identical cost vectors produces distinct support types. Their masses are positive, sum to one, and have the claimed binary encoding lengths. The number and length of the constructed vectors are polynomial in the explicitly listed source instance. No expansion of rational masses into voters is involved.
An exact cover makes the displayed assignment’s row totals equal to the prescribed type masses.
If \(G\cap A\) is nonempty, the common-vector definition guarantees that the corresponding type has zero cost at \(c_A\). Thus every positive assigned entry has zero cost, proving CC feasibility.
Each selected triple receives mass \(3/(3q)=1/k\), so the same assignment also satisfies every Monroe quota. Merging identical vectors does not invalidate either calculation.
At threshold zero, nonnegativity forces every positive assignment entry onto a zero-cost pair. Positive type masses and the row constraints ensure that each type has such an entry. Because all elements in a type share their incidence vector, every element is covered by a selected triple.
There are exactly \(q\) selected triples. The displayed incidence count is therefore \(3q=|U|\). Coverage gives \(r(u)\ge1\) for every element; equality of the total count forces \(r(u)=1\) throughout. Hence the selected triples form an exact cover.
This argument uses no Monroe-specific assumption, so it establishes the reverse implication separately for both schemes. Fractional assignments introduce no loophole.
The product defining \(D\) has bit length \(O(L)\), since the denominator encoding lengths contribute to the total input length. It clears both the mass denominators and the quota denominator. Every scaled capacity has \(O(L)\) bits.
The claimed \(O(L^3)\) preprocessing bound is a valid conservative bound using elementary integer arithmetic. Flow and residual-capacity values retain \(O(L)\) bits, so the stated arithmetic cost is valid.
The invoked Edmonds–Karp bound, \(O(VE^2)\) graph and arithmetic operations, applies to the finite directed network with nonnegative integer capacities obtained by scaling. The original paper establishes the shortest augmenting path bound underlying this runtime. [Edmonds and Karp](https://ftp.eecs.umich.edu/~pettie/matching/Edmonds-Karp-network-flow.pdf)
Substituting the stated vertex and arc counts yields the displayed Monroe bound. The CC bound likewise covers scanning the selected costs and exact rational arithmetic. Multiplication by \(\binom{m}{k}\) correctly accounts for exhaustive committee enumeration. For constant \(k\), both bounds are polynomial in the specified input parameters.
The output resolves the assigned question for both schemes, including normalized rational support, divisible assignments, discrete committee selection, and binary encoding. No additional mathematical clarification or repair 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.