Answer: \(\mathrm{NP}\text{-complete}\)
Theorem 5.1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateGiven a fair division instance with partition-based utilities and 𝐾> 0, the problem of deciding whether there exists an ex-ante envy-free and Pareto-optimal allocation lottery of social welfare at least 𝐾 is NP-complete. It is easy to see that the above problem belongs to the complexity class NP. First, notice that it is trivial to check whether a given lottery q is ex-ante envy-free and has social welfare at least 𝐾.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given agent types \(\Theta\) with rational masses \(\mu_\theta\), admissible partitions \(k\in[m]\), bundle classes with rational supply masses \(\nu_b^k\), rational utilities \(u_{\theta b}^k\), and threshold \(\kappa\), decide whether there are partition probabilities \(p_k\) and assignment masses \(x_{\theta b}^k\) satisfying \(\sum_b x_{\theta b}^k=p_k\mu_\theta\), \(\sum_\theta x_{\theta b}^k=p_k\nu_b^k\), and \(\sum_k p_k=1\), such that the induced lottery is ex-ante envy-free, Pareto-optimal, and has social welfare \(W(x)=\sum_{k,\theta,b}u_{\theta b}^k x_{\theta b}^k\)\ at least \(\kappa\).
Definitions. An instance has a finite type set \(\Theta\), rational masses \(\mu_\theta\ge0\) with \(\sum_\theta\mu_\theta=1\), templates \(k\) with roles \(b\), rational supplies \(\sigma_{k,b}\), and utilities \(u^\theta_{k,b}\). A feasible mass lottery consists of \(p_k\ge0\) and \(x_{k\theta b}\ge0\) such that \(\sum_b x_{k\theta b}=p_k\mu_\theta\), \(\sum_\theta x_{k\theta b}=p_k\sigma_{k,b}\), and \(\sum_k p_k=1\). For \(\mu_\theta>0\), let \(U_\theta(x)=\mu_\theta^{-1}\sum_{k,b}u^\theta_{k,b}x_{k\theta b}\) and \(U_\theta(x;\phi)=\mu_\phi^{-1}\sum_{k,b}u^\theta_{k,b}x_{k\phi b}\). Require \(U_\theta(x)\ge U_\theta(x;\phi)\) for all positive-mass \(\theta,\phi\), and Pareto-optimality among feasible mass lotteries with respect to \((U_\theta)_{\mu_\theta>0}\). Let \(W_\mu(x)=\sum_\theta\mu_\theta U_\theta(x)\).
Target. Is deciding whether such an \(x\) with \(W_\mu(x)\ge K\) exists NP-hard, or does it admit a polynomial-time algorithm?
Known results. For finite agents with partition-based utilities, deciding whether an ex-ante envy-free and Pareto-optimal allocation lottery of social welfare at least \(K\) exists is NP-complete.
Under the standard explicit rational encoding of templates, roles, masses, supplies, utilities, and \(K\), the decision problem is \(\mathrm{NP}\)-complete. In particular, it is \(\mathrm{NP}\)-hard even when every type has equal mass and every role has equal supply.
Thus it does not admit a polynomial-time algorithm unless \(\mathrm{P}=\mathrm{NP}\).
Consider the supplied finite-agent problem with agents \(N=[n]\), admissible partitions \(k\in[m]\), and \(n\) bundles \(b\in[n]\) in every partition. Let \(u^i_{k,b}\) be agent \(i\)'s utility for bundle \(b\) in partition \(k\).
A finite allocation lottery has succinct marginal variables \(p_k\) and \(q_{kib}\), where \(q_{kib}\) is the probability that partition \(k\) is selected and agent \(i\) receives bundle \(b\). They satisfy
\(\sum_b q_{kib}=p_k\), \(\sum_i q_{kib}=p_k\), and \(\sum_k p_k=1\).
The expected own and comparison utilities are
\(V_i(q)=\sum_{k,b}u^i_{k,b}q_{kib}\)
and
\(V_i(q;j)=\sum_{k,b}u^i_{k,b}q_{kjb}\).
Its social welfare is \(\operatorname{SW}(q)=\sum_iV_i(q)\). This is exactly the succinct lottery representation used in the finite partition-based model, whose welfare-threshold decision problem is \(\mathrm{NP}\)-complete by Theorem 5.1 of the [AAMAS 2024 paper](https://aamas.csc.liv.ac.uk/Proceedings/aamas2024/pdfs/p244.pdf).
Given a finite instance and threshold \(K_{\mathrm{fin}}\), construct the following mass instance:
For a finite lottery \((p,q)\), define
\(x_{kib}=q_{kib}/n\).
Then
\(\sum_bx_{kib}=(1/n)\sum_bq_{kib}=p_k/n=p_k\mu_i\),
and
\(\sum_ix_{kib}=(1/n)\sum_iq_{kib}=p_k/n=p_k\sigma_{k,b}\).
Hence \((p,x)\) is a feasible mass lottery.
Conversely, from a feasible mass lottery define
\(q_{kib}=n x_{kib}\).
The mass constraints imply
\(\sum_bq_{kib}=p_k\)
and
\(\sum_iq_{kib}=p_k\).
Thus \((p,q)\) satisfies the finite lottery constraints.
For completeness, these marginal constraints really do describe distributions over deterministic assignments. If \(p_k>0\), the matrix \(A^k\) defined by \(A^k_{ib}=q_{kib}/p_k\) is doubly stochastic. By the Birkhoff–von Neumann theorem, it is a convex combination of permutation matrices. Multiplying the corresponding coefficients by \(p_k\) gives a distribution over deterministic assignments in partition \(k\). If \(p_k=0\), nonnegativity and the marginal constraints force \(q_{kib}=0\).
Therefore the maps \(q\mapsto x=q/n\) and \(x\mapsto q=nx\) give an exact correspondence between the two feasible-lottery polytopes.
Because \(\mu_i=1/n\),
\(U_i(x)=n\sum_{k,b}u^i_{k,b}x_{kib}=\sum_{k,b}u^i_{k,b}q_{kib}=V_i(q)\).
Similarly, for every \(i,j\),
\(U_i(x;j)=n\sum_{k,b}u^i_{k,b}x_{kjb}=\sum_{k,b}u^i_{k,b}q_{kjb}=V_i(q;j)\).
Consequently,
\(U_i(x)\ge U_i(x;j)\)
holds exactly when
\(V_i(q)\ge V_i(q;j)\).
Thus the mass lottery is envy-free if and only if the corresponding finite lottery is ex-ante envy-free.
The correspondence preserves every coordinate of the own-utility vector:
\((U_i(x))_{i\in[n]}=(V_i(q))_{i\in[n]}\).
Moreover, it is surjective in both directions on feasible lotteries. Therefore a feasible mass lottery \(y\) Pareto-dominates \(x\) if and only if its corresponding finite lottery Pareto-dominates the finite lottery corresponding to \(x\).
Hence \(x\) is Pareto-optimal among feasible mass lotteries if and only if \(q\) is ex-ante Pareto-optimal among finite allocation lotteries.
This is the critical point: splitting a type of mass \(1/n\) does not introduce utility vectors unavailable to the finite lottery. It merely records that finite agent's assignment probabilities.
The mass welfare is
\(W_\mu(x)=\sum_i\mu_iU_i(x)=\frac1n\sum_iV_i(q)=\frac1n\operatorname{SW}(q)\).
It follows that
\(W_\mu(x)\ge K_{\mathrm{fin}}/n\)
if and only if
\(\operatorname{SW}(q)\ge K_{\mathrm{fin}}\).
The construction is polynomial-time: only the rational numbers \(1/n\) and \(K_{\mathrm{fin}}/n\) are introduced.
Thus the finite instance is a yes-instance if and only if the constructed mass instance is a yes-instance. This proves \(\mathrm{NP}\)-hardness.
Given a rational candidate \((p,x)\), feasibility, envy-freeness, and the welfare threshold are checkable by exact rational arithmetic.
Pareto-optimality can also be checked in polynomial time. Let \(\Theta^+=\{\theta:\mu_\theta>0\}\), and solve the linear program
\(\max_y\sum_{\theta\in\Theta^+}U_\theta(y)\)
subject to \(y\) being a feasible mass lottery and
\(U_\theta(y)\ge U_\theta(x)\) for every \(\theta\in\Theta^+\).
The candidate \(x\) itself is feasible for this linear program. Hence \(x\) is Pareto-optimal exactly when its optimum equals \(\sum_{\theta\in\Theta^+}U_\theta(x)\): a larger optimum is equivalent to weak improvement in every coordinate and strict improvement in at least one coordinate.
It remains to justify that every yes-instance has a polynomial-size rational witness. Let \(P\) be the rational feasible-lottery polytope and let \(C=U(P)\) be its utility polytope. Suppose a possibly real witness \(x^\ast\) exists, and let \(G\) be the minimal face of \(C\) containing \(U(x^\ast)\). Then \(U(x^\ast)\) lies in the relative interior of \(G\).
Every point of \(G\) is Pareto-optimal. Indeed, suppose \(g\in G\) were dominated by \(v\in C\). Relative interiority gives some \(\varepsilon>0\) such that
\(h=U(x^\ast)+\varepsilon(U(x^\ast)-g)\in G\).
With \(\alpha=\varepsilon/(1+\varepsilon)\), convexity gives
\((1-\alpha)h+\alpha v=U(x^\ast)+\alpha(v-g)\in C\),
which would Pareto-dominate \(U(x^\ast)\), a contradiction.
Because \(G\), \(P\), and all envy and threshold constraints are rational polyhedral, their nonempty intersection has a rational basic feasible point of polynomial encoding length. Its utility lies in \(G\), and is therefore Pareto-optimal. Thus a polynomial-size certificate always exists.
The problem is consequently in \(\mathrm{NP}\), completing the \(\mathrm{NP}\)-completeness proof.
⟨structured verdict parsed — rendered above⟩
The reduction correctly establishes \(\mathrm{NP}\)-hardness. The claimed \(\mathrm{NP}\)-membership is sound in substance, but its polynomial-size-certificate argument contains a small, technically relevant polyhedral encoding gap.
Accordingly, the proof is best classified as proved with minor gaps. The target question is resolved: the mass problem is \(\mathrm{NP}\)-hard, so it cannot have a polynomial-time algorithm unless \(\mathrm{P}=\mathrm{NP}\).
The cited theorem states that, for partition-based utilities and \(K>0\), deciding the existence of an ex-ante envy-free, Pareto-optimal lottery with social welfare at least \(K\) is \(\mathrm{NP}\)-complete. This agrees with the known result supplied in the task and with [Theorem 5.1 of the cited paper](https://aamas.csc.liv.ac.uk/Proceedings/aamas2024/pdfs/p244.pdf).
The finite marginal constraints written by the prover also match the paper’s succinct representation:
The source theorem assumes \(K>0\). This is sufficient for the reduction and therefore does not restrict the target problem’s hardness.
The scaling \(x_{kib}=q_{kib}/n\) is correct.
For each \(i,k\),
\[ \sum_b x_{kib} = \frac1n\sum_b q_{kib} = \frac{p_k}{n} = p_k\mu_i. \]
For each \(k,b\),
\[ \sum_i x_{kib} = \frac1n\sum_i q_{kib} = \frac{p_k}{n} = p_k\sigma_{k,b}. \]
The inverse scaling \(q_{kib}=nx_{kib}\) recovers the finite marginal constraints. Nonnegativity and \(\sum_kp_k=1\) are preserved.
The Birkhoff–von Neumann application is valid: when \(p_k>0\), \(q_{kib}/p_k\) is a nonnegative square matrix whose row and column sums are one. When \(p_k=0\), the row-sum constraints and nonnegativity indeed force every \(q_{kib}=0\).
Thus the correspondence between feasible finite lotteries and feasible mass lotteries is exact.
With \(\mu_i=1/n\), both own utility and comparison utility are preserved exactly:
\[ U_i(x)=V_i(q),\qquad U_i(x;j)=V_i(q;j). \]
Consequently, every envy inequality in one formulation is identical to the corresponding inequality in the other formulation. This step is correct.
The correspondence is bijective on feasible marginal lotteries and preserves the complete own-utility vector coordinatewise. Therefore Pareto domination exists on one side exactly when it exists on the other side.
The conclusion that Pareto-optimality is preserved is correct. No additional assumption about envy-freeness is improperly introduced into the Pareto comparison.
The calculation
\[ W_\mu(x) = \frac1n\sum_iV_i(q) = \frac1n\operatorname{SW}(q) \]
is correct. Hence choosing \(K_{\mathrm{mass}}=K_{\mathrm{fin}}/n\) preserves yes-instances and no-instances.
The introduced rational numbers have polynomial encoding length. The reduction therefore proves \(\mathrm{NP}\)-hardness, including under equal masses and equal role supplies.
For a rational candidate \((p,x)\), feasibility, envy-freeness and the welfare threshold are systems of rational linear equalities or inequalities and are polynomial-time checkable.
The proposed Pareto-optimality linear program is also correct. Under the constraints \(U_\theta(y)\ge U_\theta(x)\), its objective exceeds \(\sum_\theta U_\theta(x)\) exactly when at least one coordinate is strictly improved. Exact rational linear programming permits polynomial-time comparison of the optimum with the stated rational value.
The geometric part of the argument is correct:
\[ (1-\alpha)h+\alpha v = U(x^\ast)+\alpha(v-g). \]
Thus every point of \(G\) is Pareto-optimal.
There are nevertheless two related expositional gaps:
These are minor because they concern a standard polyhedral bit-complexity justification rather than a new mathematical idea, but they are necessary to make the \(\mathrm{NP}\)-membership argument fully verifiable.
The \(\mathrm{NP}\)-hardness reduction is rigorous and complete. The stronger \(\mathrm{NP}\)-completeness claim is mathematically credible and sound in substance, subject only to the stated polynomial-bit-complexity clarification.
⟨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.