Answer: \(\text{polynomial-time solvable; every valid instance is feasible}\)
Theorem 7.3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAssuming that the valuations are restricted additive, there exists a polynomial-time algorithm that returns an $\EFXp$ and Pareto efficient allocation.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite goods \(G\) with common values \(v(g)\), restricted-additive interest types \(I_t\), rational type masses \(\mu_t\), and per-capita supplies \(q_g\), find masses \(z_{t,B}\geq 0\) over integral bundles \(B\) satisfying \(\sum_B z_{t,B}=\mu_t\) and \(\sum_{t,B}B_gz_{t,B}=q_g\), such that every positive-mass type-\(t\) bundle \(B\) weakly prefers its bundle to every positive-mass bundle \(B'\) after deleting any valued copy of one good, and no feasible reassignment of mass to integral bundles Pareto-improves the allocation.
Let \(G\) contain \(m\) good categories. A society is given by its support: the list of \(\tau\) interest types \(I_t\subseteq G\) with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Common values \(v(g)\) and per-capita supplies \(q_g\geq0\) are binary rationals; \(v(g)>0\) for goods valued by some type, and \(v(g)=0\) otherwise. Let \(L\) be the total input bit length.
An integral bundle is \(B\in\mathbb Z_{\geq0}^{G}\), allowing multiple copies without a per-person cap; its utility to type \(t\) is \(u_t(B)=\sum_{g\in I_t}v(g)B_g\).
An allocation is a finitely supported family of nonnegative rational masses \(z_{t,B}\) satisfying \(\sum_Bz_{t,B}=\mu_t\) and \(\sum_{t,B}B_gz_{t,B}=q_g\) for every \(g\).
It satisfies \(\mathsf{EFX}^{+}\) if, whenever \(z_{t,B}>0\) and \(z_{s,B'}>0\), one has \(u_t(B)\geq u_t(B'-e_g)\) for every \(g\in I_t\) with \(v(g)>0\) and \(B'_g\geq1\), where \(e_g\) denotes one copy of \(g\). Comparisons include different bundles held by the same type.
Pareto efficiency means that no reassignment of individuals to integral bundles, preserving types and aggregate supplies, weakly increases utility almost everywhere and strictly increases it on positive mass; reassignment may split each original bundle class and need not satisfy fairness.
Can an allocation satisfying \(\mathsf{EFX}^{+}\) and Pareto efficiency be found, or infeasibility reported, in time polynomial in \(m,\tau,L\), or is this computational problem NP-hard?
For finitely many agents and individually listed goods, a complete \(\mathsf{EFX}^{+}\), Pareto-efficient allocation can be computed in polynomial time. [Akrami–Rezvan–Seddighin](https://arxiv.org/html/2202.13676v2)
No result settling this exact mass-allocation problem was identified in the literature search.
The problem is polynomial-time solvable, and every instance satisfying the stated hypotheses is feasible.
More precisely, an allocation satisfying \(\mathsf{EFX}^{+}\) and Pareto efficiency can be constructed with at most \(m+\tau\) positive type–bundle classes. Its entire explicit binary encoding has polynomial length.
The algorithm compresses the descending-value greedy rule from [Akrami–Rezvan–Seddighin, Algorithm 4 and Theorem 7.3](https://arxiv.org/html/2202.13676v2). The key is to process all copies of one category in a single batch, without expanding the population or the supplies.
Write every input rational in numerator–denominator form. Let \(N\) be the product of the denominators appearing in the type masses and supplies. Then
\[
\]
\(n_t=N\mu_t\in\mathbb Z_{>0},\qquad K_g=Nq_g\in\mathbb Z_{\geq0},\qquad \sum_t n_t=N.\)
Thus we may consider an implicit finite instance with \(N\) individuals, including \(n_t\) individuals of type \(t\), and \(K_g\) copies of category \(g\). These numbers may be exponentially large, but their binary lengths are polynomial in \(L\).
Likewise, let \(P\) be the product of the denominators of the common values, and put \(w_g=Pv(g)\). Every \(w_g\) is a nonnegative integer. Multiplying all utilities by the positive number \(P\) preserves the fairness inequalities.
We represent the implicit individuals by cohorts. A cohort is a triple \((t,B,n)\): it consists of \(n\) individuals of type \(t\), all holding bundle \(B\). Initially there are \(\tau\) cohorts, namely \((t,0,n_t)\).
After constructing the finite allocation implicitly, a cohort \((t,B,n)\) contributes mass \(n/N\) to \(z_{t,B}\). Identical type–bundle pairs can be merged.
Call an allocation *nonwasteful* if every copy with positive common value is assigned to an interested type. Categories with zero common value impose no restriction.
For any feasible mass allocation, total utility satisfies
\( \displaystyle \sum_{t,B}z_{t,B}u_t(B)\leq \sum_g v(g)q_g=:W. \)
Indeed, each copy contributes either its common value or zero to its holder’s utility. A nonwasteful allocation attains equality.
This proves Pareto efficiency even under the reassignment notion in the question. Any supply-preserving reassignment still has total utility at most \(W\). If it weakly improved utility almost everywhere and strictly improved it on positive mass, its total utility would exceed \(W\).
To justify that last inference explicitly, let \(\Delta\) be the individual utility gain. Under such a reassignment, \(\Delta\) is nonnegative almost everywhere, and \(\{\Delta>0\}\) has positive mass. Since
\( \displaystyle \{\Delta>0\}=\bigcup_{k\geq1}\{\Delta\geq 1/k\}, \)
one of these sets has positive mass, so the integral of \(\Delta\) is positive. All utilities are integrable because supplies and common values are finite and nonnegative.
Consequently, it suffices to construct a nonwasteful \(\mathsf{EFX}^{+}\) allocation.
Process copies in nonincreasing order of their common values. Give each positive-valued copy to a minimum-utility individual among those interested in its category. Zero-valued copies may be assigned arbitrarily.
Here is the fairness argument, including repeated copies. Use scaled utilities, and write \(V(B)=\sum_g w_gB_g\).
Suppose a copy of \(g\) is added to individual \(i\)’s bundle. Before this addition, nonwastefulness gives \(u_i(B_i)=V(B_i)\). Only comparisons whose target is the updated bundle need checking, because nobody’s own utility decreases.
If observer \(j\) does not value \(g\), the required inequalities follow from the previous allocation. If \(j\) values \(g\), greedy choice gives \(u_j(B_j)\geq u_i(B_i)\). For every copy \(h\) valued by \(j\) in the updated bundle, processing order gives \(w_h\geq w_g\). Therefore
\( \displaystyle u_j(B_i+e_g-e_h)\leq V(B_i)+w_g-w_h\leq V(B_i)=u_i(B_i)\leq u_j(B_j). \)
The observer’s utility after the addition is at least the last expression, including when \(j=i\). Zero-valued additions affect no utilities or required comparisons.
Starting from empty bundles, induction proves \(\mathsf{EFX}^{+}\). The rule also preserves nonwastefulness.
The remaining issue is implementing this rule without performing one iteration per copy.
Fix a positive-valued category \(g\), with scaled value \(w=w_g>0\) and supply \(K=K_g>0\). Consider the current eligible cohorts, indexed by \(j\). Let their sizes and current utilities be \(n_j\) and \(U_j\).
For each individual initially having utility \(U_j\), the priorities of successive copies of this category are
\( U_j,\ U_j+w,\ U_j+2w,\ldots. \)
The greedy rule selects the first \(K\) entries from the union of these sequences, counting every cohort sequence with multiplicity \(n_j\).
This characterization is exact: an individual’s successive priorities strictly increase. Hence ordering the marginal entries by priority always selects that individual’s preceding entries first, and each selected entry corresponds to a currently available greedy choice.
Write
\( U_j=wh_j+f_j,\qquad h_j=\lfloor U_j/w\rfloor,\qquad 0\leq f_j<w. \)
For an integer \(a\geq0\), define
\( \displaystyle F(a)=\sum_j n_j\max\{0,a-h_j\}. \)
This is precisely the number of marginal entries with priority strictly below \(aw\). For one individual in cohort \(j\), those entries have indices \(0,\ldots,a-h_j-1\) when \(a>h_j\), and there are none otherwise.
Find an integer \(a\) satisfying
\( F(a)\leq K<F(a+1). \)
This takes polynomial time by binary search. We have \(F(0)=0\), and the integer
\( H=\max_j h_j+K+1 \)
satisfies \(F(H)>K\). Thus binary search on the integer interval from zero to \(H\) yields the desired adjacent cutoff values.
Give every individual in eligible cohort \(j\) the base number
\( k_j=\max\{0,a-h_j\} \)
of copies. This assigns exactly \(F(a)\) copies. Put \(R=K-F(a)\).
The remaining relevant priorities lie in the interval from \(aw\), inclusive, to \((a+1)w\), exclusive. Each cohort with \(h_j\leq a\) contributes exactly one such entry per individual, with priority \(aw+f_j\). Cohorts with \(h_j>a\) contribute none. Consequently,
\( \displaystyle 0\leq R<F(a+1)-F(a)=\sum_{j:h_j\leq a}n_j. \)
Sort the cohorts with \(h_j\leq a\) by \(f_j\), breaking ties by any fixed cohort order. Assign one additional copy to individuals in this order until exactly \(R\) additional copies have been assigned.
Each eligible cohort receives its base number of copies uniformly. In the additional-copy step, each cohort receives either:
Only the cohort at the stopping point can fall into the third case. If it has size \(n_j\) and exactly \(s\) individuals receive the extra copy, replace it by cohorts
\( (t_j,B_j+(k_j+1)e_g,s) \)
and
\( (t_j,B_j+k_je_g,n_j-s), \)
omitting any zero-size cohort. Thus processing one category increases the number of cohorts by at most one.
The batch selects all priorities below \(aw\), followed by the first \(R\) priorities in the next interval. It therefore implements a valid sequence of individual greedy choices. The fairness proof in Section 3 applies exactly.
For a category with zero common value, write
\( K_g=bN+R,\qquad 0\leq R<N. \)
Give every individual \(b\) copies. Then give one additional copy to \(R\) individuals, following any fixed order of the current cohorts. Again, at most one cohort splits. Utilities and fairness remain unchanged.
Categories with zero supply require no operation.
Initially there are \(\tau\) cohorts. Each of the \(m\) categories increases this number by at most one. Hence the final allocation has at most \(m+\tau\) positive type–bundle classes.
We now check the sizes of all numbers used.
The integers \(N\), \(P\), \(n_t\), \(K_g\), and \(w_g\) have bit lengths bounded by a constant multiple of \(L\): their defining products involve input denominators whose total binary length is at most \(L\).
Throughout the algorithm:
Therefore these numbers, and the quotients and remainders used in batching, have polynomial bit length. The binary-search upper bound \(H\) also has polynomial bit length, so binary search takes polynomially many iterations.
Each evaluation of \(F\) uses at most \(m+\tau\) terms. Sorting, updating bundle vectors, and splitting one cohort also take polynomial time. There are only \(m\) category batches.
Finally, every output mass is \(n/N\), and every output bundle has \(m\) polynomial-length coordinates. Thus the complete explicit output has polynomial length.
For each type \(t\), the final cohort sizes sum to \(n_t\). For each category \(g\), the final bundles contain exactly \(K_g\) copies in aggregate. Dividing cohort sizes by \(N\) therefore gives
\( \displaystyle \sum_B z_{t,B}=\mu_t,\qquad \sum_{t,B}B_gz_{t,B}=q_g. \)
Every positive output class contains at least one implicit individual. The individual greedy allocation satisfies all required \(\mathsf{EFX}^{+}\) comparisons, so the mass allocation satisfies the support-wide comparisons as well. Comparison of a bundle with itself is immediate.
Every positive-valued copy is assigned to an interested type. Section 2 therefore proves Pareto efficiency against arbitrary permitted mass-splitting reassignments.
This establishes a polynomial-time construction for every valid input; no infeasible instance arises under the stated premises.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The output establishes a polynomial-time construction for every valid input, including a polynomial bound on the explicit output size. I found no substantive error, missing lemma, or unjustified theorem application.
Verified. The product \(N\) of the denominators of masses and supplies makes every \(n_t=N\mu_t\) a positive integer and every \(K_g=Nq_g\) a nonnegative integer. Normalization gives \(\sum_t n_t=N\).
The potentially exponential magnitude of \(N\) does not invalidate the construction: the algorithm represents individuals through cohorts and never explicitly enumerates the population.
The analogous scaling \(w_g=Pv(g)\) produces nonnegative integral values and preserves all fairness inequalities. Sections 3–4 explicitly work with scaled utilities.
The denominator products have polynomial binary length because their logarithms are bounded by the total input length. The corresponding scaled numerators also have polynomial binary length.
This scaling is sufficient for the claimed existence result. The prover does not need to show that every feasible mass allocation corresponds to this particular finite population.
Verified, including arbitrary mass-splitting reassignments.
The bound
\[
\sum_{t,B}z_{t,B}u_t(B)\leq \sum_g v(g)q_g=W
\]
follows from the common-value assumption: a copy contributes either its common value or zero. Nonwastefulness attains the upper bound.
The argument applies to arbitrary supply-preserving reassignments, rather than just reallocations among the implicit finite individuals. Nonnegative utility is bounded pointwise by the common-value sum of the bundle, whose integral is \(W\). Thus utilities remain integrable even if a competing reassignment uses unbounded bundle sizes.
The positive-gain argument is also correct. If the measurable gain \(\Delta\) is nonnegative almost everywhere and positive on positive mass, the stated countable-union identity ensures that some set where \(\Delta\geq 1/k\) has positive mass. Consequently its integral is strictly positive, contradicting the upper bound \(W\).
No additional restriction on the competing reassignment is used.
Verified.
For each positive-valued category, an eligible individual exists: the input assumptions ensure that some positive-mass type values the category, and scaling preserves a positive number of individuals of that type.
The induction correctly isolates comparisons whose target bundle changes. All other target bundles remain unchanged, and observers’ own utilities cannot decrease.
If observer \(j\) does not value the added category \(g\), adding its copy changes neither the relevant target utility nor the eligible removals.
If \(j\) values \(g\), the minimum-utility choice gives
\[
u_j(B_j)\geq u_i(B_i).
\]
Nonwastefulness gives \(u_i(B_i)=V(B_i)\). Every positively valued removable copy \(h\) in the updated bundle was processed no later than \(g\), so \(w_h\geq w_g\). Therefore the displayed chain
\[
u_j(B_i+e_g-e_h)
\leq V(B_i)+w_g-w_h
\leq V(B_i)
\leq u_j(B_j)
\]
is valid.
This argument covers repeated copies: removing one copy subtracts exactly \(w_h\). It also covers \(j=i\), because the observer’s utility after the update is at least its utility before the update.
Zero-valued additions create no new positively valued removal comparisons and change no utilities.
The citation is accurate: Algorithm 4 uses the stated descending-value, minimum-utility rule, and Theorem 7.3 asserts polynomial-time construction of an \(\mathsf{EFX}^{+}\), Pareto-efficient allocation for restricted additive valuations. The implicit finite instance satisfies those valuation hypotheses. Crucially, the prover supplies its own batching and mass-efficiency arguments rather than relying on the finite theorem for the continuous conclusion. [Akrami–Rezvan–Seddighin, Section 7](https://arxiv.org/html/2202.13676v2#S7)
Verified. An individual’s priorities for successive copies are \(U_j+\ell w\), with \(\ell\) a nonnegative integer. They increase strictly because \(w>0\).
Ordering these entries selects each individual’s predecessors before its later entries. Accordingly, the selected prefix can be realized by successive valid greedy choices. Ties between different individuals do not obstruct this reasoning.
Verified. With \(U_j=wh_j+f_j\) and \(0\leq f_j<w\), the number of entries strictly below \(aw\) is exactly \(\max\{0,a-h_j\}\) per individual. This remains correct when \(f_j=0\): the next entry is exactly at the boundary and is excluded.
Thus the formula for \(F(a)\), including multiplicity \(n_j\), is correct.
Verified. The eligible cohort set is nonempty. The proposed upper bound \(H=\max_j h_j+K+1\) satisfies \(F(H)>K\), while \(F(0)=0\).
The function is nondecreasing and eventually strictly increasing. Binary search therefore finds adjacent integers satisfying \(F(a)\leq K<F(a+1)\), including cases where \(F\) initially has a plateau.
The cutoff interval contains precisely one entry per individual from cohorts with \(h_j\leq a\). Its priority is \(aw+f_j\). Both the residual bound and the ordering by \(f_j\) are correct.
The boundary case \(K=F(a)\) gives \(R=0\) and requires no additional assignment.
Verified. Base assignments are uniform within each cohort. The residual assignment traverses cohorts consecutively, so only the stopping cohort can receive a partial extra assignment.
The resulting bundles and cohort sizes match the selected marginal entries. Omitting zero-size cohorts preserves positivity, and the total number of cohorts increases by at most one.
The zero-valued batch likewise assigns exactly \(bN+R=K_g\) copies and splits at most one cohort. It preserves utilities and fairness.
Verified.
Starting with \(\tau\) cohorts and adding at most one per category gives the claimed bound \(m+\tau\). Merging identical type–bundle pairs can only decrease it.
The bounds on cohort sizes, bundle coordinates, and utilities are valid:
\[
n_j\leq N,\qquad B_g\leq K_g,\qquad
U_j\leq\sum_g w_gK_g.
\]
They imply polynomial binary length for all stored quantities. Quotients, remainders, binary-search bounds, and intermediate values of \(F\) also have polynomial binary length.
Binary search takes a number of iterations polynomial in the binary length of \(H\), rather than in its magnitude. Each iteration examines at most \(m+\tau\) cohorts. Sorting and updating polynomially many bundle vectors also take polynomial time.
Consequently, both the running time and the complete explicit output encoding are polynomial in \(m,\tau,L\).
Verified. Preserving type counts and assigning exactly \(K_g\) copies yields the required mass and supply equalities after division by \(N\).
Every positive output class corresponds to implicit individuals, so fairness between output classes follows from individual fairness. Comparisons between distinct bundles of the same type are included. Comparing a bundle with itself is valid because removing a positively valued copy decreases its utility.
The construction also covers zero supplies, zero-valued categories, empty interest types, and the case of no goods. Positive masses and normalization ensure a nonempty population. No infeasibility branch is needed under the stated hypotheses.
Actionable feedback: No mathematical repair or additional clarification is required. The batching construction and the Pareto argument establish the claimed continuous result.
⟨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.