Answer: \(\mathrm{NP}\text{-hard}\)
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe problem of determining whether there exists a Pareto-efficient and envy-free allocation for a given allocation problem with monotonic, dichotomous preferences under logical form is Σp 2- hard, even when: (i) each agent’s preferences are expressed by a (positive) 3DNF formula with at most 4 terms; and (ii) each item occurs in at most 3 agents’ expressed preferences.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(\Theta\), rational masses \(\mu_\theta\ge0\) summing to \(1\), item kinds \(O\), rational supplies \(q_o\in[0,1]\), and a dichotomous formula \(\phi_\theta\) over \(O\) for each type, where \(Nq_o\) denotes identical indivisible copies of kind \(o\) at scale \(N\), decide whether there exists a rational table \(a_{\theta,B}\ge0\) for \(B\subseteq O\) satisfying \(\sum_B a_{\theta,B}=\mu_\theta\) and \(\sum_{\theta,B:o\in B}a_{\theta,B}=q_o\), with \(a_{\theta,B}>0\) and \(\phi_\theta(B)=0\) implying that every used bundle \(B'\) satisfies \(\phi_\theta(B')=0\), and such that no feasible table weakly increases \(h_\theta=\sum_{B:\phi_\theta(B)=1}a_{\theta,B}\) for every type while strictly increasing it for some positive-mass type; output such a table if one exists.
Input: finite item classes \(O\), types \(T\), nonnegative rational masses \(\mu_t\), rational supplies \(q_o\), and propositional formulas \(\phi_t\) over \(O\). For \(B\subseteq O\), \(\phi_t(B)=1\) means that type \(t\) accepts bundle \(B\).
An allocation is \(x_{t,B}\ge 0\) with \(\sum_B x_{t,B}=\mu_t\) and \(\sum_{t,B:o\in B}x_{t,B}=q_o\). Write \(U_x(B)=\sum_t x_{t,B}\) and \(h_t(x)=\sum_{B:\phi_t(B)=1}x_{t,B}\).
It is envy-free when, for every \(t,B\), \(x_{t,B}>0\) and \(\phi_t(B)=0\) imply \(U_x(B')=0\) for every \(B'\) with \(\phi_t(B')=1\). It is Pareto-efficient when no feasible \(y\) has \(h_t(y)\ge h_t(x)\) for all \(t\) and \(h_t(y)>h_t(x)\) for some \(t\).
Is deciding whether an envy-free Pareto-efficient allocation exists in this continuous mass-allocation model in \(\mathrm{P}\), or is it NP-hard?
For discrete indivisible goods with monotonic dichotomous preferences given by logical formulas, deciding whether an envy-free Pareto-efficient allocation exists is \(\Sigma^p_2\)-hard, even under restricted positive \(3\)DNF preferences.
No verified result is supplied here for the exact continuous mass-allocation formulation above.
The decision problem is \(\mathrm{NP}\)-hard under polynomial-time many-one reductions. This holds even with:
Consequently, the problem is not polynomial-time solvable unless \(\mathrm{P}=\mathrm{NP}\).
Suppose there is only one type \(t\), of mass \(1\). Then \(U_x(B)=x_{t,B}\).
If an allocation assigns positive mass to both an unacceptable bundle \(B^{-}\) and an acceptable bundle \(B^{+}\), then it is not envy-free. Indeed, applying the envy-free condition to \(t,B^{-}\) would require \(U_x(B^{+})=0\), contradicting \(x_{t,B^{+}}>0\).
Thus, in a one-type instance, every envy-free allocation has support consisting entirely of acceptable bundles or entirely of unacceptable bundles.
Also, any allocation satisfying \(h_t(x)=1\) is Pareto-efficient: every feasible allocation \(y\) satisfies
\[
h_t(y)\leq \sum_B y_{t,B}=\mu_t=1.
\]
Let
\[
F(v_1,\ldots,v_n)=\bigwedge_{j=1}^{m} C_j
\]
be a \(3\)-CNF formula. Introduce one fresh item \(z\). Construct the mass-allocation instance as follows:
\[ \phi_t=\neg z\lor F. \]
The formula can be written as
\[
\phi_t=\bigwedge_{j=1}^{m}(\neg z\lor C_j),
\]
so it is a \(4\)-CNF formula of size polynomial in the size of \(F\).
A bundle \(B\subseteq O\) is interpreted as the truth assignment in which exactly the items in \(B\) are true.
The constructed supply constraints are feasible independently of \(F\): for example, assigning mass \(\tfrac12\) to \(O\) and mass \(\tfrac12\) to \(\varnothing\) gives every item supply \(\tfrac12\).
Assume \(F\) has a satisfying assignment \(a\). Define two bundles
\[
B_1=\{z\}\cup\{v_i:a(v_i)=1\}
\]
and
\[
B_0=\{v_i:a(v_i)=0\}.
\]
Assign
\[
x_{t,B_1}=x_{t,B_0}=\tfrac12,
\]
with all other variables equal to \(0\).
The type-mass constraint holds because the assigned masses sum to \(1\). The item-supply constraints also hold:
Both supported bundles are acceptable. For \(B_0\), the literal \(\neg z\) is true. For \(B_1\), \(z\) is true but the restriction to the variables \(v_i\) is the satisfying assignment \(a\), so \(F(B_1)=1\).
Therefore \(h_t(x)=1\). The allocation is envy-free because it assigns no mass to an unacceptable bundle. It is Pareto-efficient because \(1=\mu_t\) is the maximum possible happiness.
Hence, if \(F\) is satisfiable, the constructed instance admits an envy-free Pareto-efficient allocation.
Assume \(F\) is unsatisfiable. Then \(F(B)=0\) for every bundle \(B\), and consequently
\[
\phi_t(B)=1
\quad\Longleftrightarrow\quad
z\notin B.
\]
Let \(x\) be any feasible allocation. The supply constraint for \(z\) gives
\[
\sum_{B:z\in B}x_{t,B}=\tfrac12.
\]
The type-mass constraint then gives
\[
\sum_{B:z\notin B}x_{t,B}
=
1-\tfrac12
=
\tfrac12.
\]
Because these are finite sums of nonnegative numbers, there exist bundles \(B^{-}\) and \(B^{+}\) such that
The first bundle is unacceptable, while the second is acceptable. Envy-freeness applied to \(t,B^{-}\) would require
\[
U_x(B^{+})=0.
\]
But there is only one type, so
\[
U_x(B^{+})=x_{t,B^{+}}>0,
\]
a contradiction.
Thus, when \(F\) is unsatisfiable, the constructed instance has no envy-free allocation at all, and therefore no envy-free Pareto-efficient allocation.
The construction is computable in polynomial time and satisfies
\[
F\text{ is satisfiable}
\quad\Longleftrightarrow\quad
\text{the constructed instance admits an envy-free Pareto-efficient allocation}.
\]
This proves \(\mathrm{NP}\)-hardness. The argument does not rely on transferring the known discrete \(\Sigma_2^p\)-hardness result; it applies directly to the continuous mass-allocation definition.
The proof does not establish membership in \(\mathrm{NP}\), \(\Sigma_2^p\)-hardness, or hardness for monotone positive \(3\)-DNF preferences.
⟨structured verdict parsed — rendered above⟩
The prover correctly establishes NP-hardness by a polynomial-time many-one reduction from \(3\)-SAT. The reduction directly applies to the continuous allocation model and does not rely on the cited discrete result. No substantive gaps or incorrect steps were found.
With one type, \(U_x(B)=x_{t,B}\). If both an unacceptable bundle \(B^{-}\) and an acceptable bundle \(B^{+}\) receive positive mass, the envy-free condition for \(B^{-}\) requires \(U_x(B^{+})=0\), contradicting \(x_{t,B^{+}}>0\).
Hence an envy-free allocation cannot mix acceptable and unacceptable bundles in its support. This argument is correct.
Since \(\sum_B y_{t,B}=1\) and all allocation variables are nonnegative, every feasible allocation satisfies \(h_t(y)\leq 1\). Thus an allocation with \(h_t(x)=1\) cannot be Pareto-dominated. This correctly applies the stated definition of Pareto efficiency.
The constructed instance has \(n+1\) items, one type, rational data of constant encoding length, and preference formula
\[
\phi_t=\neg z\lor F=\bigwedge_j(\neg z\lor C_j).
\]
This equivalence is a valid distributive identity. When each \(C_j\) contains three literals, each resulting clause contains four literals, so the claimed \(4\)-CNF representation has polynomial size.
Interpreting item membership as Boolean truth values is consistent with the given semantics of formulas over \(O\).
Assigning mass \(1/2\) to \(O\) and mass \(1/2\) to \(\varnothing\) satisfies the type-mass constraint and gives each item total supply \(1/2\). Thus the reduction does not create infeasibility unrelated to satisfiability.
Given a satisfying assignment \(a\), the bundles \(B_1\) and \(B_0\) partition the variable items, while \(z\) belongs only to \(B_1\). Assigning mass \(1/2\) to each bundle therefore gives every item supply exactly \(1/2\).
Bundle \(B_0\) is acceptable because \(z\notin B_0\). Bundle \(B_1\) is acceptable because \(z\in B_1\) and its variable restriction satisfies \(F\). Consequently all allocated mass is acceptable, so \(h_t(x)=1\), envy-freeness holds vacuously for supported unacceptable bundles, and Pareto efficiency follows from maximal happiness.
If \(F\) is unsatisfiable, then \(\phi_t(B)=1\) exactly when \(z\notin B\). Every feasible allocation assigns total mass \(1/2\) to bundles containing \(z\) and, by the total type mass, total mass \(1/2\) to bundles not containing \(z\).
Because the bundle space is finite and the variables are nonnegative, each of these positive sums contains a positive term. Thus the support necessarily contains both an unacceptable bundle containing \(z\) and an acceptable bundle not containing \(z\). This contradicts envy-freeness. Therefore no envy-free allocation exists in the unsatisfiable case.
The construction is polynomial in the \(3\)-SAT instance size, and the completeness and soundness arguments establish the required biconditional. This proves NP-hardness of the target decision problem. Membership in NP is not needed for that conclusion.
No major or minor mathematical issues were identified.
⟨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.