| paper | d4-conf-ijcai-2007-0221 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-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: 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\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
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.
Types are complete misrepresentation-cost profiles \(t\), each carrying rational mass \(w_t\). Choose \(k\) candidates and assign each type’s mass to them, minimizing total mass-weighted misrepresentation; Monroe imposes a \(1/k\) mass quota per winner, while Chamberlin–Courant does not.
The mirror covers winner determination in Monroe and Chamberlin–Courant, including Theorem 5 and Proposition 6. It leaves the manipulation and control results in Propositions 1–4 aside.
My lead anchor is Theorem 5, proved in this paper. It says that WINNER-DETERMINATION is NP-complete in both Monroe’s and Chamberlin–Courant’s schemes, even when every misrepresentation value is binary. The decision problem takes voters, candidates, a number \(k\) of winners, values \(\mu_{vc}\in\{0,1\}\), and a threshold \(t\); it asks whether some size-\(k\) committee has an assignment of voters to its members with total misrepresentation at most \(t\). Chamberlin–Courant places no balance restriction on that assignment. Monroe requires a balanced assignment; in the paper’s divisible-\(n/k\) case, each winner represents exactly \(n/k\) voters. The paper proves the result by reduction from MAX \(k\)-COVER, though it omits the reduction details.
A useful secondary anchor is Proposition 6, also proved here: when \(k=O(1)\), WINNER-DETERMINATION is in P for both schemes. The paper enumerates committees and computes the best assignment for each; for Monroe, it gives a polynomial procedure for finding the best balanced assignment when \(k\) is fixed.
I would mirror these with Mass Winner Determination. An instance consists of a candidate set \(C\), a number \(k\), a listed support \(T\) of \(\tau\) types, positive rational masses \(w_t\) summing to \(1\), binary misrepresentation costs \(d(t,c)\in\{0,1\}\), a threshold \(B\), and a scheme \(R\in\{\mathrm{CC},\mathrm{Monroe}\}\). A type is its full vector of costs to the candidates: two people share a type exactly when the problem treats them identically.
The question is whether there exist a committee \(S\subseteq C\), \(|S|=k\), and nonnegative assigned masses \(x_{tc}\) for \(t\in T\), \(c\in S\), such that
\[ \sum_{c\in S}x_{tc}=w_t \quad\text{for every }t, \qquad \sum_{t\in T}\sum_{c\in S}d(t,c)x_{tc}\le B. \]
For CC there are no further constraints. For Monroe, require \(\sum_{t\in T}x_{tc}=1/k\) for every \(c\in S\). A yes-instance has the committee and assignment as a witness; optimizing the same objective gives the minimum-misrepresentation committee.
This is a plausible regime for large associations or civic bodies choosing representatives: millions of members may share a much smaller set of stable preference or representation-cost profiles. The mass \(x_{tc}\) is a portion of a type group assigned to a representative; it need not mean an individual receives a fractional representative. Monroe’s \(1/k\) quota is the natural per-capita version of its balanced assignment. The paper’s formal input is the cost matrix, so the cost vector is a faithful type description; if an application uses ballots as well, the ballot can be included in the type.
For variable \(k\), the continuous problem mirrors Theorem 5 and should be NP-complete for each scheme. A discrete instance with \(n_t\) voters of type \(t\) becomes masses \(w_t=n_t/n\), with threshold \(B=t/n\). In CC, each type can be assigned to its cheapest selected candidate, preserving the discrete objective. In Monroe, take \(n\) divisible by \(k\): scaling each mass assignment by \(n\) gives a transportation problem with integer row totals \(n_t\) and column totals \(n/k\). Its constraint matrix is totally unimodular, so fractional assignments do not create a cheaper optimum than an integral discrete assignment. Thus the hardness comes from selecting the committee, not from counting individual voters. The problem is in NP because a committee and a polynomial-bit rational allocation witness can be checked in polynomial time.
For fixed \(k\), Fixed-\(k\) Mass Winner Determination is in P, mirroring Proposition 6. Enumerate the \(\binom{m}{k}\) committees and, for each, find the best assignment: directly for CC and with a transportation LP for Monroe. For constant \(k\), this takes time polynomial in \(m,\tau\), and the input bit length \(L\). Here \(\tau\) remains an input parameter and may grow; the claim is not hardness at fixed support.
The mirror covers winner determination in Monroe and Chamberlin–Courant, including the paper’s fixed-\(k\) result. It does not try to continuize the paper’s manipulation or control results. Further questions include whether useful approximation guarantees hold for minimum misrepresentation under rational masses, and what algorithms become possible when both \(k\) and \(\tau\) are restricted.
The weak point is that this is a very close rational-clone formulation: it gives no new tractability result, and its hardness largely carries over intact. Its positive case is a faithful Class B mirror. The paper studies committee selection over voter assignments, and selecting the committee retains the hard combinatorics even after the electorate is represented by type masses.
The strongest case against this mirror is that its continuum may add almost nothing to the computational question. Given rational masses, choose a common denominator \(D\) and clone each type into \(kD\,w_t\) voters. For Monroe, each winner then has quota \(D\). The assignment problem is a transportation problem with integer margins, so it has an integral optimum; for Chamberlin–Courant, each type can simply go to its cheapest selected candidate. Thus the continuous optimum is exactly the cloned election’s optimum, divided by the population size.
That makes Theorem 5’s mirror look like weighted committee selection over cost profiles, while Proposition 6 becomes enumeration of committees followed by a transportation problem. The fractional assignment itself creates no new computational behavior. If the aim were specifically to find cases where continuization changes complexity or unlocks continuous optimization, this would be a low-yield example.
But that does not defeat either anchor under this programme’s criteria. Exact agreement with a discrete problem is an allowed result, and identifying the clone correspondence is itself part of the programme’s dictionary. A rational-mass input can also represent a huge electorate compactly, with \(\tau\) shared cost profiles; that is a sensible high-multiplicity regime. The proposed civic-body scenario is plausible, and enlarging types to include underlying preference rankings only strengthens it. Monroe’s balanced allocation remains meaningful in that setting.
So I cannot make a convincing case that these anchors fail. Proposition 6 is a valid fixed-\(k\) question, and Theorem 5 supports a well-posed Class B mirror. The negative case is limited to saying that this mirror may offer less new algorithmic structure than the programme’s most rewarding examples; that is a priority concern, not a reason to reject it.
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.