| paper | d4-journals-mss-2008-0038 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 6.2 gives a computational result, but the quota simplex already represents a distribution of party-list vote types, and the theorem operates directly on that real-valued input. The proposed continuous problem therefore restates the paper’s existing model rather than bridging a discrete population to a continuous one.
fails bit b-already — the paper is already native to the continuum
Theorem 6.2 and Corollaries 6.3–6.6 cover separable error minimization and quota-based rounding losses; the paper’s discussion of apportionment properties and paradoxes is not part of this computational mirror.
The cleanest mirror is a large party-list electorate. A type is a voter who casts a list vote for party \(P_j\); \(\mu_j\) is that type’s fraction of the electorate, and \(\tau\) is the number of parties with positive support. In a regime with millions of voters and relatively few active parties, \(\mu\) is a sensible description of the society: voters of the same type are indistinguishable for this problem. The decision remains an integral seat allocation, since seats are indivisible.
My lead anchor is Theorem 6.2, proved in this paper; the authors say a slightly weaker version was announced by Niemeyer and Wolf (1984). It establishes that a decomposable error function \(\psi(\mathbf m)=\sum_j\varphi_j(m_j)\), whose marginal increments \(H_j(\ell)=\varphi_j(\ell)-\varphi_j(\ell-1)\) are increasing, has a minimizing allocation among nonnegative integer vectors summing to \(M\). An allocation \(\mathbf m_0\) is minimal exactly when \(H_j(m_j^0+1)\ge H_k(m_k^0)\) for every pair \(j,k\); strict inequalities across distinct parties give uniqueness. The theorem also proves that MinimalSolution finds all minima by selecting the \(M\) smallest entries from the matrix of marginal costs \(H_j(\ell)\), for \(1\le\ell\le M\).
A precise continuous-population problem mirroring that result is Continuous-Support Separable Apportionment. An instance consists of rational masses \(\mu_1,\ldots,\mu_n\) summing to \(1\), a house size \(M\), and rational penalty functions \(\varphi_j\) on \(\{0,\ldots,M\}\) with nondecreasing marginal increments. Given quotas \(q_j=M\mu_j\), find a vector \(\mathbf m\in\mathbb Z_{\ge0}^n\) with \(\sum_jm_j=M\) minimizing \(\sum_j\varphi_j(m_j)\). The standard squared-quota-error objective, \(\sum_j(m_j-q_j)^2\), is one instance. A solution is an optimal seat vector. This is tractable when marginal costs are supplied explicitly: selecting the \(M\) smallest of the \(nM\) costs takes polynomial time in that input size. With succinct penalties and binary-encoded \(M\), the theorem’s stated algorithm takes time polynomial in \(n\) and \(M\), which is only a pseudopolynomial guarantee; it does not by itself establish polynomial time in \(\log M\).
The authors would likely recognize this as their problem: they already define the quota space using real vectors and require homogeneity, so the allocation depends on vote proportions rather than the electorate’s absolute size. That makes the population interpretation especially plausible, but also exposes my weakest point. For this paper, the continuous mirror is largely already present in its real-quota formulation. It is a strong case that the apportionment optimization is a sensible continuous-population problem, but a weak claim that the paper has left that problem unformulated. The paper supplies no named hardness result to anchor a hardness-transfer question; the further computational question suggested by Theorem 6.2 is whether succinctly represented convex penalties admit an algorithm polynomial in \(n\), \(\log M\), and the rational input bit length.
For Theorem 6.2, the proposed continuous problem is already the paper’s problem in different coordinates. In a party-list election, set \(\mu_j=q_j/M\): the quota simplex \(\mathcal Q\) is exactly the simplex of party-vote type masses. The theorem ranges over real quota vectors and minimizes the same separable penalty over the same integer seat allocations. It therefore already solves the continuous-population version, including the mass inputs in the proposed mirror. Corollaries 6.4–6.6 make the connection explicit for quota-based rounding losses. This is a collision with the paper’s model, not an objection that its outcome is discrete.
A large electorate with a few party-vote types is an especially convincing high-multiplicity regime. But it strengthens the collision: the paper already discards voter identities, uses real proportions as its input, and makes the outcome depend on those proportions. Recasting those proportions as a distribution over ballot types adds no new continuous-population question.
The possible opening is bit complexity. MinimalSolution selects \(M\) marginal costs, so with explicitly tabulated penalties it is polynomial in the table size, while a succinctly represented penalty and binary-encoded \(M\) raise a separate question about dependence on \(\log M\). That could be worthwhile algorithmics, but its difficulty turns on how the penalties are encoded; changing the population representation does not create it. The negative case is strongest for this anchor, though not airtight as a claim that no related project could be valuable: the paper gives an algorithmic characterization, not a full bit-complexity classification.
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.