Answer: \(\mathrm{NP}\)-hard
Theorem 11 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFinding a set of winners under αB-ℓ1-Monroe voting rule is NP-hard, even for single-crossing elections. The proof of this theorem is somewhat involved. We first need the following two lemmas.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), parliament size \(k\), and a rational distribution \(\mu=(\mu_1,\ldots,\mu_\tau)\) over complete ranking types \(t_1,\ldots,t_\tau\), ordered so that for every candidate pair \(a,b\), the types preferring \(a\) to \(b\) form a prefix, choose \(S\subseteq C\) with \(|S|=k\) and masses \(x_{i,c}\ge 0\) satisfying \(x_{i,c}=0\) for \(c\notin S\), \(\sum_{c\in S}x_{i,c}=\mu_i\), and \(\sum_i x_{i,c}=1/k\) for each \(c\in S\), minimizing \(\sum_i\sum_{c\in S}x_{i,c}\alpha_B(\operatorname{pos}_{t_i}(c))\); output an optimal parliament and allocation.
Given a candidate set \(C\) with \(m\geq 1\) and an integer \(1\leq k\leq m\), a society is given by its support: \(\tau\geq 1\) distinct strict complete ranking types \(t_1,\ldots,t_\tau\), each with positive binary rational mass \(\mu_i\), where \(\sum_i\mu_i=1\). Here \(\tau\) is the support size, not the number of possible rankings; \(L\) is the total input bit length.
The supplied type order witnesses single-crossing: for every pair \(a,b\) with \(a\succ_{t_1}b\), the indices \(i\) satisfying \(a\succ_{t_i}b\) form a prefix.
A feasible solution consists of \(S\subseteq C\), \(|S|=k\), and divisible allocations \(x_{i,c}\in\mathbb{R}_{\geq0}\) satisfying \(x_{i,c}=0\) for \(c\notin S\), \(\sum_{c\in C}x_{i,c}=\mu_i\), and \(\sum_i x_{i,c}=1/k\) for every \(c\in S\).
Minimize \(D(S,x)=\sum_i\sum_{c\in S}x_{i,c}\alpha_B(\operatorname{pos}_{t_i}(c))\), where \(\alpha_B\) is Borda dissatisfaction and positions are measured in the full ranking over \(C\). Return any optimal parliament and allocation.
Is this continuous utilitarian Monroe problem solvable exactly in polynomial time in \(m,\tau,k,L\), or is it NP-hard?
Discrete utilitarian Monroe winner determination with Borda dissatisfaction is NP-hard even for single-crossing electorates. [Source](https://arxiv.org/pdf/1307.1252)
No result settling the exact continuous problem specified above was located in the literature search.
The specified continuous utilitarian Monroe problem is \(\mathrm{NP}\)-hard. Consequently, an exact algorithm polynomial in \(m,\tau,k,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
The key is that the cited discrete hardness construction satisfies an additional property: its number of voters is divisible by its committee size. On those instances, allowing divisible allocations does not improve the optimal value, even after identical rankings are merged into distinct support types.
Lemma. Let \(p_1,\ldots,p_\tau\) and \(q\) be positive integers satisfying \(\sum_i p_i=kq\). Fix a committee \(S\) of size \(k\) and real costs \(d_{i,c}\). The optimization problem
\[ \min \sum_{i=1}^{\tau}\sum_{c\in S}d_{i,c}y_{i,c} \]
subject to
\[ y_{i,c}\geq 0,\qquad \sum_{c\in S}y_{i,c}=p_i,\qquad \sum_{i=1}^{\tau}y_{i,c}=q \]
has an integral optimal solution.
Proof. The feasible set is nonempty: assigning \(y_{i,c}=p_i/k\) satisfies every constraint. It is closed and bounded, since every variable lies between zero and \(p_i\). Therefore an optimum exists. Choose an optimum \(y\) with the fewest positive entries.
Form a bipartite graph whose vertices are the types and committee members, with an edge wherever \(y_{i,c}>0\). Suppose this graph contains a cycle. Its length is even. Add \(\varepsilon\) and subtract \(\varepsilon\) alternately around the cycle. This preserves every row sum and column sum.
Both signs of sufficiently small \(\varepsilon\) are feasible. Since the objective is linear and \(y\) is optimal, the coefficient of \(\varepsilon\) must be zero; otherwise one sign would improve the objective. Thus every feasible perturbation in this direction preserves optimality. Taking positive \(\varepsilon\) equal to the smallest entry on a subtracting edge removes at least one positive entry and introduces none. This contradicts the choice of \(y\).
The support graph is therefore a forest. In any component containing an edge, take a leaf. Its unique incident edge has value equal to that vertex’s prescribed sum, which is an integer. Delete the leaf and its edge, subtracting this integer from the neighboring vertex’s prescribed sum. All remaining prescribed sums remain integers. Repeating this argument proves that every positive entry is integral. \(\square\)
Consider an explicit discrete electorate with \(N\) voters, committee size \(K\), and \(K\mid N\). Put \(q=N/K\). Suppose its distinct ranking types are \(t_1,\ldots,t_\tau\), with multiplicities \(n_1,\ldots,n_\tau\).
Construct a continuous instance on the same candidates and with the same committee size by assigning
\[ \mu_i=\frac{n_i}{N}. \]
Fix any committee \(S\) of size \(K\), and define
\[ d_{i,c}=\operatorname{pos}_{t_i}(c)-1. \]
Positions here are in the original full rankings; no candidates are removed.
Scale a continuous allocation by setting \(y_{i,c}=Nx_{i,c}\). Its constraints become
\[ \sum_{c\in S}y_{i,c}=n_i,\qquad \sum_i y_{i,c}=\frac{N}{K}=q,\qquad y_{i,c}\geq 0. \]
Furthermore,
\[ N D(S,x)=\sum_i\sum_{c\in S}d_{i,c}y_{i,c}. \]
By the lemma, this scaled problem has an integral optimum.
An integral feasible \(y\) gives a discrete Monroe assignment: for each type \(i\), partition its \(n_i\) voters into groups of sizes \(y_{i,c}\), assigning each group to its corresponding candidate. Each voter receives exactly one representative, and each elected candidate receives exactly \(q\) voters.
Conversely, every discrete Monroe assignment yields an integral feasible \(y\) by counting assignments within each ranking type. Its dissatisfaction is precisely the scaled objective above.
Thus, writing \(F_{\mathrm{disc}}(S)\) and \(F_{\mathrm{cont}}(S)\) for the respective optimal values with committee \(S\), we obtain
\[ F_{\mathrm{cont}}(S)=\frac{F_{\mathrm{disc}}(S)}{N} \qquad\text{for every }S\text{ with }|S|=K. \]
Taking minima over committees shows that the two problems have exactly the same optimal committees. This conclusion applies to any continuous optimal committee, regardless of whether the allocation returned with it is integral.
Suppose the explicit voter order witnesses single-crossing.
First, every ranking type occurs in one contiguous block. Indeed, suppose voters at indices \(r<s\) have identical rankings. For any pair of candidates, its relative order can change at most once along the voter order. Since its order agrees at both endpoints, it agrees throughout the interval from \(r\) to \(s\). Applying this to every pair shows that all intermediate voters have the same ranking.
Replace each such block by its ranking type and assign that type its multiplicity divided by \(N\). The resulting types are distinct, their masses are positive rational numbers summing to one, and their order witnesses single-crossing: a prefix of voters preferring one candidate to another becomes a prefix of ranking blocks.
This compression is polynomial-time. There are at most \(N\) types, and each mass \(n_i/N\) has binary encoding length \(O(\log N)\). Hence the continuous input has bit length polynomial in the explicit discrete input length. The reduction never expands a binary-encoded population.
We use the established discrete hardness theorem: finding a utilitarian Borda Monroe winning committee is \(\mathrm{NP}\)-hard on single-crossing electorates. The required divisibility follows from the construction proving Theorem 11. [Skowron, Yu, Faliszewski and Elkind, Theorem 11 and its construction, pp. 10–11](https://arxiv.org/pdf/1307.1252).
Here is the count explicitly. Write \(m_0,n_0,k_0\) for the source parameters and \(q_0=n_0/k_0\), which is an integer. Let \(a,b\) be the sizes of the auxiliary candidate collections underlying voter blocks \(V_2,V_5\), and put \(r=a+b\). Besides these candidates, the construction has \(m_0-k_0\) candidates in \(H\) and \(m_0\) original candidates. Its committee size is therefore
\[ K=r+m_0. \]
The five voter blocks have sizes
\[ (m_0-k_0)q_0,\quad a(q_0+1),\quad m_0,\quad n_0,\quad b(q_0+1). \]
Consequently their total is
\[ N=(m_0-k_0)q_0+r(q_0+1)+m_0+n_0 =(r+m_0)(q_0+1)=K(q_0+1). \]
Thus \(K\mid N\). This count strengthens the cited hardness statement to the divisible subfamily needed here.
Take an instance from that \(\mathrm{NP}\)-hard discrete subfamily. Merge identical rankings and give each resulting type mass \(n_i/N\). Sections 2 and 3 prove that this is a valid instance of the specified continuous problem, computable in polynomial time, and that its optimal committees are precisely the discrete optimal committees.
Therefore, an exact polynomial-time algorithm returning any optimal continuous parliament and allocation would return a discrete optimal parliament on an \(\mathrm{NP}\)-hard family. This proves the claimed hardness.
The argument uses integrality only after fixing a committee. It does not relax committee selection. Divisible representation therefore preserves the combinatorial difficulty of choosing the winners.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The integrality argument is valid, the compression preserves the required single-crossing order, and the cited hardness construction does satisfy the divisibility condition needed for the reduction. I found no major or minor issues requiring repair.
Every hypothesis used in the argument is sufficient:
The cycle argument is correct. Every cycle in the bipartite support graph has even length, so alternating perturbations preserve all prescribed sums. Because every cycle edge is positive, sufficiently small perturbations of either sign are feasible. Optimality forces the objective’s directional coefficient to vanish.
The larger perturbation used to eliminate an edge remains feasible: subtracting the smallest value on a subtracting edge makes at least one such entry zero and makes none negative. All adding edges were already positive. Thus the perturbation reduces the number of positive entries while preserving optimality, giving the stated contradiction.
The leaf elimination argument is also valid. A leaf’s unique positive incident edge equals its current prescribed sum. Initially these sums are integers; deleting an edge of integer value leaves integer residual sums. Induction therefore proves integrality of every positive entry. Isolated vertices require no argument. The reasoning also covers committees of size one.
Finding: The lemma is fully established.
The scaling \(y_{i,c}=Nx_{i,c}\) is a bijection between the continuous feasible allocations and the displayed transportation feasible set. Its column sums equal the positive integer \(q=N/K\), so the integrality lemma applies.
The objective identity is exact because Borda dissatisfaction is \(d_{i,c}=\operatorname{pos}_{t_i}(c)-1\), measured in the unchanged full rankings.
Both assignment correspondences are valid:
Every elected candidate receives exactly \(q\) voters. The correspondence therefore respects discrete Monroe’s capacity requirement on divisible electorates.
Consequently, the claimed identity \(F_{\mathrm{cont}}(S)=F_{\mathrm{disc}}(S)/N\) holds for every committee. Multiplication by the same positive constant preserves all comparisons and ties, so the sets of optimal committees coincide.
Finding: The equivalence includes every optimal continuous committee; it does not require the returned continuous allocation itself to be integral.
The contiguity argument is correct. For each candidate pair, single-crossing permits at most one reversal. If two endpoint rankings agree, that pair cannot reverse between them and subsequently return. Applying this argument to every pair forces all intermediate rankings to agree with the endpoints.
Thus each distinct ranking occupies one block. Replacing blocks by their types preserves the prefix condition in the task, including pairs whose relative order never changes.
The resulting masses \(n_i/N\) are positive, sum to one, and have binary rational descriptions of length \(O(\log N)\). The number of types is at most \(N\). Since the source electorate is explicit, compression and the resulting input size are polynomial in its input length.
Finding: All support, encoding, and order requirements are satisfied.
The cited Theorem 11 concerns precisely utilitarian Monroe winner determination with Borda dissatisfaction on single-crossing elections. Its proof starts from a hard family with \(k_0\mid n_0\) and constructs an explicitly ordered electorate in polynomial time. [Source, Theorem 11 and its construction](https://arxiv.org/pdf/1307.1252).
The auxiliary collections counted by \(a,b\) exhaust the auxiliary candidates outside \(H\). The source specifies committee size as the total candidate count minus \(m_0-k_0\), giving \(K=r+m_0\). Its five block sizes match those reported by the prover. Using \(n_0=k_0q_0\), the displayed sum simplifies exactly to \(N=(r+m_0)(q_0+1)=K(q_0+1)\). [Source, construction on PDF pages 11–12](https://arxiv.org/pdf/1307.1252).
Finding: The required divisibility is verified for the outputs of the cited hardness reduction, rather than inferred from hardness on unrestricted single-crossing instances.
The reduction preserves the candidates, committee size, full-ranking costs, and optimal committees while producing a valid continuous input of polynomial size.
An algorithm returning any optimal continuous parliament would therefore return an optimal discrete parliament on the verified hard family. No recovery of an integral allocation is needed for this conclusion.
The prover establishes the requested hardness classification. It does not claim completeness or membership in a decision complexity class, and neither is necessary to answer the task.
Repair feedback: None required.
⟨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.