Answer: \(\mathrm{NP\text{-}hard}\)
Proposition 4.2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor any reasonable uncertainty model that is independent, given a set M ′ ⊂M with |M ′| = n of houses, an allocation of M ′ to N which maximizes the prob- ability of EF can be computed in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite applicant types with rational masses, a fixed menu of recurring house classes with rational capacities summing to one, and an independent preference lottery for each type, compute a feasible mass matching \(x\) maximizing the per-capita log EF probability \(\sum_{t,h} x_{t,h} \log q_{t,h}\), where \(q_{t,h}\) is the probability that \(h\) is top among the menu for type \(t\).
Definitions. Given finite sets \(\Theta,H,K\), rational masses \(\mu_\theta\ge 0\) with \(\sum_\theta\mu_\theta=1\), rational capacities \(\kappa_h\), and a rational distribution \(\pi\) on \(K\), each type \(\theta\) has a complete strict ranking \(\rho_\theta^k\) of \(H\) in each state \(k\). Choose \(x_{\theta h}\ge0\) with \(\sum_hx_{\theta h}=\mu_\theta\) and \(\sum_\theta x_{\theta h}\le\kappa_h\). It is envy-free in state \(k\) if, whenever \(x_{\theta h}>0\), \(h\) is strictly ranked above every \(h'\ne h\) with \(x_{\theta' h'}>0\) for some \(\theta'\). Its score is \(\sum_{k\in K}\pi_k\mathbf{1}[x\text{ is envy-free in }k]\).
Target. Is computing a maximum-score mass assignment polynomial-time solvable, or NP-hard?
Nearest known results. For finite agents and houses under a joint distribution over strict preference profiles, maximizing the probability of an envy-free allocation admits no polynomial-time \(\left(\frac65-\varepsilon\right)\)-approximation for any constant \(\varepsilon>0\), unless \(\mathrm{P}=\mathrm{NP}\). No result for exactly the mass-assignment variant above is verified here.
Computing a maximum-score mass assignment is \(\mathrm{NP\text{-}hard}\). More strongly, deciding whether the maximum score equals \(1\) is \(\mathrm{NP\text{-}complete}\), even when all positive type masses are equal, all house capacities are equal, and the number of states is constant.
The finite-agent hardness therefore survives the mass formulation exactly; fractional assignments do not remove it.
Write \(h\succ_\theta^k g\) when type \(\theta\) strictly prefers \(h\) to \(g\) in state \(k\).
Lemma 1. If a feasible mass assignment \(x\) is envy-free in some state \(k\), then every type \(\theta\) with \(\mu_\theta>0\) is assigned entirely to one house.
Proof. Suppose instead that, for some \(\theta\), there are distinct houses \(h\) and \(g\) with
\[ x_{\theta h}>0\qquad\text{and}\qquad x_{\theta g}>0. \]
Because \(x_{\theta g}>0\), house \(g\) is occupied. Applying envy-freeness to the positive cell \(x_{\theta h}\) gives
\[ h\succ_\theta^k g. \]
Similarly, since \(h\) is occupied, applying envy-freeness to \(x_{\theta g}>0\) gives
\[ g\succ_\theta^k h. \]
These two inequalities contradict the fact that \(\rho_\theta^k\) is a strict ranking. Hence there is a unique house \(f(\theta)\) with \(x_{\theta f(\theta)}>0\). The row-sum constraint then gives
\[ x_{\theta f(\theta)}=\mu_\theta. \]
This proves the lemma. \(\square\)
Corollary 2. Every mass assignment having positive score is type-pure.
Indeed, positive score means that the assignment is envy-free in at least one state \(k\) with \(\pi_k>0\), so Lemma 1 applies.
Thus, except for assignments of score \(0\), the apparently fractional problem reduces to choosing a map
\[ f:\{\theta:\mu_\theta>0\}\longrightarrow H \]
satisfying
\[ \sum_{\theta:f(\theta)=h}\mu_\theta\leq\kappa_h \]
for every \(h\in H\).
Consider a finite house-allocation instance with agent set \(A\), house set \(H\), \(n=|A|\), and \(n\leq |H|\). In every state \(k\), each agent \(a\) has a strict ranking \(\rho_a^k\). A finite allocation is an injection
\[ \varphi:A\longrightarrow H. \]
It is envy-free in state \(k\) precisely when, for every pair of distinct agents \(a,b\),
\[ \varphi(a)\succ_a^k\varphi(b). \]
Construct the following mass instance:
\[ \Theta=A,\qquad \mu_a=\frac1n\quad(a\in A),\qquad \kappa_h=\frac1n\quad(h\in H). \]
Copy the states, their probabilities, and all rankings unchanged. This transformation is polynomial-time: the rational number \(1/n\) has polynomial encoding length.
For an injection \(\varphi\), define
\[ x^\varphi_{ah}= \begin{cases} \frac1n,&h=\varphi(a),\\ 0,&h\neq\varphi(a). \end{cases} \]
This is feasible. Its occupied houses are exactly \(\varphi(A)\), and the mass envy-free condition for agent-type \(a\) is
\[ \varphi(a)\succ_a^k h \quad\text{for every }h\in\varphi(A)\setminus\{\varphi(a)\}. \]
Because \(\varphi\) is injective, this is exactly the finite-agent envy-free condition. Therefore \(x^\varphi\) and \(\varphi\) have the same score.
Conversely, let \(x\) be a feasible mass assignment of positive score. By Corollary 2, there is a map \(f:A\to H\) such that
\[ x_{a,f(a)}=\frac1n. \]
If two distinct agents \(a,b\) had \(f(a)=f(b)=h\), then the load on \(h\) would be at least
\[ \frac1n+\frac1n=\frac2n>\frac1n=\kappa_h, \]
contradicting feasibility. Hence \(f\) is injective. By the preceding equivalence, \(f\) has exactly the same score as \(x\).
Let \(\mathrm{OPT}_{\mathrm{fin}}\) be the maximum score in the finite instance and let \(\mathrm{OPT}_{\mathrm{mass}}\) be the maximum score in the constructed mass instance.
Every finite allocation produces a mass assignment of the same score, so
\[ \mathrm{OPT}_{\mathrm{mass}}\geq \mathrm{OPT}_{\mathrm{fin}}. \]
Conversely, consider any feasible mass assignment \(x\).
Thus every feasible mass assignment has score at most \(\mathrm{OPT}_{\mathrm{fin}}\), and consequently
\[ \mathrm{OPT}_{\mathrm{mass}}\leq \mathrm{OPT}_{\mathrm{fin}}. \]
Therefore
\[ \mathrm{OPT}_{\mathrm{mass}}=\mathrm{OPT}_{\mathrm{fin}}. \]
This also handles the case in which the common optimum is \(0\): fractional zero-score assignments may exist, but they cannot improve the optimum.
For the finite joint-distribution model, deciding whether there is an allocation that is envy-free with probability \(1\) is \(\mathrm{NP\text{-}complete}\), even with a constant number of explicitly listed strict preference profiles. The same work proves the stated \((6/5-\varepsilon)\)-inapproximability for the maximum-probability problem [Aziz et al., Theorems 7.1 and 7.2](https://ojs.aaai.org/index.php/AAAI/article/download/28802/29534).
Apply the embedding above to an instance of the finite probability-\(1\) decision problem. Equality of optimal values gives
\[ \mathrm{OPT}_{\mathrm{mass}}=1 \quad\Longleftrightarrow\quad \mathrm{OPT}_{\mathrm{fin}}=1. \]
Hence deciding whether the mass optimum is \(1\) is \(\mathrm{NP\text{-}hard}\).
It is also in \(\mathrm{NP}\). A certificate consists of a map \(f:\Theta\to H\). In polynomial time one can check
\[ \sum_{\theta:f(\theta)=h}\mu_\theta\leq\kappa_h \]
for every house and, for every state \(k\) with \(\pi_k>0\), verify that
\[ f(\theta)\succ_\theta^k g \]
for every positive-mass type \(\theta\) and every other occupied house \(g\neq f(\theta)\). Lemma 1 guarantees that every score-\(1\) assignment has such a certificate.
Thus the score-\(1\) decision problem is \(\mathrm{NP\text{-}complete}\), and computing an optimal mass assignment is \(\mathrm{NP\text{-}hard}\).
The same embedding preserves approximation ratios. If an approximation algorithm returns a mass assignment with positive score, Corollary 2 converts it into a finite allocation of exactly the same score. If the optimum is \(0\), every finite allocation is optimal.
Consequently, for every fixed \(0<\varepsilon<1/5\), a polynomial-time \((6/5-\varepsilon)\)-approximation for the mass problem would give the same approximation for the finite problem. Therefore no such algorithm exists unless \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover correctly establishes that computing a maximum-score mass assignment is NP-hard. The stronger claim that deciding whether the optimum equals \(1\) is NP-complete is also justified.
The reduction preserves the optimum exactly, including the zero-optimum case. No substantive gaps or false steps were found.
The argument is correct.
If one positive-mass type \(\theta\) has positive assignments to distinct houses \(h\) and \(g\), both houses are occupied. Envy-freeness applied to \(x_{\theta h}>0\) requires \(h\succ_\theta^k g\), while its application to \(x_{\theta g}>0\) requires \(g\succ_\theta^k h\). These conclusions contradict strictness of the ranking.
Once at most one cell in the row is positive, the row-sum condition implies that the unique positive cell equals \(\mu_\theta\). The restriction to \(\mu_\theta>0\) is necessary and is stated.
This is correct. Since \(\pi\) is a probability distribution, a positive score implies envy-freeness in at least one state having positive probability. Lemma 1 then applies to every positive-mass type.
Zero-mass types cause no difficulty because they contribute neither occupied mass nor capacity load.
The construction
\[ \mu_a=\frac1n,\qquad \kappa_h=\frac1n \]
is polynomially encoded and feasible for every finite injection.
For an injection \(\varphi\), the occupied houses are exactly \(\varphi(A)\). The mass envy-free condition for type \(a\) therefore says precisely that \(a\) ranks \(\varphi(a)\) above every house assigned to another agent. This matches the finite-agent definition.
The converse is also correct for every positive-score mass assignment. Purity assigns each type its entire mass \(1/n\) at one house. Two types cannot share a house because that would create load \(2/n\), exceeding capacity \(1/n\). Hence the induced map is injective.
Both inequalities are established correctly.
Every finite allocation gives a mass assignment of equal score, yielding \(\mathrm{OPT}_{\mathrm{mass}}\geq\mathrm{OPT}_{\mathrm{fin}}\).
Every positive-score mass assignment yields an injection of equal score. A zero-score assignment cannot exceed \(\mathrm{OPT}_{\mathrm{fin}}\), since the latter is nonnegative. Thus \(\mathrm{OPT}_{\mathrm{mass}}\leq\mathrm{OPT}_{\mathrm{fin}}\).
The separate treatment of score-zero assignments correctly closes a possible gap left by the purity lemma.
The cited result supports the required source problem. The referenced paper states that, in the joint probability model, existence of an allocation that is certainly envy-free is NP-complete even with a constant number of profiles. It also states the claimed \(6/5-\varepsilon\) inapproximability result. See [Aziz et al., Theorems 7.1 and 7.2](https://arxiv.org/html/2312.11286).
The cited model uses strict preference profiles and the same finite house-allocation envy condition employed in the reduction. Its hypotheses therefore match the construction as written.
The certificate argument is correct. A map from positive-mass types to houses has polynomial size. Exact rational capacity sums and all relevant ranking comparisons can be checked in polynomial time.
For an optimum-\(1\) assignment, at least one positive-probability state exists, so Lemma 1 guarantees a type-pure certificate. Verification over every state with \(\pi_k>0\) is exactly what score \(1\) requires.
The construction indeed gives equal positive masses, equal capacities, and preserves the constant number of states.
The approximation consequence is also valid. A finite-factor approximation cannot return score \(0\) when the optimum is positive. When the optimum is \(0\), every finite allocation attains the optimum. Thus the reduction transfers the cited multiplicative inapproximability.
No major or minor mathematical issues were identified. No additional clarification is needed to verify the proof.
⟨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.