Answer: —
Theorem 7 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThere exists a poly-time algorithm computing an sEF1 allocation which is optimal for MAXUT. Sketch. The theorem is a consequence of the following ob- servation: Given an optimal allocation OPT, if i sa-envies j, then si(g) = sj(g), for each g ∈OPTj. Our algorithm sequentially assigns the goods in G opti- mally while maintaining EF1. Assume at a certain step the current partial allocation A is EF1 and g has to be assigned to an agent i∗∈arg maxi si(g), to guarantee optimality.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finitely many agent types with rational masses, finitely many good types with rational per-capita supplies, additive private and social-impact valuations, compute a mass allocation over integral bundle vectors maximizing total social impact subject to support-wise sEF1.
Definitions. Let \(G\) be a finite set of indivisible good classes and \(\Theta\) a finite type set. Each type \(\theta\) has nonnegative additive agent valuation \(v_\theta\) and social-impact valuation \(s_\theta\). Given rational \(\mu_\theta\) with \(\sum_\theta\mu_\theta=1\) and supplies \(\rho_g\), choose \(x_{\theta,B}\ge0\) for \(B\subseteq G\), with \(\sum_Bx_{\theta,B}=\mu_\theta\) and \(\sum_{\theta,B:g\in B}x_{\theta,B}=\rho_g\). It is support-wise \(\mathrm{EF}k\) if, whenever \(x_{\theta,B},x_{\phi,B'}>0\), some \(S\subseteq B'\) with \(|S|\le k\) satisfies \(v_\theta(B)\ge v_\theta(B'\setminus S)\). Let \(\operatorname{OPT}_{\mathrm{EF}k,\infty}\) maximize \(\sum_{\theta,B}x_{\theta,B}s_\theta(B)\); let \(\operatorname{OPT}_{\mathrm{all}}\) be the same optimum without the \(\mathrm{EF}k\) constraint.
Target. Given a rational threshold \(T\), is deciding whether \(\operatorname{OPT}_{\mathrm{EF}k,\infty}\ge T\) polynomial-time solvable, or NP-hard? Determine the worst-case ratio \(\sup \operatorname{OPT}_{\mathrm{all}}/\operatorname{OPT}_{\mathrm{EF}k,\infty}\) for fixed \(\Theta,\mu,\rho,k\) over additive valuations, including the specified \(\varepsilon\to0\) regime.
Nearest known results. In the discrete \(n\)-agent setting, for \(h=n-k\), \(m=hn+k-1\), identical unit agent valuations, and social impact \(1\) only for goods assigned to agent \(1\), every \(\mathrm{EF}k\) allocation has social welfare at most \(h+k-1\), while the unconstrained optimum is \(m\); thus no approximation better than \(n-k+1\) is possible. This result does not address allocations of mass over bundles.
Under the standard binary encoding of rational data:
\[
\frac{M}{\varepsilon M+(1-\varepsilon)k},
\]
which tends to \(1/\varepsilon\) as \(M\to\infty\), and hence diverges when \(\varepsilon\to0\).
Fix the support of a feasible solution. On that support, the mass and supply constraints form a rational linear program with \(|\Theta|+|G|\) equality constraints. Maximizing the social objective over this fixed support has a basic optimal solution with at most \(|\Theta|+|G|\) positive variables.
Passing to a sub-support preserves support-wise \(\mathrm{EF}k\). Standard determinant bounds show that the nonzero masses in such a basic solution have polynomial encoding length. Thus a certificate consists of polynomially many triples \((\theta,B,x_{\theta,B})\).
For two positive support cells \((\theta,B)\) and \((\phi,B')\), the best set \(S\) consists of the at most \(k\) goods in \(B'\) having largest \(v_\theta\)-value. Hence the condition can be verified in polynomial time by checking
\[
v_\theta(B)\ge v_\theta(B')-\sum_{g\in L_k^\theta(B')}v_\theta(g),
\]
where \(L_k^\theta(B')\) denotes those largest-valued goods. Consequently, the threshold problem belongs to \(\mathrm{NP}\).
We reduce from PARTITION. Let the input be positive integers \(a_1,\ldots,a_m\), with \(W=\sum_i a_i\). Write \(O=\{g_1,\ldots,g_m\}\).
Create two types \(A,B\), each of mass \(1/2\). Add \(k\) dummy goods \(D=\{d_1,\ldots,d_k\}\), and give every good supply \(1/2\).
Let \(H=W+1\). Both types have the same agent valuation:
\[
v_A(g_i)=v_B(g_i)=a_i,\qquad
v_A(d_j)=v_B(d_j)=H.
\]
Only type \(A\) has positive social impact:
\[
s_A(g_i)=a_i,\qquad s_A(d_j)=H,\qquad s_B(g)=0.
\]
Set
\[
T=\frac{kH}{2}+\frac{W}{4}.
\]
Assign all original goods to \(A\) and all dummy goods to \(B\). Type \(A\) can remove all \(k\) dummy goods when comparing itself with \(B\), while type \(B\)'s own value is \(kH>W\). Thus this allocation is support-wise \(\mathrm{EF}k\).
For dummy \(d_j\), let \(\delta_j\) be the mass of type \(B\) receiving \(d_j\), and put \(L=\sum_j\delta_j\). Since \(d_j\) has supply \(1/2\), the mass of type \(A\) missing \(d_j\) is also \(\delta_j\). The dummy contribution to social welfare is therefore
\[
H\left(\frac{k}{2}-L\right).
\]
Call an \(A\)-bundle full if it contains all \(k\) dummies, and call a \(B\)-bundle zero if it contains no dummy. When \(L<1/2\), the masses of full \(A\)-bundles and zero \(B\)-bundles are both at least \(1/2-L\).
Let \(w(X)=\sum_{g_i\in X}a_i\). For every supported full \(A\)-bundle \(X\) and zero \(B\)-bundle \(Y\), support-wise \(\mathrm{EF}k\) from \(B\)'s perspective implies
\[
w(Y)\ge w(X).
\]
Indeed, \(v_B(Y)\le W\). If fewer than all \(k\) dummies were removed from \(X\), a dummy of value \(H>W\) would remain. Thus the only possible witness removes all \(k\) dummies.
Let \(y_F\) be the total original-good impact on full \(A\)-bundles, \(y_N\) that on nonfull \(A\)-bundles, and \(z_0\) the original weight on zero \(B\)-bundles. The pointwise ordering above and the possible mass discrepancy of at most \(L\) give
\[
y_F\le z_0+LW.
\]
Moreover, \(y_N\le LW\). Since the total original-good weight supplied is \(W/2\),
\[
\frac W2\ge y_F+y_N+z_0
\ge 2y_F+y_N-LW.
\]
Consequently, the total original impact \(y=y_F+y_N\) satisfies
\[
y\le \frac W4+LW.
\]
For \(L<1/2\), total welfare is therefore at most
\[
\frac{kH}{2}-HL+\frac W4+LW
=T-L(H-W)\le T.
\]
Since \(H>W\), equality requires \(L=0\).
If \(L\ge1/2\), the cruder bound \(y\le W/2\) gives welfare at most
\[
\frac{kH}{2}-\frac H2+\frac W2<T.
\]
Thus every allocation attaining \(T\) assigns every dummy entirely to type \(A\).
When \(L=0\), every \(A\)-bundle contains all dummies and every \(B\)-bundle contains none. For every supported pair \(X_A,X_B\), the preceding argument gives
\[
w(X_B)\ge w(X_A).
\]
Reaching \(T\) requires original impact \(W/4\). Hence the average original weight of both an \(A\)-agent and a \(B\)-agent is \(W/2\). The pointwise inequality then forces every supported original part to have weight exactly \(W/2\). Any supported \(A\)-bundle therefore yields a partition.
Conversely, if \(S\subseteq O\) satisfies \(w(S)=W/2\), assign \(D\cup S\) to all \(A\)-agents and \(O\setminus S\) to all \(B\)-agents. Type \(B\) removes the \(k\) dummies from \(A\)'s bundle, after which both original parts have value \(W/2\). Its welfare is exactly \(T\).
Therefore the threshold is attainable if and only if the PARTITION instance is positive.
Use two types of mass \(1/2\), the original goods with supply \(1/2\), and one dummy \(d\) with supply \(1/2\). Let \(H=W+1\), and define
\[
v_A(d)=H,\qquad v_B(d)=0,\qquad
v_A(g_i)=v_B(g_i)=a_i.
\]
Let \(s_A(g_i)=a_i\), with every other social impact zero, and set \(T=W/4\).
The allocation giving \(d\) to \(A\) and all originals to \(B\) is envy-free, so feasibility is promised.
In every envy-free allocation, no positive mass of \(d\) can go to \(B\). Otherwise some \(A\)-bundle misses \(d\) and has \(A\)-value at most \(W\), while some \(B\)-bundle contains \(d\) and has \(A\)-value at least \(H>W\).
Thus every \(A\)-bundle contains \(d\), and every \(B\)-bundle does not. Envy-freeness from \(B\)'s perspective gives \(w(X_B)\ge w(X_A)\) for every supported pair. Hence \(A\)'s original impact is at most \(W/4\), with equality only when all supported original parts have weight \(W/2\). Equality is therefore equivalent to a partition.
Together with membership in \(\mathrm{NP}\), this proves \(\mathrm{NP}\)-completeness for every fixed \(k\ge0\).
Let \(1\le k\le n-1\), \(h=n-k\), and
\[
m=hn+k-1=(n-1)(n-k+1).
\]
Take \(n\) types of mass \(1/n\), \(m\) goods each of supply \(1/n\), and identical unit agent valuations. Only type \(1\) has unit social impact for every good.
The unconstrained allocation gives every good to type \(1\), so
\[
\operatorname{OPT}_{\mathrm{all}}=\frac mn.
\]
Consider any support-wise \(\mathrm{EF}k\) allocation. Let \(a\) be the average cardinality of a type-\(1\) bundle, and let \(M\) be the maximum cardinality in type \(1\)'s support. Every supported bundle of every other type has size at least \(M-k\). Therefore
\[
\frac mn\ge \frac an+\frac{n-1}{n}(M-k),
\]
so
\[
a\le m-(n-1)(M-k).
\]
Also \(a\le M\). If \(M\le n-1\), this immediately gives \(a\le n-1\). If \(M\ge n\), then
\[
a\le m+(n-1)k-(n-1)M
=n^2-1-(n-1)M
\le n-1.
\]
Thus
\[
\operatorname{OPT}_{\mathrm{EF}k,\infty}\le\frac{n-1}{n}.
\]
This bound is attainable. Give type \(1\) the uniform distribution over all \((n-1)\)-subsets, and every other type the uniform distribution over all \(h\)-subsets. The two supported cardinalities differ by \(k-1\), so the allocation is support-wise \(\mathrm{EF}k\). Symmetry gives every good marginal \(1/n\). Hence
\[
\operatorname{OPT}_{\mathrm{EF}k,\infty}=\frac{n-1}{n},
\qquad
\frac{\operatorname{OPT}_{\mathrm{all}}}
{\operatorname{OPT}_{\mathrm{EF}k,\infty}}
=n-k+1.
\]
Thus fractional population mass does not improve this example.
The question does not specify which parameters depend on \(\varepsilon\). The following explicit regime gives a precise result.
Take two types \(A,B\) with masses
\[
\mu_A=\varepsilon,\qquad \mu_B=1-\varepsilon.
\]
There are \(M\) goods, each with supply \(\varepsilon\). Let
\[
v_A(g)=0,\qquad v_B(g)=1,\qquad
s_A(g)=1,\qquad s_B(g)=0.
\]
The unconstrained allocation gives every good to \(A\), yielding
\[
\operatorname{OPT}_{\mathrm{all}}=\varepsilon M.
\]
In a fair allocation, let \(a\) and \(b\) be the average bundle sizes of types \(A\) and \(B\), and let \(Q\) be the largest supported \(A\)-bundle size. Type \(B\)'s fairness condition implies \(b\ge Q-k\), while \(a\le Q\). Supply feasibility gives
\[
\varepsilon M=\varepsilon a+(1-\varepsilon)b
\ge \varepsilon a+(1-\varepsilon)(a-k).
\]
Therefore
\[
a\le\varepsilon M+(1-\varepsilon)k,
\]
and hence
\[
\operatorname{OPT}_{\mathrm{EF}k,\infty}
\le\varepsilon\bigl(\varepsilon M+(1-\varepsilon)k\bigr).
\]
This bound is exact whenever \(\varepsilon=p/q\) in lowest terms and \(M=k+q\ell\). Put
\[
b_\star=p\ell,\qquad a_\star=p\ell+k.
\]
Give \(A\) the uniform distribution over all \(a_\star\)-subsets and \(B\) the uniform distribution over all \(b_\star\)-subsets. Every good then has marginal \(\varepsilon\), and a \(B\)-agent removes \(k\) goods from an \(A\)-bundle to reduce its size from \(a_\star\) to \(b_\star\). Thus the exact ratio is
\[
\frac{\operatorname{OPT}_{\mathrm{all}}}
{\operatorname{OPT}_{\mathrm{EF}k,\infty}}
=
\frac{M}{\varepsilon M+(1-\varepsilon)k}.
\]
For fixed \(\varepsilon>0\), this tends to \(1/\varepsilon\) as \(M\to\infty\). In particular, taking \(\varepsilon=1/q\), \(\ell=q\), and \(M=k+q^2\) gives
\[
\frac{q^2+k}{q+k}\sim q=\frac1\varepsilon.
\]
Hence the global worst-case ratio is \(+\infty\) as \(\varepsilon\to0\), even though the number of types remains two.
For fixed \(G,\Theta,\mu,\rho,k\), the supremum over valuations is not always the same:
An exact characterization for every fixed tuple with \(k\ge1\) is not established here.
⟨structured verdict parsed — rendered above⟩
The prover establishes substantial correct content:
However, the principal fixed-data ratio question is explicitly left unresolved. The family in Section 6 varies \(\mu\), \(\rho\), and \(G\), so it does not determine the supremum for an arbitrary fixed tuple \((G,\Theta,\mu,\rho,k)\). The claimed fixed-tuple example with infinite ratio is also insufficiently specified and unproved. The appropriate status is therefore partial.
This part is essentially correct.
No major gap occurs here.
The reduction is correct in substance.
The proposed allocation assigns \(O\) to type \(A\) and all \(k\) dummies to type \(B\). Type \(A\) can remove all dummies from \(B\)'s bundle. Type \(B\)'s own value is \(kH>W\), so it does not envy \(A\). Same-type comparisons are trivial. Thus promised feasibility is established.
The identities involving \(\delta_j\) and \(L\) are correct:
For every full \(A\)-bundle and zero \(B\)-bundle, type \(B\)'s comparison must remove all \(k\) dummies: leaving even one dummy leaves value at least \(H>W\). Since all \(k\) removal slots are then exhausted, the original portions satisfy \(w(Y)\ge w(X)\).
The inequality
\[ y_F\le z_0+LW \]
is plausible and correct, but its derivation is omitted. It requires explicitly combining the pairwise ordering with the two support masses, whose discrepancy is at most \(L\), and the bound \(w(\cdot)\le W\). This is a minor presentation gap because the asserted inequality follows by a short calculation, but that calculation is critical to the reduction.
The subsequent calculations check out:
When \(L=0\), all supported \(A\)-bundles contain every dummy and all supported \(B\)-bundles contain none. Pairwise ordering gives every supported \(B\)-weight at least every supported \(A\)-weight.
At welfare \(T\), both types have conditional average original weight \(W/2\). Together with the pointwise ordering, this forces all supported original parts on both sides to have weight \(W/2\). Thus any supported \(A\)-part supplies a partition.
The converse allocation is feasible, fair in both directions, and has welfare \(T\).
Accordingly, the reduction from PARTITION proves NP-hardness. It proves ordinary, potentially weak, NP-hardness, which is sufficient for the claimed NP-completeness.
This reduction is also correct in substance.
If any positive mass of \(d\) went to type \(B\), supply balance would produce both an \(A\)-bundle missing \(d\) and a \(B\)-bundle containing \(d\). From type \(A\)'s perspective their values are at most \(W\) and at least \(H=W+1\), respectively, contradicting envy-freeness.
Consequently, every \(A\)-bundle contains \(d\) and every \(B\)-bundle excludes it. Type \(B\)'s comparisons then order every supported \(B\)-original weight above every supported \(A\)-original weight. Equal type masses imply that \(A\)'s total original impact is at most \(W/4\), and equality forces all supported original weights to equal \(W/2\).
The promised feasible allocation and partition-based converse both satisfy envy-freeness. Thus NP-completeness for fixed \(k=0\) is established.
For \(1\le k\le n-1\), this argument is correct.
Let \(a\) be type \(1\)'s conditional average bundle size and \(M\) its maximum supported bundle size. Every other type must receive bundles of size at least \(M-k\). Supply balance therefore gives
\[ \frac mn\ge\frac an+\frac{n-1}{n}(M-k). \]
Combining this with \(a\le M\) gives \(a\le n-1\) in both cases \(M\le n-1\) and \(M\ge n\). Hence fair welfare is at most \((n-1)/n\).
The proposed uniform distributions have cardinalities \(n-1\) and \(h=n-k\). Their difference is \(k-1\), so all cross-type comparisons satisfy \(\mathrm{EF}k\). The marginal calculation is also correct because
\[ m=(n-1)(h+1). \]
Thus every good has aggregate marginal \(1/n\), and the exact ratio is \(n-k+1\).
The conclusion that the stated construction survives “exactly” is slightly broader than the proof: the proof explicitly assumes \(1\le k\le n-1\), while the preceding general discussion includes \(k=0\). The claim should either be restricted to the proved range or the omitted endpoint addressed.
The calculations in this section are correct for the family actually defined.
Supply balance gives
\[ \varepsilon M=\varepsilon a+(1-\varepsilon)b. \]
If \(Q\) is the largest supported \(A\)-bundle, type \(B\)'s fairness condition gives \(b\ge Q-k\), while \(a\le Q\). Hence \(b\ge a-k\), producing
\[ a\le\varepsilon M+(1-\varepsilon)k. \]
Since only \(A\) creates social impact, the fair objective is \(\varepsilon a\), yielding the stated upper bound.
For \(\varepsilon=p/q\) and \(M=k+q\ell\), the proposed cardinalities satisfy
\[ a_\star=p\ell+k,\qquad b_\star=p\ell. \]
Their difference is exactly \(k\), and the aggregate marginal of each good is indeed \(\varepsilon\). Thus the upper bound is attained and the ratio is exactly
\[ \frac{M}{\varepsilon M+(1-\varepsilon)k}. \]
The limits as \(M\to\infty\) along the specified congruence class and then \(\varepsilon\to0\) are correct. This proves an unbounded global ratio when the instance data are allowed to vary.
It does not, however, determine the supremum for fixed \(\mu\), \(\rho\), and \(G\), because all of those parameters vary in this family.
This is the central unresolved part.
The target asks for the supremum over valuations with \((G,\Theta,\mu,\rho,k)\) fixed. The prover explicitly states:
“I do not derive the exact supremum for every fixed tuple with \(k\ge1\).”
Thus the requested classification is not completed.
The two ratio-\(1\) observations are valid within their stated qualifications:
The claimed fixed-data example with ratio \(+\infty\) is not verifiable as written. “Preferences \(A:g\succ h\) and \(B:h\succ g\), and opposite social impacts” does not specify the numerical additive values or even precisely define the social-impact functions. No argument is given that every support-wise envy-free mass allocation has social welfare zero. Moreover, the expression \(\operatorname{OPT}_{\mathrm{all}}/\operatorname{OPT}_{\mathrm{EF}0,\infty}\) has a zero denominator in the claimed example, and the write-up does not state an extended-real convention or provide positive-denominator instances with ratios tending to infinity.
The minimum clarification needed for this example is:
Even if that example is repaired, it would establish only that some fixed tuples have infinite supremum, not the exact supremum for arbitrary fixed tuples.
The complexity classification and both explicit welfare constructions are genuine, mostly rigorous progress. The exact fixed-data welfare ratio requested by the task remains open in the prover output, so the output is partial rather than a complete resolution.
⟨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.