Fair Allocation based on Diminishing Differences

The strongest positive case is a genuine high-multiplicity version of the paper’s envy-free existence problem, anchored in the paper’s own hardness result.

The lead anchor is Theorem 5, proved in this paper rather than merely cited:

Theorem 5. Checking the existence of NDDEF allocations is NP-complete when there are \(n\) agents and at least \(2n\) items.

Here NDDEF means that an allocation \(X\) satisfies
\[ X_i\succeq_i^{NDD}X_j \]
for every pair of agents \(i,j\), where \(X_i\succeq_i^{NDD}X_j\) means that \(X_i\) has at least as much utility as \(X_j\) for every positive additive utility function consistent with agent \(i\)’s ranking and satisfying diminishing differences. The theorem concerns the underlying allocation problem with indivisible items and strict item rankings; it is not a hardness result about an encoding.

My mirror is Continuous High-Multiplicity NDDEF Existence.

There is a finite catalogue \(G\) of item types and a finite set \(T\) of preference types. A type \(t\in T\) is a complete preference description: all agents of type \(t\) have the same strict ranking \(\succ_t\) over \(G\), and therefore the same DD-consistent utility class. The society is given by rational masses
\[ \mu_t\ge 0,\qquad \sum_{t\in T}\mu_t=1. \]

Items are supplied in per-capita quantities. For each \(g\in G\), \(\sigma_g\in\mathbb Q_{\ge 0}\) is the mass of copies of item \(g\) available per unit population. In the equal-load version, \(\sum_g\sigma_g=k\) for an integer \(k\), and every individual receives a bundle \(B\subseteq G\) of exactly \(k\) distinct items. The items remain indivisible at the individual level: a fractional variable represents a mass of agents receiving an entire bundle, not an agent receiving fractional items.

Let \(x_{t,B}\) be the mass of type-\(t\) agents assigned bundle \(B\). A feasible aggregate allocation satisfies
\[ \sum_{B:|B|=k}x_{t,B}=\mu_t \]
for every \(t\), and
\[ \sum_{t\in T}\sum_{B\ni g}x_{t,B}=\sigma_g \]
for every item \(g\).

The decision question is whether there exists such an allocation for which
\[ x_{t,B}>0,\ x_{t',B'}>0 \quad\Longrightarrow\quad B\succeq_t^{NDD}B' \]
for every pair of types \(t,t'\) and bundles \(B,B'\). Thus every agent of type \(t\) weakly prefers her own bundle, according to the paper’s NDD relation, to every bundle received by any positive-mass part of society. A solution is the mass-assignment vector \(x\), together with its finite bundle support.

This is a natural scenario for the authors: a large course-allocation or internship-allocation market in which thousands or millions of students belong to a relatively small number of recurring preference cohorts. The item catalogue consists of courses, placements, or programme slots; each has many copies, and the supply scales with the population. The cohort ranking and DD assumption are exactly the information model used in the paper. Nothing is changed into a lottery or a fractional bundle.

The finite-to-continuous dictionary is exact. A finite instance with \(n\) agents maps to masses \(\mu_t=1/n\) and item supplies \(\sigma_g=1/n\) for each original item. Conversely, clearing denominators in rational masses and supplies produces a finite replicated instance. In particular, take \(K\) identical copies of every agent and every item in a finite instance. The physical population becomes \(Kn\), while the number of preference types remains the number of distinct rankings. Hence the same mathematical problem naturally describes a regime with very high multiplicity.

I expect this mirror to be Class B: hardness transfers. The obstruction in Theorem 5 is not the names of the agents. It is the combinatorial choice of indivisible bundles subject to pairwise DD-envy constraints. In the continuous model, mass compresses repeated agents, but each positive-mass type still has to be assigned integral bundles and the item-supply equations still have to be met. Theorem 5’s finite instances therefore embed as rational-mass instances.

The important qualification is that this is not a generic LP relaxation. Exact NDDEF itself prevents a type from being split among genuinely different bundles: if two agents have the same ranking and receive \(B\) and \(B'\), NDDEF applies in both directions, forcing the two bundles to be mutually NDD-equivalent; with strict rankings and equal bundle sizes, that essentially means the same bundle. Thus the continuous variable \(x_{t,B}\) records population mass, while the bundle choice remains discrete. That is precisely why the discrete hardness can survive.

This mirror covers Theorem 5 emphatically, but not the paper’s simulations, its equivalence results for Pareto efficiency, or Theorem 3’s characterization of NDD-proportional allocations. Those would require separate continuum definitions of proportionality and are not needed for the present case.

The weakest point is therefore clear: the mirror may look like a compressed finite allocation problem rather than a genuinely fractional one, and Theorem 5 itself does not establish hardness when the number of preference types is fixed. The honest follow-up questions are whether the problem is fixed-parameter tractable in \(|T|\) or \(k\), whether hardness persists with \(|T|\ll\) population size, and what happens under an \(\varepsilon\)-NDDEF or type-average envy notion that permits a type to split across bundles. Those are extensions of the authors’ problem, not reasons to reject the exact high-multiplicity mirror.