| paper | Fair Allocation with Diminishing Differences |
| authors | Erel Segal-Halevi, Avinatan Hassidim, H. Aziz |
| venue | JAIR 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: \(\mathrm{NP}\)-complete · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 7.4
statement extracted from the paper’s text layer
Given finite item categories \(G\), finite agent types \(R\) with complete strict rankings \(\succ_r\), rational masses \(\mu_r\) summing to \(1\), and rational per-capita supplies \(q_g\in[0,1]\) with \(\sum_{g\in G}q_g=\ell\), does there exist \(x_{r,B}\ge0\) over integral bundles \(B\in\binom{G}{\ell}\) such that \(\sum_Bx_{r,B}=\mu_r\), \(\sum_{r\in R}\sum_{B\ni g}x_{r,B}=q_g\), and \(x_{r,B}x_{s,C}>0\Rightarrow B\succeq_{\mathrm{NDD}}^r C\) for all \(r,s,B,C\)?
A finite-type high-multiplicity feasibility model with type masses \(\mu_r\), bundle-mass variables \(x_{r,B}\), integral bundles \(B\), per-capita supplies \(q_g\), and support-wise NDD envy constraints.
Under strict rankings and simple bundles, support-wise NDDEF forces \(x_{r,B}\in\{0,\mu_r\}\) for every type, so the mirror has no within-type fractional allocation and the proposed Exact-3-Cover lifting is unproved.
fatal: False
The mirror covers only Theorem 7.4: the existence problem for necessary-DD envy-free allocations. Theorem 5.1, Corollary 4.7, Pareto-efficiency results, chore variants, and simulation findings remain uncovered.
The strongest mirror is built around the paper’s hardness result for necessary-DD envy-freeness.
The anchor is Theorem 7.4, proved in this paper, with the reduction supplied in Appendix C. It states that, when there are \(n\ge 3\) agents and at least \(2n\) indivisible items, deciding whether an allocation satisfying necessary-DD envy-freeness exists is NP-complete, with complexity measured as a function of \(n\). Membership in NP follows from Lemma 7.2 and Theorem 4.1: a proposed allocation can be checked using at most \(n^2\) necessary-DD comparisons, each polynomial-time. NP-hardness is proved by reduction from Exact-3-Cover, using \(3n\) agents and \(6n\) items divided into main, dummy, and auxiliary items. The construction ensures that a necessary-DD envy-free allocation exists exactly when the Exact-3-Cover instance has a solution.
I would mirror this as Continuous Necessary-DD Envy-Free Allocation.
There is a finite catalogue \(G\) of item categories and a finite set \(R\) of agent types. A type \(r\in R\) is a complete ranking \(\succ_r\) over \(G\), together with any other attributes relevant to eligibility or fairness. The society is a distribution \(\mu=(\mu_r)_{r\in R}\), where \(\mu_r\) is the fraction of agents of type \(r\). There are \(\ell\) item units per agent in total. Category \(g\) has per-capita supply \(q_g\), with \(\sum_{g\in G}q_g=\ell\). The quantities \(\mu_r\) and \(q_g\) are rational.
An individual receives an integral bundle \(B\subseteq G\) of exactly \(\ell\) distinct categories. The continuum appears only in the mass of agents receiving each bundle. Let
\[ x_{r,B}\ge 0 \]
be the mass of type-\(r\) agents receiving bundle \(B\). The allocation must satisfy
\[ \sum_{B}x_{r,B}=\mu_r \]
for every type \(r\), and
\[ \sum_{r,B:g\in B}x_{r,B}=q_g \]
for every item category \(g\). Thus \(x\) is not a fractional bundle assigned to an individual: every unit of mass receives an integral bundle, while \(x\) records how many agents receive each bundle.
For type \(r\), define \(B\succeq_{\mathrm{NDD}}^r C\) exactly as in the paper. Since all bundles have size \(\ell\), this means that for every \(k\le \ell\), the sum of the levels of the \(k\) best categories in \(B\), according to \(\succ_r\), is at least the corresponding sum for \(C\). The continuous allocation is NDD envy-free when
\[ x_{r,B}>0\ \text{and}\ x_{s,C}>0 \quad\Longrightarrow\quad B\succeq_{\mathrm{NDD}}^r C \]
for every pair of types \(r,s\) and bundles \(B,C\). The decision question is whether such an \(x\) exists; a solution is any mass allocation satisfying the supply constraints and this support-wise no-envy condition.
This is a natural high-multiplicity regime for a national-scale allocation system: for example, a large internship or educational-placement programme in which millions of applicants receive two distinct placements from a finite catalogue of hospital, region, or course categories. Applicants may share rankings because they belong to common training, geographic, or eligibility cohorts. The number of agents is enormous, while the number of ranking types and item categories is comparatively small. Repeated seats are not a relaxation of indivisibility: they are many interchangeable physical copies, and each applicant still receives an integral bundle.
The authors should recognise this as their problem. It retains their central object—ordinal rankings extended to bundles through the DD restriction—and their exact fairness requirement. The only necessary co-modification is to replace one-off item identities by a finite catalogue with per-capita supplies, because a continuum of agents cannot be served by a fixed finite set of physical objects. Equal bundle size is also faithful rather than arbitrary: the paper’s NDD comparison requires cardinality dominance, and an NDDEF allocation therefore cannot mix smaller and larger bundles.
I would expect hardness to transfer, making this a candidate Class B mirror, although the lifting argument would need to be proved. Take the Appendix C construction, give each original agent type mass \(1/(3n)\), and give each original item category supply \(1/(3n)\). Then replicate every type and item category by a common factor \(K\), and let \(K\) grow. The Exact-3-Cover combinatorics live in the item catalogue and ranking structure, not in the existence of only one physical copy of each agent. Moreover, the envy condition is universal over the support: if positive mass of one type receives two incompatible bundles, agents receiving the worse bundle can envy those receiving the better one. This suggests that the all-or-nothing gadget arguments in Appendix C may survive aggregation, preventing arbitrary fractional mixing from destroying the reduction.
The important unresolved issue is precisely whether that intuition is correct. Continuous mass can sometimes turn an integral exact-cover constraint into a fractional-cover constraint. The first technical question is therefore whether the Appendix C reduction admits a genuine high-multiplicity lifting, or whether the continuous problem instead has a flow, LP, or column-generation algorithm. Either outcome would be informative: hardness would show that the discrete obstruction survives population continuization, while tractability would identify a case where population multiplicity dissolves the paper’s NP-hardness.
My weakest point is that the paper’s hardness parameter is the number of agents, whereas the mirror aggregates agents into types. A careless formulation could therefore erase the very integrality that drives the reduction. The proposed support-wise definition and integral bundle catalogue are meant to preserve the underlying allocation problem, but the hardness transfer is not automatic. That is a genuine conjecture about the mirror, not something established by Theorem 7.4 itself.
This case deliberately covers only Theorem 7.4. The paper’s polynomial results for NDD proportionality, such as Theorem 5.1 and Corollary 4.7, could support separate mirrors, but they are weaker anchors than the explicit NP-completeness theorem.
The strongest negative case is that the proposed mirror is not genuinely fractional in the way it claims. Under support-wise NDDEF, if a positive-mass type \(r\) receives both \(B\) and \(C\), then applying the condition with \(r=s\) gives
\[ B\succeq_{\mathrm{NDD}}^r C \quad\text{and}\quad C\succeq_{\mathrm{NDD}}^r B. \]
By Theorem 4.1, the bundles must have equal cardinality and identical prefix level sums. With strict rankings and simple bundles, that implies \(B=C\). Hence every positive-mass type receives one bundle only:
\[ x_{r,B}\in\{0,\mu_r\}. \]
The advertised continuum therefore does not permit a type’s population to divide across bundles. The variables \(x_{r,B}\) merely encode a discrete bundle choice for each type, weighted by \(\mu_r\). With the proposed supplies \(q_g=\mu_r\), each item category is likewise assigned to one cohort, and the Appendix C construction becomes a finite exact-cover allocation with replicated agents. The population masses scale the instance but do not create a new mass-allocation object.
The natural repairs each change the anchor. Allowing a type to split requires replacing exact NDDEF by an ex-ante, expected, or aggregate envy notion; that is a new fairness criterion, not the paper’s Theorem 7.4. Requiring each cohort to remain unsplit preserves the theorem’s combinatorics, but makes the problem a discrete allocation over types. Giving agents different rankings to permit splitting makes the number of types track the number of agents, abandoning the high-multiplicity regime.
This also means the proponent’s claimed technical uncertainty is misplaced: the same-type envy constraints themselves supply the missing integrality. The question is not whether a fractional exact-cover relaxation destroys the reduction; faithful NDDEF prevents that relaxation from occurring.
That is the best case against the anchor, but it is not decisive. A weighted finite-type allocation problem is still a sensible high-multiplicity object, and hardness surviving at the type level would be a legitimate Class B result under the programme. The paper’s Theorem 7.4 is therefore a credible continuous-population anchor despite the degeneracy above. I cannot honestly defend the universal claim that no worthwhile mirror exists; the negative case only shows that this mirror is less continuously substantive than the proponent suggests.
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.