The Frontier of Intractability for EFX with Two Agents (d4-conf-sagt-2023-0005)

Given a succinct monotone submodular valuation \(v:2^M\to\mathbb{Q}_{\ge 0}\) for one unit-mass type and per-capita supply \(b_g=\tfrac12\) for every good \(g\in M\), find an explicitly represented finite-support distribution \(\lambda_X\) over integral bundles \(X\subseteq M\) satisfying \(\sum_X\lambda_X=1\), \(\sum_{X:g\in X}\lambda_X=\tfrac12\), and \(v(X)\ge v(Y\setminus\{g\})\) for every pair of supported bundles \(X,Y\) and every \(g\in Y\).

A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) denotes support size, not the number of possible types. Here \(\tau=1\), with total mass \(1\).
Let \(M\) be a finite set of \(m\) goods. The type's valuation \(v:2^M\to\mathbb{Q}_{\ge0}\) is given by a Boolean circuit taking a bundle's incidence vector and outputting a binary numerator and positive binary denominator. It is promised to be monotone, submodular, and normalized by \(v(\varnothing)=0\). Let \(L\) be the total input bit length.
Each good has per-capita supply \(b_g=\tfrac12\). Find a finite list \(\mathcal S\subseteq2^M\) of distinct integral bundles and positive binary rational weights \(\lambda_X\), satisfying \(\sum_{X\in\mathcal S}\lambda_X=1\) and \(\sum_{X\in\mathcal S:g\in X}\lambda_X=\tfrac12\) for every \(g\in M\).
Require \(v(X)\ge v(Y\setminus\{g\})\) for every \(X,Y\in\mathcal S\) and every \(g\in Y\), including goods with zero marginal value. Empty bundles are allowed, and supported bundles may overlap.

Is this distribution search problem solvable in time polynomial in \(m,\tau,L\), or is it NP-hard?

For two identical discrete agents, computing an EFX partition with succinct submodular valuations is PLS-hard and lies in PLS. [Goldberg–Høgh–Hollender](https://www.cs.ox.ac.uk/people/paul.goldberg/papers/TCS-GHH.pdf)
No result settling the exact distribution search problem above was located in the literature search.

Status and new progress

I do not settle whether the general distribution problem has a polynomial-time algorithm or is NP-hard.

I prove a stronger separation than the counterexample in the notes:

There is an explicit family of succinct, normalized, monotone submodular valuations for which computing an EFX partition is PLS-hard, while the requested distribution has a fixed four-bundle solution computable without evaluating the valuation circuit.

Consequently, even a general polynomial-time procedure converting valid distributions into EFX partitions would imply that every problem in $\mathrm{PLS}$ is polynomial-time solvable.

I also prove an exact characterization of distributions for this family and re-establish the PLS upper bound for the general promised problem.

1. A PLS upper bound for the distribution problem

A partition $(A,B)$ of $M$ is EFX if
$$ v(A)\ge v(B\setminus\{g\})\quad(g\in B), \qquad v(B)\ge v(A\setminus\{g\})\quad(g\in A). $$
The comparisons of a bundle with its own deletions hold by monotonicity.

Let $r\ge 1$ bound both output widths of the valuation circuit. Every circuit value has a representation $p/q$ with
$$ 0\le p<2^r,\qquad 1\le q<2^r. $$
If two represented values differ, then
$$ \left|\frac pq-\frac{p'}{q'}\right| =\frac{|pq'-p'q|}{qq'} >2^{-2r}. $$
Thus
$$ z(X)=\left\lfloor 2^{2r}v(X)\right\rfloor $$
preserves strict comparisons and equality between valuation values. It is polynomial-time computable and satisfies $0\le z(X)<2^{3r}$.

Define
$$ s(X)=(m+1)z(X)+|X|. $$
Comparing these integers is equivalent to lexicographically comparing $(v(X),|X|)$.

Consider local maximization over partitions, with objective
$$ \Phi(A,B)=\min\{s(A),s(B)\}, $$
and neighbors obtained by transferring one good between the two bundles. A partition has an $m$-bit representation; its $m$ neighbors and their polynomial-bit objectives can be computed in polynomial time. The initial partition is $(\varnothing,M)$. These are the defining ingredients of a basic polynomial local search problem.

Every local maximum is EFX. Indeed, suppose
$$ v(X)<v(Y\setminus\{g\}) $$
for the two partition bundles and some $g\in Y$. Monotonicity implies $v(Y)>v(X)$, so the current objective is $s(X)$.

After transferring $g$, let
$$ X'=X\cup\{g\},\qquad Y'=Y\setminus\{g\}. $$
We have $s(Y')>s(X)$ because $v(Y')>v(X)$. Also $s(X')>s(X)$: either its value increases, or its value stays equal and its cardinality increases. Consequently,
$$ \Phi(X',Y')>s(X)=\Phi(X,Y). $$
An EFX violation therefore contradicts local optimality. The cardinality term explicitly handles a transferred good with zero marginal value.

For $m>0$, an EFX partition gives a valid distribution by assigning weight $1/2$ to each of its two distinct complementary bundles. For $m=0$, the single empty bundle with weight $1$ is valid.

Proven conclusion. On the promised inputs, the distribution task has a polynomial-time solution reduction to $\mathrm{PLS}$, and every instance has a solution supported on at most two bundles. This argument supplies no polynomial bound on the number of improvement steps.

2. A polynomial-size family of submodular circuits

We next construct the family separating partition search from distribution search.

Let
$$ C:\{0,1\}^n\longrightarrow\{0,\ldots,W\} $$
be a Boolean circuit, where $W=2^r-1$ for an output width $r\ge 1$. Choose an even integer
$$ k\ge \max\{4,n\}, $$
with $k$ polynomial in $n$, and define
$$ F(x_0,\ldots,x_{k-1})=C(x_0,\ldots,x_{n-1}). $$

The goods are
$$ M=\{a_i,b_i:0\le i<k\}\cup\{z\}, \qquad |M|=2k+1. $$
For a bit vector $x\in\{0,1\}^k$, define the transversal
$$ T(x)=\{a_i:x_i=1\}\cup\{b_i:x_i=0\}. $$
It contains one good from each pair and omits $z$.

For a $k$-element bundle $S$, write
$$ c_i(S)=|S\cap\{a_i,b_i\}|, \qquad d(S)=|\{i:c_i(S)\ne 1\}|. $$
Here $d(S)$ counts pairs that are empty or contain both goods.

Define an integer score $f$ on $k$-element bundles as follows.

• If $d(S)=0$, then $S=T(x)$ for a unique $x$, and set

$$ f(S)=2F(x). $$

• If $d(S)=1$, then $S$ contains $z$, has one empty pair, and contains one good from every other pair. There are exactly two transversals $T(x),T(y)$ disjoint from $S$; their bit vectors differ only at the empty pair. Set

$$ f(S)=2\max\{F(x),F(y)\}-1. $$

• If $d(S)\ge 2$, set

$$ f(S)=-d(S). $$

To justify the assertion in the second case, let $a$ be the number of double pairs, $s$ the number of empty pairs, and $b=\mathbf 1_{\{z\in S\}}$. Since $|S|=k$,
$$ s=a+b,\qquad d(S)=a+s=2a+b. $$
Thus $d(S)=1$ forces $a=0$, $b=1$, and $s=1$.

The score satisfies
$$ -k\le f(S)\le 2W. $$
Put
$$ D=2(2W+k+1) $$
and define
$$ v(S)= \begin{cases} 2|S|,& |S|<k,\\[2mm] 2k-1+\dfrac{f(S)+k}{D},& |S|=k,\\[3mm] 2k,& |S|>k. \end{cases} $$

Verification of the valuation promises

For every $k$-element bundle,
$$ 0\le \frac{f(S)+k}{D}<\frac12, $$
and hence
$$ 2k-1\le v(S)<2k-\frac12. $$
The valuation is nonnegative and satisfies $v(\varnothing)=0$.

Its marginal values have the following bounds.

| Size before addition | Marginal value |
|---|---:|
| Less than $k-1$ | $2$ |
| $k-1$ | In $[1,3/2)$ |
| $k$ | In $(1/2,1]$ |
| Greater than $k$ | $0$ |

All marginals are nonnegative, proving monotonicity.

For submodularity, take $S\subseteq T$ and $g\notin T$. If $|S|=|T|$, then $S=T$ and the two marginals agree. Otherwise, the table shows that every possible marginal at size $|S|$ is at least every possible marginal at size $|T|$. Therefore
$$ v(S\cup\{g\})-v(S) \ge v(T\cup\{g\})-v(T). $$
This is the diminishing-returns definition of submodularity.

The circuit representation also has polynomial size. It counts selected goods, identifies the three cases defining $f$, and evaluates at most two copies of $C$. The denominator $D$ has $O(r+\log k)$ bits. At cardinality $k$, the numerator is
$$ (2k-1)D+f(S)+k, $$
which is nonnegative and has polynomial bit length. Other cardinalities use denominator $1$. Thus the construction meets the exact binary-rational circuit model of the task.

3. Computing EFX partitions in this family is PLS-hard

We use the standard Flip problem: given a nonnegative integer-valued Boolean circuit, find an input whose value cannot be increased by flipping one input bit. This problem is PLS-complete. The minimization formulation stated in [Goldberg–Høgh–Hollender, Section 4.2.2](https://www.cs.ox.ac.uk/people/paul.goldberg/papers/TCS-GHH.pdf) is equivalent: replacing the circuit value $C(x)$ by $W-C(x)$ reverses comparisons and is polynomial-time computable.

We prove directly that any EFX partition for the constructed valuation yields a Flip solution for $C$.

3.1. EFX partitions are exactly score-local maxima

Let $(A,B)$ be an EFX partition of $M$.

If its smaller bundle has size at most $k-1$, the larger has size at least $k+2$. Deleting any good from the larger leaves value $2k$, whereas the smaller has value at most $2k-2$. This violates EFX.

Consequently, the bundle sizes must be $k$ and $k+1$. Assume $|A|=k$.

The inequalities comparing $B$ with deletions of $A$ hold automatically:
$$ v(B)=2k>2k-2=v(A\setminus\{g\}). $$
The remaining inequalities are precisely
$$ f(A)\ge f(B\setminus\{g\})\qquad(g\in B). $$

The $k$-element bundles disjoint from $A$ are exactly the sets $B\setminus\{g\}$ for $g\in B$. Hence:

A $k$-element bundle $A$ forms an EFX partition with its complement exactly when it is a local maximum of $f$ under the neighborhood consisting of disjoint $k$-element bundles.

3.2. No nontransversal is a local maximum

First suppose $d(S)=1$. Its two disjoint transversal neighbors are $T(x)$ and $T(y)$ from the definition of $f$. At least one has score
$$ 2\max\{F(x),F(y)\}=f(S)+1. $$
Thus $S$ is not locally maximal.

Now suppose $d(S)\ge 2$. With $a,s,b$ as above, $s=a+b$ implies $s\ge 1$. Choose a pair that is empty in $S$. Both its goods belong to $M\setminus S$. Remove one of them from this complement, obtaining a disjoint $k$-element neighbor $S'$.

The double pairs of $S'$ are the formerly empty pairs, except the chosen pair. Its empty pairs are the formerly double pairs. Therefore
$$ d(S')=(s-1)+a=d(S)-1. $$
If $d(S')\ge 2$, then
$$ f(S')=-d(S')=-d(S)+1>f(S). $$
If $d(S')=1$, then $f(S')\ge -1>-d(S)$. If $d(S')=0$, then $f(S')\ge 0>-d(S)$.

Thus every nontransversal has a strictly improving neighbor.

3.3. A locally maximal transversal decodes a Flip solution

Let $T(x)$ be a local maximum. For any index $i$, let $x^{(i)}$ denote $x$ with bit $i$ flipped, and define
$$ E_i=\{z\}\cup \left(T(\overline{x})\setminus\{a_i,b_i\}\right). $$
This is a $k$-element bundle disjoint from $T(x)$. It has one empty pair, and its two disjoint transversal neighbors are $T(x)$ and $T(x^{(i)})$. Hence
$$ f(E_i)=2\max\{F(x),F(x^{(i)})\}-1. $$

If $F(x^{(i)})>F(x)$, integrality gives
$$ f(E_i)\ge 2F(x)+1>f(T(x)), $$
contradicting local maximality. Therefore
$$ F(x)\ge F(x^{(i)})\qquad(0\le i<k). $$
In particular, $(x_0,\ldots,x_{n-1})$ is a Flip solution for $C$.

The valuation construction and this decoding are polynomial-time computable, and every constructed valuation satisfies all promises. This proves PLS-hardness of EFX partition search on this family.

4. The same family has a fixed four-bundle distribution

Define
$$ T_0=\{b_i:0\le i<k\}, \qquad T_1=\{a_i:0\le i<k\}, $$
and
$$ C_0=\{a_i,b_i:0\le i<k/2\}, \qquad C_1=\{a_i,b_i:k/2\le i<k\}. $$
Both $C_0$ and $C_1$ have size $k$. Put
$$ B_0=M\setminus C_0,\qquad B_1=M\setminus C_1. $$

Use the four distinct bundles
$$ \mathcal S=\{T_0,T_1,B_0,B_1\}, \qquad \lambda_X=\frac14\quad(X\in\mathcal S). $$
These bundles depend only on the labeled goods and $k$, not on $C$ or its values.

Supply verification

Every paired good belongs to exactly one of $T_0,T_1$ and exactly one of $B_0,B_1$. The good $z$ belongs to both $B_0,B_1$ and neither transversal.

Every good therefore belongs to exactly two supported bundles, giving marginal probability $1/2$. The four weights are positive binary rationals and sum to $1$.

EFX verification

Since $F$ is nonnegative,
$$ v(T_j)\ge 2k-1+\frac{k}{D}\qquad(j=0,1). $$
Also $v(B_j)=2k$. Thus every supported bundle has value at least
$$ 2k-1+\frac{k}{D}. $$

Deleting a good from a supported transversal leaves value $2k-2$.

Consider a deletion from $B_j$.

• Deleting $z$ leaves the other $C$-bundle, which has defect $k$ and score $-k$.
• Deleting a paired good leaves a bundle containing $z$ with defect $k-1$. Since $k\ge 4$, this falls in the third score case and has score $-(k-1)$.

Consequently, every deletion from $B_j$ has value at most
$$ 2k-1+\frac1D. $$
Every supported deletion therefore has value at most $2k-1+1/D$, while every supported bundle has value at least $2k-1+k/D$. All required EFX inequalities hold.

Proven separation. Partition search is PLS-hard on this explicitly constructed family, but distribution search on the family is solvable by outputting these four bundles and weights.

In particular, suppose a polynomial-time procedure could take a valuation circuit and any valid distribution and return an EFX partition for that valuation. Applying it to this fixed distribution, followed by the decoding in Section 3, would solve Flip in polynomial time. Thus such a procedure would make every problem in $\mathrm{PLS}$ polynomial-time solvable.

5. An exact characterization of arbitrary distributions in the family

The four-bundle construction reflects a precise distinction between the two search problems.

Let a feasible EFX distribution for a valuation from Section 2 be given. The supply equations imply
$$ \mathbb E[|X|] =\sum_{g\in M}\Pr[g\in X] =\frac{2k+1}{2} =k+\frac12. $$

5.1. Only cardinalities $k$ and $k+1$ can occur

At least one supported bundle has size at least $k+1$. If another has size at most $k-1$, deleting a good from the former leaves size at least $k$, with value at least $2k-1$. The latter has value at most $2k-2$, contradicting EFX.

Thus every supported bundle has size at least $k$.

If some supported bundle has size at least $k+2$, its deletions have value $2k$. EFX then forces every supported bundle to have value at least $2k$. Since every $k$-element bundle has value strictly below $2k$, all supported bundles would have size at least $k+1$. That contradicts the displayed expectation.

Hence all supported bundles have size $k$ or $k+1$. The expectation equation now forces total weight $1/2$ on each cardinality.

5.2. Equal incidence averages replace equality of bundles

For each supported $k$-element bundle $A$, put
$$ p_A=2\lambda_A. $$
For each supported $(k+1)$-element bundle $B$, associate its $k$-element complement $C=M\setminus B$ and put
$$ r_C=2\lambda_B. $$
Both $p$ and $r$ are probability distributions.

Let $\mathbf 1_A$ denote the incidence vector of $A$, and let $\mathbf 1$ be the all-ones vector. The marginal constraints become
$$ \frac12\sum_Ap_A\mathbf 1_A + \frac12\sum_Cr_C(\mathbf 1-\mathbf 1_C) =\frac12\mathbf 1. $$
Equivalently,
$$ \sum_Ap_A\mathbf 1_A = \sum_Cr_C\mathbf 1_C. $$

Let $N(C)$ be the collection of $k$-element bundles disjoint from $C$. These are exactly the deletions of $M\setminus C$.

All EFX comparisons are automatic except comparisons of a supported $k$-element bundle with a deletion of a supported $(k+1)$-element bundle. Thus EFX is equivalent to
$$ \min_{A:p_A>0}f(A) \ge \max_{C:r_C>0}\ \max_{Z\in N(C)}f(Z). $$

Conversely, any finitely supported rational probability distributions $p,r$ satisfying these two displayed conditions give a valid distribution: assign weights $p_A/2$ to $A$ and $r_C/2$ to $M\setminus C$.

This is an exact characterization. A partition corresponds to the special case where $p$ and $r$ are the same point mass. A general distribution requires only equality of their incidence averages.

For the four-bundle solution, $p$ is uniform on $T_0,T_1$, while $r$ is uniform on $C_0,C_1$. Their averages agree, despite the completely different scores and neighborhood behavior.

6. Four bundles are necessary for the complement-extraction obstruction

The new family also yields a smallest possible support size for a valid distribution from which no supported bundle forms an EFX partition with its complement.

First, for any nonempty ground set, a feasible distribution on two distinct bundles must assign weight $1/2$ to each and use complementary bundles. Indeed, each coordinate must select a nonempty proper subset of the two weights summing to $1/2$, so it selects exactly one weight. The marginal constraints therefore force complementarity. If the distribution is EFX, this supported pair is an EFX partition.

There is no feasible distribution on exactly three distinct bundles with positive weights. To see this, write the weights as $\lambda_1,\lambda_2,\lambda_3$. Any coordinate selects a subset of these weights summing to $1/2$. That subset or its complement is a singleton, so some weight, say $\lambda_1$, equals $1/2$. The other two positive weights sum to $1/2$.

For every coordinate, the selected indices must then be either $\{1\}$ or $\{2,3\}$: selecting index $1$ with another index exceeds $1/2$, and selecting only index $2$ or only index $3$ falls short. Bundles $2$ and $3$ consequently have identical incidence vectors, contradicting distinctness.

Now specialize the constructed family to $n=k$ and
$$ C(x)=\sum_{i=1}^{k-1}(x_i\oplus x_0). $$
Here $\oplus$ denotes exclusive OR. Both the all-zero and all-one vectors have value $0$, while flipping any bit with index $i\ge 1$ raises their value to $1$.

Therefore $T_0$ and $T_1$ each have an improving disjoint neighbor of score $1$, exceeding their own score $0$. Neither forms an EFX partition with its complement, by Section 3.1.

For $B_j$, its complement $C_j$ has score $-k$. Deleting a paired good from $B_j$ gives a disjoint neighbor of $C_j$ with score $-(k-1)>-k$. Thus neither $B_j$ forms an EFX partition with its complement.

The fixed four-bundle distribution remains valid by Section 4. Hence support size four is the smallest possible size of this obstruction.

7. What remains unresolved

The general task has a PLS upper bound, but the local-search proof does not yield a polynomial running time.

The new construction proves that partition hardness can coexist with an elementary solution to the distribution problem on the entire hard family. It also gives a conditional obstruction to any general polynomial-time conversion from valid distributions to EFX partitions.

It does not establish hardness or a polynomial-time algorithm for the general distribution problem. A successful hardness reduction must constrain every valid overlapping-support output, rather than relying on the hardness of complementary partitions.

⟨structured verdict parsed — rendered above⟩

Verification report

Overall assessment: partial, with sound substantive progress. The output proves the stated upper bound, the separation between partition search and distribution search on its constructed family, and the characterization of valid distributions in that family. It does not settle the polynomial-time versus NP-hardness question in USER_TASK, and explicitly acknowledges this.

I found no false central step or substantive mathematical gap in the auxiliary results. The minimum-support claim omits one routine edge case.

1. General upper bound

Rational-value encoding

The output-width assumption supplies
$$ 0\le p<2^r,\qquad 1\le q<2^r. $$
For distinct rational values, the cross-product numerator is a nonzero integer, so its absolute value is at least $1$. Since $qq'<2^{2r}$, the stated bound
$$ \left|\frac pq-\frac{p'}{q'}\right|>2^{-2r} $$
is correct. Reduced fractions are not required.

Consequently,
$$ z(X)=\left\lfloor 2^{2r}v(X)\right\rfloor $$
preserves strict order and equality. The bound $z(X)<2^{3r}$ also follows from the numerator and denominator bounds. Computing this integer requires only polynomial-length integer arithmetic.

Cardinality tie-breaking

The definition
$$ s(X)=(m+1)z(X)+|X| $$
correctly implements lexicographic comparison of $(v(X),|X|)$. A strict increase in $z$ contributes at least $m+1$, while cardinality differences have absolute value at most $m$.

Local-search specification

The partition representation, initial partition, objective, and single-good-transfer neighborhood are polynomially computable. Enumerating the $m$ neighbors suffices to identify an improvement or certify local optimality. Objective values have polynomial bit length.

These ingredients establish the claimed basic polynomial local search problem; they do not establish a polynomial number of improvement steps.

Local optimality implies EFX

Suppose an EFX violation is witnessed by
$$ v(X)<v(Y\setminus\{g\}). $$
Monotonicity gives $v(Y)>v(X)$, so the current minimum objective is $s(X)$.

After the transfer, $s(Y\setminus\{g\})>s(X)$. Also,
$$ s(X\cup\{g\})>s(X), $$
because either the valuation increases or the valuation stays equal and cardinality increases. Thus both arguments of the new minimum strictly exceed the old minimum.

This proves the implication correctly, including goods with zero marginal value.

Conversion to a distribution

For $m>0$, complementary partition bundles are distinct. Giving each weight $1/2$ satisfies every marginal constraint. Cross-bundle EFX comparisons follow from the partition property, and self-comparisons follow from monotonicity.

For $m=0$, the explicitly supplied singleton distribution is valid.

Assessment: The polynomial-time solution reduction to $\mathrm{PLS}$ and existence of a solution supported on at most two bundles are established. Neither implies the requested polynomial-time algorithm or NP-hardness classification.

2. Constructed valuation family

Defect cases

For a $k$-element bundle, the counting identity
$$ s=a+b,\qquad d=2a+b $$
is correct. Hence $d=0$ means a transversal omitting $z$, and $d=1$ means exactly one empty pair, no double pairs, and inclusion of $z$.

In the latter case, disjointness fixes the transversal choice at every occupied pair and leaves two choices at the empty pair. The claimed two transversals therefore exist and are exactly the possibilities.

Score and valuation bounds

All three score cases satisfy
$$ -k\le f(S)\le 2W. $$
With the specified denominator,
$$ 0\le\frac{f(S)+k}{D} \le\frac{2W+k}{2(2W+k+1)} <\frac12. $$
The resulting bounds on $v(S)$ at cardinality $k$ are correct.

Monotonicity and submodularity

The marginal table is accurate:

• Below cardinality $k-1$, the marginal is $2$.
• At cardinality $k-1$, it lies in $[1,3/2)$.
• At cardinality $k$, it lies in $(1/2,1]$.
• Above cardinality $k$, it is $0$.

These intervals prove monotonicity. They also justify every diminishing-returns comparison when $S\subsetneq T$: the marginal interval at the smaller cardinality lies entirely above or equal to the interval at the larger cardinality. If the cardinalities agree, inclusion forces $S=T$.

Thus the submodularity argument does not assume additional regularity of $C$.

Succinct representation

The construction evaluates at most two copies of $C$ and performs counting, comparisons, and polynomial-length arithmetic. Although $f$ can be negative, the circuit’s actual valuation numerator
$$ (2k-1)D+f(S)+k $$
is nonnegative. The denominator is positive, and both output lengths are polynomial.

Assessment: All valuation promises and representation requirements are verified.

3. Partition-search hardness

Cited theorem

The cited paper states that Flip is $\mathrm{PLS}$-complete and defines its circuit objective as an unsigned binary integer, with single-bit flips as neighbors and minimization as the goal. This matches the prover’s stated source problem after reversing the objective by $W-C(x)$. The reversal is polynomially computable and preserves precisely the required local-optimum correspondence. [Goldberg–Høgh–Hollender, Section 4.2.2](https://www.cs.ox.ac.uk/people/paul.goldberg/papers/TCS-GHH.pdf)

Partition cardinalities and neighborhood equivalence

A partition with smaller cardinality at most $k-1$ has larger cardinality at least $k+2$. Its deletion values and smaller-bundle value violate EFX exactly as stated.

For cardinalities $k$ and $k+1$, comparisons against deletions of the smaller bundle are automatic. The remaining comparisons are exactly
$$ f(A)\ge f(B\setminus\{g\}). $$
Every disjoint $k$-element bundle is one such deletion, since the complement of $A$ has cardinality $k+1$.

The claimed equivalence with score-local maximality is therefore correct in both directions.

Excluding nontransversals

For defect $1$, a disjoint transversal has score exactly one larger than the bundle’s score.

For defect at least $2$, the counting identity ensures an empty pair exists. Complementing and deleting one good from such a pair produces the stated neighbor, with defect reduced by one. The score comparisons are correct both within the third score case and when crossing into either earlier case.

Thus every score-local maximum is a transversal.

Decoding a Flip solution

The bundle $E_i$ has cardinality $k$, is disjoint from $T(x)$, and has the asserted two disjoint transversal neighbors. If a bit flip improves $F$, integrality makes its score strictly exceed that of $T(x)$.

Therefore every returned EFX partition decodes to a local maximum of $C$ on its original input bits. Padding introduces no problem because $F$ ignores the added bits.

Assessment: The claimed $\mathrm{PLS}$-hardness of partition search on this family is established. It is not hardness of distribution search.

4. Four-bundle distribution and conversion obstruction

The four bundles are distinct: the transversals differ from one another, the larger bundles differ from one another, and their cardinalities separate the two groups.

Every paired good appears in exactly two supported bundles, and $z$ appears in exactly the two larger bundles. The positive weights sum to $1$ and yield all required marginals.

The deletion calculations are correct:

• A transversal deletion has value $2k-2$.
• Deleting $z$ from a larger bundle leaves defect $k$ and score $-k$.
• Deleting a paired good leaves defect $k-1$ and score $-(k-1)$.

The condition $k\ge4$ ensures the last case uses the third score clause. Hence every deletion has value at most
$$ 2k-1+\frac1D, $$
while every supported bundle has value at least
$$ 2k-1+\frac{k}{D}. $$
This verifies every required ordered comparison, including self-comparisons and zero-marginal deletions.

The conditional conversion claim follows: the explicit distribution has polynomial size, so a polynomial-time converter accepting any valid distribution would compose with the partition decoder to solve Flip in polynomial time.

Assessment: Both the family-specific distribution algorithm and the conditional conversion obstruction are established.

5. Exact characterization of distributions

The expectation identity follows directly from the marginal equations.

The two cardinality-exclusion arguments are valid. They force all support cardinalities to be $k$ or $k+1$, with total weight $1/2$ on each.

Rescaling the weights and complementing the larger bundles gives probability distributions $p,r$. The algebra converting marginal constraints to equality of incidence averages is correct.

All EFX comparisons other than a smaller bundle against a deletion of a larger bundle are automatic from the cardinality valuation bounds. The remaining comparisons are exactly the displayed minimum-versus-maximum score condition.

The converse is also correct: dividing the probability weights by $2$ reconstructs positive rational support weights, the marginal equations, and EFX. Bundles arising from the two groups cannot coincide because their cardinalities differ.

Assessment: The characterization is proved.

6. Minimum support for the extraction obstruction

The two-bundle argument is correct for a nonempty ground set.

The three-bundle argument is also correct. A marginal equation forces a singleton weight of $1/2$; thereafter every coordinate must select either that singleton or the other two indices together. The other two bundles consequently coincide, contradicting distinctness.

The specialized circuit has the claimed values and improving bit flips. The complementary partition failures for all four supported bundles follow from the previously proved score characterization.

Minor issue: The assertion that four is the *smallest possible* support omits explicit exclusion of support size one. The stated task also permits an empty ground set, which should be addressed when phrasing this global minimum claim.

Minimum clarification: Add the routine singleton-support and empty-ground-set checks. No new lemma or substantive mathematics is needed.

7. Scope deficit and actionable feedback

Major scope deficit: The central question in USER_TASK remains unresolved. The output proves an upper bound by reduction to $\mathrm{PLS}$ and a polynomial algorithm restricted to its constructed family. It supplies neither a polynomial-time algorithm for arbitrary promised valuation circuits nor an NP-hardness reduction for the distribution problem.

This is an acknowledged limitation, not a concealed failure in the auxiliary proofs.

To complete the assignment, the prover must supply one of the requested general complexity results, including its running-time justification or its search-reduction specification and correctness for every valid returned distribution. Clarification of the present arguments alone cannot supply that missing result.

⟨structured verdict parsed — rendered above⟩