Answer: \(\mathrm{NP}\)-hard
Theorem 3.6 — class: algorithmic
Given a finite set ϴ of complete valuation types with rational masses μθ, ∑θ μθ = 1, two indivisible good classes, and a known sequence of rational per-population supplies qᵣ,ᵍ for rounds r = 1,…,R, decide whether and construct temporally EF1 mass transitions xᵣ,θ,b,b′. Each household has an integer bundle b ∈ ℤ≥0², transitions preserve its valuation type and satisfy b′ ≥ b coordinatewise, mass is conserved, and ∑θ,b,b′ (b′g − bg)xᵣ,θ,b,b′ = qᵣ,ᵍ. After every prefix r, every pair of positive-mass states (θ,b) and (θ′,b′) must satisfy vθ·b ≥ minₙ:b′g>0 vθ·(b′−eₙ).
An instance has valuation types \(T\) with rational masses \(\mu_t\ge0\), \(\sum_{t\in T}\mu_t=1\); \(K\) good types; rational supplies \(a_j\ge0\) in each of two identical rounds; and rational additive values \(v_{t,j}\ge0\). Write \(v_t(b)=\sum_{j=1}^K b_jv_{t,j}\) for \(b\in\mathbb Z_{\ge0}^K\).
A feasible repeated allocation is a finitely supported family \(\lambda_{t,b}\ge0\) with \(\sum_b\lambda_{t,b}=\mu_t\) and \(\sum_{t,b}\lambda_{t,b}b_j=a_j\) for every \(j\). For all \(\lambda_{t,b},\lambda_{t',b'}>0\) and \(r\in\{1,2\}\), require either \(r v_t(b)\ge r v_t(b')\), or some \(j\) with \(b'_j\ge1\) satisfies \(r v_t(b)\ge r v_t(b')-v_{t,j}\).
Is deciding whether such a feasible repeated allocation exists NP-hard, or solvable in polynomial time?
For indivisible agents and goods, deciding whether a repetitive allocation is TEF1 is NP-complete, even with two rounds and identical valuations.
No result for the exact mass-distribution formulation above is supplied here.
Deciding whether a feasible repeated allocation exists is weakly \(\mathrm{NP}\)-hard under polynomial-time many-one reductions. Hardness holds even with:
Consequently, a polynomial-time algorithm would imply \(\mathrm{P}=\mathrm{NP}\).
Write \(u(b)=v_t(b)\). If the condition for \(r=2\) holds through removal of good \(j\), then
\(2u(b)\ge 2u(b')-v_{t,j}\),
and hence
\(u(b)\ge u(b')-\frac12v_{t,j}\ge u(b')-v_{t,j}\).
Thus the corresponding \(r=1\) condition also holds. The direct no-envy alternative behaves similarly. It therefore suffices to analyze \(r=2\).
Reduce from PARTITION. Let \(s_1,\ldots,s_n\) be positive integers with
\(\sum_{i=1}^n s_i=2B\).
The question is whether some \(S\subseteq\{1,\ldots,n\}\) satisfies \(\sum_{i\in S}s_i=B\). We may assume \(n\ge2\).
Define
\(R=n+1\), \(q_i=R^{i-1}\), and \(Q=\sum_{i=1}^nq_i\).
Next put
\(D=nQ+1\),
\(C=s_{\max}D+q_n\),
\(C_\star=BD+Q\),
\(L=nC+C_\star+1\),
and
\(W=nL+C_\star\).
For each \(i\), introduce two ordinary goods \(x_i,y_i\), with values
\(w(x_i)=L+s_iD+q_i\),
\(w(y_i)=L+q_i\).
All these numbers have encoding length polynomial in the PARTITION input: \(q_n=(n+1)^{n-1}\) has \(O(n\log n)\) bits, and all remaining numbers are formed using polynomially many arithmetic operations.
There exists a nonnegative integral multiset of the ordinary goods having total value exactly \(W\) if and only if the PARTITION instance is positive. Moreover, every such multiset contains exactly one of \(x_i,y_i\) for every \(i\).
Let \(N\) be the total number of ordinary goods, counted with multiplicity. Every ordinary good has value between \(L\) and \(L+C\).
If \(N\ge n+1\), its value is at least
\((n+1)L>nL+C_\star=W\),
because \(L>C_\star\).
If \(N\le n-1\), its value is at most
\((n-1)(L+C)<nL<W\),
because \(L>(n-1)C\).
Thus an exact-\(W\) multiset must have \(N=n\).
Let \(b_{x_i}\) and \(b_{y_i}\) be its multiplicities, and put \(c_i=b_{x_i}+b_{y_i}\). Removing the contribution \(nL\) from its value gives
\(D\left(\sum_i b_{x_i}s_i-B\right)+\left(\sum_i c_iq_i-Q\right)=0\).
Since \(\sum_i c_i=n\), both \(\sum_i c_iq_i\) and \(Q\) lie strictly below \(D=nQ+1\). Consequently,
\(\left|\sum_i c_iq_i-Q\right|<D\).
The displayed equality therefore forces
\(\sum_i c_iq_i=Q\)
and
\(\sum_i b_{x_i}s_i=B\).
Furthermore, \(0\le c_i\le n<R\). Uniqueness of base-\(R\) representation applied to
\(\sum_i c_iR^{i-1}=\sum_iR^{i-1}\)
gives \(c_i=1\) for every \(i\). Hence exactly one of \(x_i,y_i\) occurs for each \(i\), and the indices for which \(x_i\) occurs form a partition side of sum \(B\).
Conversely, if \(S\) has sum \(B\), select \(x_i\) for \(i\in S\) and \(y_i\) otherwise. Its value is
\(nL+D\sum_{i\in S}s_i+\sum_iq_i=nL+BD+Q=W\).
This proves the lemma.
Finally, the total value of all \(2n\) ordinary goods is
\(\sum_i\bigl(w(x_i)+w(y_i)\bigr)=2nL+2BD+2Q=2W\).
Also, every ordinary good has value at most \(W\), since \(n\ge2\) and \(L+C<W\).
Create one valuation type \(t\) with \(\mu_t=1\). Its values for the ordinary goods are the numbers above.
Add one distinguished good \(h\) with value
\(v_t(h)=2W\).
Give every ordinary good and \(h\) supply
\(a_j=\frac13\).
Because there is only one type, a feasible family \(\lambda_{t,b}\) is simply a finitely supported probability distribution over integer bundles.
For a bundle \(b\), write:
Supply conservation implies
\(\mathbb E[k(b)]=\frac13\),
\(\mathbb E[x(b)]=\frac13\cdot 2W=\frac{2W}{3}\),
and therefore
\(\mathbb E[u(b)]=\frac{4W}{3}\).
In every feasible repeated allocation for the constructed instance:
Because \(\mathbb E[u]=4W/3<2W\), some occupied bundle has value below \(2W\). Choose an occupied bundle \(b_0\) of minimum value and write \(m=u(b_0)\). Necessarily \(k(b_0)=0\) and \(m<2W\).
There is also an occupied bundle \(b'\) with \(k(b')\ge1\), because \(\mathbb E[k]=1/3\).
Compare \(b_0\) with \(b'\) under the \(r=2\) fairness condition. The direct no-envy alternative is impossible because \(u(b')\ge2W>m\). Thus some good must be removable from \(b'\). Every single good has value at most \(2W\), so
\(2m\ge2u(b')-2W\).
Equivalently,
\(m\ge u(b')-W=(2k(b')-1)W+x(b')\).
If \(k(b')\ge2\), this would give \(m\ge3W\), contradicting \(m<2W\). Hence every occupied bundle has \(k(b)\in\{0,1\}\).
Since \(\mathbb E[k]=1/3\), the total mass of bundles with \(k=1\) is exactly \(1/3\). Let \(\overline{x}_1\) and \(\overline{x}_0\) be the conditional average ordinary values among bundles with \(k=1\) and \(k=0\), respectively. Let \(x_{\max}\) be the maximum ordinary value in a bundle with \(k=1\).
The previous inequality gives \(m\ge W+x_{\max}\). By minimality of \(b_0\), every bundle with \(k=0\) has ordinary value at least \(m\). Hence
\(\overline{x}_0\ge W+x_{\max}\ge W+\overline{x}_1\).
On the other hand, aggregate ordinary value gives
\(\frac13\overline{x}_1+\frac23\overline{x}_0=\frac{2W}{3}\).
Combining the two relations yields
\(\frac{2W}{3}\ge\frac13\overline{x}_1+\frac23(W+\overline{x}_1)=\frac{2W}{3}+\overline{x}_1\).
Thus \(\overline{x}_1=0\). Nonnegativity implies that every bundle containing \(h\) contains no ordinary goods. The aggregate equation then gives \(\overline{x}_0=W\). Since every \(k=0\) bundle has ordinary value at least \(W\), every such bundle has value exactly \(W\).
This proves the rigidity lemma.
Let \(S\) be a subset of sum \(B\). Define one ordinary bundle \(b^S\) by choosing \(x_i\) when \(i\in S\) and \(y_i\) otherwise. Define \(b^{\overline S}\) by making the opposite choice.
The encoding lemma gives
\(u(b^S)=u(b^{\overline S})=W\).
Each ordinary good occurs in exactly one of these two bundles. Assign mass \(1/3\) to each of \(b^S\), \(b^{\overline S}\), and the singleton bundle \(\{h\}\). This realizes supply \(1/3\) of every good.
The two ordinary bundles have equal value. The singleton \(\{h\}\) has value \(2W\). An ordinary bundle compared with \(\{h\}\) satisfies
\(2W=2\cdot W\ge2\cdot2W-v_t(h)=4W-2W\).
All reverse comparisons satisfy direct no-envy. Hence the allocation satisfies the \(r=2\) condition, and therefore also the \(r=1\) condition.
Suppose a feasible repeated allocation exists. By the rigidity lemma, every bundle not containing \(h\) has ordinary value exactly \(W\), and such bundles have total mass \(2/3>0\). Hence at least one nonnegative integral multiset of ordinary goods has value \(W\).
The encoding lemma then produces a subset \(S\) with
\(\sum_{i\in S}s_i=B\).
Thus the original PARTITION instance is positive.
The construction is polynomial and is positive exactly when the given PARTITION instance is positive. Therefore the mass-distribution problem is weakly \(\mathrm{NP}\)-hard, even for a single valuation type. The fractional splitting of valuation types does not make the problem polynomial: the anchor good and aggregate-value equalities force a genuinely combinatorial exact bundle.
⟨structured verdict parsed — rendered above⟩
The reduction is substantively correct and establishes weak \(\mathrm{NP}\)-hardness. The encoding lemma, rigidity argument, and both directions of the reduction check out. There are minor quantifier and source-problem formalization gaps, but neither requires new mathematical ideas.
The implication from the \(r=2\) removal condition to the \(r=1\) removal condition is correct:
\[ 2u(b)\ge 2u(b')-v_{t,j} \]
implies
\[ u(b)\ge u(b')-\frac12v_{t,j}\ge u(b')-v_{t,j}, \]
using \(v_{t,j}\ge0\). The direct no-envy alternative is independent of \(r\) after division by \(r>0\). Thus verifying \(r=2\) suffices.
The quantities \(q_i=(n+1)^{i-1}\) have polynomial bit length, with \(q_n\) using \(O(n\log n)\) bits. The displayed formulas for \(Q,D,C,C_\star,L,W\) use additions and multiplications of quantities whose bit lengths remain polynomial in the original input length. No pseudopolynomial expansion of the instance occurs.
The statement that polynomially many arithmetic operations alone ensure polynomial encoding length is not generally sufficient, but the explicit formulas here do have polynomial bit length.
The cardinality argument is correct.
Hence an exact-\(W\) multiset contains exactly \(n\) goods.
After subtracting \(nL\), the equality
\[ D\left(\sum_i b_{x_i}s_i-B\right)+\left(\sum_i c_iq_i-Q\right)=0 \]
is correct. Because \(\sum_i c_i=n\),
\[ 0\le\sum_i c_iq_i\le nq_n\le nQ<D, \]
while \(Q<D\). Therefore
\[ \left|\sum_i c_iq_i-Q\right|<D. \]
Since the first summand is divisible by \(D\), both summands must vanish.
The base-\(R\) argument is valid: \(0\le c_i\le n<R=n+1\), so the \(c_i\) are legitimate base-\(R\) digits. Uniqueness of base-\(R\) representation then gives \(c_i=1\) for every \(i\).
The converse construction has value
\[ nL+D B+Q=W. \]
Thus the encoding lemma is correct.
The computation that all ordinary goods together have value \(2W\) is also correct:
\[ \sum_i\bigl(w(x_i)+w(y_i)\bigr) =2nL+D\sum_i s_i+2Q =2nL+2BD+2Q =2W. \]
The bound \(w(g)\le W\) for every ordinary good follows from \(w(g)\le L+C<W\).
Supply conservation correctly yields
\[ \mathbb E[k]=\frac13, \qquad \mathbb E[x]=\frac13(2W)=\frac{2W}{3}, \]
and hence
\[ \mathbb E[u]=2W\mathbb E[k]+\mathbb E[x]=\frac{4W}{3}. \]
Finite support guarantees that a minimum-value occupied bundle exists.
Since \(\mathbb E[u]<2W\), some occupied bundle has value below \(2W\). A minimum such bundle \(b_0\) necessarily has no copy of \(h\).
For an occupied bundle \(b'\) containing \(h\), direct no-envy from \(b_0\) to \(b'\) is impossible. The removal alternative gives
\[ 2m\ge 2u(b')-v(g)\ge 2u(b')-2W, \]
because every individual good has value at most \(2W\). Thus
\[ m\ge u(b')-W=(2k(b')-1)W+x(b'). \]
If \(k(b')\ge2\), this implies \(m\ge3W\), contradicting \(m<2W\). The calculation is correct.
Once it is established for every occupied bundle that \(k\in\{0,1\}\), the total mass of the \(k=1\) bundles is exactly \(1/3\). Both conditional averages are well-defined.
For every \(k=1\) bundle, the same inequality gives \(m\ge W+x(b')\). Consequently,
\[ \overline{x}_0\ge W+x_{\max}\ge W+\overline{x}_1. \]
Combining this with
\[ \frac13\overline{x}_1+\frac23\overline{x}_0=\frac{2W}{3} \]
correctly yields
\[ \frac{2W}{3}\ge\frac{2W}{3}+\overline{x}_1. \]
Nonnegativity forces \(\overline{x}_1=0\). Because the support is finite and every occupied support point has positive mass, every \(k=1\) bundle has ordinary value zero. The aggregate equation then gives \(\overline{x}_0=W\), and the lower bound on all \(k=0\) bundles forces each one to have value exactly \(W\).
If \(S\) has sum \(B\), its complement also has sum \(B\), since the total is \(2B\). The two opposite-choice bundles therefore both have value \(W\), and together contain every ordinary good exactly once.
Giving mass \(1/3\) to those two bundles and to \(\{h\}\) realizes every supply.
The only nontrivial fairness comparison is from an ordinary bundle of value \(W\) to \(\{h\}\) of value \(2W\). Removing \(h\) gives equality:
\[ 2W=4W-2W. \]
All other ordered comparisons satisfy direct no-envy or equality. Hence the allocation is feasible.
The rigidity lemma gives positive total mass \(2/3\) to ordinary bundles of value exactly \(W\). Therefore at least one integral multiset of ordinary goods has value \(W\). The encoding lemma then produces a subset of sum \(B\). This direction is correct.
⟨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.