| paper | d4-conf-ecai-2025-0651 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathsf{NP}\)-hard under polynomial-time Turing reductions, already for \(m=\tau=2\) and \(\mu_1=\mu_2=\tfrac12\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 3
statement extracted from the paper’s text layer
Given \(m\) party-choice types with rational masses \(\mu_p>0\), \(\sum_p\mu_p=1\), and a fixed full-supply slate of indivisible seats with binary-encoded positive integer weights \(w_1\ge\cdots\ge w_k\), let \(\omega=\sum_t w_t\), \(q(p)=\omega\mu_p\), and \(\ell_o(p)=\max\{\sum_{t\in S}w_t:S\subseteq[k],\ |S|\le\lfloor k\mu_p\rfloor,\ \sum_{t\in S}w_t\le q(p)\}\). Find an assignment \(\sigma:[k]\to[m]\) such that \(\sum_{t:\sigma(t)=p}w_t\ge\ell_o(p)\) for every \(p\), whenever such an assignment exists.
The electorate is a rational mass distribution over party-choice types; party \(p\) has mass \(\mu_p\). The fixed weighted seats remain indivisible, and the decision is whether an assignment can meet every party’s obtainable weighted lower quota.
Every rational mass vector has a polynomial-size common-denominator encoding as the paper’s vote vector, so this may be a normalization of the source model rather than a distinct population regime.
fatal: False
The mirror covers Proposition 3’s WLQo assignment hardness; it leaves the other quota results, method guarantees, house-monotonicity results, and Bundestag case study outside its scope.
The strongest mirror is Continuous WLQo Assignment, anchored on Proposition 3. That proposition is proved in this paper: it says that if a polynomial-time algorithm can find a seat assignment satisfying WLQo whenever one exists, then \(P=NP\), even with only two parties. The proof reduces from PARTITION.
In the mirror, a type is a voter’s chosen party. A society is a rational distribution \(\mu\) over \(m\) parties, with \(\mu_p>0\) and \(\sum_p\mu_p=1\). For a fixed slate of \(k\) indivisible seats with positive integer weights \(w_1\ge\cdots\ge w_k\), let \(\omega=\sum_t w_t\). Party \(p\)’s mass is its vote share, and its quota is \(q(p)=\omega\mu_p\). Assume each party has enough members to fill the slate.
Here is the precise problem. Define
\[
\ell_o(p)=\max\left\{\sum_{t\in S}w_t:
S\subseteq[k],\ |S|\le\lfloor k\mu_p\rfloor,\
\sum_{t\in S}w_t\le\omega\mu_p\right\}.
\]
An assignment is a map \(\sigma:[k]\to[m]\), giving each seat to one party; its representation for \(p\) is
\[
R_p(\sigma)=\sum_{t:\sigma(t)=p}w_t.
\]
Given \(\mu\) and the weighted slate, find an assignment whenever one exists such that \(R_p(\sigma)\ge\ell_o(p)\) for every party. The objective is feasibility: produce such an assignment. This is a question about the underlying allocation problem, not an encoding.
The regime is a large electorate with many voters but few party-choice types: for example, millions of voters distributed over a small number of parties, with parties assigned a fixed slate of roles whose values differ. Mass means the fraction supporting each party. The number of agents can be vastly larger than the number of types; in the mirror, only the rational masses need to be given. This is a credible high-multiplicity regime for apportionment, and the authors should recognize the quota and allocation question as theirs. The weighted seats remain indivisible, as in the paper.
I expect this mirror to be hardness-transferring (Class B). The Proposition 3 reduction already uses just two parties with equal mass, \(\mu=(1/2,1/2)\), and takes the PARTITION numbers as seat weights. Its combinatorics are in the weighted slate, not in the number of voters, so replacing vote counts with masses does not remove the reduction. A polynomial-time algorithm for the mirror would imply \(P=NP\). This anchor covers the paper’s WLQo allocation-computation result; it does not extend the claim to the paper’s other axiomatic findings.
The weak point is also the main limitation: because the paper’s quotas already depend on vote shares, and rational mass profiles correspond to finite vote-count profiles after choosing a common denominator, this mirror may add no new computational behavior. It is a sensible continuous-population formulation, but a modest case for a new complexity landscape: here, continuization faithfully preserves the hardness rather than making the problem easier.
The strongest case against this anchor is a model collision. Proposition 3 already takes the electorate as an aggregate vote vector \(v\), not as a list of named voters. For every paper instance, set \(\mu_p=v_p/n\). Then \(q(p)=\omega\mu_p\), the seat-count bound is \(\lfloor k\mu_p\rfloor\), and the obtainable quota \(\ell_o(p)\) and feasible assignments are exactly the same. Conversely, any rational \(\mu\) in the proposed mirror can be converted to integer vote counts by taking a common denominator. The conversion preserves the problem and has polynomial-size encodings in both directions.
That makes the proposed mirror a change of units, not a new continuous-population version of Proposition 3. The paper already aggregates voters by party, and its allocation rule uses only those aggregate shares. A larger electorate, or a richer story about its voters, does not change the instance the theorem sees. Refining voter types by geography or other traits also adds nothing unless those traits affect the allocation rule; if they do, the result is no longer a mirror of Proposition 3.
This objection is about whether the mirror introduces a distinct model, not whether it would have the same complexity answer. Its weakness is that the programme may still value a continuous formulation as a clean way to state apportionment. And the electorate-share interpretation is plainly sensible. So I can make a credible case against this being worthwhile *as a new ChoCo mirror*, but not an airtight case that no scenario or reformulation of the paper deserves study.
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.