| paper | On the Computation of Fully Proportional Representation |
| authors | Nadja Betzler, A. Slinko, Johannes Uhlmann |
| venue | JAIR 2013 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 11
statement extracted from the paper’s text layer
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 divisible-population Monroe model: types \(t\) carry mass \(\mu_t\); an integral \(k\)-candidate committee \(W\) is chosen; mass \(x_{t,c}\) is routed from types to winners with supply and quota constraints; and weighted total misrepresentation \(\sum_{t,c}r_t(c)x_{t,c}\) is minimized.
Theorem 11 uses engineered, voter-dependent misrepresentation values, and the continuous reduction still needs an explicit scaling-and-integrality lemma.
fatal: False
The mirrors cover Theorems 4, 8, and 11, while leaving the remaining parameterized classifications, variants, open problems, and non-computational discussion untouched.
The strongest honest positive case is that this paper contains a very natural high-multiplicity version of its winner-determination problems. My lead mirror is a continuous version of Minimax CC-Multiwinner; it preserves the candidates, rankings, Borda misrepresentation, number of winners, and worst-case objective, while making only the population divisible.
A type is a complete voter description: a ranking together with its misrepresentation values and any other parameters used by the problem. A society is \((T,\mu)\), where \(\mu_t\) is the mass of type \(t\). This fits a large electorate containing repeated cohorts of citizens with the same ideological position and candidate evaluations. If there are \(M\) copies of each of \(\tau\) types, then the actual population has \(M\tau\) agents while the continuous input records only \(\tau\) types. The candidates remain discrete, and the winning committee remains an integral set of \(k\) candidates.
My lead problem is Minimax-CC-Multiwinner\(_\infty\). Its input is a finite candidate set \(C\), a finite type set \(T\), rational masses \(\mu_t\), an integer \(k\), and a threshold \(R\). For Borda, type \(t\)'s cost for candidate \(c\) is
\[ r_t(c)=\operatorname{pos}_t(c)-1. \]
A solution consists of a set \(W\subseteq C\) with \(|W|=k\), together with mass transfers \(x_{t,c}\ge 0\), satisfying
\[ \sum_{c\in W}x_{t,c}=\mu_t \]
for every type \(t\). The question is whether all assigned mass can have misrepresentation at most \(R\):
\[ x_{t,c}>0 \Longrightarrow r_t(c)\le R. \]
Equivalently, the optimization version minimizes
\[ \min_{|W|=k}\ \max_{\mu_t>0}\ \min_{c\in W} r_t(c). \]
This is plainly the continuous-population form of CC-Multiwinner: choose \(k\) representatives and assign every member of the society to one of them, minimizing worst misrepresentation. Nothing about the outcome is fractional; only the population assignment is.
The anchor is Theorem 4, proved in this paper. It states, in full, that for the Borda misrepresentation function, Minimax CC-Multiwinner and Minimax M-Multiwinner are solvable in polynomial time when \(R=0\), but are NP-hard for every \(R\ge 1\).
The CC half of that theorem transfers especially cleanly. The paper's reduction for \(R=1\) starts from Hitting Set restricted so that every set has two elements and every element occurs in at most three sets. For each element \(u\), create a candidate \(c_u\). For every set \(F=\{u,v\}\), create a voter type whose top two candidates are \(c_u\) and \(c_v\), in either order, and give that type positive mass. Under Borda, those two candidates have costs \(0\) and \(1\), while every other candidate has cost at least \(2\).
Thus a size-\(k\) committee represents every type with cost at most \(1\) exactly when it intersects every set \(F\). Dividing the voters into mass cohorts changes nothing: if \(W\) hits \(F\), all of type \(F\)'s mass can be assigned to a permissible candidate; if it does not, no positive mass of that type can be represented within the threshold. Hence the continuous problem is Hitting Set. The expected classification is therefore Class B: hardness transfers, and it transfers for a reason located in the candidate-incidence structure rather than in the number of named voters.
A more ambitious second mirror covers Monroe's equal-representation requirement. Call it M-Multiwinner\(_\infty\). The input is \(C,T,\mu,k\), a common single-peaked societal axis when appropriate, a type-level misrepresentation function \(r_t(c)\), and a threshold \(\rho\). A solution consists of \(W\subseteq C\), \(|W|=k\), and mass assignments \(x_{t,c}\ge0\) such that
\[ \sum_{c\in W}x_{t,c}=\mu_t \]
and every selected candidate receives exactly one \(k\)-th of the population:
\[ \sum_t x_{t,c}=\frac1k \qquad(c\in W). \]
The objective is
\[ \sum_{t\in T}\sum_{c\in W} r_t(c)x_{t,c}, \]
and the decision question is whether this is at most \(\rho\). The exact \(1/k\) quota is the natural continuous counterpart of Monroe's \(\lfloor n/k\rfloor/\lceil n/k\rceil\) rule; it is not outcome-space continuization.
The anchor is Theorem 11, proved here. It says that M-Multiwinner is NP-hard even for single-peaked profiles and integer-valued misrepresentation functions whose maximum value is polynomial in the number of candidates; moreover, every winner represents exactly three voters.
The reduction is from restricted Exact 3-Cover. For each element \(e_i\), the construction has one candidate \(e_i\), one forcing voter \(f_i\), and three occurrence voters \(v_i^1,v_i^2,v_i^3\). For every set \(S_j\), it has a candidate \(s_j\). There are \(4n\) voters, \(k=4n/3\), and each winner must represent exactly three voters. The candidate \(e_i\) is the only affordable representative for \(f_i\); it must therefore be selected. Each \(e_i\) then has capacity for exactly two of its three occurrence voters. The remaining occurrence mass must be assigned to selected set candidates, with zero cost precisely when the corresponding element belongs to that set. The target total cost is \(2n^2\).
In the continuous version, give each of the \(4n\) types mass \(1/(4n)\). Each winner has quota \(3/(4n)\), and the normalized threshold is
\[ \rho=\frac{2n^2}{4n}=\frac n2. \]
After rescaling masses so that each type has unit mass, the same capacity argument applies: every \(e_i\) must absorb \(f_i\) and two units of its occurrence mass, leaving exactly one unit per element for the selected set candidates. The \(n/3\) selected set candidates have total capacity \(n\), and zero-cost eligibility follows exactly the set-incidence relation. Reaching the threshold therefore requires an exact cover. Fractional assignment does not obviously destroy the reduction, because a fractional zero-cost flow of total \(n\) through \(n/3\) three-element set candidates already forces every selected set to be full and every element to be covered exactly once.
I would classify this as expected Class B hardness transfer, although it is a less secure anchor than Theorem 4 because the original proof uses a finely tuned, voter-dependent misrepresentation function and needs a careful fractional-flow version of its lower-bound argument.
There is also a clean Class A mirror. Theorem 8, proved in the paper, states that for a single-peaked input profile and an arbitrary misrepresentation function, CC-Multiwinner can be solved in \(O(nm^2)\) time, returning the minimum total misrepresentation for \(k\) winners. Its continuous counterpart is
\[ \min_{|W|=k}\sum_{t\in T}\mu_t\min_{c\in W}r_t(c), \]
with all types single-peaked on a common candidate axis. The paper's dynamic program lifts directly: every sum over voters becomes a weighted sum over types. Thus the running time becomes polynomial in \(\tau\), \(m\), and the encoding length of the masses and costs, rather than in the possibly enormous population size. This is a genuine high-multiplicity algorithmic benefit, not a different voting problem.
The paper's anonymous multiset model makes these mirrors plausible: it already treats voters with identical ballots as interchangeable, while the continuous version additionally makes identical type mass divisible. Existing high-multiplicity work would support this interpretation rather than create a novelty collision. The proposed mirrors do not continuize the committee, the candidate set, or the axioms; they continuize the population and its assignment.
The weakest point is the Monroe mirror based on Theorem 11. Its arbitrary type-dependent costs may be less sociologically natural than common positional misrepresentation, and the fractional extension of the exact-cover reduction should be proved carefully. The lead Minimax-CC mirror survives independently: its Hitting Set equivalence is exact even when type mass can be split.
The strongest negative case is that the proponent’s first anchor is unusually thin. In Minimax CC-Multiwinner, the masses \(\mu_t\) do not affect feasibility or the objective except through whether \(\mu_t>0\). The proposed continuum therefore collapses to the support of the distribution: it is a finite hitting-set problem with types renamed as voter cohorts. It has no genuinely fractional population effect, and no high-multiplicity compression in the hardness construction, since each set in the Hitting Set instance becomes its own type.
That objection does not defeat the anchor, however. A support-based continuum is still a legitimate high-multiplicity winner-determination problem, and the paper’s anonymous multiset model supplies a natural interpretation: arbitrarily large cohorts of voters with identical rankings. Replacing counts by rational masses is not a change of outcome space. The Hitting Set equivalence remains exact, so this is a valid Class B mirror even if it is not the most informative continuous one. Replacing the minimax objective by the paper’s Harsanyi sum would make masses matter directly, yielding an even stronger mirror.
Theorem 11 is also not successfully defeated by saying that fractional assignments destroy the exact-cover reduction. In the proposed instance, after scaling each type to unit mass, every selected candidate has capacity three and every type has supply one. For any fixed committee, the resulting assignment problem is an integral min-cost flow: an optimal fractional assignment has an integral optimum. Thus the continuous relaxation can recover the paper’s assignment structure, and the threshold rescales from \(2n^2\) to \(n/2\). The arbitrary type-dependent misrepresentation values are somewhat engineered, but they are part of the agents’ complete type descriptions; repeated cohorts with those evaluations are admissible under the programme.
Theorem 8 is the hardest anchor to oppose. Its dynamic programme genuinely lifts from voters to types: each occurrence of \(\sum_{v\in V}\) becomes \(\sum_t \mu_t\), producing a weighted objective
\[ \min_{|W|=k}\sum_t \mu_t\min_{c\in W} r_t(c). \]
Single-peaked cohorts with common ideological axes are a natural high-multiplicity regime, and the running time becomes polynomial in the number of distinct types rather than the population size. This is precisely the computational benefit the programme is designed to study.
So the honest negative case is weak. One can show that the minimax CC mirror is mass-insensitive and that the Monroe transfer needs an explicit integrality argument, but neither point establishes that the continuous questions are unworthwhile. All three anchors admit sensible population-continuum formulations; Theorems 4 and 11 support hardness-transfer questions, while Theorem 8 supports a genuine high-multiplicity algorithmic gain. A universal negative verdict cannot be defended against this paper.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.