Answer: Polynomial-time solvable in \(m,\tau,L\), with an optimal EFX allocation supported on at most \(\tau+m\) type–bundle pairs.
Theorem 8 — class: algorithmic
Given \(m\) good classes with rational prices \(p_r>0\), supported types \(T\) with rational masses \(\mu_t\) summing to \(1\), and rational per-capita supplies \(q_r\), compute a finite list of bundle masses \(x_{t,z}\ge 0\), where \(z\in\mathbb Z_{\ge 0}^m\) is each person’s integral bundle and type \(t\) values classes in \(D_t\), with \(u_t(z)=\sum_{r\in D_t}p_rz_r\). Require \(\sum_z x_{t,z}=\mu_t\) and \(\sum_{t,z}z_rx_{t,z}=q_r\). For every two bundles \(z,w\) receiving positive mass and every \(r\in D_t\) with \(w_r>0\), require \(u_t(z)\ge u_t(w)-p_r\); among feasible allocations, maximize \(\sum_{t,z}x_{t,z}u_t(z)\). Is this computable in time polynomial in \(m\), \(\tau=|T|\), and the binary input length \(L\)?
There are \(m\ge 1\) good classes with binary rational prices \(p_r>0\) and per-capita supplies \(q_r\ge 0\). A society is given by its support: the list of \(\tau\ge 1\) types with positive binary rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types. Each type specifies \(D_t\subseteq\{1,\ldots,m\}\), and every class belongs to at least one supported type's \(D_t\).
Each person receives an integral bundle \(z\in\mathbb Z_{\ge 0}^m\), with utility \(u_t(z)=\sum_{r\in D_t}p_rz_r\); empty bundles and empty interest sets are allowed.
An allocation is a finite list of nonnegative rational masses \(x_{t,z}\), with omitted entries zero, satisfying \(\sum_zx_{t,z}=\mu_t\) and \(\sum_{t,z}z_rx_{t,z}=q_r\) for every class \(r\).
Require EFX across all supported recipients: for every \((t,z),(s,w)\) with \(x_{t,z}>0\) and \(x_{s,w}>0\), and every \(r\in D_t\) with \(w_r>0\), require \(u_t(z)\ge u_t(w)-p_r\). This includes recipients of the same type.
The computational problem is to compute such an allocation maximizing \(\sum_{t,z}x_{t,z}u_t(z)\), or report infeasibility. All numbers and bundle coordinates are encoded in binary; \(L\) is the total input bit length.
Can this exact optimization problem be solved in time polynomial in \(m,\tau,L\), or is it NP-hard?
For \(n\) explicitly listed agents and \(M\) explicitly listed indivisible goods with these generalized binary utilities, an EFX, Pareto-optimal allocation maximizing unrestricted utilitarian welfare is computable in \(O(M\log M+Mn)\) operations ([Camacho et al.](https://arxiv.org/html/2109.08461v2)).
No result settling this precise mass-allocation problem was located in the literature search.
The problem is polynomial-time solvable. Every instance satisfying the stated hypotheses is feasible, and an optimal allocation can be computed with at most \(\tau+m\) supported type–bundle pairs. Its welfare is
\(\displaystyle \sum_{r=1}^{m}p_rq_r.\)
The algorithm implements the decreasing-price least-utility idea underlying [Camacho et al., Theorem 8](https://arxiv.org/html/2109.08461v2) in bulk. The proof below establishes its correctness directly, including EFX between recipients of the same type.
Let \(\operatorname{den}(a)\) denote the positive denominator in the input representation of a rational number \(a\). Define
\(\displaystyle N=\prod_{t=1}^{\tau}\operatorname{den}(\mu_t)\prod_{r=1}^{m}\operatorname{den}(q_r),\qquad A=\prod_{r=1}^{m}\operatorname{den}(p_r).\)
Then
\(\displaystyle c_t=N\mu_t,\qquad T_r=Nq_r,\qquad P_r=Ap_r\)
are integers, with \(c_t>0\), \(T_r\geq 0\), \(P_r>0\), and \(\sum_tc_t=N\).
We work with scaled utilities
\(\displaystyle v_t(z)=\sum_{r\in D_t}P_rz_r=A u_t(z).\)
Multiplication by the positive number \(A\) preserves every EFX inequality.
A block is a triple \((t,z,c)\), representing \(c\) individuals of type \(t\), all receiving the same integral bundle \(z\). Its eventual mass is \(c/N\). We maintain blocks without explicitly expanding their populations.
Initially, there is one block \((t,0,c_t)\) for each type. Relabel the classes so that
\(\displaystyle P_1\geq P_2\geq\cdots\geq P_m.\)
Process the classes in this order. Class \(r\) is assigned only to blocks whose type is interested in \(r\).
Consider one class of scaled price \(P>0\), with \(T\geq 0\) copies to assign. Let \(I\) be the nonempty set of interested blocks. For each \(i\in I\), let \(c_i>0\) be its integer population and \(U_i\geq 0\) its current integer utility.
We construct an assignment with these properties:
Write the Euclidean divisions
\(\displaystyle U_i=Pb_i+h_i,\qquad b_i\in\mathbb Z_{\geq 0},\qquad 0\leq h_i<P.\)
For an integer \(k\), define
\(\displaystyle C(k)=\sum_{i\in I}c_i\max\{0,k-b_i\}.\)
For every integer \(k\geq b_{\min}:=\min_{i\in I}b_i\),
\(\displaystyle C(k+1)-C(k)=\sum_{\substack{i\in I\\b_i\leq k}}c_i>0.\)
Also, \(C(b_{\min})=0\), and \(C(k)\) tends to infinity. Consequently, there is a unique integer \(k\geq b_{\min}\) satisfying
\(\displaystyle C(k)\leq T<C(k+1).\)
First give every member of block \(i\) exactly
\(\displaystyle a_i=\max\{0,k-b_i\}\)
copies. This uses \(C(k)\) copies. Put
\(\displaystyle \Delta=T-C(k).\)
The difference formula gives
\(\displaystyle 0\leq\Delta<\sum_{\substack{i\in I\\b_i\leq k}}c_i.\)
Among the blocks with \(b_i\leq k\), order them by nondecreasing \(h_i\), breaking ties arbitrarily. Give one additional copy to precisely \(\Delta\) individuals by taking consecutive whole blocks in this order and, if necessary, part of the next block.
Because all counts are integers, the partial block, when present, splits into two positive integer populations. There is at most one such split. The total number of assigned copies is exactly \(C(k)+\Delta=T\).
If \(\Delta=0\), take \(H=Pk\).
For \(b_i\leq k\), the final utility is \(Pk+h_i\), which is at least \(H\) and less than \(H+P\). For \(b_i>k\), the block receives nothing and retains utility at least \(P(k+1)>H\). Thus both required bounds hold.
Now suppose \(\Delta>0\). Let \(h_*\) be the remainder of the last block from which individuals receive an additional copy, and set
\(\displaystyle H=Pk+h_*.\)
By the prefix construction, among blocks with \(b_i\leq k\):
An interested recipient therefore belongs to one of three cases.
Case 1: \(b_i>k\). Its unchanged utility is at least \(P(k+1)>H\).
Case 2: \(b_i\leq k\), without an additional copy. Its final utility is
\(\displaystyle U_i'=Pk+h_i\geq Pk+h_*=H.\)
If it received any baseline copies, its final utility also satisfies
\(\displaystyle U_i'<P(k+1)\leq H+P.\)
Case 3: \(b_i\leq k\), with an additional copy. Its final utility is
\(\displaystyle U_i'=P(k+1)+h_i.\)
Since \(h_*<P\), this is greater than \(H\); since \(h_i\leq h_*\), it is at most \(H+P\).
These cases prove the lemma.
Let
\(\displaystyle S=\sum_{i\in I}c_i,\qquad b_{\max}=\max_{i\in I}b_i,\qquad K=b_{\max}+\left\lfloor T/S\right\rfloor+1.\)
Then
\(\displaystyle C(K)\geq S(K-b_{\max})=S\left(\left\lfloor T/S\right\rfloor+1\right)>T.\)
Thus binary search between \(b_{\min}\) and \(K\) finds \(k\). Afterward, sorting the eligible blocks by their remainders and scanning their counts determines the additional-copy assignment. No operation iterates over the individuals or copies.
For each class \(r\), apply the bulk assignment lemma with:
The set \(I\) is nonempty: every class interests at least one supported type, and the algorithm preserves that type’s positive total population.
Adding copies updates a block’s \(r\)-coordinate. A partial additional-copy assignment splits the block into two bundles differing by one copy of class \(r\).
The construction immediately preserves the following properties:
Starting with \(\tau\) blocks, the final allocation therefore has at most \(\tau+m\) blocks.
It remains to prove EFX.
We prove by induction on the processed classes that all supported blocks satisfy EFX for the scaled utilities.
Initially every bundle is empty, so EFX holds.
Suppose it holds before processing class \(r\). Let \(P=P_r\), and let \(H\) be the threshold supplied by the bulk assignment lemma.
Take arbitrary resulting supported recipients \((t,z)\) and \((s,w)\). Let \(z^0,w^0\) be their respective bundles before this step. Fix any \(g\in D_t\) with \(w_g>0\). We must show
\(\displaystyle v_t(z)\geq v_t(w)-P_g.\)
There are two cases.
Because \(t\) is interested in the newly processed class, the threshold lemma gives
\(\displaystyle v_t(z)\geq H.\)
Because \(w\) received a new copy, it also gives
\(\displaystyle v_s(w)\leq H+P.\)
Every good in \(w\) is liked by its owner \(s\). Hence
\(\displaystyle v_t(w)\leq v_s(w).\)
Moreover, every class present in \(w\) has already been processed, so descending price order implies \(P_g\geq P\). Therefore,
\(\displaystyle v_t(w)-P_g\leq v_s(w)-P\leq H\leq v_t(z).\)
This proves the desired inequality.
In either situation,
\(\displaystyle v_t(w)=v_t(w^0).\)
Also, the class \(g\) must already have been present in \(w^0\). Indeed, the only newly added class is \(r\), and a newly added positively valued copy of \(r\) would put us in Case 1.
The induction hypothesis thus gives
\(\displaystyle v_t(z^0)\geq v_t(w^0)-P_g.\)
The new assignment cannot decrease the first recipient’s utility, so
\(\displaystyle v_t(z)\geq v_t(z^0)\geq v_t(w^0)-P_g=v_t(w)-P_g.\)
This completes the induction.
The recipients were arbitrary; the argument includes recipients of the same type and recipients produced by splitting a block. Dividing the inequalities by \(A\) proves EFX for the original utilities.
For every final block \(i=(t_i,z_i,c_i)\), output mass
\(\displaystyle x_{t_i,z_i}=c_i/N.\)
If identical type–bundle pairs occur, add their masses. This does not increase support size.
Population conservation gives
\(\displaystyle \sum_{i:t_i=t}\frac{c_i}{N}=\frac{c_t}{N}=\mu_t.\)
Exact assignment of each class gives
\(\displaystyle \sum_i\frac{c_i}{N}z_{i,r}=\frac{T_r}{N}=q_r.\)
Thus the output is an allocation of the required form.
For any feasible allocation, whether or not it satisfies EFX, nonnegativity implies
\(\displaystyle \sum_{t,z}x_{t,z}u_t(z)=\sum_r p_r\sum_{t:r\in D_t}\sum_z z_rx_{t,z}\leq\sum_r p_rq_r.\)
Our construction assigns every copy only to an interested type, so it attains equality. It therefore maximizes welfare even without imposing EFX, and consequently also maximizes welfare subject to EFX.
In particular, every promised instance is feasible.
The products defining \(N\) and \(A\) have binary lengths bounded by the sum of the input denominator lengths, hence by \(O(L)\). All scaled counts \(c_t,T_r\) and prices \(P_r\) also have \(O(L)\) bits.
Every block count stays between \(1\) and \(N\). For every maintained block and class,
\(\displaystyle 0\leq z_{i,r}\leq T_r.\)
To justify the upper bound, the aggregate number of assigned copies never exceeds \(T_r\), and the block has integer count at least one. Its contribution to that aggregate is therefore at least \(z_{i,r}\).
Consequently, every block’s utility is bounded by
\(\displaystyle W=\sum_rP_rT_r,\)
which has \(O(L)\) bits. Thus its quotient and remainder on division by any \(P_r\) have polynomial encoding length.
The binary-search upper bound satisfies
\(\displaystyle K=b_{\max}+\left\lfloor T_r/S\right\rfloor+1\leq W+T_r+1,\)
because \(P_r\geq1\) and \(S\geq1\). Binary search therefore uses \(O(L)\) iterations. Each evaluation of \(C(k)\) scans at most \(\tau+m\) blocks and uses integers of \(O(L)\) bits. Sorting remainders, updating bundles, and splitting at most one block likewise take polynomial time.
There are \(m\) stages. The final output contains at most \(\tau+m\) bundles, each with \(m\) coordinates of \(O(L)\) bits, and rational masses with \(O(L)\)-bit numerators and denominators.
Hence the algorithm, including its explicit output, runs in time polynomial in \(m,\tau,L\).
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output resolves the stated mass-allocation problem with an exact polynomial-time algorithm. Its feasibility, EFX, optimality, support-size, and bit-complexity claims are justified. I found no major or minor mathematical issues.
The denominator products ensure that \(c_t=N\mu_t\), \(T_r=Nq_r\), and \(P_r=Ap_r\) are integers with the asserted signs. The population identity \(\sum_t c_t=N\) follows from \(\sum_t\mu_t=1\).
Multiplication by \(A>0\) preserves EFX inequalities. Integer populations are a valid construction device: dividing final block counts by \(N\) produces rational masses allowed by the task. The proof does not assume that every possible feasible allocation has this denominator.
The difference formula for \(C(k)\) follows directly from its definition. For \(k\geq b_{\min}\), its increment is positive because at least one positive-population block has \(b_i\leq k\). Together with \(C(b_{\min})=0\) and unbounded growth, this establishes the unique threshold integer \(k\).
Baseline assignments use exactly \(C(k)\) copies. The remaining count satisfies
\[
0\leq\Delta<\sum_{b_i\leq k}c_i,
\]
so the prescribed prefix assignment is possible. Integer counts ensure that any proper partial assignment splits one block into two positive integer populations. There is at most one such split.
Both threshold arguments are valid:
Thus the stated lower threshold and upper threshold differ by at most \(P\), as required by the later induction.
The proposed upper endpoint satisfies \(K>b_{\max}\), making the bound
\[
C(K)\geq S(K-b_{\max})>T
\]
valid. Strict monotonicity on the search interval permits binary search. Sorting remainders and scanning block counts implements the prefix assignment without expanding populations or supplies.
The lemma also handles \(T=0\): it selects \(k=b_{\min}\), assigns no copies, and its upper threshold condition is vacuous.
Every class has an interested supported type. Conservation of that type’s positive integer population guarantees a nonempty interested-block set at its processing stage.
Assignments preserve integral nonnegative coordinates and type populations. They allocate exactly the scaled supply and give goods only to interested owners. Each stage increases the number of blocks by at most one, yielding the claimed bound of \(\tau+m\).
The empty initial allocation satisfies EFX vacuously. After a stage, each resulting recipient has a positive-population parent block, so the induction hypothesis applies to its previous bundle.
In Case 1, both threshold applications satisfy their hypotheses: \(t\) is interested in the current class, and \(w\) receives at least one new copy. Since every coordinate of \(w\) is liked by its owner,
\[
v_t(w)\leq v_s(w).
\]
Every class present in \(w\) has already been processed, so \(P_g\geq P\), including equal-price classes. Consequently, the displayed chain establishes EFX for every eligible \(g\).
Case 2 is exhaustive with Case 1. If \(t\) does not like the current class, additions do not change \(v_t(w)\); if \(w\) receives nothing, its bundle is unchanged. Furthermore, a class \(g\in D_t\) newly appearing in \(w\) would necessarily trigger Case 1. Thus \(g\) was present in \(w^0\), and the induction hypothesis applies. The first recipient’s utility cannot decrease.
The argument includes same-type comparisons and comparisons between descendants of a split block. Scaling back by \(A\) preserves the inequalities.
Dividing block counts by \(N\) gives the required type masses and exact supplies. Merging identical type–bundle pairs preserves these identities and EFX, because it introduces no new supported bundles.
The welfare upper bound holds for every feasible allocation: each class contributes at most its price times its total supply. The construction attains that bound because all allocated goods are liked by their owners. Therefore its welfare is exactly
\[
\sum_{r=1}^{m}p_rq_r,
\]
and it is optimal among EFX allocations.
The products defining \(N\) and \(A\), and the resulting scaled quantities, have \(O(L)\) bits. Every maintained block has integer population at least one, so supply conservation justifies \(z_{i,r}\leq T_r\). Consequently, the stated utility bound \(W=\sum_rP_rT_r\) is valid and has \(O(L)\) bits.
The bound \(K\leq W+T_r+1\) establishes \(O(L)\) binary-search iterations. Intermediate products and sums in evaluating \(C(k)\) also have \(O(L)\) bits: their factors have that bit bound, and there are at most \(\tau+m\) terms. Standard exact integer arithmetic therefore gives polynomial bit cost.
With \(m\) stages and polynomially many explicitly encoded output coordinates, this is a polynomial-time algorithm in the requested binary representation.
Empty interest sets receive empty bundles and impose no EFX comparisons as evaluators. Zero supplies, all-zero supplies, arbitrary positive rational masses, and price ties are covered by the construction.
The contextual reference to decreasing-price ordering agrees with [Camacho et al., Theorem 8](https://arxiv.org/html/2109.08461v2). The submitted proof establishes its mass-allocation result directly; it does not import the finite-agent theorem’s operation count as a binary-input complexity bound.
Actionable feedback: No mathematical repair or additional clarification 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.