| paper | Constrained Serial Dictatorships Can Be Fair |
| authors | Sylvain Bouveret, Hugo Gilbert, Jérôme Lang, Guillaume Méroué |
| venue | IJCAI 2025 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Proposition 2
statement extracted from the paper’s text layer
Given rational ranking-type masses \(\mu\in\Delta(T)\) for \(T\subseteq S_m\), per-capita class supplies \(\sigma\in[0,1]^m\), a scoring vector \(s\), and a block bound \(R\), choose a feasible rational \(R\)-block quota schedule \(q:[0,1]\to\{0,\ldots,m\}\). Each type receives at most one copy of each class by greedy picking; if \(b_{t,k}(a)\) is the \(k\) highest-ranked available classes for type \(t\) at inventory \(a\), the induced inventory satisfies \(a_q'(z)=-\sum_{t\in T}\mu_t b_{t,q(z)}(a_q(z))\), and the expected utility is \(u_q(z)=\sum_{t\in T}\mu_t\sum_{g_j\in b_{t,q(z)}(a_q(z))}s_{\operatorname{rank}_t(g_j)}\). Maximize \(\mathrm{USW}_\infty(q)=\int_0^1u_q(z)\,dz\), subject to feasibility and \(\int_0^1q(z)\,dz=\sum_j\sigma_j\).
A high-multiplicity clone model with \(N\mu_t\) agents of ranking type \(t\) and \(N\sigma_j\) copies of item class \(g_j\). The continuous decision variables are block lengths \(z_\ell-z_{\ell-1}\) and quotas \(q_\ell\), with the inventory trajectory \(a_q\) induced by greedy picking; the objective is integrated expected utilitarian welfare, or alternatively the essential-infimum egalitarian welfare.
The proposed mirror is not a literal limit of Proposition 2: its inventory is \(m\)-dimensional and its \(R\)-block representation is an added restriction, so the paper’s scalar \((i,\tau)\) dynamic programme supplies no complexity bound.
fatal: False
The mirror covers population-level analogues of Propositions 1 and 2; it leaves the finite Plackett–Luce oracle results in Propositions 10 and 11, Mallows sampling guarantees, and the experiments without a separate population-complexity interpretation.
There is a credible mirror, though I would present it as a high-multiplicity extension rather than a literal atomless version of the paper. The strongest setting is a large school, housing, or course-allocation market: many agents share one of a small number of complete rankings over item classes, while the supply of item copies scales with the population.
Let \(G=\{g_1,\ldots,g_m\}\) be item classes and \(T\subseteq S_m\) the complete ranking types. The population is \(\mu\in\Delta(T)\). For a scale \(N\), there are \(N\mu_t\) agents of type \(t\), and \(N\sigma_j\) indivisible copies of item class \(g_j\), where \(\sigma\in\mathbb{Q}_{\ge 0}^m\) is the per-capita supply. Agents may receive at most one copy of each class, and a copy ranked \(r\) has score \(s_r\). Thus individual bundles remain integral; only the population and item multiplicities are compressed.
A quota policy is a finite rational step schedule
\[
q(z)=q_\ell\quad\text{for }z\in[z_{\ell-1},z_\ell),
\]
where \(z\in[0,1]\) is serial position, \(q_\ell\in\{0,\ldots,m\}\), \(\sum_\ell(z_\ell-z_{\ell-1})q_\ell=\sum_j\sigma_j\), and the schedule is feasible under greedy picking. The type of each position is drawn from the population mixture \(\mu\); equivalently, finite populations use a uniformly shuffled multiset of \(N\mu_t\) clones.
For a schedule \(q\), let \(a_j(z)\) be the remaining per-capita supply of class \(g_j\). If \(b_{t,k}(a)\) is the integral bundle consisting of the \(k\) highest-ranked available classes for type \(t\), the mean-field depletion equation is
\[
a'(z)=-\sum_{t\in T}\mu_t b_{t,q(z)}(a(z)).
\]
The expected utility at position \(z\) is
\[
u_q(z)=\sum_{t\in T}\mu_t
\sum_{g_j\in b_{t,q(z)}(a(z))}
s_{\operatorname{rank}_t(g_j)}.
\]
My lead problem is therefore:
\[ \textsc{Mass-OptSD-}\mathrm{USW}_\infty \]
Given \(\mu,\sigma,s\), and a bound \(R\) on the number of quota blocks, find a feasible \(R\)-block schedule \(q\) maximizing
\[
\mathrm{USW}_\infty(q)=\int_0^1u_q(z)\,dz.
\]
This mirrors Proposition 2, proved in the paper: under prefix independence, \(\mathrm{OptSD}\text{-}\Psi\text{-U}\) is solvable in \(O(nm^2K(n,m,s))\) time. The correspondence is quite close. The original dynamic-programming state \((i,\tau)\)—current picker and number of previously allocated goods—becomes the continuous state \((z,\alpha)\), where \(\alpha\) is cumulative per-capita consumption. Under IC or Plackett–Luce, the local reward depends only on the current quota and \(\alpha\), not on the identities of earlier pickers. I would expect this mirror to be Class A, via a continuous dynamic program or event-based shortest-path formulation. Propositions 10 and 11 provide supporting pricing results for Plackett–Luce: the required \(eu(\kappa,\tau)\) values are computable exactly in FPT time in \(m\), and in XP time in the number \(\rho\) of distinct Luce parameters.
A second worthwhile anchor is Proposition 1, also proved here. It states that Algorithm 1 returns an optimal CSD for egalitarian social welfare in \(O(nmK(n,m,s))\), assuming an expected-utility oracle. Its continuous counterpart is:
\[ \textsc{Mass-OptSD-}\mathrm{ESW}_\infty \]
Given the same \(\mu,\sigma,s,R\), find a feasible quota schedule maximizing
\[
\mathrm{ESW}_\infty(q)=\operatorname*{ess\,inf}_{z\in[0,1]}u_q(z).
\]
This is the fairness-first mirror of the paper’s central question: how should priority in a serial dictatorship be compensated by larger quotas later in the sequence? Proposition 1 suggests a density-greedy or water-filling algorithm that repeatedly allocates additional quota to the least well-served mass. I would again expect Class A, but the required compressed implementation is an open question: the finite proof does not by itself show polynomial time in the number of types and the encoding length of rational masses.
The regime is plausible. Think of a university with hundreds of thousands of students, perhaps a few dozen recurring preference rankings, and course-section supplies scaling with enrollment. The authors should recognize the mirror: the mechanism is still a constrained serial dictatorship, agents still greedily pick indivisible goods, quotas still determine the sequence, and welfare is still computed from the same positional scoring vector. The paper’s ex-ante anonymity also makes replacing an IID preference profile by a large exchangeable population especially natural.
The weak point is the replicated-item extension. The original paper has \(m\) individually distinct goods, whereas a nondegenerate population limit needs item supply to scale as well; otherwise almost everybody receives nothing. Copies of course or room classes are a natural scenario, but they are not literally the original finite instance. A second unresolved issue is whether every optimal continuum schedule has a polynomial-size rational block representation. I would state these explicitly. Still, the mirror preserves the source of the paper’s problem—quota design under serial dictatorship—while making the population, rather than the outcome, the continuous object.
The strongest negative case is not that the paper lacks computational anchors: Propositions 1 and 2 are genuine polynomial-time results. It is that the proposed continuation cannot preserve the paper’s computational object without either degenerating or becoming a different problem.
In the paper, \(n\) is the number of serial positions and \(m\) is the fixed number of distinct goods. A CSD is an integer vector
\[
k\in\mathbb{Z}_{\ge 0}^{n},\qquad \sum_{i=1}^{n}k_i=m.
\]
The natural high-multiplicity limit sends \(n\) to infinity while keeping \(m\) fixed. That limit is degenerate. At most \(m\) agents can receive a positive quota, so at least \(n-m\) agents receive utility zero. Consequently,
\[
\mathrm{ESW}_{\Psi}(k)=0
\]
for all sufficiently large \(n\), while normalized utilitarian welfare satisfies
\[
\frac{1}{n}\mathrm{SW}^{U}_{\Psi}(k)
\leq \frac{m s_1}{n}\longrightarrow 0.
\]
In the atomless formulation, \(q(z)=0\) almost everywhere. Unnormalized welfare merely concentrates all value on a measure-zero set of positions; it is not a meaningful population welfare density.
The proponent’s repair—scaling the supply of goods with the population—is sensible as a new model, but it is not a population-only continuization of this paper. The paper has distinct goods with complete rankings over those goods. Replicated course or housing classes introduce copies, ties, capacity constraints, and a new utility model. If copies remain distinct to preserve the paper, the number of goods and the ranking type space grow with the population; there is no fixed finite \(T\) of preference types. If copies are collapsed into classes, the object being studied is no longer the paper’s serial allocation problem.
This defeats the proposed mirror of Proposition 2. The proof there exploits prefix independence: expected utility depends on the integer pair \((\kappa,\tau)\), where \(\tau\) is the number of previously allocated distinct goods. In the replicated-resource model, the relevant state is not a scalar cumulative consumption but the inventory vector
\[
a(z)\in\mathbb{R}^{m}.
\]
The bundle available to a type depends on which classes have been depleted, not merely on how much total mass has been consumed. Thus the finite dynamic programme becomes a hybrid continuous-control problem over an \(m\)-dimensional state. Proposition 2 supplies no algorithm, separation oracle, or complexity bound for that problem.
The restriction to \(R\) quota blocks does not repair this correspondence. The original theorem permits an arbitrary integer quota at every position. Bounding the number of blocks creates a new bounded-change scheduling problem; allowing \(R\) to grow again leaves the output as an arbitrary measurable control whose exact representation is unspecified. The unresolved question of whether an optimum has a polynomial-size rational block representation is not a peripheral technicality: it is part of defining the computational problem.
Proposition 1 fares worse. Algorithm 1 repeatedly gives one indivisible item to one named least-served agent. Its proof relies on finite monotonicity: a candidate with greater egalitarian welfare must dominate the current quota vector coordinatewise. In an atomless limit, an infinitesimal set of positions has no welfare weight, while giving an extra quota to a positive-measure interval changes the inventory and every subsequent agent’s utility. There is no direct “least happy agent” operation and no resulting density-greedy theorem.
Moreover,
\[
\operatorname*{ess\,inf}_{z}u_q(z)
\]
is not unambiguously the paper’s egalitarian objective. It ignores exceptional serial positions, including possible first or last agents, and averages over preference types before taking the infimum. In a fixed high-multiplicity population, a more natural fairness criterion might be
\[
\inf_{\substack{t:\mu_t>0\\z\in[0,1]}}u_{t,q}(z),
\]
but that is a new type-sensitive fairness notion, not the ex-ante ESW used in the paper. Either choice is defensible, but neither is Proposition 1’s continuous limit.
Propositions 10 and 11 do not provide a third surviving anchor. They compute \(eu(\kappa,\tau)\) for a finite Plackett–Luce ranking over distinct goods. They do not address the inventory trajectory, the quota-control representation, or the complexity of optimizing over schedules. In the class-copy model, a Plackett–Luce distribution over classes is a different probabilistic model; in the distinct-copy model, its dimension grows with the population. The FPT and XP statements therefore do not transfer.
The proponent has identified a plausible research project: a mean-field resource-allocation model with replicated item classes, serial priority, and quota-control dynamics. Rational instances could indeed be lifted to large finite clone populations. That is the strongest point for the mirror, and it prevents an airtight impossibility claim. But its interest comes from the added scalable-resource model and the new continuous-control problem, not from continuizing the computational results of this paper. Under a strict ChoCo standard requiring the population to be the continuous object while preserving the source problem, I would reject the mirror; under a permissive extension standard, the verdict is at most a narrow, explicitly re-modelled green.
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.