Answer: \(\mathrm{NP}\)-hard
Theorem 4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe LEE problem is NP-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given student types \(T\) with rational masses \(\mu_t\), schools \(S\) with per-capita capacities \(q_s\), strict student preferences, school priority orders over types, and an acquaintance graph \(H\) on types, does there exist an assignment of individuals to schools or to being unmatched whose aggregate masses \(x_{t,s}\) satisfy \(\sum_s x_{t,s}=\mu_t\) and \(\sum_t x_{t,s}\le q_s\), and which is locally envy-free and Pareto efficient? Interpret each edge of \(H\) as acquaintance between every individual in its endpoint cohorts; local envy occurs when positive mass of type \(t\) prefers school \(s\) to its assignment, positive mass of adjacent type \(u\) attends \(s\), and \(t\) has higher priority than \(u\) at \(s\). Pareto efficiency rules out any feasible reassignment that weakly improves almost every individual and strictly improves a positive mass.
A society is given by its support: a list \(T\) of \(\tau\ge1\) types with positive binary rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. Each cohort is nonatomic.
There are \(m\ge1\) schools \(S\), nonnegative binary rational capacities \(q_s\), and an explicitly listed set \(A\subseteq T\times S\) of mutually acceptable pairs. Type \(t\) strictly ranks its acceptable schools and the unmatched option \(\varnothing\), placing \(\varnothing\) last; each school strictly prioritizes its acceptable types. Individuals of one type share these rankings and have equal priority.
A simple undirected graph \(H=(T,E)\) specifies acquaintance: every individual in one endpoint cohort knows every individual in the other, with no acquaintances within a cohort.
An assignment measurably assigns each individual one acceptable school or \(\varnothing\). Its aggregate masses are real numbers \(x_{t,a}\ge0\), with \(x_{t,s}=0\) for \((t,s)\notin A\), \(\sum_{a\in S\cup\{\varnothing\}}x_{t,a}=\mu_t\), and \(\sum_t x_{t,s}\le q_s\).
The assignment is locally envy-free if there are no \(\{t,u\}\in E\), \((t,s),(u,s)\in A\), and \(a\in S\cup\{\varnothing\}\) such that \(x_{t,a}>0\), \(x_{u,s}>0\), \(s\succ_t a\), and \(t\succ_s u\).
It is Pareto efficient if no feasible measurable reassignment weakly improves almost every individual and strictly improves a positive mass of individuals, using only student preferences; the reassignment need not be locally envy-free. Let \(L\) be the total binary input length.
Is deciding whether a feasible, locally envy-free, Pareto-efficient assignment exists solvable in time polynomial in \(m,\tau,L\), or is it NP-hard?
Discrete existence of a locally envy-free, Pareto-efficient matching is NP-complete, even with unit school capacities and complete acceptability ([verified discrete result](https://arxiv.org/html/2508.15296v1)).
No result settling the exact nonatomic decision problem specified here was identified in the literature search.
The decision problem is \(\mathrm{NP}\)-hard, even when \(m=\tau=n\), acceptability is complete, and every cohort mass and school capacity equals \(1/n\).
The key is an exact existence equivalence: for this restricted class, a locally envy-free, Pareto-efficient nonatomic assignment exists if and only if a locally envy-free, Pareto-efficient discrete matching exists. The proof below allows arbitrary real assignment masses.
We use the discrete hardness result supplied in the question. More precisely, the construction in Theorem 4 has equally many students and schools, unit school capacities, complete acceptability, strict preferences and priorities, and an undirected acquaintance graph. Deciding whether such an instance admits a locally envy-free, Pareto-efficient matching is \(\mathrm{NP}\)-hard. [Takeshima et al., Theorem 4](https://arxiv.org/html/2508.15296v1).
Let such a discrete instance have student set \(I\), school set \(S\), and \(|I|=|S|=n\). Construct a nonatomic instance as follows:
All preferences place \(\varnothing\) last. Each type is a nonatomic cohort, with no acquaintances within the cohort, exactly as required.
This construction has polynomial encoding length: each new mass and capacity has a binary encoding of length \(O(\log n)\). We prove that it preserves the answer in both directions.
A nonnegative \(n\times n\) matrix \(D\) is doubly stochastic if every row sum and every column sum equals \(1\). For a bijection \(M:T\to S\), let \(P^M\) denote its permutation matrix, so \(P^M_{t,s}=1\) precisely when \(s=M(t)\).
Lemma. Every doubly stochastic matrix admits a finite decomposition
\(D=\sum_{k=1}^{r}\lambda_k P^{M_k}\),
where \(\lambda_k>0\), \(\sum_k\lambda_k=1\), and every \(M_k\) uses only positive entries of \(D\).
Proof. Form the bipartite graph whose edges are the positive entries of \(D\). For any subset \(U\) of rows, let \(N(U)\) be its neighboring columns. Then
\[
|U|
=\sum_{t\in U}\sum_{s\in N(U)}D_{t,s}
\leq \sum_{s\in N(U)}\sum_{t\in T}D_{t,s}
=|N(U)|.
\]
Thus Hall’s condition holds, so the graph contains a perfect matching \(M\).
Set \(\varepsilon=\min_t D_{t,M(t)}>0\). If \(\varepsilon=1\), then \(D=P^M\). Otherwise,
\((D-\varepsilon P^M)/(1-\varepsilon)\)
is doubly stochastic and has strictly fewer positive entries than \(D\). Applying the same argument recursively terminates after finitely many steps and gives the claimed decomposition. Subtraction never introduces a positive entry outside the original support. \(\square\)
In particular, every positive entry of \(D\) belongs to at least one permutation appearing with positive coefficient in the decomposition.
Suppose the constructed nonatomic instance has a feasible, locally envy-free, Pareto-efficient assignment with aggregate masses \(x\).
Let \(u=\sum_t x_{t,\varnothing}\). The total school capacity is \(1\), while assigned mass is \(1-u\). Consequently, total unused capacity is \(u\).
If \(u>0\), some type \(t\) has positive unmatched mass and some school \(s\) has positive unused capacity. Complete acceptability lets us move a positive mass of unmatched type-\(t\) individuals into \(s\), strictly improving them and leaving everyone else unchanged. This contradicts Pareto efficiency.
Therefore \(u=0\). Every school is also full, since total assigned mass and total capacity both equal \(1\). Hence \(D_{t,s}=n x_{t,s}\) is doubly stochastic.
Apply the lemma and choose any permutation \(M\) appearing in its decomposition. In particular,
\(x_{t,M(t)}>0\) for every \(t\).
Suppose \(M\) had local justified envy. There would be adjacent types \(t,u\), with \(s=M(u)\), such that
\(s\succ_t M(t)\) and \(t\succ_s u\).
But \(x_{t,M(t)}>0\) and \(x_{u,s}>0\). These are precisely the positive masses forbidden by nonatomic local envy-freeness. Thus \(M\) is locally envy-free.
Suppose instead that a feasible discrete matching \(M'\) Pareto dominated \(M\).
Because \(M\) assigns every student to an acceptable school, no weak improvement can leave a student unmatched. Thus \(M'\) also matches every student and, with \(n\) unit-capacity schools, is a bijection. We have
\(M'(t)\succeq_t M(t)\) for every \(t\), with strict preference for at least one type.
Choose
\(0<\delta<\min_t x_{t,M(t)}\).
For each type \(t\), select a measurable subset of mass \(\delta\) among its individuals currently assigned to \(M(t)\), and move this subset to \(M'(t)\). Such subsets exist because the cohorts are nonatomic.
Every school loses mass \(\delta\) from the subset corresponding to its unique preimage under \(M\), and receives mass \(\delta\) from its unique preimage under \(M'\). Its total load therefore stays unchanged. Equivalently, the new aggregate matrix is
\(x'=x+\delta(P^{M'}-P^M)\),
which is nonnegative and preserves every row and column sum.
Every moved individual weakly improves. For any type with \(M'(t)\succ_t M(t)\), mass \(\delta\) strictly improves. Everyone else retains their assignment. This is a feasible measurable Pareto improvement, contradicting the efficiency of \(x\).
Therefore \(M\) is a locally envy-free, Pareto-efficient discrete matching.
Conversely, suppose the discrete instance has a locally envy-free, Pareto-efficient matching \(M\).
First, \(M\) must be perfect. Otherwise, equally many students and schools imply that there is both an unmatched student and an empty school. Complete acceptability would permit a strict improvement for that student.
Assign the entire type-\(t\) cohort to \(M(t)\). Thus
\(x_{t,M(t)}=1/n\),
with all other aggregate masses zero.
This assignment is feasible. It is locally envy-free because any nonatomic local-envy violation would directly give the same violation in \(M\).
It remains to prove efficiency against arbitrary measurable reassignments, including those that split cohorts.
Suppose such a reassignment weakly improved almost every individual and strictly improved a positive mass. Let \(y\) be its aggregate matrix. Since every type-\(t\) individual originally received \(M(t)\), weak improvement implies
\(y_{t,s}>0\Longrightarrow s\succeq_t M(t)\),
and \(y_{t,\varnothing}=0\). Null sets do not affect these aggregate conclusions.
All mass remains assigned. Since total school capacity is \(1\), every school remains full. Therefore \(D'=n y\) is doubly stochastic.
Moreover, strict improvement on a positive mass implies that some pair \((t_0,s_0)\) satisfies
\(y_{t_0,s_0}>0\) and \(s_0\succ_{t_0}M(t_0)\):
the set of strictly improved individuals is a finite union of type–destination classes.
Decompose \(D'\) using the lemma. Because \(D'_{t_0,s_0}>0\), some permutation \(M_k\) in the decomposition assigns \(t_0\) to \(s_0\). Every entry used by \(M_k\) is positive in \(D'\), so
\(M_k(t)\succeq_t M(t)\) for every \(t\).
For \(t_0\), this preference is strict.
Thus \(M_k\) is a feasible discrete Pareto improvement of \(M\), contradicting its efficiency. The nonatomic assignment is therefore Pareto efficient.
The construction is polynomial and preserves existence in both directions. Hence the exact nonatomic decision problem is \(\mathrm{NP}\)-hard, already for complete acceptability, equal masses and capacities, and \(m=\tau\).
Consequently, an algorithm polynomial in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\). No unresolved mathematical step remains in this hardness proof.
⟨structured verdict parsed — rendered above⟩
The proof resolves the task correctly. It establishes \(\mathrm{NP}\)-hardness through a polynomial reduction and proves the claimed existence equivalence for arbitrary real assignment masses. I found no major or minor mathematical issues.
The cited discrete result has the restrictions needed here. The construction in Theorem 4 adds one student and one school to equally sized sets, uses complete acceptability and unit capacities, and specifies strict preferences, strict priorities, and an undirected acquaintance graph. Its definition of Pareto efficiency uses student preferences and compares against all feasible matchings. These agree with the discrete problem used by the prover. [Takeshima et al., model definitions and Theorem 4](https://arxiv.org/html/2508.15296v1)
The nonatomic construction satisfies every relevant input requirement:
The encoding claim is correct: representing \(1/n\) requires \(O(\log n)\) bits. Explicitly listing acceptability, rankings, priorities, and graph edges has polynomial size. The construction is polynomial-time.
The support graph satisfies Hall’s condition. For every row subset \(U\), the displayed calculation correctly establishes \(|U|\leq |N(U)|\). The graph is finite and its two vertex classes each have size \(n\), so Hall’s theorem yields a perfect matching.
The recursive decomposition is valid:
The resulting coefficients are positive and sum to \(1\). The final support assertion also follows: a positive entry of a nonnegative sum of positively weighted permutation matrices must occur in at least one summand.
The lemma applies to real entries; no rationality assumption is used.
Full assignment. The equality between unmatched mass and total unused capacity is correct. If either is positive, finiteness supplies a type with positive unmatched mass and a school with positive slack. Complete acceptability and nonatomicity permit moving a positive measurable mass into that school. This is a feasible individual Pareto improvement.
Consequently, unmatched mass is zero. Since assigned mass equals total capacity and all capacity slacks are nonnegative, every school is full. Scaling by \(n\) therefore gives a doubly stochastic matrix.
Local envy-freeness. Every selected permutation entry has positive mass in the original assignment. Any discrete local-envy violation consequently supplies exactly the two positive masses, preference comparison, priority comparison, and acquaintance edge forbidden by the nonatomic definition. This implication is correct.
Pareto efficiency. A discrete weak improvement of the perfect matching cannot leave anyone unmatched, because every school is preferred to the unmatched option. With equal numbers of students and unit-capacity schools, the improving matching is another bijection.
The minimum used to choose \(\delta\) is positive because there are finitely many selected positive entries. Nonatomicity permits the stated measurable selections. The update
\(x'=x+\delta(P^{M'}-P^M)\)
is nonnegative and preserves all row and column sums. Types whose destinations coincide simply retain their assignments.
Every selected individual weakly improves, and at least one type contributes mass \(\delta>0\) of strict improvement. Thus the contradiction uses precisely the task’s individual Pareto criterion. The improving reassignment need not satisfy local envy-freeness.
Perfectness and feasibility. A nonperfect discrete matching leaves both an unmatched student and an empty school. Complete acceptability makes assigning that student to that school a Pareto improvement. Hence the source solution is perfect, and assigning each whole cohort to its matched school is feasible.
Local envy-freeness. Only the original matching destinations have positive mass. A nonatomic violation would therefore be the same discrete violation. This is correct.
Efficiency against splitting. Since every individual of type \(t\) initially receives \(M(t)\), almost-everywhere weak improvement excludes positive aggregate mass at any worse destination, including the unmatched option. Exceptional null sets do not alter aggregate masses.
All mass remains assigned, so every school remains full and \(ny\) is doubly stochastic. Positive mass of strict improvement yields a positive type–destination class because there are only finitely many such classes.
The decomposition contains a permutation using that strictly improved entry. Every entry of this permutation is supported by \(y\), so every student weakly improves and the selected student strictly improves. This contradicts discrete Pareto efficiency.
This argument covers arbitrary measurable cohort splitting and arbitrary real aggregate masses.
Both directions establish the claimed equivalence, and the reduction is polynomial. Therefore the exact nonatomic decision problem is \(\mathrm{NP}\)-hard under the stated restrictions. The implication that a polynomial-time algorithm would yield \(\mathrm{P}=\mathrm{NP}\) is justified.
The prover claims hardness, not membership in \(\mathrm{NP}\), so no continuous certificate argument is missing. No repair or additional clarification is required.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.