Answer: \(\mathrm{NP}\)-complete
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateDetermining whether a given instance admits an EFX and rank-maximal allocation is NP- complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite goods categories \(M\), complete-ranking types \(T\), rational masses \(\mu_t\) with \(\sum_t\mu_t=1\), and rational per-capita supplies \(\rho_g\), decide whether there exist masses \(x_{t,B}\ge0\) over integral bundles \(B\subseteq M\) satisfying \(\sum_Bx_{t,B}=\mu_t\) and \(\sum_{t,B:g\in B}x_{t,B}=\rho_g\), such that every positive-support pair satisfies EFX and \(R_j(x)=\sum_{t,B}x_{t,B}\mathbf{1}[g_j(t)\in B]\) is lexicographically maximal among feasible allocations.
Let \(M\) be a set of \(m\geq1\) goods categories. Each type \(t\) is a strict complete ranking of \(M\), extended lexicographically to bundles; write \(\succeq_t\) for its weak bundle preference and \(g_j(t)\) for its good at rank \(j\).
A society is given by its support: the list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings. Supplies \(\rho_g\) are binary rationals satisfying \(0<\rho_g\leq1\); let \(L\) be the total input bit length.
A feasible allocation consists of real masses \(x_{t,B}\geq0\) for \(t\in T\) and integral bundles \(B\subseteq M\), including the empty bundle, satisfying \(\sum_{B\subseteq M}x_{t,B}=\mu_t\) and \(\sum_{t,B:g\in B}x_{t,B}=\rho_g\). Bundles contain at most one unit of each category; all supplies must be allocated.
It is EFX if, for every ordered pair \((t,B),(u,C)\) with \(x_{t,B}>0\) and \(x_{u,C}>0\), and every \(g\in C\), one has \(B\succeq_t C\setminus\{g\}\). This includes comparisons within a type.
Define \(R_j(x)=\sum_{t,B}x_{t,B}\mathbf{1}[g_j(t)\in B]\). An allocation is rank-maximal if \((R_1(x),\ldots,R_m(x))\) is lexicographically maximal over all feasible allocations, without imposing EFX on the benchmark.
Is deciding whether an EFX and rank-maximal allocation exists solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finitely many agents and distinct indivisible goods, existence of an EFX and rank-maximal allocation under strict lexicographic preferences is NP-complete. [Hosseini–Sikdar–Vaish–Xia](https://doi.org/10.1609/aaai.v35i6.16689)
Related continuous work studies envy-freeness and Pareto efficiency for divisible shares, rather than EFX between supported integral bundles. [Schulman–Vazirani](https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.543) No result settling exactly the problem above was located.
The decision problem is \(\mathrm{NP}\)-complete, even when all types have the same dyadic mass and every good has supply equal to that mass.
The reduction adapts the signature-and-dummy construction of [Hosseini–Sikdar–Vaish–Xia](https://doi.org/10.1609/aaai.v35i6.16689). The essential additional argument proves that arbitrary splitting of population masses cannot activate both signs of a variable.
Write \(r_t(g)\) for the rank of good \(g\) under type \(t\), and define its allocation marginal by
\[ y_{t,g}:=\sum_{B:g\in B}x_{t,B}. \]
The feasible marginal vectors are exactly those satisfying
\[ 0\leq y_{t,g}\leq\mu_t, \qquad \sum_t y_{t,g}=\rho_g. \]
Necessity follows directly from allocation feasibility. For sufficiency, put \(p_{t,g}=y_{t,g}/\mu_t\) and define
\[ x_{t,B} = \mu_t \prod_{g\in B}p_{t,g} \prod_{g\notin B}(1-p_{t,g}). \]
Summing this product distribution over all bundles gives mass \(\mu_t\); summing over bundles containing \(g\) gives marginal \(y_{t,g}\). Thus these marginals are realizable, including when some probabilities equal zero or one.
For each good and rank, define
\[ c_{g,j}:=\sum_{t:r_t(g)=j}\mu_t. \]
The lexicographically optimal allocation of the supply of \(g\) fills these capacities in increasing rank order. Its aggregate mass at rank \(j\) is
\[ a_{g,j} = \min\left\{ c_{g,j}, \max\left\{0,\rho_g-\sum_{k<j}c_{g,k}\right\} \right\}. \]
Indeed, after the earlier ranks have been maximized, rank \(j\) can receive at most its capacity and the remaining supply. This bound is attainable by assigning that much mass among the types at rank \(j\).
Consequently, the optimal rank signature is
\[ R_j^*=\sum_g a_{g,j}. \]
To justify that optimizing each good separately optimizes their sum, let \(z_{g,j}\) be the rank aggregates of any feasible marginal allocation. Each vector \(z_g\) is lexicographically at most \(a_g\). If any differs, take the earliest coordinate at which any differs. At that coordinate every difference \(a_g-z_g\) is nonnegative, and at least one is positive; all earlier differences vanish. Hence \(\sum_g z_g\) is strictly lexicographically below \(\sum_g a_g\).
In particular:
Minimum-rank observation. Suppose every type has mass \(q\) and every good has supply \(q\). An allocation is rank-maximal exactly when each good is assigned exclusively to types ranking it highest among the support.
For each good, at least one highest-ranking type has enough capacity to receive its whole supply. Thus its optimal rank vector places mass \(q\) at that minimum rank and zero at all other ranks.
The preceding formula computes \(R^*\) in polynomial time using rational arithmetic.
Suppose a feasible EFX allocation with signature \(R^*\) exists. Restrict attention to its supported type-bundle pairs. On these columns impose:
This is a system \(Az=b\), \(z\geq0\), with at most \(d:=\tau+2m\) rows and entries of \(A\) in \(\{0,1\}\).
Choose a feasible solution having the smallest number of positive coordinates. Its positive columns are linearly independent. Otherwise, a nonzero dependence among them gives a direction preserving all equalities. Choosing its sign so that some coordinate decreases, and moving until the first coordinate becomes zero, preserves nonnegativity and reduces the support, a contradiction. Therefore the solution has at most \(d\) positive coordinates.
Its masses have polynomial rational encoding length. To see this explicitly, let \(Q\) be the product of the denominators of the input masses and supplies. Then \(\log Q\leq L\), and every coordinate of \(b\), including \(R_j^*\), is an integer multiple of \(1/Q\). Select a nonsingular square submatrix on the independent columns. Cramer’s rule and Hadamard’s determinant bound give encoding length \(O(L+d\log d)\) for each resulting mass.
The new support is a subset of the original support, so EFX is preserved: deleting supported pairs cannot introduce a violating comparison.
A certificate therefore lists at most \(\tau+2m\) type-bundle pairs and polynomially encoded rational masses. Feasibility, equality with \(R^*\), and every required EFX comparison can all be checked in polynomial time. This proves membership in \(\mathrm{NP}\).
Let a \(\mathrm{3SAT}\) instance have variables \(X_1,\ldots,X_n\) and nonempty clauses \(C_1,\ldots,C_s\). Choose the smallest power of two
\[ r\geq\max\{n,s,2\}, \]
and add unused variables through \(X_r\). This padding preserves satisfiability and is polynomial in size.
For a sign \(\sigma\in\{+,-\}\), let \(X_i^\sigma\) denote \(X_i\) or \(\neg X_i\), respectively.
Create four types per variable:
\[ \ell_i^+,\quad \ell_i^-,\quad d_i^+,\quad d_i^-. \]
The \(\ell_i^\sigma\) are literal types and the \(d_i^\sigma\) are dummy types. Every type has mass
\[ q:=\frac1{4r}. \]
Create the following goods:
Every good has supply \(q\). Thus \(\tau=4r\), \(m=4r+s\), the type masses sum to one, and all masses and supplies are dyadic rationals.
Fix a reference order consisting of all signature goods, then all top dummy goods, then \(c_1,\ldots,c_s\), then all bottom dummy goods.
Type \(\ell_i^\sigma\) ranks \(s_i^\sigma\) first.
For each \(j\in\{1,\ldots,s\}\), its position \(j+1\) contains:
There are enough filler signatures because \(s\leq r\leq2r-1\). Append all remaining goods in reference order.
This defines a strict complete ranking. Every incident clause good \(c_j\) has rank \(j+1\), while every nonincident clause good lies after position \(s+1\).
Type \(d_i^\sigma\) begins with
\[ h_i\succ s_i^\sigma\succ b_i, \]
and appends all remaining goods in reference order.
All constructed types are distinct. The construction and its encoding have polynomial size.
The highest-ranking types for each good are exactly as follows.
| Good | Minimum rank | Types attaining it |
|---|---:|---|
| \(s_i^\sigma\) | \(1\) | \(\ell_i^\sigma\) |
| \(h_i\) | \(1\) | \(d_i^+,d_i^-\) |
| \(b_i\) | \(3\) | \(d_i^+,d_i^-\) |
| \(c_j\) | \(j+1\) | \(\ell_i^\sigma\) with \(X_i^\sigma\) occurring in \(C_j\) |
Here are the relevant checks. Only the indicated types rank their signature or top dummy good first. Every literal type places all signatures and top dummy goods before every bottom dummy good, so its bottom-good ranks exceed \(3\). Other dummy types place \(b_i\) after their first three positions.
For clauses, incident literal types have the prescribed rank \(j+1\), while nonincident literal types rank them after position \(s+1\). In every dummy ranking, \(3r+1\) goods precede the clause block, so \(c_j\) has rank \(3r+1+j>j+1\).
By the minimum-rank observation, every rank-maximal allocation therefore has these support restrictions:
\[ B=\{s_i^\sigma\}\cup D \quad\text{for a supported bundle of }\ell_i^\sigma, \]
where
\[ D\subseteq\{c_j:X_i^\sigma\text{ occurs in }C_j\}, \]
and
\[ B\subseteq\{h_i,b_i\} \quad\text{for a supported bundle of }d_i^\sigma. \]
The signature must occur in every supported bundle of its literal type: its supply \(q\) is allocated exclusively to that type, whose total mass is also \(q\).
Call \(\ell_i^\sigma\) active if some positively supported bundle of that type contains a clause good.
Lemma. In any EFX and rank-maximal allocation, activity of \(\ell_i^\sigma\) forces the entire mass \(q\) of \(d_i^\sigma\) to receive \(h_i\).
Proof. Choose a positively supported literal bundle \(C\) containing a clause good \(c_j\). It also contains \(s_i^\sigma\).
Suppose \(d_i^\sigma\) has a positively supported bundle \(A\) without \(h_i\). By the support restrictions, \(A\subseteq\{b_i\}\). The bundle \(C\setminus\{c_j\}\) still contains \(s_i^\sigma\).
Under \(d_i^\sigma\), the first-ranked good \(h_i\) occurs in neither bundle, while the second-ranked good \(s_i^\sigma\) occurs only in \(C\setminus\{c_j\}\). Hence
\[ C\setminus\{c_j\}\succ_{d_i^\sigma}A, \]
contradicting EFX. Thus every supported bundle of \(d_i^\sigma\) contains \(h_i\), proving the lemma.
Since \(h_i\) has supply \(q\), both \(\ell_i^+\) and \(\ell_i^-\) cannot be active: the lemma would require its two dummy types to receive total mass \(2q\) of \(h_i\).
This argument allows arbitrary real masses and arbitrary splitting within every type.
Suppose the constructed instance admits an EFX and rank-maximal allocation.
Each clause good \(c_j\) has positive supply. Its allocation is restricted to the literal types corresponding to literals occurring in \(C_j\). Therefore at least one such literal type is active.
Assign \(X_i\) to be true if \(\ell_i^+\) is active, false if \(\ell_i^-\) is active, and arbitrarily if neither is active. Section 5 ensures that these choices are consistent.
Every clause has an active incident literal, and the chosen assignment makes that literal true. Thus the original formula is satisfiable.
Conversely, suppose the formula has a satisfying assignment. Extend it arbitrarily to the padded variables.
Give each type a single bundle, with its entire mass \(q\), as follows:
Every good belongs to exactly one such bundle, so its allocated mass is \(q\). The allocation is feasible. Every good goes to a minimum-rank type from the table, so it is rank-maximal.
It remains to verify EFX. A singleton target bundle becomes empty after its good is removed, and every bundle is weakly preferred to the empty bundle. Hence only target bundles containing at least two goods require further checking. Such a target is a literal bundle consisting of its signature and one or more clause goods, belonging to a true literal.
For every observing type:
Whenever the observer weakly prefers its bundle to the whole target, it also weakly prefers it after any deletion, by monotonicity and transitivity of lexicographic preference. This checks every ordered supported pair and every required deletion, including within-type comparisons. The allocation is EFX.
The reduction is polynomial and preserves satisfiability in both directions. Its soundness explicitly covers real allocation masses and population splitting. Together with membership in \(\mathrm{NP}\), it proves that the stated decision problem is \(\mathrm{NP}\)-complete.
⟨structured verdict parsed — rendered above⟩
The proof resolves the stated problem. The marginal characterization, certificate argument, reduction, and EFX checks are valid, including for allocations with arbitrary real masses and splitting within types. I found no major or minor issues.
The necessary marginal conditions are correct: a type’s marginal for any good cannot exceed its total mass, and the marginal allocations of each good must sum to its supply.
The product-distribution construction proves sufficiency. It is well-defined because every \(\mu_t\) is positive and each \(p_{t,g}\) lies in \([0,1]\). It gives the prescribed type mass and all prescribed good marginals, including at the endpoints \(0\) and \(1\). The potentially exponential number of bundles is harmless here: this construction establishes existence, rather than claiming a polynomial-size representation.
The capacities \(c_{g,j}\) correctly describe the feasible rank aggregates for each good. The formula for \(a_{g,j}\) fills the earliest ranks first, respecting both capacity and remaining supply.
The argument that separate optimization yields the global optimal signature is valid. At the earliest coordinate where any good’s aggregate differs from its optimum, every differing good has a deficit and no good has a surplus. Consequently, summing over goods cannot cancel that deficit. This also establishes that a globally rank-maximal allocation must attain each good’s optimal rank aggregate.
The minimum-rank observation follows correctly. When each type has mass \(q\) and each good has supply \(q\), any type attaining that good’s minimum rank has enough marginal capacity to absorb its entire supply. Thus rank-maximality is equivalent to assigning that good exclusively among its minimum-rank types.
The optimal signature can be computed in polynomial time from the explicit rankings and rational input data. The sums, minima, and maxima in its formula have polynomial encoding length.
The certificate compression argument is sound:
The rational-size argument is also valid. Every coordinate of the right-hand side has denominator dividing the product \(Q\) of the input denominators. In particular, the operations defining \(R_j^*\) preserve this property. Independent columns admit a nonsingular square submatrix, and Cramer’s rule with Hadamard’s bound gives the claimed polynomial encoding length.
Changing the masses on the retained columns does not create an EFX violation: EFX depends on which type-bundle pairs have positive mass, rather than on their positive magnitudes. The new support is a subset of the original support.
A certificate therefore has polynomial length. Feasibility, the rank signature, and all ordered EFX comparisons are checkable in polynomial time. This establishes membership in \(\mathrm{NP}\), despite the original allowance of real masses.
The padding is polynomial: the smallest power of two \(r\) above \(\max\{n,s,2\}\) is less than twice that quantity. Adding unused variables preserves satisfiability.
There are exactly \(4r\) types, each of mass \(q=1/(4r)\), so their masses sum to one. Because \(r\) is a power of two, these masses and all supplies are dyadic rationals. Every supply satisfies the required strict positivity and upper bound.
The literal rankings are well-defined. At most \(s\) filler signatures are required, and each literal type has \(2r-1\) available signatures other than its own. The inequality \(s\leq r\leq2r-1\) supplies enough fillers. Appending only remaining goods produces strict complete rankings.
The types are distinct: literal types have different first-ranked signatures; dummy types have first-ranked top dummy goods and are distinguished within each variable by their second-ranked signatures. Thus the stated support size is correct.
Every entry of the table is correct.
The dummy clause-rank calculation is correct: all \(2r\) signatures, all \(r\) top dummy goods, and the dummy’s own bottom good precede the clause block. Thus \(c_j\) has rank \(3r+1+j\).
Every clause is nonempty, so at least one incident literal type exists for its clause good. The claimed clause minimum rank is therefore attained.
Applying the minimum-rank observation gives exactly the stated support restrictions. The signature appears in every positively supported bundle of its literal type because its marginal equals that type’s entire mass. This reasoning applies equally to real masses and split allocations.
The activity lemma uses a required EFX comparison correctly.
An active literal bundle \(C\) contains both its signature \(s_i^\sigma\) and a clause good \(c_j\). A supported bundle \(A\) of \(d_i^\sigma\) lacking \(h_i\) must be a subset of \(\{b_i\}\).
After deleting \(c_j\), neither compared bundle contains \(h_i\), while only \(C\setminus\{c_j\}\) contains the dummy’s second-ranked good \(s_i^\sigma\). Hence the dummy strictly prefers the reduced target to \(A\), violating EFX.
The lemma consequently forces the whole dummy mass \(q\) to receive \(h_i\). If both signs were active, the two corresponding dummy types would require total marginal \(2q\), contradicting supply \(q\).
No integrality or lower bound on a positive supported mass is used. The argument explicitly covers arbitrary splitting.
Positive supply of each clause good implies that some positively supported bundle contains it. The rank-maximal support restrictions ensure that this bundle belongs to an incident literal type, making that type active.
The exclusion lemma makes the extracted truth assignment consistent. Each clause contains an active literal, and the assignment makes that literal true. Arbitrary choices for variables with neither sign active do not affect this conclusion.
Thus existence of an EFX and rank-maximal allocation implies satisfiability.
The proposed allocation assigns one bundle of mass \(q\) to each type and assigns every good exactly once. It satisfies all type-mass and supply equalities. Every good is assigned to a minimum-rank type, so the allocation is rank-maximal.
The EFX verification covers every supported observer and target:
The passage from comparison with the whole target to comparison after deletion is valid by monotonicity and transitivity of lexicographic preferences. This includes within-type comparisons, since each type has exactly one supported bundle in the constructed allocation.
Thus satisfiability implies existence of an EFX and rank-maximal allocation.
The reduction has polynomial size and proves both directions. Its soundness remains valid for the continuous allocation model in the task. Together with the polynomial certificate argument, it establishes the claimed \(\mathrm{NP}\)-completeness, including the stated restriction to equal dyadic type masses and equal supplies.
No additional clarification or repair is needed.
⟨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.