Answer: Neither alternative applies as stated: the required allocation need not exist, even for \(|G|=2\) and a normalized additive valuation, so the formulation is not a total search problem.
Theorem 4.8 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe problem of computing an EEFX alloca- tion for for any number n ≥2 of agents with identical sub- modular valuations is PLS-hard. Since our reduction works even for three agents, Theo- rems 4.7 and 4.8 hold true for the problem of computing EEFX allocations even for three agents with identical sub- modular valuations. Note that the set of EFX and EEFX al- locations coincide for the case of two agents and hence it inherits the same computational hardness guarantees as that of EFX here.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational masses of valuation types, rational capacities of finitely many indivisible item kinds, and value-oracle access to each type valuation, output an aggregate allocation x over whole bundles B⊆G satisfying type and capacity marginals, together with an EEFX certificate for every supported (type,B): a mass partition of the remaining item supply into whole comparison bundles C satisfying v(B)≥v(C\{g}) for every g∈C.
Let \(G\) be a finite set of goods, \(\Theta\) a finite set of types with rational masses \(\mu\in\Delta(\Theta)\), and rational supplies \(s_g\in[0,1]\). Each type has a normalized monotone valuation \(v_\theta:2^G\to\mathbb{Q}_{\ge0}\), accessed by rational value queries; restrict to \(v_\theta=v\) for all \(\theta\), where \(v\) is submodular.
A societal allocation is rational \(x_{\theta,B}\ge0\) for \(B\subseteq G\), with \(\sum_Bx_{\theta,B}=\mu_\theta\) and \(\sum_{\theta,B\ni g}x_{\theta,B}=s_g\). For every used \((\theta,B)\), it must provide a rational distribution \(y^{\theta,B}\) on \(2^G\) whose marginals are \(s_g\), and such that \(v(B)\ge v(C\setminus\{g\})\) whenever \(y^{\theta,B}_C>0\) and \(g\in C\).
Target. Is this continuous EEFX search problem solvable in polynomial time, or is it PLS-hard, in the rational value-query model?
Nearest known results. For discrete agents, computing an EEFX allocation for any \(n\ge2\) agents with identical submodular valuations is PLS-hard; it also has an exponential value-query lower bound. These results concern integral allocations to finitely many agents, not the type-mass problem above.
Let \(\Delta(s)\) denote the set of distributions \(p\) on \(2^G\) having marginals \(s\). For \(C\subseteq G\), define
\[ r(C):= \begin{cases} \max_{g\in C}v(C\setminus\{g\}),&C\neq\varnothing,\\ 0,&C=\varnothing. \end{cases} \]
Because all types have the same valuation, the type structure is inessential.
A societal allocation exists if and only if there are rational distributions \(p,q\in\Delta(s)\) such that
\[ v(B)\ge r(C) \]
for every \(B\in\operatorname{supp}(p)\) and \(C\in\operatorname{supp}(q)\).
Suppose a societal allocation \(x\) exists. Define \(p_B=\sum_{\theta}x_{\theta,B}\). Then \(p\in\Delta(s)\).
Choose a used pair \((\theta_0,B_0)\) minimizing \(v(B)\) over all used pairs, and put \(q=y^{\theta_0,B_0}\). For every \(C\in\operatorname{supp}(q)\), the certificate condition gives \(v(B_0)\ge r(C)\). Every \(B\in\operatorname{supp}(p)\) is used by some type, so \(v(B)\ge v(B_0)\ge r(C)\).
Conversely, given such \(p,q\), define \(x_{\theta,B}=\mu_\theta p_B\) and use \(q\) as the certificate for every used \((\theta,B)\). The mass and supply equations follow from \(p\in\Delta(s)\), while the displayed inequality verifies every certificate. \(\square\)
Equivalently, for \(a\in\mathbb Q_{\ge0}\), define
\[ \mathcal H_a=\{B\subseteq G:v(B)\ge a\}, \qquad \mathcal L_a=\{C\subseteq G:r(C)\le a\}. \]
Then feasibility is equivalent to the existence of \(a\) such that
\[ s\in\operatorname{conv}\{\mathbf 1_B:B\in\mathcal H_a\} \cap \operatorname{conv}\{\mathbf 1_C:C\in\mathcal L_a\}. \]
This characterization already shows that existence is an additional condition, not a consequence of monotonicity or submodularity.
Let
\[ G=\{a,b\},\qquad \Theta=\{\theta\},\qquad \mu_\theta=1, \qquad s_a=s_b=\frac34. \]
Use the additive valuation
\[ v(\varnothing)=0,\qquad v(\{a\})=\frac13,\qquad v(\{b\})=\frac23,\qquad v(\{a,b\})=1. \]
This valuation is rational, normalized even under the stronger convention \(v(G)=1\), monotone, additive, and therefore submodular.
Assume for contradiction that a societal allocation exists. Let \(B\) be any used bundle, and consider its certificate \(y^B\). If \(C\) is distributed according to \(y^B\), then
\[ \Pr(a,b\in C) \ge \Pr(a\in C)+\Pr(b\in C)-1 = \frac12. \]
Consequently \(y^B_{\{a,b\}}>0\). Applying the certificate inequality to \(C=\{a,b\}\) and \(g=a\) gives
\[ v(B)\ge v(\{b\})=\frac23. \]
The only bundles satisfying this inequality are \(\{b\}\) and \(\{a,b\}\). Thus every used bundle contains \(b\). The allocation marginal of \(b\) must therefore be
\[ \sum_{B\ni b}x_{\theta,B} = \sum_Bx_{\theta,B} = 1, \]
contradicting the required supply \(s_b=3/4\). Hence this valid input has no solution. \(\square\)
More generally, let \(G=\{a,b\}\), with \(v(\{a\})<v(\{b\})\). If \(s_a+s_b>1\), every marginal-\(s\) certificate assigns positive probability to \(\{a,b\}\). It follows exactly as above that every used allocation bundle must have value at least \(v(\{b\})\), hence must contain \(b\). Therefore feasibility requires \(s_b=1\).
Conversely, \(s_b=1\) is sufficient: put probability \(s_a\) on \(\{a,b\}\) and \(1-s_a\) on \(\{b\}\), both for the allocation and its certificates. Thus, when singleton values are unequal and supplies overlap, infeasibility occurs throughout a nontrivial region of the supply space.
The requested output does not allow an “infeasible” answer, yet valid instances need not possess any required allocation. Therefore the formulation is not a total search problem.
In particular:
⟨structured verdict parsed — rendered above⟩
The prover correctly establishes a substantive obstruction: the stated allocation relation is not total. The two-good additive instance is valid and rigorously shown to be infeasible.
However, this does not fully resolve the target’s “polynomial-time or PLS-hard” question. Non-membership in PLS does not by itself rule out PLS-hardness: a partial search problem can still be PLS-hard under reductions whose generated instances are feasible. Thus the conclusion that “neither alternative applies” is stronger than what the counterexample proves.
The forward direction is correct:
The converse is also correct. Setting \(x_{\theta,B}=\mu_\theta p_B\) satisfies the type-mass and supply equations, and the common distribution \(q\) certifies every used pair.
The convex-hull reformulation is substantively correct. There is a minor omitted rationality justification: membership of rational \(s\) in a convex hull initially provides real convex coefficients, whereas the original problem requires rational distributions. Because these are rational finite linear systems, rational feasible coefficients exist, but this fact should be stated.
The valuation is normalized, monotone, additive, and submodular.
For any certificate with both marginals \(3/4\), the union bound gives
\[ \Pr(a,b\in C)\ge \frac34+\frac34-1=\frac12. \]
On a two-good ground set, this is exactly the probability of \(C=\{a,b\}\), so that bundle has positive certificate probability.
Taking \(g=a\) in the certificate condition correctly yields \(v(B)\ge v(\{b\})=2/3\). The only bundles meeting this threshold are \(\{b\}\) and \(\{a,b\}\), both containing \(b\). Hence every used allocation bundle contains \(b\), forcing its allocation marginal to be \(1\), contradicting \(s_b=3/4\).
This counterexample is correct and proves that the stated relation is not total.
The necessity argument is correct for two goods. If \(s_a+s_b>1\), every certificate places positive probability on \(\{a,b\}\). If \(v(\{a\})<v(\{b\})\), every bundle with value at least \(v(\{b\})\) must contain \(b\).
The sufficiency claim for \(s_b=1\) is also correct, although its certificate check is omitted. On the proposed support, \(r(\{b\})=0\) and \(r(\{a,b\})=v(\{b\})\), while both allocation bundles have value at least \(v(\{b\})\). This is a routine but necessary verification.
The following conclusions are justified:
The stronger conclusion that neither polynomial-time solvability nor PLS-hardness applies is not established. Being outside PLS does not imply being outside the class of PLS-hard problems. A partial relation can be PLS-hard if every PLS problem reduces to feasible instances of that relation. The prover neither excludes nor proves such a reduction.
The assertion that the feasibility-search variant is “presently unsettled” is also unsupported by a citation or argument. It is ancillary to the valid infeasibility result but cannot be accepted as verified.
The output rigorously proves that the allocation requirement is not guaranteed to be feasible, even for two goods and a normalized additive valuation. This is a decisive correction to any interpretation of the formulation as an unconditional total search problem.
The prover must distinguish these two conclusions:
Any claim that related variants are presently unsettled also needs a precise reference or should be removed.
⟨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.