Answer: \(\mathrm{NP}\)-complete, already for \(K=0\).
Theorem 8 (OPTIMISATION) — class: other
PDF text-layer excerpt — equations and symbol order may be approximateLet Θ be a MARA Setting with preferences in one of bundle, k-additive, logic based or weighted goals form. Let ΠΘ P ref be defined according to the table above, and ΠΘ G, ΠEF od, and ΠEF om as before. Then: • for each allocation M ∈M Θ : ∄M ′ ∈M Θ, envy (M ′) < envy (M) there is an answer set S ∈AS(ΠΘ G ∪ΠΘ P ref ∪ΠEF od ∪ ΠEF om) such that has(a,r,o)∈S iff r ∈M (a). • for each answer set S ∈AS(ΠΘ G∪ΠΘ P ref ∪ΠEF od∪ΠEF om) there is an allocation M ∈M Θ such that has(a,r,o)∈S iff r ∈M (a) and ∄M ′ ∈M Θ, envy (M ′) < envy (M). 5.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite resource set \(R\), complete utility types \(t\in\mathcal{T}\) with rational shares \(\mu_t\), per-capita supplies \(q_r\in\mathbb{Q}\cap[0,1]\), and utilities \(u_t:2^R\to\mathbb{Q}\), choose masses \(x_{tB}\ge 0\) for \(t\in\mathcal{T}\) and integral bundles \(B\subseteq R\), subject to \(\sum_{B\subseteq R}x_{tB}=\mu_t\) and \(\sum_{t\in\mathcal{T}}\sum_{B:r\in B}x_{tB}=q_r\) for every \(r\in R\). Find a feasible \(x\) minimizing \(\sum_{t,B}\sum_{s,C}x_{tB}x_{sC}[u_t(C)-u_t(B)]_+\), where \([z]_+=\max\{0,z\}\).
Let \(R\) be a resource set with \(m\geq 1\). A society is given by its support: the list of its \(\tau\geq 1\) utility types with positive masses \(\mu_t\), each a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) counts supported types, not all possible types.
Each type has an explicitly listed complete utility table \(u_t:2^R\to\mathbb{Q}\), with binary rational entries; no monotonicity or normalization is assumed. Supplies are binary rationals \(q_r\in[0,1]\). Let \(L\) be the total input bit length, including these tables and a threshold \(K\in\mathbb{Q}_{\geq 0}\).
An allocation assigns real masses \(x_{tB}\geq 0\) to integral bundles \(B\subseteq R\), including the empty bundle, satisfying \(\sum_{B\subseteq R}x_{tB}=\mu_t\) and \(\sum_t\sum_{B\subseteq R:r\in B}x_{tB}=q_r\) for every resource. Thus every resource's supply is fully allocated, and each individual receives at most one unit of each resource.
Define total envy by \(E(x)=\sum_{t,s}\sum_{B,C\subseteq R}x_{tB}x_{sC}\max\{0,u_t(C)-u_t(B)\}\). Comparisons include individuals of the same type; utility ties contribute zero.
Is deciding whether a feasible allocation satisfies \(E(x)\leq K\) in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? State running times in \(m,\tau,L\).
For finite agents and fully allocated indivisible resources, a sound and complete answer-set encoding characterizes allocations minimizing the sum of positive pairwise utility differences; this is an encoding result, not a polynomial-time guarantee ([Leite, Alferes and Mito](https://www.ifaamas.org/Proceedings/aamas2009/pdf/01_Full%20Papers/11_25_139_FP_0134.pdf)).
Polynomial-time algorithms exist for interim envy-free lotteries in matching instances, a different fairness condition and feasible space ([Caragiannis, Kanellopoulos and Kyropoulou](https://repository.essex.ac.uk/30538/23/On_Interim_Envy_Free_Allocation_Lotteries.pdf)). No result settling the exact mass-based objective above was located.
I interpret the question as asking whether there exists a feasible allocation \(x\) with \(E(x)\leq K\).
This decision problem is \(\mathrm{NP}\)-complete. Hardness already holds for \(K=0\), with distinct utility values within each type, nonnegative integer utilities, and dyadic masses and supplies. The reduction uses \(m=O(\log\tau)\), so its complete utility tables have polynomial size.
A general exact algorithm runs in \(2^{\tau2^m}\operatorname{poly}(L)\) time. For \(K=0\), an algorithm runs in \(2^{2^m}\operatorname{poly}(L)\) time. The case \(m=1\) is polynomial-time solvable.
Call a type’s utility table *injective* if different bundles have different utility values.
Lemma 1. If every supported type has an injective utility table and \(E(x)=0\), then each type assigns its entire mass to one bundle.
Proof. Every summand defining \(E(x)\) is nonnegative. Suppose a type \(t\) assigns positive masses to distinct bundles \(B,C\). Injectivity implies that, after interchanging their names if necessary, \(u_t(C)>u_t(B)\). The same-type comparison contributes
\[ x_{tB}x_{tC}\bigl(u_t(C)-u_t(B)\bigr)>0, \]
contradicting \(E(x)=0\). Consequently, exactly one bundle has positive mass for type \(t\), and its mass is \(\mu_t\). \(\square\)
The inclusion of same-type comparisons is essential to this argument.
The reduction will encode several simultaneous constraints in the binary representations of the masses.
Lemma 2. Let \(w_0,\ldots,w_{n-1}\) be positive integers, \(W=\sum_i w_i\), and \(H=W+1\). Suppose \(a_i,b_i\in\{0,1\}\), \(c_i\in\{0,1,2\}\), and \(0\leq e\leq W\). If
\[ \sum_i\bigl((H5^i+w_i)a_i+H5^i b_i\bigr) = H\sum_i5^ic_i+e, \]
then \(a_i+b_i=c_i\) for every \(i\), and \(\sum_iw_i a_i=e\).
Proof. Rearranging gives
\[ H\sum_i5^i(a_i+b_i-c_i)+\left(\sum_iw_i a_i-e\right)=0. \]
The parenthesized expression is an integer whose absolute value is at most \(W<H\). Since it is a multiple of \(H\), it must be zero. Therefore
\[ \sum_iw_i a_i=e, \qquad \sum_i5^i(a_i+b_i-c_i)=0. \]
Each coefficient in the second equality belongs to \(\{-2,-1,0,1,2\}\). Reduction modulo \(5\) forces its first coefficient to be zero. Dividing by \(5\) and repeating forces all coefficients to be zero. \(\square\)
We reduce from the standard \(\mathrm{NP}\)-complete problem SUBSET SUM with positive integer weights \(w_0,\ldots,w_{n-1}\) and an integer target \(T\), where \(0\leq T\leq W=\sum_iw_i\). The question is whether some \(S\subseteq\{0,\ldots,n-1\}\) satisfies \(\sum_{i\in S}w_i=T\).
Let \(\ell=\lceil\log_2 n\rceil\), and choose distinct codes \(c_i\in\{0,1\}^{\ell}\). For \(n=1\), the sole code is empty.
There are \(\ell\) address resources \(r_1,\ldots,r_\ell\), a tag resource \(r_{\mathrm{tag}}\), and a selection resource \(r_{\mathrm{sel}}\). Thus
\[ m=\ell+2, \qquad N=2^m=4\cdot2^\ell\leq8n. \]
For each item \(i\), tag \(a\in\{0,1\}\), and selection bit \(v\in\{0,1\}\), define \(B_{i,a,v}\) as follows:
These distinguished bundles are all different.
Set
\[ H=W+1,\qquad \alpha_i=H5^i+w_i,\qquad \beta_i=H5^i, \qquad D_0=\sum_i(\alpha_i+\beta_i). \]
Choose a power of two \(D>2D_0\), and set \(\gamma=D-D_0\). In particular, \(\gamma>D_0\).
For each item \(i\), create two types \((i,1)\) and \((i,0)\), with masses
\[ \mu_{i,1}=\frac{\alpha_i}{D}, \qquad \mu_{i,0}=\frac{\beta_i}{D}. \]
Create one additional type \(*\), with mass \(\mu_*=\gamma/D\). All masses are positive dyadic rationals, their sum is one, and the number of supported types is exactly \(\tau=2n+1\).
Fix a bijection \(h:2^R\to\{0,\ldots,N-1\}\), with \(h(\varnothing)=0\).
For type \((i,a)\), assign
\[ u_{i,a}(B_{i,a,0})=N, \qquad u_{i,a}(B_{i,a,1})=N+1. \]
At every other bundle \(B\), assign \(u_{i,a}(B)=h(B)\).
For the additional type, assign \(u_*(\varnothing)=N+1\), and \(u_*(B)=h(B)\) at every nonempty bundle.
Every table is injective. For each ordinary type, both distinguished bundles have higher utility than every other bundle. The tables contain only nonnegative integers at most \(N+1\).
Set \(K=0\). For each address coordinate \(j\), set
\[ q_{r_j} = \frac{\sum_i(\alpha_i+\beta_i)c_{ij}}{D}. \]
Set the remaining supplies to
\[ q_{\mathrm{tag}}=\frac{\sum_i\alpha_i}{D} = \frac{H\sum_i5^i+W}{D}, \qquad q_{\mathrm{sel}}=\frac{H\sum_i5^i+T}{D}. \]
Every supply numerator lies between zero and \(D_0\). Hence the supplies are dyadic rationals in \([0,1]\), and, for every resource \(r\),
\[ q_r\leq\frac{D_0}{D}<\frac{\gamma}{D}=\mu_*. \]
Suppose a feasible allocation has \(E(x)\leq0\). Nonnegativity gives \(E(x)=0\), and Lemma 1 makes every type’s allocation deterministic.
The additional type must receive the empty bundle: receiving any resource \(r\) would allocate at least \(\mu_*>q_r\) units of that resource, violating feasibility.
For an address resource \(r_j\), let \(a_i,b_i\) indicate whether the bundles assigned to types \((i,1)\) and \((i,0)\), respectively, contain that resource. Its supply equality becomes
\[ \sum_i(\alpha_i a_i+\beta_i b_i) = H\sum_i5^i(2c_{ij})+\sum_iw_ic_{ij}. \]
Lemma 2 implies \(a_i+b_i=2c_{ij}\). Since both indicators are binary, both equal \(c_{ij}\). Thus both types belonging to item \(i\) receive the correct address.
For the tag resource, Lemma 2 gives
\[ a_i+b_i=1\quad\text{for every }i, \qquad \sum_iw_i a_i=W. \]
Because every \(w_i\) is positive, the second equality forces every \(a_i=1\). Consequently, type \((i,1)\) receives the tag resource, and type \((i,0)\) does not.
For the selection resource, Lemma 2 gives
\[ a_i+b_i=1\quad\text{for every }i, \qquad \sum_iw_i a_i=T. \]
Therefore the items whose type \((i,1)\) receives the selection resource form a subset summing to \(T\).
Conversely, suppose \(S\) satisfies \(\sum_{i\in S}w_i=T\). Let \(s_i\) be its membership indicator. Allocate:
The address and tag supplies hold by construction. The selection-resource numerator is
\[ \sum_i\bigl(\alpha_i s_i+\beta_i(1-s_i)\bigr) = H\sum_i5^i+\sum_iw_is_i = H\sum_i5^i+T. \]
Thus every supply is fully allocated.
Each ordinary type receives one of its two distinguished bundles. Bundles assigned to other ordinary types have different addresses or tags, so their utilities are at most \(N-1\).
The additional type’s empty bundle also causes no envy. If it is a distinguished bundle of an ordinary type, it is that type’s selection-bit-zero bundle, with utility \(N\); the assigned distinguished bundle has utility \(N\) or \(N+1\). Otherwise, the empty bundle has utility at most \(N-1\). The additional type itself receives its unique favorite bundle.
Every positive utility difference in the envy objective is therefore zero. Hence \(E(x)=0\).
The construction has
\[ \tau=2n+1,\qquad m=\lceil\log_2 n\rceil+2,\qquad 2^m=O(n). \]
Consequently, all complete utility tables together have \(O(n^2)\) entries, each using \(O(\log(n+1))\) bits.
The masses and supplies use \(O(n+\log(W+1))\) bits each. The output length is polynomial in the original binary SUBSET SUM input length, and all quantities can be computed in polynomial time.
This proves \(\mathrm{NP}\)-hardness under the stated explicit-table representation, already for \(K=0\).
The real allocation variables do not prevent membership in \(\mathrm{NP}\): every yes-instance has a rational witness of polynomial bit length. Here is a direct proof of that fact for this problem; general quadratic-programming membership in \(\mathrm{NP}\) was established by [Vavasis (1990)](https://doi.org/10.1016/0020-0190(90)90100-C).
Let \(d=\tau2^m\), and write the feasible set as
\[ P=\{x\in\mathbb{R}^d:Ax=b,\ x\geq0\}. \]
Here \(A\) encodes the type-mass and resource-supply equalities.
The set is nonempty: assigning each type mass according to the same product distribution of independent resource inclusions, with inclusion probabilities \(q_r\), satisfies every equality. It is compact because \(0\leq x_{tB}\leq\mu_t\).
Write \(E(x)=x^{\mathsf T}Qx\), with \(Q\) symmetric and rational. Its coefficients have polynomial encoding length. Thus \(E\) attains a minimum at some \(x^*\in P\).
Let \(S\) be the positive-coordinate support of \(x^*\). Restrict the constraint matrix and quadratic matrix to this support, writing them as \(A_S,Q_{SS}\). Choose a rational matrix \(V\) whose columns form a basis of \(\ker A_S\).
Every direction in \(\ker A_S\) permits sufficiently small perturbations of both signs around the strictly positive vector \(x^*_S\). First-order optimality therefore gives
\[ V^{\mathsf T}Q_{SS}x^*_S=0. \]
Consider the rational polytope
\[ H_S= \{z\geq0:A_Sz=b,\ V^{\mathsf T}Q_{SS}z=0\}. \]
It is nonempty and bounded. Moreover, the quadratic objective is constant on \(H_S\). Indeed, for \(z,w\in H_S\), the vector \(v=z-w\) belongs to \(\ker A_S\). The stationarity equalities imply \(v^{\mathsf T}Q_{SS}z=v^{\mathsf T}Q_{SS}w=0\). Symmetry then gives
\[ z^{\mathsf T}Q_{SS}z-w^{\mathsf T}Q_{SS}w = v^{\mathsf T}Q_{SS}(z+w)=0. \]
A rational vertex of \(H_S\) has polynomial bit length: rational nullspace computation has polynomial bit complexity, and vertex coordinates satisfy the usual determinant bounds for rational linear systems. Extending such a vertex by zeros gives a rational feasible allocation attaining the global minimum.
Thus any yes-instance has a polynomial-size rational allocation certificate. Its feasibility and objective value can be checked by exact rational arithmetic in polynomial time. The problem belongs to \(\mathrm{NP}\), completing the proof of \(\mathrm{NP}\)-completeness.
Enumerate all supports \(S\subseteq\{1,\ldots,d\}\). For each support, construct \(H_S\) as above and test its feasibility by rational linear programming. If feasible, evaluate the objective at any rational point of \(H_S\).
Every candidate is feasible for the original problem. The support of a global minimizer produces a candidate attaining the global minimum. Each iteration takes \(\operatorname{poly}(L)\) time, giving the bound
\[ 2^{\tau2^m}\operatorname{poly}(L). \]
Unless \(\mathrm{P}=\mathrm{NP}\), there is no general algorithm polynomial in \(L\).
For \(K=0\), enumerate nonempty sets \(S\subseteq2^R\). For each type, allow allocation only to bundles maximizing its utility over \(S\), and test the resulting linear feasibility system.
Any feasible solution has zero envy, since no assigned bundle is worse, for its recipient, than any bundle in \(S\).
Conversely, if an allocation has zero envy, take \(S\) to be its globally used bundles. Every bundle assigned to a type must maximize that type’s utility over \(S\): otherwise a positive mass of that type envies a globally used bundle, producing a positive summand.
This gives an exact running time of
\[ 2^{2^m}\operatorname{poly}(L). \]
In particular, zero-envy feasibility is polynomial-time solvable for each fixed \(m\).
Let \(p_t=x_{t,\{r\}}\), \(q=q_r\), and \(\delta_t=u_t(\{r\})-u_t(\varnothing)\). Write \(\delta_t^+=\max\{0,\delta_t\}\) and \(\delta_t^-=\max\{0,-\delta_t\}\).
The total masses receiving the resource and the empty bundle are fixed at \(q\) and \(1-q\), respectively. Therefore
\[ E(x) = q\sum_t\delta_t^+(\mu_t-p_t) + (1-q)\sum_t\delta_t^-p_t. \]
This is a linear objective in \(p_t\), subject to \(0\leq p_t\leq\mu_t\) and \(\sum_tp_t=q\).
Sort the coefficients \((1-q)\delta_t^- -q\delta_t^+\) and fill the available masses in increasing coefficient order. An exchange from a larger coefficient to a smaller one never increases the objective, proving optimality of this procedure.
It uses \(O(\tau\log\tau)\) rational comparisons and polynomial bit time in \(L\).
⟨structured verdict parsed — rendered above⟩
The output resolves the intended existential decision problem. The reduction, membership-in-\(\mathrm{NP}\) argument, and algorithms are sound. I found one minor clarification concerning the size of the denominator chosen in the reduction. No major issue or false central step was found.
The appropriate classification is proved with minor gaps: the claimed \(\mathrm{NP}\)-completeness stands in substance.
The prover explicitly interprets the question as asking whether there exists a feasible allocation with \(E(x)\leq K\). This matches the intended decision problem.
Lemma 1 is correct. Every summand of \(E(x)\) is nonnegative. If two distinct bundles have positive mass within an injective type, one ordered same-type comparison has both a positive mass product and a strictly positive utility difference. Consequently, zero envy prohibits such a pair. The positive type mass and its mass equality then force exactly one assigned bundle.
The proof correctly relies on comparisons within the same type. It does not assume monotonicity, normalization, or integral allocation masses.
Lemma 2 is correct, including its bounds.
Because the weights are positive and the indicators are binary,
\(\sum_i w_i a_i\) lies in \([0,W]\). Thus
\(\left|\sum_i w_i a_i-e\right|\leq W<H\).
The displayed equality makes this integer a multiple of \(H\), so it must vanish.
The remaining coefficients \(a_i+b_i-c_i\) belong to
\(\{-2,-1,0,1,2\}\). Among these integers, only zero is divisible by \(5\). Successive reduction modulo \(5\) and division therefore force every coefficient to vanish. There is no unhandled carry or cancellation.
The resource and bundle construction is valid. Different item codes, tags, or selection bits distinguish the specified bundles. The case \(n=1\) is explicitly covered by the empty address code.
The count \(2^m=4\cdot2^\ell\leq8n\) holds for every \(n\geq1\). Together with \(\tau=2n+1\), this supports the claimed logarithmic dependence of \(m\) on \(\tau\).
All masses are positive, sum to one, and are dyadic. Every supply is nonnegative and at most \(D_0/D<1\). The selection numerator satisfies the same bound because \(0\leq T\leq W\).
The ordinary utility tables are injective: their two exceptional values are distinct and exceed every remaining value of \(h\). The additional table is also injective, and its empty bundle is its unique favorite. Every utility entry is a permitted nonnegative integer.
The restricted SUBSET SUM source problem is appropriate. Positive weights and targets in \([0,W]\) retain the standard hardness; targets outside that interval are immediately negative instances.
The soundness argument checks out.
Thus the indicated selected items constitute a valid subset-sum solution. Each invocation of Lemma 2 satisfies its stated hypotheses.
The proposed allocation satisfies the mass equalities. Its address and tag incidences give the prescribed supplies, and the displayed selection calculation is correct.
The envy argument covers all relevant comparisons:
In particular, receiving the lower-valued distinguished bundle causes no omitted comparison with the unassigned higher-valued bundle: the objective compares only bundles carrying allocation mass.
Where: “Choose a power of two \(D>2D_0\)” and the subsequent reduction-size claim.
Issue: The inequality alone places no upper bound on the bit length of \(D\). An arbitrarily large permitted power of two need not satisfy the stated encoding bound.
Minimum clarification: Specify that \(D\) is the least power of two exceeding \(2D_0\), or explicitly require a polynomial bit-length bound for its choice.
This is a minor construction-detail omission. It requires no change to the arithmetic, feasibility, or envy arguments.
Subject to that clarification, the utility-table entry counts, utility bit lengths, and mass and supply encoding bounds establish a polynomial-size reduction.
The rational-witness argument is correct.
The common product distribution proves nonemptiness for all permitted supplies, including boundary values zero and one. The type equalities bound every coordinate, so the feasible set is compact. The rational quadratic objective therefore attains a minimum.
On the positive-coordinate support of a minimizer, every kernel direction admits sufficiently small feasible perturbations of both signs. Hence the stated first-order stationarity equality is justified; the omitted derivative factor of two is immaterial.
The auxiliary set \(H_S\) contains the minimizer’s restriction and is bounded by the type-mass equalities. Its objective-constancy calculation is valid: differences of its points lie in the constraint kernel, both points satisfy stationarity, and symmetry supplies the displayed identity. No convexity or positive-semidefiniteness assumption is needed.
The polynomial certificate-size claim correctly uses standard rational linear-algebra bounds. The explicit tables ensure that \(d=\tau2^m\) is polynomially bounded by \(L\). The nullspace basis, auxiliary system, and vertex coordinates consequently have polynomial encoding length. Extending a vertex by zeros produces a feasible rational global minimizer.
Exact verification of its constraints and quadratic objective takes polynomial bit time. This establishes membership in \(\mathrm{NP}\).
The cited [Vavasis paper](https://www.sciencedirect.com/science/article/pii/002001909090100C) supports the historical attribution, but the proof does not depend on importing its theorem: the output supplies its own argument.
The support-enumeration algorithm is correct. Every point found in an \(H_S\) is feasible for the original allocation problem, and the support of a global minimizer supplies a candidate with the global minimum value.
There is no need to reject nonminimal stationary candidates: they are feasible allocations, so they cannot have an objective below the global minimum.
Each auxiliary rational linear system has polynomial encoding size in \(L\), and rational linear programming supplies a polynomial-size feasible point when one exists. The bound
\(2^{\tau2^m}\operatorname{poly}(L)\) follows.
Both directions of the characterization are correct.
Restricting each type to maximizers over \(S\) ensures that it never envies any assigned bundle. Conversely, if a positively assigned bundle fails to maximize utility over the globally used bundles, comparison with a positively used better bundle yields a strictly positive summand.
Positive total population guarantees that the globally used set is nonempty. The enumeration therefore covers every zero-envy solution, including solutions with utility ties. The bound
\(2^{2^m}\operatorname{poly}(L)\), and its polynomial-time consequence for fixed \(m\), are valid.
The objective formula correctly aggregates comparisons against resource recipients of total mass \(q\) and empty-bundle recipients of total mass \(1-q\), including same-type comparisons.
The resulting objective is linear in the variables \(p_t\). Filling their capacities in increasing coefficient order is justified by the stated exchange argument. Ties and the boundary supplies \(q=0\) and \(q=1\) cause no failure.
The claimed \(O(\tau\log\tau)\) rational comparisons and polynomial bit time in \(L\) are valid.
The prover establishes the intended hardness classification, membership in \(\mathrm{NP}\), and the stated algorithmic bounds. The only requested revision is to make the polynomial-size choice of \(D\) explicit.
⟨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.