| paper | Mathematical aspects of degressive proportionality |
| authors | Wojciech Słomczyński, K. Życzkowski |
| venue | MSS 2012 |
| filed under | voting · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | no |
The paper’s numbered results are mathematical characterizations of allocation functions, not algorithms, hardness results, approximation guarantees, or computational formulations used to compute. The proposed LP is a coherent new high-multiplicity design problem, but it is introduced by the proponent rather than supplied as a computational result of this paper. Thus the required computational anchor is absent.
fails bit a — no named computational result to mirror
No named result in the paper supplies a computational problem to mirror; the proposed LP changes the paper’s deterministic rounding and common-family model into a mass-splitting feasibility problem.
fatal: True
The candidate mirror covers allocation-function constraints and the total-seat condition, but leaves aside the paper’s named one-parameter families, deterministic rounding analysis, and European Parliament comparisons.
The honest verdict is that this paper has no qualifying computational anchor. Its numbered results are mathematical characterizations of allocation functions, not statements that a problem is in P, NP-hard, FPT, approximable, or otherwise computationally classified. The algorithmic remarks in Section 5 and the complexity-relevant results cited from other papers are not results proved here. Under the programme’s strict anchor rule, there is therefore no fully compliant positive case.
There is nevertheless a credible conditional mirror.
The lead problem would be Continuous Degressive Apportionment Design. A type is a member state or administrative unit characterized by its population \(t_j\), together with any common eligibility and seat-bound parameters. The society is a rational distribution \(\mu=(\mu_1,\ldots,\mu_\tau)\) over types \(t_1<\cdots<t_\tau\), where \(\mu_j\) is the fraction of units of type \(t_j\). The intended regime is a federation with thousands of municipalities, districts, or local governments but only a small number of repeated population/institutional types, so \(N\gg\tau\).
Let \(p=t_1\), \(P=t_\tau\), and let \(m,M\) be the minimum and maximum seats per unit. Given a target seat density \(\sigma=S/N\), the problem is:
Find a continuous allocation function \(A:[p,P]\to[m,M]\) with \(A(p)=m\), \(A(P)=M\), \(A\) non-decreasing, and \(A(t)/t\) non-increasing, such that
\[ > \sum_{j=1}^{\tau}\mu_j A(t_j)=\sigma. > \]
Each unit must still receive an integral number of seats: if \(y_{j,q}\) is the mass of type \(t_j\) receiving \(q\in\{m,\ldots,M\}\) seats, require
\[ > \sum_q y_{j,q}=\mu_j,\qquad > \sum_q qy_{j,q}=\mu_j A(t_j). > \]
Thus the continuous object is the population of administrative units, not the seat bundles. Fractional \(A(t_j)\) values are type-level averages induced by splitting an atomless mass of otherwise identical units among integral seat counts. This is the natural high-multiplicity analogue of the paper’s equation
\[
\sum_i [A_d(p_i)]=S.
\]
For an optimization version, one could minimize weighted deviation from a status-quo allocation \(b_j\),
\[
\sum_j \mu_j\lvert A(t_j)-b_j\rvert,
\]
but the faithful core is the exact-total feasibility/search problem, since that is what the paper actually studies.
The strongest mathematical support is Proposition 1, proved in the paper. It states that \(A\) is an allocation function if and only if
\[
\frac{A(s)}{A(t)}\le \max\left(1,\frac{s}{t}\right),
\]
or equivalently
\[
\min\left(1,\frac{s}{t}\right)\le \frac{A(s)}{A(t)}
\]
for every \(s,t\in[p,P]\). On the finite support, this becomes the pair of linear inequalities, for every \(i<j\),
\[
A(t_i)\le A(t_j),
\qquad
t_jA(t_i)\ge t_iA(t_j).
\]
Consequently, the finite-support mirror is an LP in the variables \(a_j=A(t_j)\), with box constraints, endpoint constraints, pairwise monotonicity/degressive-proportionality constraints, and the total-seat equation
\[
\sum_j\mu_j a_j=\sigma.
\]
Proposition 6, also proved here, gives a second structural route. If
\[
L(\ln t)=\ln A(t),
\]
then \(A\) is non-decreasing exactly when \(L'\ge0\), degressively proportional exactly when \(L'\le1\), and an allocation function exactly when
\[
0\le L'\le1.
\]
This lets a finite feasible vector \((a_j)\) be extended between support points by piecewise-linear interpolation in log-log coordinates. The resulting \(A\) is a valid continuous allocation function.
I would expect this mirror to be Class A. Proposition 1 reduces the design problem to polynomially many linear inequalities, and the integer-seat requirement does not restore hardness in the atomless model: any \(a_j\in[m,M]\) can be implemented by splitting type mass between adjacent integral seat counts. Rational \(\mu_j\) and \(\sigma\) also give the expected dictionary back to finite high-multiplicity instances by clearing denominators.
The mirror is not a novelty collision. The paper uses a continuous function \(A\), but its society is still a finite list of \(N\) named member states. Replacing that list by a distribution over repeated state types is a genuine population continuization. It also does not make the outcomes divisible: individual units still receive integral seat bundles.
The weakest point is decisive: this paper never formulates the above as a computational problem and proves no complexity result for it. Moreover, the European Parliament itself has only \(27\) member states, so the paper’s literal setting is not a compelling high-multiplicity regime. The positive case depends on transferring the same apportionment question to a plausible large federation of repeated administrative units. That makes the mirror mathematically natural, but under the stated grading rule it remains a conditional construction, not a paper-anchored computational case.
The negative case is stronger than the proponent admits: this paper has no qualifying computational anchor at all. Its numbered results are characterizations of a class of real functions, not complexity, approximation, parameterized, or algorithmic results. The “simple algorithm” in Section 5 is a construction by integration, and the computational claims in the references are not results proved here. Under ChoCo’s anchor rule, that is decisive: any computational problem proposed for this paper is a new problem inspired by its mathematics, not a continuous mirror of one of its computational results.
Proposition 1 does not change that. It characterizes allocation functions by pairwise inequalities. The proposed LP is algebraically valid, but it is obtained by adding a new feasibility problem to the proposition. It is not a computational question formulated or solved in the paper.
More importantly, the proposed LP changes the paper’s central apportionment object in three linked ways. The paper studies a common allocation function, usually from one of the one-parameter families \(A_d\), followed by a specified rounding operation:
\[
\sum_i [A_d(p_i)]=S.
\]
The proposed mirror instead chooses arbitrary values \(a_j\) satisfying generic monotonicity and degressive-proportionality inequalities, and imposes
\[
\sum_j \mu_j a_j=\sigma.
\]
The variables \(y_{j,q}\) then convexify the integer seat assignment: identical units of type \(t_j\) can receive different numbers of seats, with \(a_j\) merely their average.
That is not a minor formal adjustment. It removes the paper’s substantive discrete object: the interaction between a single rule, deterministic rounding, and a fixed integer chamber size. If identical units must receive the same rounded value, then the proposed fractional \(a_j\) is unavailable and the model reduces to a weighted version of the paper’s original equation. If identical units may be split or randomized, then the model has become an expected-seat or lottery apportionment problem. The individual bundles remain integral, but the defining output of the apportionment rule is now fractional in expectation. That is a new outcome-convexified problem, not the paper’s problem made continuous because of population multiplicity.
The strongest possible repair does not rescue the anchor. One could posit thousands of municipalities with repeated population and institutional types, retain integral seats, and interpret \(y_{j,q}\) as a genuine distribution over otherwise identical municipalities. That is a coherent high-multiplicity model, and I am not objecting merely because the paper itself has only \(27\) member states. Nor would existing high-multiplicity work count against it. The objection is that this repaired model is an externally invented apportionment problem whose main theorem would be “the generic function class has a finite inequality description.” The paper supplies the mathematical ingredients, but not the computational problem or computational contribution.
Proposition 6 is weaker still as an anchor. It says that, after the change of coordinates \(x=\ln t\) and \(L(x)=\ln A(e^x)\), admissibility is the slope condition
\[
0\le L'(x)\le 1.
\]
Piecewise-linear interpolation in log-log coordinates is therefore an extension certificate. But the interpolation occurs between population sizes, not between members of a continuous society. In the proposed finite-support model, only the values \(A(t_j)\) matter; what happens between \(t_j\) and \(t_{j+1}\) has no effect on the population, the seat total, or the objective. Proposition 6 therefore continuizes the allocation function, which was already continuous in the paper, rather than producing a computational continuization of the population.
One could instead use a genuinely continuous density \(\rho(t)\) of unit populations and impose
\[
\int A(t)\rho(t)\,dt=\sigma.
\]
But then the new content is an infinite-dimensional functional-design problem, still with no computational result in the paper to mirror. Alternatively, restricting to the paper’s named families and deterministic rounding gives only
\[
\sum_j\mu_j [A_d(t_j)]=\sigma,
\]
which is just the original finite apportionment equation with repeated entries grouped by multiplicity. The two repairs exhaust the natural options: preserve the paper’s semantics and the continuization adds little; obtain a richer continuous LP by relaxing those semantics and one has changed the problem.
So the honest verdict is not that no imaginable large-federation story exists. One does. The stronger and more relevant conclusion is that no such story yields a worthwhile *computational mirror of this paper*. The paper contributes function theory, numerical comparison, and policy analysis, not a computational result whose high-multiplicity version can enter ChoCo’s complexity landscape. The proposed mirror is mathematically defensible as a new research direction, but it does not survive the programme’s anchor and population-continuization tests.
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.