Answer: Polynomial-time solvable; every valid instance admits a rational WEFX and identity-preserving Pareto-optimal configuration.
Theorem 4.3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateUnder binary additive valuations, for any number of agents, a WEFX and PO allocation exists and can be computed in polynomial-time. However, while an allocation satisfying WEFX exists in this restricted setting, there are not many of them, as illus- trated with the following result.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite item kinds \(G\), agent types \(T\), rational masses \(\mu_t\), entitlements \(w_t>0\), binary values \(a_{t,g}\in\{0,1\}\), and rational per-capita supplies \(\rho_g\), where a bundle is an indivisible-copy vector \(b\in\mathbb{Z}_{\ge0}^{G}\), find a rational sparse configuration \(x_{t,b}\ge0\) satisfying \(\sum_b x_{t,b}=\mu_t\) and \(\sum_{t,b}b_gx_{t,b}=\rho_g\). Require that every pair of supported type-bundle pairs satisfies WEFX after removing any one copy, and that the configuration is PO under identity-preserving measurable reallocations; determine whether such a configuration can be computed in time polynomial in \(|T|+|G|\) and the input bit length, independently of the common denominator.
A society is given by its support: a list of \(\tau\) types \(T\) with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
There are \(m=|G|\) item kinds, binary-rational supplies \(\rho_g\ge0\), binary-rational entitlements \(w_t>0\), and binary additive valuations \(v_t(b)=\sum_g a_{t,g}b_g\), where \(a_{t,g}\in\{0,1\}\) and \(b\in\mathbb Z_{\ge0}^{G}\). Let \(L\) be the total input bit length.
A configuration is a finite list of positive rational entries \(x_{t,b}\), with all unlisted entries zero, satisfying \(\sum_bx_{t,b}=\mu_t\) and \(\sum_{t,b}b_gx_{t,b}=\rho_g\) for every \(g\); all supply must be allocated.
Require WEFX: for every supported \((t,b),(s,c)\) and every \(g\) with \(c_g>0\), \(v_t(b)/w_t\ge v_t(c-e_g)/w_s\), where \(e_g\) is the unit vector. This includes removal of copies valued zero by the evaluating type.
For identity-preserving Pareto optimality, realize each entry as an interval of agents of length \(x_{t,b}\), with fixed type \(t\) and initial bundle \(b\). No measurable reassignment of integer bundles preserving the supply integrals may weakly improve utility almost everywhere and strictly improve it on a set of positive measure; competing assignments need not satisfy WEFX.
Is finding a rational configuration satisfying WEFX and Pareto optimality, or reporting that none exists, solvable in time polynomial in \(m,\tau,L\), independently of the numerical common denominator except through \(L\), or is this computational problem NP-hard?
For finitely many explicitly listed agents and goods, binary additive valuations and positive entitlements always admit a complete WEFX and Pareto-optimal allocation computable in polynomial time ([Neoh and Teh, 2025](https://arxiv.org/html/2504.03951v1)).
No result settling this exact atomless configuration problem was located in the literature search.
The problem is polynomial-time solvable. Every valid instance admits a rational configuration satisfying WEFX and the stated identity-preserving Pareto optimality. A configuration can be computed in time polynomial in \(m,\tau,L\), with at most \(\tau(m+1)\) positive entries and polynomial total encoding length.
The proof uses an exactly optimizable discrete potential and a short, explicit decomposition of rational averages into integer bundles.
Define
\[
\]
\(G^+=\{g\in G:\text{some }t\in T\text{ has }a_{t,g}=1\}\),
\(G^0=G\setminus G^+\), and
\(S=\sum_{g\in G^+}\rho_g\).
Call a configuration *nonwasteful* if every supported \((t,b)\) satisfies \(b_g=0\) whenever \(g\in G^+\) and \(a_{t,g}=0\).
Lemma 1. A configuration is Pareto optimal in the sense of the question if and only if it is nonwasteful.
Proof. For every feasible measurable assignment, integrated utility is at most \(S\): each copy of a kind in \(G^+\) contributes at most one unit of utility, and kinds in \(G^0\) contribute zero. A nonwasteful configuration attains integrated utility exactly \(S\).
If a competing assignment weakly improves utility almost everywhere and strictly improves it on a set of positive measure, its integrated utility is strictly larger. Indeed, utilities are integer-valued, so every strict improvement increases utility by at least one. This contradicts the upper bound \(S\).
Conversely, suppose a supported entry \((t,b)\) wastes a copy of \(g\in G^+\). Choose a type \(s\) valuing \(g\), and a positive-measure entry of that type. On equal, sufficiently small portions of the two entries, remove one copy of \(g\) from the first portion and add one copy to the second. Supply integrals are preserved, donors lose no utility, and recipients strictly improve. Thus the original configuration is not Pareto optimal. \(\square\)
We initially allocate only \(G^+\), nonwastefully. Section 5 allocates \(G^0\).
For an integer utility \(k\geq 0\), define
\(f_t(k)=k(k-1)/(2w_t)\).
For a nonwasteful configuration on \(G^+\), define its potential by
\(\Phi(x)=\sum_{t,b}x_{t,b}f_t(v_t(b))\).
Its marginal increments satisfy
\(f_t(k+1)-f_t(k)=k/w_t\).
Lemma 2. Every global minimizer of \(\Phi\) among rational nonwasteful configurations on \(G^+\) satisfies WEFX.
Proof. Suppose supported entries \((t,b)\) and \((s,c)\) violate WEFX for some \(g\) with \(c_g>0\). Put \(k=v_t(b)\) and \(h=v_s(c)\). Nonwastefulness implies that every copy in \(c\) is valued by \(s\), so \(h=\sum_r c_r\). Consequently,
\(k/w_t<v_t(c-e_g)/w_s\leq(h-1)/w_s\).
The violating right-hand side is positive. Hence \(c\) contains a copy of some kind \(r\) valued by \(t\). That copy is also valued by \(s\), by nonwastefulness.
Choose equal portions of rational mass \(\varepsilon>0\) from the two supported entries. Transfer one copy of \(r\) from every donor in the second portion to a recipient in the first. The entries must be distinct, since an entry cannot violate WEFX against itself. Thus the portions can be chosen disjoint.
The transfer preserves supplies and nonwastefulness. Its potential change is
\(\varepsilon\bigl(f_t(k+1)-f_t(k)+f_s(h-1)-f_s(h)\bigr)
=\varepsilon\bigl(k/w_t-(h-1)/w_s\bigr)<0\).
This contradicts global minimality. \(\square\)
The next two sections establish that such a minimizer can be constructed in polynomial time.
Let \(F_t\) be the piecewise-linear interpolation of \(f_t\) between consecutive nonnegative integers. For \(q\geq0\), writing \(k=\lfloor q\rfloor\), we have
\(F_t(q)=\bigl(kq-k(k+1)/2\bigr)/w_t\).
We need the following explicit decomposition.
Lemma 3. Given a nonnegative rational vector \(r=(r_1,\ldots,r_d)\), one can compute a rational distribution on at most \(d+1\) nonnegative integer vectors \(b\) such that:
The computation and output encoding length are polynomial in the encoding length of \(r\) and in \(d\).
Proof. Define cumulative sums \(C_0=0\) and \(C_j=\sum_{i=1}^j r_i\). For \(\theta\in[0,1)\), set
\(b_j(\theta)=\lfloor C_j+\theta\rfloor-\lfloor C_{j-1}+\theta\rfloor\).
Because cumulative sums are nondecreasing, these are nonnegative integers. Telescoping gives
\(\sum_j b_j(\theta)=\lfloor q+\theta\rfloor\),
which has the required two possible values.
For every nonnegative real \(u\),
\(\int_0^1\lfloor u+\theta\rfloor\,d\theta=u\).
Indeed, writing \(u=n+\delta\) with \(0\leq\delta<1\), the integrand equals \(n\) on length \(1-\delta\) and \(n+1\) on length \(\delta\). Therefore,
\(\int_0^1 b_j(\theta)\,d\theta=C_j-C_{j-1}=r_j\).
Each cumulative floor changes at most once inside \([0,1)\). Thus at most \(d\) distinct internal breakpoints partition the interval into at most \(d+1\) constant-bundle intervals. Their rational lengths give the distribution weights.
Cumulative sums, breakpoint sorting, floor computations, and interval-length calculations require polynomial time and produce rationals and integers of polynomial encoding length. For \(d=0\), use the empty vector with probability one. \(\square\)
In particular, if all coordinates correspond to goods valued by type \(t\), this distribution has expected potential exactly \(F_t(q)\).
For every \(g\in G^+\) and type \(t\) valuing it, introduce a rational aggregate allocation variable \(z_{t,g}\geq0\). Require
\(\sum_{t:a_{t,g}=1}z_{t,g}=\rho_g\).
The average utility of type \(t\) is
\(q_t=\mu_t^{-1}\sum_{g:a_{t,g}=1}z_{t,g}\).
Consider minimizing
\(\sum_t\mu_tF_t(q_t)\)
over these aggregate allocations.
This is an exact relaxation of potential minimization. To prove the lower bound, fix a type \(t\), let \(k=\lfloor q_t\rfloor\), and observe that for every nonnegative integer \(h\),
\(f_t(h)-\bigl(kh-k(k+1)/2\bigr)/w_t
=(h-k)(h-k-1)/(2w_t)\geq0\).
The last inequality holds because \(h-k\) is an integer: its product with the preceding integer is nonnegative. Multiplying this inequality by the configuration masses and summing within type \(t\) gives
\(\sum_b x_{t,b}f_t(v_t(b))\geq\mu_tF_t(q_t)\).
Conversely, any rational feasible aggregate allocation can attain this lower bound. Apply Lemma 3 within each type to the averages \(r_g=z_{t,g}/\mu_t\), using only kinds valued by that type. Multiply the distribution weights by \(\mu_t\).
The resulting configuration has the required type masses and kind supplies. Its utilities within each type are consecutive integers surrounding \(q_t\), so its potential equals \(\sum_t\mu_tF_t(q_t)\).
Set
\(K_t=\lceil S/\mu_t\rceil\)
and
\(H_t=(K_t+1)^2/w_t\).
Every feasible aggregate allocation satisfies \(0\leq q_t\leq K_t\). On this interval,
\(F_t(q)=\max_{0\leq k\leq K_t,\;k\in\mathbb Z}
\bigl(kq-k(k+1)/2\bigr)/w_t\).
To verify the maximum formula, the difference between the expressions indexed by \(k+1\) and \(k\) is \((q-k-1)/w_t\). Thus a maximizing index is \(\lfloor q\rfloor\), with a possible adjacent tie at integer \(q\).
Introduce epigraph variables \(y_t\). The linear program minimizes
\(\sum_t\mu_ty_t\)
subject to the aggregate allocation constraints, the defining equations for \(q_t\), and
\(0\leq q_t\leq K_t\), \(0\leq y_t\leq H_t\), together with
\(w_ty_t\geq kq_t-k(k+1)/2\)
for every integer \(k\in\{0,\ldots,K_t\}\).
The upper bounds \(H_t\) do not alter the optimum, because
\(F_t(q)\leq f_t(K_t)\leq H_t\)
throughout the allowed interval.
The linear program is nonempty: assign each kind in \(G^+\) entirely to any type valuing it, and set \(y_t=F_t(q_t)\). It is bounded, since supplies bound every \(z_{t,g}\), and explicit bounds constrain \(q_t,y_t\).
Although there may be exponentially many epigraph inequalities, separation is polynomial-time:
If that inequality holds, all epigraph inequalities for that type hold, because its right-hand side is maximal.
We apply the standard strong separation–optimization theorem for rational polyhedra: a rational linear program can be optimized exactly in polynomial time given a polynomial-time strong separation oracle and a polynomial bound on inequality encoding lengths. The theorem also applies to lower-dimensional polyhedra. See [Grötschel–Lovász–Schrijver, Chapter 6, Theorem 6.4.9](https://link.springer.com/chapter/10.1007/978-3-642-78240-4_7).
Its hypotheses hold here:
Therefore an exact rational optimum of polynomial encoding length can be computed in polynomial time. Since every \(\mu_t\) is positive, optimal epigraph values satisfy \(y_t=F_t(q_t)\).
Apply Lemma 3 to this optimum. The resulting rational nonwasteful configuration attains the global minimum of \(\Phi\). By Lemma 2, it satisfies WEFX.
Let the constructed configuration on \(G^+\) be \(x\). Choose a supported entry \((s,c)\) minimizing normalized utility, and write
\(\lambda=v_s(c)/w_s=\min_{(t,b):x_{t,b}>0}v_t(b)/w_t\).
Let its mass be \(\gamma=x_{s,c}>0\).
Allocate every kind in \(G^0\) within this entry. Specifically, apply Lemma 3 to the vector of averages \((\rho_g/\gamma)_{g\in G^0}\), and replace the chosen entry by the resulting entries with bundles \(c+d\). Their masses sum to \(\gamma\), and their aggregate allocations of worthless kinds are exactly the required supplies.
All agents’ utilities remain unchanged. For any evaluating type \(t\),
\(v_t(c+d)=v_t(c)\leq v_s(c)\),
because all copies in \(c\) are valued by \(s\), valuations are binary, and every copy in \(d\) is globally worthless.
Hence, for every kind \(g\) present in a modified target bundle and every supported evaluating bundle \(b'\),
\(v_t(c+d-e_g)/w_s
\leq v_s(c)/w_s
=\lambda
\leq v_t(b')/w_t\).
This proves WEFX for every modified target bundle, including removal of a copy valued zero by the evaluator. For unmodified target bundles, the original inequalities continue to hold because evaluating utilities are unchanged.
The completed configuration is nonwasteful, so Lemma 1 proves its identity-preserving Pareto optimality against arbitrary feasible measurable reassignment.
Write \(d=|G^+|\) and \(d_0=|G^0|\). The initial construction uses at most \(\tau(d+1)\) entries. Replacing one entry to allocate worthless kinds adds at most \(d_0\) entries. Thus the final support size is at most
\(\tau(d+1)+d_0\leq\tau(m+1)\).
All masses and bundle counts have polynomial encoding length. This follows from the polynomial encoding length of the exact linear-program optimum and the explicit rational operations in Lemma 3. The division by \(\gamma\) when allocating worthless kinds also preserves polynomial encoding length because \(\gamma\) is a positive rational of polynomial encoding length. Duplicate entries can be merged.
The construction never expands rational masses or supplies into grid agents or individual copies. Its bit complexity is polynomial in \(m,\tau,L\), independently of the numerical common denominator except through its contribution to \(L\).
⟨structured verdict parsed — rendered above⟩
Result: proved. The output resolves the assigned problem: every valid instance admits the required rational configuration, and the construction runs in polynomial bit complexity in \(m,\tau,L\). I found no major or minor mathematical gaps.
Lemma 1 is correct for the specified identity-preserving notion.
For any feasible measurable assignment, binary additive valuations imply that integrated utility is at most \(S\). Globally worthless goods contribute nothing, and each allocated copy of a positively valued kind contributes at most one. The finite supply integrals also ensure utility is integrable.
A nonwasteful configuration attains this bound. A competing assignment that weakly improves utility almost everywhere and strictly improves it on a positive-measure set would increase integrated utility strictly: integer utilities make the increase at least one on that set. Thus the integrated-utility argument applies to arbitrary measurable competitors, as required.
For the converse, a wasted copy belongs to a positive-mass entry, and a type valuing it has positive mass. The donor and recipient entries are distinct because their types disagree about the value of that kind. Equal sufficiently small portions exist in their agent intervals. The described transfer preserves supplies and identities, leaves donor utility unchanged, and strictly increases recipient utility on positive measure.
No restriction requiring competitors to satisfy WEFX is used.
Lemma 2 is correct.
The marginal identity
\(f_t(k+1)-f_t(k)=k/w_t\)
is correct, including at \(k=0\).
For a supported target bundle \(c\), nonwastefulness on \(G^+\) gives
\(v_s(c)=\sum_r c_r=h\).
Removing any present copy leaves total size \(h-1\), so
\(v_t(c-e_g)\leq h-1\).
This bound remains valid when the removed copy has value zero for the evaluating type.
A violation therefore implies
\(k/w_t<(h-1)/w_s\).
Its original right-hand side is positive, which ensures that \(c\) contains a copy valued by \(t\). Nonwastefulness ensures that the same copy is valued by \(s\).
The transfer preserves nonnegative integer bundles, supplies, and nonwastefulness. Rational positive portions can be chosen from the rational entry masses. An entry cannot violate WEFX against itself, so the two portions can be disjoint even when their types coincide.
The computed potential change,
\(\varepsilon(k/w_t-(h-1)/w_s)\),
is strictly negative. This contradicts global minimality within precisely the rational feasible class stated in the lemma.
The argument establishes every required WEFX inequality.
Lemma 3 and its complexity claim are correct.
The cumulative-floor differences are nonnegative integers because cumulative sums are nondecreasing. Their sum telescopes to
\(\lfloor q+\theta\rfloor\),
which takes only the asserted total sizes.
The integral identity for each cumulative floor is correct, including when its argument is an integer. Subtracting the two integral identities gives the claimed coordinate average.
Each of the \(d\) nonconstant cumulative-floor expressions has at most one internal breakpoint. Distinct internal breakpoints therefore produce at most \(d+1\) positive-length intervals. Values at isolated breakpoints do not affect the distribution.
All cumulative sums and breakpoints are rational. Their exact calculation, sorting, interval lengths, and resulting bundle coordinates have polynomial encoding length and require polynomial time. The stated treatment of \(d=0\) is valid.
For a type receiving only goods it values, bundle size equals utility. Consequently the decomposition attains exactly the piecewise-linear interpolation \(F_t(q)\), as claimed.
Both directions of the relaxation are justified.
The interpolation formula is correct. The identity
\(f_t(h)-(kh-k(k+1)/2)/w_t=(h-k)(h-k-1)/(2w_t)\)
also checks out.
For integer \(h-k\), the product of the two consecutive integers is nonnegative, including when \(h<k\). Thus the claimed affine lower bound holds for every possible integer utility.
Summing with configuration masses gives the lower bound at the type’s average utility. Conversely, applying Lemma 3 to the rational coordinate averages produces a feasible rational configuration attaining the bound. The multiplication by \(\mu_t\) preserves the required type masses and supplies.
This proves exact equivalence of the two minimization problems, rather than merely a lower bound on the original optimum.
The linear program and separation oracle are valid.
The bound \(q_t\leq S/\mu_t\leq K_t\) follows from nonnegative aggregate allocations and total positively valued supply.
For the affine expressions defining the epigraph, the stated difference between consecutive indices is correct. It proves that \(\lfloor q_t\rfloor\) is a maximizing permitted index whenever \(0\leq q_t\leq K_t\). The endpoint cases are covered.
The upper bound on \(y_t\) does not remove an optimum: \(F_t\) is nondecreasing on the relevant interval, and
\(F_t(q_t)\leq f_t(K_t)\leq H_t\).
The given feasible construction establishes nonemptiness. Nonnegative supply equations bound every aggregate variable, while explicit bounds constrain the remaining variables.
The oracle checks the explicit constraints before taking floors. Thus the selected index is always permitted. A violated checked inequality supplies a separating hyperplane; otherwise, maximizing the right-hand side certifies all epigraph inequalities.
The cited strong separation–optimization theorem applies to well-described rational polyhedra and yields exact optimization without a full-dimensionality assumption. This is confirmed by [Grötschel–Lovász–Schrijver, Theorem 6.4.9](https://www.zib.de/userpage/groetschel/pubnew/paper/groetschellovaszschrijver1988.pdf).
Its hypotheses are satisfied as written:
In particular, numerical values of \(K_t\) need not be polynomially bounded: their binary lengths, and the binary lengths of \(k(k+1)/2\), are polynomially bounded.
Since all objective coefficients \(\mu_t\) are positive, an optimum has \(y_t=F_t(q_t)\). The subsequent decomposition therefore produces an actual global potential minimizer of polynomial encoding length.
Section 5 correctly addresses the additional WEFX constraints introduced by worthless copies.
A minimum normalized-utility entry exists because the constructed support is finite and nonempty. Replacing it using Lemma 3 preserves its total mass and allocates precisely the supplies in \(G^0\).
Every evaluating utility is unchanged. For the original selected bundle, nonwastefulness and binary valuations give
\(v_t(c)\leq v_s(c)\).
Globally worthless additions contribute zero to every type.
Consequently, removing any present copy from a modified target bundle gives an evaluated value at most \(v_s(c)\). Dividing by \(w_s\) and using the selected minimum \(\lambda\) proves all WEFX inequalities involving modified targets. This explicitly covers removal of copies valued zero.
For unmodified targets, unchanged evaluating utilities preserve the original inequalities. Nonwastefulness is preserved, so Lemma 1 establishes the required Pareto optimality.
The final resource bounds are correct.
The initial support bound is \(\tau(d+1)\). Replacing one entry by at most \(d_0+1\) entries adds at most \(d_0\), yielding
\(\tau(d+1)+d_0\leq\tau(m+1)\).
Here \(\tau\geq1\) follows from the normalized positive masses.
Polynomial encoding length survives both decomposition stages. In particular, division by the positive rational mass \(\gamma\) increases bit length only polynomially; a small numerical value does not require a large unary representation.
The argument covers zero supplies, \(S=0\), types valuing no goods, \(G^+=\varnothing\), \(G^0=\varnothing\), and \(m=0\). No denominator-dependent expansion is performed.
No mathematical repair or additional clarification is required. The prover’s claimed polynomial-time resolution is supported by the argument.
⟨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.