Answer: Constructible in \(\operatorname{poly}(m,\tau,L)\) time and output size, with at most \(\tau+m\) occupied pairs.
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateA nearly jealousy-free base allocation always exists and it can be computed within O(nm ln m) time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), rational masses \(\mu_t>0\) summing to \(1\), item categories \(E\), rational per-capita supplies \(b_e\ge 0\), and nonnegative rational utilities \(u_t(e)\) normalized by \(\sum_{e\in E} b_e u_t(e)=1\), construct an explicit polynomial-size distribution \(y_{t,k}\) over integral bundles \(k\in\mathbb{Z}_{\ge 0}^{E}\). Require \(\sum_k y_{t,k}=\mu_t\), \(\sum_{t,k}y_{t,k}k_e=b_e\) for each \(e\), and, for every two occupied type-bundle pairs \((t,k)\) and \((t',k')\) with \(k'\ne 0\), \(U_t(k)\ge U_{t'}(k')-\min_{e:k'_e>0}u_{t'}(e)\), where \(U_t(k)=\sum_e u_t(e)k_e\). Is such a distribution constructible in time polynomial in \(|E|\), \(|T|\), and the binary input length \(L\)?
A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m=|E|\) item categories, binary rational per-capita supplies \(b_e\geq 0\), and nonnegative binary rational utilities \(u_t(e)\), normalized by \(\sum_{e\in E}b_eu_t(e)=1\) for every \(t\). Let \(L\) be the total binary input length.
An integral bundle is \(k\in\mathbb Z_{\geq 0}^{E}\), with additive utility \(U_t(k)=\sum_{e\in E}u_t(e)k_e\). Types may be split among bundles.
An allocation is a finitely supported family of nonnegative rational masses \(y_{t,k}\) satisfying \(\sum_k y_{t,k}=\mu_t\) and \(\sum_{t,k}y_{t,k}k_e=b_e\) for every category \(e\).
Require \(U_t(k)\geq U_{t'}(k')-\min_{e:k'_e>0}u_{t'}(e)\) whenever \(y_{t,k}>0\), \(y_{t',k'}>0\), and \(k'\neq 0\). The minimum includes categories of zero utility; empty comparison bundles impose no condition.
The output explicitly lists the occupied pairs and their masses, with bundle coordinates and rational masses encoded in binary.
Is constructing such an allocation on every valid input, with output size and running time polynomial in \(m,\tau,L\), possible, or is this construction problem NP-hard?
For finitely many agents and explicitly listed indivisible goods, a nearly jealousy-free allocation always exists and is computable in \(O(nq\log q)\) time, where \(n\) is the number of agents and \(q\) the number of goods; this extends to allocating a matroid base, excluding independence-oracle costs ([Gourvès–Monnot–Tlilane](https://doi.org/10.3233/978-1-61499-419-0-393)).
No result settling this exact distribution-over-types problem was located in the literature search.
The construction problem is polynomial-time solvable. There is a deterministic algorithm that outputs an allocation with at most \(\tau+m\) occupied pairs, with running time and output size polynomial in \(m,\tau,L\).
The algorithm batches a greedy allocation process. Its phases are determined by category exhaustion, rather than by the potentially exponential number of agents or goods obtained by clearing denominators.
Choose positive integers \(D,H\) such that
For example, take \(D\) to be the product of the denominators of the masses and supplies, and \(H\) the product of the utility denominators. Both have bit length \(O(L)\).
Conceptually, there are \(D\) agents, with \(N_t\) agents of type \(t\), and \(Q_e^0\) goods of category \(e\). We will never enumerate these agents or goods.
Represent the current allocation by groups \(g\). Each group has:
Its scaled utility is \(a_g=\sum_e w_{t_g}(e)k_e^g\).
Initially, there is one group \((t,N_t,0)\) for each type. Let \(Q_e\) denote the remaining number of goods of category \(e\).
Throughout the algorithm, population and inventory conservation mean
\(\sum_{g:t_g=t}n_g=N_t\), and \(\sum_g n_gk_e^g+Q_e=Q_e^0\).
At termination, combine groups with identical type and bundle, and divide their populations by \(D\) to obtain the output masses.
Let \(M=\min_g a_g\). For a group with nonempty bundle, define its adjusted utility by
\(c_g=a_g-\min_{e:k_e^g>0}w_{t_g}(e)\).
The requested fairness condition, after scaling by \(H\), is exactly
\(c_g\le M\quad\text{for every group with }k^g\ne0.\)
Indeed, this says that every occupied bundle’s adjusted utility is at most every occupied bundle’s utility. Empty comparison bundles are excluded as required.
We maintain this fairness invariant.
We also maintain a dominance invariant: whenever some goods remain, every category already present in a group’s bundle has value at least that type’s maximum value among remaining categories. Explicitly,
\(k_f^g>0\ \Longrightarrow\ w_{t_g}(f)\ge\max_{e:Q_e>0}w_{t_g}(e).\)
Both invariants hold initially: all bundles are empty.
The dominance invariant arises because goods are assigned only from a recipient’s favorite remaining category. As categories become exhausted, each type’s maximum remaining value can only decrease.
Suppose some goods remain. Put \(S=\{e:Q_e>0\}\).
For every type, choose a favorite remaining category \(e_t\in\operatorname*{arg\,max}_{e\in S}w_t(e)\), breaking ties by a fixed category order. For each group, write
\(e_g=e_{t_g}\), and \(v_g=w_{t_g}(e_g)\).
Thus all agents in a group have the same current utility and favorite category.
If \(v_g>0\), successive assignments from the favorite category occur at pre-assignment utility levels
\(a_g,\ a_g+v_g,\ a_g+2v_g,\ldots.\)
For an integer \(x\ge-1\), define
\(F_e(x)=\sum_{\substack{g:e_g=e\\v_g>0}}n_g\max\left\{0,\left\lfloor\frac{x-a_g}{v_g}\right\rfloor+1\right\}.\)
This counts the goods of category \(e\) needed to perform all such assignments whose pre-assignment utility is at most \(x\). In particular, \(F_e(-1)=0\), since all current utilities are nonnegative.
If a positive-value group exists, define \(h\) to be the smallest nonnegative integer satisfying
\(F_e(h)\ge Q_e\quad\text{for some }e\in S.\)
This threshold exists. For any positive-value group \(g\), setting \(B=a_g+v_gQ_{e_g}\) gives
\(F_{e_g}(B)\ge n_g(Q_{e_g}+1)\ge Q_{e_g}.\)
Because every \(F_e\) is nondecreasing, binary search on the integer interval from \(0\) to \(B\) finds \(h\). If no positive-value group exists, set \(h=+\infty\).
Zero-valued favorite categories require separate treatment. Define
\(z=\min_{g:v_g=0}a_g\),
with \(z=+\infty\) if there is no such group. Let \(\ell=\min\{h,z\}\). This level is finite: every group either has positive favorite value or contributes to \(z\).
For each group with \(v_g>0\), set
\(r_g=\max\left\{0,\left\lceil\frac{\ell-a_g}{v_g}\right\rceil\right\}.\)
Give every agent in that group \(r_g\) goods of category \(e_g\). Set \(r_g=0\) for groups with \(v_g=0\).
This operation consumes
\(R_e(\ell)=\sum_{g:e_g=e}n_gr_g=F_e(\ell-1)\)
goods of category \(e\). The identity follows from integer arithmetic:
\(\max\{0,\lceil(\ell-a)/v\rceil\}=\max\{0,\lfloor(\ell-1-a)/v\rfloor+1\}\).
For every active category, \(R_e(\ell)<Q_e\). To see this, if \(h\) is finite, minimality of \(h\) gives \(F_e(h-1)<Q_e\), and \(\ell\le h\). If \(h=+\infty\), there are no positive-value groups and all these counts are zero.
Consequently, this bulk update is feasible and exhausts no category. It also creates no new groups.
There are two cases.
Case A: \(h<z\).
Choose a category \(e^*\) satisfying \(F_{e^*}(h)\ge Q_{e^*}\), where \(Q_{e^*}\) here denotes its inventory before the bulk update.
After that update, the remaining inventory of this category is
\(q=Q_{e^*}-R_{e^*}(h)>0.\)
Let \(W\) be the total population of groups whose favorite category is \(e^*\) and whose updated utility is exactly \(h\). Then
\(W=F_{e^*}(h)-F_{e^*}(h-1).\)
For verification, a positive-value group contributes \(n_g\) to this difference precisely when \(h=a_g+jv_g\) for some integer \(j\ge0\). Precisely those groups end the bulk update at utility \(h\).
It follows that \(q\le W\). Give one additional good of category \(e^*\) to exactly \(q\) agents among these groups.
Implement this by traversing the eligible groups: assign to entire groups until the remaining number is smaller than the next group’s population, then split that group if necessary. Thus at most one group splits.
This exhausts category \(e^*\). Begin the next phase.
Case B: \(z\le h\).
Choose a group with \(v_g=0\) and \(a_g=z\). Its bundle was unchanged by the bulk update.
Every remaining category has zero value for this group’s type: its favorite remaining value is zero, and all utilities are nonnegative.
Give all remaining goods to one agent from this group. Isolating that agent splits at most one group. Its utility remains \(z\).
All inventories are now exhausted, and the algorithm terminates.
We verify that each phase preserves both invariants.
First, \(\ell\ge M\), where \(M\) is the minimum utility before the phase. Certainly \(z\ge M\). Also, for any integer \(x<M\), all positive-value groups contribute zero to \(F_e(x)\), so a finite threshold \(h\) cannot be below \(M\).
A positive-value group receiving no goods has \(a_g\ge\ell\). A zero-value group also has \(a_g\ge z\ge\ell\).
For a group receiving goods, let \(a'_g=a_g+r_gv_g\). The ceiling defining \(r_g\) gives
\(\ell\le a'_g<\ell+v_g.\)
By the dominance invariant, every previous item in its bundle has value at least \(v_g\). The newly assigned items have value exactly \(v_g\). Therefore its new adjusted utility satisfies
\(c'_g=a'_g-v_g<\ell.\)
For an unchanged nonempty bundle, the previous fairness invariant gives
\(c'_g=c_g\le M\le\ell.\)
Thus, after the bulk update, every utility is at least \(\ell\), and every nonempty bundle’s adjusted utility is at most \(\ell\). Fairness follows.
Every newly assigned item is a favorite remaining item. No category has yet exhausted, so dominance also continues to hold.
Here \(\ell=h\). An agent receiving an additional item has utility exactly \(h\) before receiving it.
If that item has value \(v_g\), all previous items have value at least \(v_g\). The resulting utility is \(h+v_g\), and the least item value is \(v_g\). Hence its adjusted utility is exactly \(h\).
All other bundles retain adjusted utility at most \(h\), and all utilities remain at least \(h\). Fairness is preserved.
After removing the exhausted category, maximum remaining values can only decrease. Dominance is therefore preserved as well.
Here \(\ell=z\). After the bulk update, every utility is at least \(z\), and every nonempty bundle’s adjusted utility is at most \(z\).
The selected agent receives only goods worth zero to its type, so its utility remains \(z\). Its new bundle contains a zero-valued item, making its adjusted utility exactly \(z\). Other bundles are unchanged.
This proves fairness, including the stipulated comparisons whose minimum item value is zero.
By induction, the final allocation satisfies the requested condition.
Every nonterminal phase exhausts one category. A terminal zero-value phase exhausts all remaining categories. Thus there are at most \(m\) phases.
The initial representation has \(\tau\) groups. The bulk update never splits a group, and each phase splits at most one group. Consequently, the final allocation has at most \(\tau+m\) occupied pairs.
All stored numbers have polynomial bit length:
Each phase therefore uses polynomially many bit operations: favorite selection, a polynomial number of binary-search iterations, bulk updates, and at most one group split. With at most \(m\) phases, total running time is polynomial in \(m,\tau,L\).
Finally, output each group’s mass \(n_g/D\), combining identical occupied pairs. Conservation gives
\(\sum_k y_{t,k}=N_t/D=\mu_t\),
and
\(\sum_{t,k}y_{t,k}k_e=Q_e^0/D=b_e.\)
Each mass and bundle coordinate has polynomial bit length, and there are at most \(\tau+m\) occupied pairs. The output size is therefore polynomial as well.
The argument uses only nonnegativity of utilities; the given normalization is fully compatible with the construction.
⟨structured verdict parsed — rendered above⟩
The claimed polynomial-time construction is correct as written. The algorithm establishes feasibility, the requested fairness condition, and polynomial bounds on running time and explicit output size. I found no major or minor issues.
The proposed denominator products produce positive integers \(D,H\) for which every \(N_t=D\mu_t\), \(Q_e^0=Db_e\), and \(w_t(e)=Hu_t(e)\) is integral. Their bit lengths are \(O(L)\): the bit length of a product is bounded by the sum of the factors’ bit lengths.
Because the masses sum to \(1\), the conceptual population is exactly \(D\). Positive masses ensure that every initial group has positive integer population.
Both conservation identities hold initially. Each subsequent operation assigns integer quantities of goods to integer populations, with splitting preserving the population of the affected type. Thus conservation remains valid. The conceptual interpretation does not require enumerating agents or individual goods.
The fairness reformulation is exact. Multiplication by the positive number \(H\) transforms the requested comparison into
\[
a_g\ge c_{g'}
\]
for every recipient group \(g\) and every nonempty comparison group \(g'\). Taking the minimum over recipient groups gives precisely \(c_{g'}\le M\).
This formulation correctly excludes empty comparison bundles and includes zero-valued categories in the minimum.
The dominance invariant also has the correct scope: it applies whenever inventory remains. Initially it is vacuous. Assigning a favorite remaining category preserves it while the remaining category set stays fixed; exhausting categories can only decrease the maximum remaining value.
For positive \(v_g\), the expression
\[
\max\left\{0,\left\lfloor\frac{x-a_g}{v_g}\right\rfloor+1\right\}
\]
correctly counts the nonnegative integers \(j\) satisfying \(a_g+jv_g\le x\). Multiplication by \(n_g\) therefore gives the stated event count.
The threshold existence bound is valid: at \(B=a_g+v_gQ_{e_g}\), the chosen group alone contributes \(n_g(Q_{e_g}+1)\), which is at least \(Q_{e_g}\). The predicate used in binary search is monotone.
When no positive-value group exists, setting \(h=+\infty\) is consistent with every \(F_e\) being zero. In every phase, \(\ell\) is finite because the nonempty collection of groups contains either a positive-value group or a zero-value group.
The ceiling–floor identity used to establish \(R_e(\ell)=F_e(\ell-1)\) is correct, including when \(\ell\le a_g\). Minimality of \(h\) gives strict inventory feasibility. When \(h=0\), the argument uses the explicitly defined value \(F_e(-1)=0\), so this boundary case is covered.
Consequently, the bulk allocation exhausts no category and requires no group splitting.
The difference \(F_{e^*}(h)-F_{e^*}(h-1)\) counts exactly the population whose next positive-value assignment occurs at level \(h\). After the bulk update, these are exactly the positive-value groups with updated utility \(h\) and favorite category \(e^*\).
The definition of \(W\) does not accidentally include zero-value groups: in this case \(h<z\), so every zero-value group has utility strictly above \(h\).
The inequalities
\[
F_{e^*}(h-1)<Q_{e^*}\le F_{e^*}(h)
\]
give \(0<q\le W\). Thus the proposed additional assignments are feasible and exhaust \(e^*\). Traversing whole eligible groups and partially using at most one group implements exactly \(q\) assignments with at most one split.
A zero favorite value implies that every remaining category has value zero for the selected type, because utilities are nonnegative.
The selected group is unchanged by the bulk operation. Isolating one agent, if necessary, is valid because its population is a positive integer. Giving that agent all remaining goods is a finite integral bundle assignment and preserves conservation.
The equality case \(z=h\) is explicitly handled by Case B.
The inequality \(\ell\ge M\) is established correctly. No positive-value event occurs below its group’s starting utility, and every starting utility is at least \(M\).
For every group receiving positive-value goods in the bulk operation, the ceiling formula gives
\[
\ell\le a'_g<\ell+v_g.
\]
Dominance ensures that the minimum item value in its updated bundle is exactly \(v_g\). Hence \(c'_g=a'_g-v_g<\ell\).
Unchanged nonempty bundles retain adjusted utility at most the previous minimum \(M\), hence at most \(\ell\). Every updated utility is at least \(\ell\). These statements establish fairness after the bulk operation.
In Case A, every additional recipient starts at utility \(h\), and its new minimum item value is \(v_g\). Its adjusted utility is therefore exactly \(h\). All utilities remain at least \(h\), so fairness survives.
In Case B, the selected agent retains utility \(z\) and receives at least one zero-valued item, since inventory remains. Its adjusted utility becomes exactly \(z\). This explicitly verifies the potentially delicate zero-minimum comparison.
Splitting groups introduces no additional fairness requirement beyond these checks: every resulting group has either the unchanged bundle or the analyzed updated bundle.
Each Case A phase exhausts a category, and Case B exhausts all remaining categories. Therefore there are at most \(m\) phases.
Starting with \(\tau\) groups and introducing at most one additional group per phase gives at most \(\tau+m\) groups. Combining identical occupied pairs can only reduce that count.
The numerical bounds are valid:
No iteration runs once per conceptual agent or good. The algorithm is therefore polynomial in the specified binary input parameters.
Dividing final populations by \(D\) produces positive rational masses with polynomial binary encoding length. Conservation yields exactly the prescribed type masses and per-category supplies.
The fairness invariant transfers back through scaling by \(H\), yielding precisely the requested condition. The explicit output has at most \(\tau+m\) occupied pairs.
The proof is self-contained and does not invoke the cited finite-agent theorem. Normalization is unnecessary for its argument, which is consistent with proving the result for the stated normalized inputs.
Repair feedback: None required.
⟨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.