| paper | Fair assignment of indivisible objects under ordinal preferences |
| authors | H. Aziz, Serge Gaspers, Simon Mackenzie, T. Walsh |
| venue | ATAL 2014 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: NP-hard, even for one type with a strict ranking; NP-complete when the allowed bundles are explicitly listed. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 11(i)
statement extracted from the paper’s text layer
Given finite object kinds \(O\), a finite set of ranking types \(T\), rational type masses \(\mu_t\), rational per-capita supplies \(\rho_o\), and a finite family of integral bundles \(\mathcal{B}\), decide whether there exist masses \(x_{t,B}\ge 0\) satisfying \(\sum_{B\in\mathcal{B}}x_{t,B}=\mu_t\) and \(\sum_{t\in T}\sum_{B\in\mathcal{B}}B_o x_{t,B}=\rho_o\) for every \(o\), such that whenever \(x_{t,B}>0\), no bundle \(C\) with positive aggregate mass is strictly SD-preferred to \(B\) by type \(t\); if so, output \(x\).
A high-multiplicity assignment model with ranking types \(t\), population mass \(\mu_t\), per-capita object capacities \(\rho_o\), and configuration masses \(x_{t,B}\), preserving integral bundles and the paper's support-wise weak SD envy-freeness.
Allowing one type's mass to split across several integral bundles may destroy the X3C reduction and could yield a tractable configuration or column-generation formulation; no rounding or hardness-preservation argument is supplied.
fatal: False
The mirror directly targets Theorem 11(i), plausibly extends to Theorem 11(ii) and (iii), and leaves the proportionality, Pareto-optimality, entitlement, and optimal-fairness results unexamined. Theorem 6 is only suggested as a contrasting possible algorithmic mirror.
The strongest positive case is a high-multiplicity version of the paper’s envy-freeness problem. It is not a claim that the paper already studies a continuum; the point is that its central computational question survives a natural population continuization.
My lead anchor is Theorem 11(i), proved in this paper. It states that deciding whether there exists a discrete assignment that is weak SD envy-free—equivalently, possible-completion envy-free—is NP-complete. The same theorem also proves NP-completeness for possible envy-freeness in part (ii) and SD envy-freeness in part (iii), but part (i) is the cleanest anchor. The hardness reduction is from X3C, and the reduction uses the allocation of indivisible objects and ordinal bundle comparisons, not merely the names of the agents.
A natural regime is a large recurring allocation system: for example, many cohorts of students receiving course bundles, residents receiving bundles of public services, or employees receiving bundles of workplace resources. There are finitely many object kinds, and many agents share the same complete ordinal ranking over those kinds. If the system has \(K\) repeated cohorts, every type occurs \(K\) times and every object kind has \(K\) copies. Thus the number of agents can be arbitrarily larger than the number of preference types. The paper’s own applications—course enrolments, houses, seats, and time slots—make this regime quite recognizable.
The finite stock of objects must be scaled per capita. Let \(O\) be the finite set of object kinds, \(T\) the finite set of ranking types, and \(\mu_t\) the mass of type \(t\), with \(\sum_t\mu_t=1\). Let \(\rho_o\) be the number of copies of object kind \(o\) available per unit population. The total supply is \(\sum_o\rho_o\); rational \(\rho_o\) can be realized by clearing denominators in a sufficiently large finite cohort. Copies of the same kind are tied in every ranking, exactly as the paper permits indifferences.
The continuous problem I would propose is:
“Continuous Weak-SD-Envy-Free Assignment, \(\mathrm{WeakSD\text{-}EF}_\infty\).” An instance consists of rational masses \(\mu\), rational per-capita supplies \(\rho\), and a complete weak order over \(O\) for each type \(t\). The decision variable is \(x_{t,B}\ge 0\), the mass of type \(t\) receiving the integral bundle \(B\subseteq O\). It must satisfy
\[ \sum_{B\subseteq O}x_{t,B}=\mu_t \]
for every \(t\), and
\[ \sum_{t\in T}\sum_{B\ni o}x_{t,B}=\rho_o \]
for every object kind \(o\). Thus every unit of population receives an integral bundle; only the aggregate mass assigned to each bundle is fractional.
For a type \(t\), let \(U_t^1,\ldots,U_t^{k_t}\) be the successive upper contour sets of its ranking. For bundles \(B,C\), write \(B\succeq_t^{SD}C\) when
\[ |B\cap U_t^\ell|\ge |C\cap U_t^\ell| \]
for every \(\ell\), and write \(B\succ_t^{SD}C\) when this holds with at least one strict inequality. Let \(S(x)\) be the set of bundles receiving positive mass. The assignment is weak SD envy-free if, whenever \(x_{t,B}>0\), no bundle \(C\in S(x)\) satisfies \(C\succ_t^{SD}B\). The question is whether such an \(x\) exists, and a solution is the mass table \(x\).
This is recognizably the authors’ problem. It preserves the indivisibility of each person’s allocation, the ordinal nature of preferences, the SD comparison, completeness of the assignment, and the existential fairness question. The only structural change is the one required to make a population continuum meaningful: object supply scales with population, while type-level averages may be fractional. It is not a lottery replacing bundles by fractional bundles.
The finite/high-multiplicity bridge is also concrete. If \(\mu_t\), \(\rho_o\), and \(x_{t,B}\) are rational, clear denominators by \(D\). Then \(D\mu_t\) agents of type \(t\), \(D\rho_o\) copies of object \(o\), and \(Dx_{t,B}\) agents receiving bundle \(B\) give a finite assignment. Conversely, every finite assignment with repeated preference types aggregates to such an \(x\). Importantly, fairness is checked on every integral bundle in the support, not merely on a fractional average bundle.
My forecast is Class B: hardness should transfer. Theorem 11’s X3C gadget is driven by object-incidence structure and the requirement that integral bundles avoid envy. Those features remain after agents are replicated into large homogeneous cohorts. In particular, the reduction uses \(40l\) agents and \(120l\) objects, so its intended fair allocations have three objects per agent; the continuous version can retain that per-capita supply while allowing arbitrarily many repeated cohorts. Since weak SD envy-freeness is support-sensitive, splitting population mass across bundles does not automatically create a universally fair fractional bundle.
That forecast still needs a real proof. The weak point is that the original reduction uses exact finite counts, whereas the continuum permits a type’s mass to split among several integral bundles. A fractional split might evade the exact-cover obstruction even though no single finite assignment can. The decisive technical question is therefore whether the X3C construction admits a support-preserving rounding argument, or whether the continuous problem instead collapses to a configuration LP. If rounding fails, this becomes a genuine Class C possibility: hardness caused by selecting a globally compatible support of integral bundles rather than by population multiplicity itself.
Further questions naturally follow: whether the same mirror is NP-complete for the possible- and strong-SD variants from Theorem 11(ii) and (iii); whether the problem becomes tractable for fixed numbers of object kinds, ranking types, or bundle size; and whether a column-generation formulation has an efficient pricing problem. The paper’s Theorem 6 suggests a contrasting secondary direction: its SD-proportionality feasibility problem is in P via bipartite \(b\)-matching, so the corresponding per-capita SD-proportional mirror may be a Class A problem.
The mirror therefore covers one result emphatically—Theorem 11(i)—without pretending to continuize the whole paper. Its weakest point is the unresolved effect of splitting homogeneous population mass. That is not a defect in the question: it is precisely the computational question created by making the society, rather than the finite list of named agents, the continuous object.
The strongest negative case is a semantic fork. It does not establish that no mirror exists, but it shows that the proponent has not yet secured the claimed anchor.
If the continuum is interpreted at the level of type-average allocations, the problem collapses to the paper’s already-noted fractional assignment setting. Give every type the same feasible lottery over bundles. Each type then receives the same fractional allocation, so there is no SD envy; with the per-capita analogue of the uniform allocation, proportionality is also immediate. This does not mirror Theorem 11: it replaces ex post indivisibility by fractional outcomes, precisely the trivialization identified in the paper’s Remark after Theorem 11. That would be outcome-space continuity, not a meaningful population continuization.
The proponent’s stronger interpretation retains integral bundles for every unit of mass and records \(x_{t,B}\). This is coherent, but it changes the computational core of Theorem 11. The X3C proof depends on a named \(N_1\)-agent making one coherent set-selection choice. In the proposed model, positive mass of one type may split among several integral bundles. The exact-cover constraint can thereby become a fractional-cover constraint: different parts of the same type can realize different set choices. The fact that every realized bundle is integral does not preserve the integrality of the global set-selection gadget.
Forbidding such splitting by requiring all mass of a type to receive one bundle would restore the reduction, but that is no longer the natural nonatomic model. It treats a whole cohort as an indivisible super-agent. Alternatively, one can impose the proponent’s support-wide condition—every bundle with positive mass must avoid envy—but then the mirror is a new ex-post support-robust fairness notion, not simply the high-multiplicity form of weak SD envy-freeness. Its feasibility is also discontinuous: adding an arbitrarily small positive mass of a dominated bundle changes a feasible allocation into an infeasible one, while that mass disappears in the limit.
The same objection applies to Theorem 11(ii) and (iii). Under fractional semantics, possible and SD envy-freeness become ordinary fractional-assignment notions with common allocations. Under ex-post semantics, the reduction must survive mass splitting and support changes; the paper supplies no such argument. Thus none of the three NP-completeness claims is yet an established anchor for the proposed continuum.
Theorem 6 is a weaker anchor still. Under type-average semantics, SD proportionality is satisfied by the common per-capita fractional allocation. Under ex-post semantics, each supported bundle \(B\) must satisfy constraints such as
\[ |B\cap U_t^\ell|\ge \rho(U_t^\ell) \]
for every upper contour set \(U_t^\ell\), while the average bundle equals the supply vector \(\rho\). Since the left side is integral, this forces exact integer threshold conditions on every supported bundle. After clearing denominators, the problem is just a capacitated lower-bound matching problem of the same kind as the paper’s \(b\)-matching algorithm. The population distribution contributes no new computational structure; it merely supplies capacities.
I would not, however, claim that this defeats the mirror universally. The recurring-cohort example with course seats or public-service bundles is a sensible high-multiplicity regime, and high-multiplicity work is supporting evidence, not prior-art collision. The honest negative conclusion is narrower: the proponent has identified a plausible research direction, but not yet a continuous mirror whose fairness semantics are both faithful to the paper and robust to population splitting. A universal “no mirror” verdict is therefore weaker than the positive case, especially for Theorem 11(i).
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.