| paper | Settling the Score: Portioning with Cardinal Preferences |
| authors | Edith Elkind, Matthias Greger, Patrick Lederer, Warut Suksompong, Nicholas J. Teh |
| venue | ECAI 2023 |
| filed under | fairalloc · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: the decision problem belongs to \(\mathrm P\), with running time \((m\tau(L+\log(m\tau)))^{O(1)}\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Proposition A.2
Given \(m\), rational types \(s^1,\ldots,s^\tau\in\Delta^m\), rational masses \(\mu\in\Delta^\tau\), and \(\bar{x}\in\Delta^m\), decide whether there exists \(y\in\Delta^m\) such that \(d_t(y)\le d_t(\bar{x})\) for every \(t\) with \(\mu_t>0\), with strict inequality for at least one such \(t\), where \(d_t(z)=\sum_{j=1}^m|s^t_j-z_j|\).
Finite-support high-multiplicity cardinal portioning with types \(s^t\), masses \(\mu_t\), and allocations in \(\Delta^m\); type-level variables \(y_j,z_{t,j}\) encode Pareto improvements and an LP minimizes \(\sum_t\mu_t\sum_j z_{t,j}\) under \(d_t(y)\le d_t(\bar{x})\).
The opponent notes that Pareto dominance treats a tiny positive-mass type like a large one, so masses mainly determine support; this limits population sensitivity but does not invalidate the high-multiplicity question.
fatal: False
The mirror covers the computational propositions on egalitarian computation and Pareto-optimality checking, while leaving the paper's axiomatic analyses, characterizations, and noncomputational rule comparisons aside.
The strongest positive case is a finite-support high-multiplicity mirror of the paper’s cardinal portioning problem. The paper does not study a continuous population: it takes \(n\) separately indexed agents. Its simplex \(\Delta^m\) is continuous because the outcome is fractional, but that is not the continuization I am proposing. I leave the outcome space exactly as in the paper and replace the finite profile by a distribution over repeated preference types.
A type is an ideal distribution \(s^t\in\Delta^m\). A society is \(\mu\in\Delta^\tau\), where \(\mu_t\) is the fraction of agents with ideal vector \(s^t\). Agents of one type have exactly the same \(\ell_1\) disutility from every outcome. A plausible regime is a large public-budget or conference-time allocation with millions of participants but only tens of recurring preference templates: for example, institutional constituencies or cohorts whose members submit the same ideal split. Thus \(N\) is enormous while \(\tau\) is moderate.
The discrete-to-continuous dictionary is exact for rational profiles. If \(n_t\) agents have type \(t\), set \(\mu_t=n_t/n\). Conversely, any rational \(\mu\) expands into a finite profile by repeating type \(t\) proportionally. This is therefore a high-multiplicity relaxation, not merely an analogy.
My lead anchor is Proposition A.1, proved in this paper. It states that the paper’s egalitarian rule \(\egal{}\) can be computed in polynomial time. The rule chooses \(x\in\Delta^m\) minimizing the largest agent disutility \(\max_i\|s_i-x\|_1\), and then applies leximin tie-breaking to the vector of agent disutilities. The proof first solves an LP minimizing \(\xi\), with variables \(x_j\) and \(z_{i,j}\), subject to \(x\in\Delta^m\), \(z_{i,j}\ge |s_{i,j}-x_j|\), and \(\sum_jz_{i,j}\le\xi\) for every agent. It then uses further LPs to implement the leximin refinement, requiring \(O(n^2)\) LPs.
The corresponding continuous problem is:
\[ \textsc{Egalitarian-Portioning}_{\infty} \]
An instance consists of \(m\), rational type vectors \(s^1,\dots,s^\tau\in\Delta^m\), and a rational society distribution \(\mu\in\Delta^\tau\). Let \(T^+=\{t:\mu_t>0\}\). Find an allocation \(x\in\Delta^m\) minimizing
\[ \max_{t\in T^+} d_t(x), \qquad d_t(x)=\sum_{j=1}^m |s^t_j-x_j|. \]
Any minimizer is a valid solution. If a canonical output is required, one can add a population-level leximin refinement by treating \(\mu_t\) as the multiplicity of type \(t\); the primary computational question is the minimax optimization itself.
This is directly tractable by the compressed LP
\[ \begin{array}{ll} \text{minimize} & \xi\\ \text{subject to} & \sum_j x_j=1,\quad x_j\ge 0,\\ & z_{t,j}\ge s^t_j-x_j,\quad z_{t,j}\ge x_j-s^t_j,\\ & \sum_j z_{t,j}\le \xi \qquad (t\in T^+). \end{array} \]
It has polynomially many variables and constraints in \(m\), \(\tau\), and the encoding length. The expected classification is therefore Class A. The gain is not that the outcome becomes fractional—it already was fractional in the paper—but that repeated agents become one type-level constraint. The paper’s egalitarian question survives intact: every positive-mass type must be protected against excessive disutility.
A second worthwhile anchor is Proposition A.2, also proved in the paper. It states that, given an outcome \(x'\), determining whether \(x'\) is Pareto optimal can be done in polynomial time. The paper constructs an LP minimizing total auxiliary disutility subject to every agent being no worse off than under \(x'\); \(x'\) is Pareto dominated exactly when the optimum is strictly smaller than the disutility of \(x'\).
The continuous counterpart is:
\[ \textsc{Pareto-Check}_{\infty} \]
An instance consists of \(m\), \((s^t,\mu_t)_{t=1}^{\tau}\), and a proposed allocation \(\bar x\in\Delta^m\). Decide whether there exists \(y\in\Delta^m\) such that
\[ d_t(y)\le d_t(\bar x) \quad\text{for every }t\in T^+, \]
with strict inequality for at least one \(t\in T^+\). Such a \(y\) is a genuine continuous-population Pareto improvement: it weakly benefits every positive-mass type and strictly benefits a positive-mass group.
The decision is again in Class A. Let \(D_t=d_t(\bar x)\), and solve
\[ \begin{array}{ll} \text{minimize} & \displaystyle\sum_{t\in T^+}\mu_t\sum_j z_{t,j}\\ \text{subject to} & y\in\Delta^m,\\ & z_{t,j}\ge s^t_j-y_j,\quad z_{t,j}\ge y_j-s^t_j,\\ & \sum_jz_{t,j}\le D_t \qquad (t\in T^+). \end{array} \]
If the optimum is strictly below \(\sum_t\mu_tD_t\), then \(\bar x\) is not Pareto optimal; otherwise it is. The LP is polynomial in \(m\), \(\tau\), and the input precision. For every rational finite profile, this gives exactly the same answer as the paper’s finite-agent Pareto test.
The authors should recognize both mirrors as their problems. The type vectors, candidate set, simplex of allocations, and \(\ell_1\) disutilities are unchanged. What changes is only that the profile is presented as its empirical distribution. This is not a weakened proxy such as averaging away preferences: \(\textsc{Egalitarian-Portioning}_{\infty}\) still protects the worst type, and \(\textsc{Pareto-Check}_{\infty}\) still quantifies over every type with positive population mass.
The weakest point is that this paper contains no hardness anchor. Its named computational results are positive propositions in the appendix, while most of the main theorems concern axioms rather than complexity. Moreover, the egalitarian objective is naturally insensitive to the numerical size of \(\mu_t\): a type with tiny positive mass still matters as much as a large type because \(\egal{}\) is a worst-agent criterion. That is a genuine limitation, though not a modelling error. It reflects the paper’s fairness objective. If one wants population shares to affect the objective, natural follow-ups are weighted utilitarian, quantile, or mass-threshold versions—but those are new questions, not results established by this paper.
Thus the case is a focused one: the paper supplies two proved polynomial anchors whose underlying problems admit faithful finite-support population mirrors, both expected to remain tractable after the high-multiplicity compression.
The strongest negative case is that the proposed lead anchor is not actually a mirror of Proposition A.1 as stated. The paper’s \(\egal{}\) rule is not merely a minimax rule: it lexicographically refines the vector of individual disutilities. The proposed \(\textsc{Egalitarian-Portioning}_{\infty}\) explicitly permits any minimax allocation, so it may return an allocation rejected by the paper’s leximin tie-breaking. The displayed LP therefore mirrors only the first optimization stage.
Repairing this requires defining population leximin carefully. For rational \(\mu\), one can expand \(\mu_t\) into repeated copies and recover the finite rule, but that may be exponentially larger than the binary encoding of \(\mu\). For arbitrary real or nonatomic populations, several inequivalent extensions are possible: lexicographically minimizing the quantile function of disutilities, using essential suprema, or using a weighted leximin refinement. The paper does not select among these. If one simply keeps the minimax objective, the mass values \(\mu_t\) disappear entirely; if one uses a genuinely mass-sensitive refinement, one has introduced a new rule rather than mirrored Proposition A.1.
That is a real defect in the proponent’s formulation, but it does not defeat the repaired mirror. A finite-support, rational, weighted-leximin version is a sensible high-multiplicity problem and is plausibly solvable by a sequence of compressed LPs.
Proposition A.2 is harder to defeat. Grouping identical agents by type gives, exactly,
\[ d_t(y)\le d_t(\bar x)\quad\text{for every }t\text{ with }\mu_t>0, \]
with strict improvement for at least one positive-mass type. The weighted objective
\[ \sum_t \mu_t d_t(y) \]
is simply the finite-agent objective divided by \(n\). Thus the proposed continuous Pareto test is not a loose analogy: for every rational finite profile it is exactly the high-multiplicity version of the paper’s test.
The only available criticism is that the numerical masses do almost no conceptual work. Pareto dominance treats a type of mass \(10^{-100}\) exactly like a type of mass \(0.9\), provided both are positive. A genuinely mass-sensitive variant would need a threshold or welfare criterion, but that would no longer be the paper’s Pareto-optimality result. Still, this is not a valid objection under the programme’s rules: a well-posed high-multiplicity question remains worthwhile even if its answer is a compressed LP.
Nor can the negative case honestly claim that cardinal agents cannot have multiplicity. Exact ideal vectors may be unrealistic as unconstrained private reports, but recurring institutional templates, budget constituencies, or conference cohorts provide plausible repeated types. The paper’s outcome simplex being continuous is not a collision either; the population is still finite in the paper.
So the honest verdict is that the negative case is weak. It can expose that the stated egalitarian mirror drops the leximin part of Proposition A.1, but Proposition A.2 survives essentially intact, and a repaired leximin version is also a defensible high-multiplicity problem. I cannot honestly defend the universal claim that no worthwhile continuous mirror exists.
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.