| paper | Simultaneously Achieving Ex-ante and Ex-post Fairness |
| authors | H. Aziz |
| venue | WINE 2020 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.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: Both the EF1 and SD-EF1 continuous implementation problems are \(\mathrm{NP}\text{-hard}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a finite type set \(T\) with rational masses \(\mu_t\), complete preference and utility types \(u_t\), item categories \(O\), rational supplies \(\sigma_o\) with \(\sum_o \sigma_o=1\), and a rational target incidence \(x\) satisfying \(\sum_o x_{t,o}=\mu_t\) and \(\sum_t x_{t,o}=\sigma_o\), decide whether there is a finite lottery over measurable assignments in which every agent receives one integral item, every realization is EF1 and Pareto optimal (or SD-EF1 and Pareto optimal), and \(\mathbb{E}[x^{B}]=x\).
An atomless population of mass \(1\) is partitioned into finitely many complete types \(T\) with masses \(\mu\), while item categories have per-capita supplies \(\sigma\). Decision variables are measurable integral type-to-bundle masses and lottery weights over complete configurations; feasibility requires exact target incidence \(x\) and EF1 plus Pareto optimality in every realization.
Atomless splitting within a type can realize the same \(x\) without preserving the paper's named-agent marginal semantics, so the exact convex-hull correspondence to finite matchings is not automatic. This limits the bridge and may change the complexity, but it does not eliminate the stated high-multiplicity configuration problem.
fatal: False
The mirror covers the implementation questions in Theorems 2 and 3: EPS with ex-post EF1, and EF1/PO or SD-EF1/PO lottery membership. It leaves the impossibility results in Theorems 4 and 5 and the binary-utility guarantees of Theorem 6 unanchored.
The strongest honest mirror is one that keeps the paper’s central distinction between an ex-ante marginal and an ex-post integral allocation. I would not sell the infinitesimal “eating” process itself as the contribution: that is already continuous in the paper. The continuization is of the population.
Let the population be the atomless interval \(A=[0,1]\), with type map \(\theta:A\to T\). Type \(t\) has mass \(\mu_t\), complete preferences over a finite set \(O\) of item categories, and, where needed, an additive utility vector \(u_t\). Item category \(o\) has per-capita supply \(\sigma_o\). Thus
\[ \sum_{t\in T}\mu_t=1,\qquad \sum_{o\in O}\sigma_o=\rho, \]
where \(\rho\) is the average number of items per agent. Each individual receives an integral bundle \(B(a)\subseteq O\); the supply constraint is
\[ \lambda\bigl(\{a:o\in B(a)\}\bigr)=\sigma_o. \]
This is the high-multiplicity version of the paper’s model: many students, residents, or applicants share one of \(\tau=|T|\) preference-and-utility types, while item categories have many copies. For an \(n\)-agent, \(m\)-item instance, the natural scaling is \(\sigma_o=1/n\), so \(\rho=m/n\). A type-level incidence matrix is
\[ x_{t,o} = \lambda\bigl(\{a:\theta(a)=t,\ o\in B(a)\}\bigr). \]
A lottery over continuum allocations is a finite distribution over measurable integral assignments \(B\). Its ex-ante outcome is the expected incidence matrix \(x\). Thus the object being continuized is genuinely the society: \(x\) is only a marginal of allocations of a population with mass distribution \(\mu\), not the whole model.
My lead anchor is Theorem 3, proved in this paper, although its reduction uses the earlier result of Aziz, Mackenzie, Xia, and Ye. The theorem states:
For \(n\) agents and \(n\) items, checking whether a given random allocation can be implemented by a lottery over EF1 and Pareto-optimal allocations is NP-hard. The same problem remains NP-hard when EF1 is strengthened to SD-EF1.
The corresponding continuous problem is:
\[ \mathsf{HM\mbox{-}PO\mbox{-}EF1\mbox{-}Implementation}. \]
The input is a rational type distribution \(\mu\), rational utilities \(u_t\), item supplies \(\sigma\), and a rational target incidence matrix \(x\) satisfying the population and supply constraints. The question is whether there exists a finite lottery \(\{(\lambda_\ell,B^\ell)\}_\ell\) over measurable integral allocations such that:
\[ x_{t,o} = \sum_\ell \lambda_\ell \lambda\bigl(\{a:\theta(a)=t,\ o\in B^\ell(a)\}\bigr). \]
Pareto optimality means that no measurable reassignment makes almost every agent weakly better off and a positive-measure set strictly better off. A finite solution can be represented by the masses assigned to each type-bundle pair \((t,B)\), so this is a concrete configuration problem rather than an informal appeal to “fractional allocation.”
The exact \(n=m\) specialization has \(\rho=1\) and \(\sigma_o=1/|O|\). Every individual receives one item, so EF1 is essentially automatic; the real question becomes whether a target type-level random assignment lies in the convex hull of Pareto-optimal continuum assignments. That is a feature, not a defect: it isolates the paper’s genuinely hard part, ex-post implementation by efficient deterministic outcomes.
This is plausible in settings such as a very large school or housing allocation market with a small number of preference-and-utility classes and many copies of each seat or housing category. The authors would recognize the question immediately: it is still asking whether a given ex-ante random allocation can be implemented by ex-post fair and efficient integral assignments. The modification is that named agents become repeated types and item counts become per-capita supplies.
My expectation for this anchor is that it is a Class C candidate, with a possible Class B boundary. The finite NP-hardness may dissolve when a type’s mass can be split across several bundles, but Pareto optimality is a global support condition involving incompatible priority structures. The difficulty may therefore survive even after individual multiplicity disappears. If the finite reduction can be reproduced using item-category and preference combinatorics, hardness transfers; if it cannot, the surviving obstruction would be continuum-specific convex-hull membership. I am not claiming Theorem 3 itself proves either conclusion for the continuum model. Its value is that it gives a sharply defined, nontrivial boundary question.
The second anchor is Theorem 2, proved in this paper. It states:
If \(c=\lceil m/n\rceil\), the EPS-Lottery Algorithm runs in time \(O((cn)^4)\) and computes a lottery over at most \((cn)^2\le(m+n)^2\) deterministic EF1 allocations whose ex-ante outcome is the extended probabilistic serial outcome, which is SD-envy-free and SD-efficient.
Its continuous counterpart is:
\[ \mathsf{Cont\mbox{-}EPS\mbox{-}EF1}. \]
Given \((T,\mu)\), item supplies \(\sigma\), and ordinal preferences, add a dummy item category of supply \(c-\rho\), where \(c=\lceil\rho\rceil\). Run the continuum EPS process: agents of type \(t\), having mass \(\mu_t\), consume their most-preferred currently available item at aggregate rate \(\mu_t\), with ties resolved by the EPS flow rule. Let \(x^{\mathrm{EPS}}\) be the resulting type-level incidence matrix.
The problem is to compute a finite-support lottery over measurable integral assignments \(B^\ell\) such that every \(B^\ell\) is EF1 and
\[ \mathbb E[x^{B^\ell}] = x^{\mathrm{EPS}}. \]
After removing dummy items, the resulting marginal must therefore be ex-ante SD-envy-free and SD-efficient. By Carathéodory, one may require support of size at most \(\tau|O|+1\), since only the type-item incidence vector matters.
This is a strong Class A candidate. The EPS outcome itself is an event-driven mass-flow computation over types and items. The remaining implementation question is a configuration or transportation problem over integral EF1 bundles. The paper’s representative-agent construction and Birkhoff decomposition suggest the right proof technology: replace individual representatives by type-mass representatives and solve the resulting finite flow problem. The pricing problem is likely substantially simpler here than in the PO-implementation anchor because the deterministic support only needs EF1, not Pareto optimality.
The regime is natural: a large course-allocation or housing market with millions of agents but perhaps dozens of demand types. The paper’s own PS/EPS language already describes agents consuming item mass, but the proposed problem adds the missing computational object: a continuum population with per-capita supplies and integral bundles in every realization.
The weakest point is that atomlessness can purify some lotteries. A type’s mass may be split deterministically among different bundles, so a referee could argue that the proposed model has turned the paper’s lottery problem into ordinary fractional assignment. That objection is valid if the model allows arbitrary fractional bundles or asks only for the marginal matrix. The mirror avoids it by requiring every realization to assign an integral bundle and to satisfy ex-post EF1 or Pareto optimality; only the population measure, not each individual’s bundle, is continuous.
Thus the mirror covers two results rather than the whole paper: Theorem 3 supplies a serious hardness boundary, while Theorem 2 supplies a natural tractable mass-flow problem. The further questions are whether PO-implementation remains hard after type splitting, whether continuum EPS marginals admit polynomial-size EF1 decompositions, and whether the binary-utility guarantees of Theorem 6 yield an especially clean flow-based special case.
The best case against is a fidelity objection: both anchors depend on a finite-agent distinction between a fractional marginal and a lottery over globally coordinated integral allocations. An atomless population either erases that distinction or must reintroduce it as an additional joint-law structure.
For Theorem 3, the paper’s hardness is especially tied to that distinction. With \(n=m\) and strictly positive utilities, EF1 is equivalent to every deterministic allocation being balanced. The problem is therefore membership of a target \(n\times n\) random assignment in the convex hull of Pareto-optimal permutation matrices. The rows matter: the lottery must reproduce each named agent’s marginal allocation, while every realization must be a globally Pareto-optimal matching.
The proposed continuous target \(x_{t,o}\) does not preserve that object. In an atomless type class \(A_t\), any feasible type-level incidence can be realized by partitioning \(A_t\) into measurable pieces. If \(z_{t,B}\) is the mass of type \(t\) receiving bundle \(B\), then
\[ x_{t,o}=\sum_{B\ni o}z_{t,B}. \]
Every individual still receives an integral bundle, but the fractional type marginal now comes from deterministic heterogeneity within the type. It no longer witnesses randomization over matchings. Clearing denominators recovers a finite cloned population, but not the converse semantics: the continuum may split one type across several bundles, whereas the paper’s implementation problem concerns a common lottery over complete assignments with exact individual marginals.
One can repair this by requiring a lottery over complete type-bundle configurations, with EF1 and Pareto optimality checked globally in every realization. But that is a new measure-valued configuration problem, not a direct continuous version of Theorem 3. Alternatively, one can preserve the original individual marginals by adding labels or sufficiently fine subtypes. Then the type space carries the identity information whose removal was supposed to create the high-multiplicity regime. The difficulty here is not whether the resulting problem is easy or hard; it is that the quantified object has changed.
The \(n=m\) specialization also exposes the degeneration. With per-capita copies and one item per agent, EF1 becomes automatic once every individual receives one item, leaving only a type-aggregated Pareto-optimal matching problem. With fixed named objects instead, an atomless population cannot receive positive-mass shares of indivisible objects at all: the objects are assigned to null sets of agents, so the population-level allocation disappears. Scaling supplies repairs this, but changes the resource ontology from the paper’s named objects to anonymous item categories.
Theorem 2 has the same problem in a softer form. EPS already computes a fractional incidence matrix by letting agents consume infinitesimal quantities. Replacing \(n\) repeated agents by type masses \(\mu_t\) merely turns those consumption rates into aggregate rates. The genuinely nontrivial part of the theorem is not the marginal \(x^{\mathrm{EPS}}\); it is the existence of a globally coordinated lottery whose every integral realization is EF1.
In an atomless population, the marginal \(x^{\mathrm{EPS}}\) can generally be realized directly by measurable partitions of type classes. Thus the proposed lottery is needed only to preserve a global correlation among all agents. But that correlation is absent from \((\mu,x^{\mathrm{EPS}})\). It must be supplied through a distribution over full type-bundle configurations, which again creates a new problem rather than a population-only mirror. Carathéodory’s theorem does not solve this: it bounds the support after one has established membership in the convex hull of valid globally EF1 configurations; it neither identifies those configurations nor supplies a polynomial decomposition algorithm.
The strongest possible repair—per-capita item supplies, integral individual bundles, a joint configuration for every lottery outcome, and global EF1 or Pareto optimality—is coherent and the authors would recognize it as related to their problem. It may even be worth studying as a high-multiplicity fair-assignment extension. That concession is important: I cannot honestly defend the universal claim that no worthwhile mirror exists in any scenario.
What the negative case does establish is narrower but substantial. The proponent has not produced a direct mirror of either theorem. The obvious type-level formulation collapses the paper’s lottery-versus-integral distinction; preserving that distinction requires an additional joint-law or configuration model. The proposed mirrors therefore deserve to be labelled new high-multiplicity extensions, not consequences of simply continuizing the population.
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.