On Optimal Tradeoffs between EFX and Nash Welfare*

NEW RESULT — discrete: polynomial-time → continuous: hard · adversarial review: proved

The anchor (named result in the paper)

statement extracted from the paper’s text layer; consult the paper for the exact wording

The continuous mirror question, as graded

Given rational masses $p_t$ over additive valuation types, rational supplies $q_g$ of indivisible item kinds, and $\alpha \in [0, \varphi-1]$, compute a complete mass allocation $y_{tB}$ over bundles $B$ such that the type-mass and item-capacity constraints hold, every occupied bundle pair satisfies support-wise $\alpha$-EFX and EF1, and $\mathrm{NW}_\infty(y)$ is at least $1/(\alpha+1)$ times the maximum continuous Nash welfare over feasible complete mass allocations.

Packaged proof task (what the prover saw — nothing else)

A society is given by its support: the list of the $\tau$ additive valuation types with positive mass $p_t$, each mass a binary rational, with $\sum_t p_t=1$. Here $\tau$ is the support size, not the number of possible types.
There are $m\ge1$ item kinds, with binary rational supplies $q_g\ge0$ and values $v_{tg}\ge0$. The input also contains a binary rational $\alpha\in[0,\varphi-1]$, where $\varphi=(1+\sqrt5)/2$; let $L$ be the total input bit length.
A bundle is a finite multiset $B\in\mathbb Z_{\ge0}^m$, with $v_t(B)=\sum_g v_{tg}B_g$. Individuals receive whole items; fractional quantities describe masses of individuals receiving bundles.
A complete mass allocation consists of finitely many nonzero entries $y_{tB}\ge0$, satisfying $\sum_B y_{tB}=p_t$ and $\sum_{t,B}B_g y_{tB}=q_g$ for every kind $g$.
Support-wise fairness requires, for every ordered pair $(t,B),(s,C)$ with $y_{tB}y_{sC}>0$, including pairs within one type, $v_t(B)\ge\alpha v_t(C-e_g)$ for every $g$ with $C_g>0$, and EF1: this inequality without $\alpha$ holds for at least one such $g$. Both requirements are satisfied when $C$ is empty; $e_g$ removes one copy, and zero-valued items are included.
Define $NW_\infty(y)=\exp(\sum_{t,B:y_{tB}>0}y_{tB}\log v_t(B))$, with value zero if any occupied bundle has zero utility. Let $\mathrm{OPT}$ be its supremum over all complete mass allocations, without fairness restrictions.

Can a complete rational mass allocation satisfying support-wise $\alpha$-EFX and EF1 and $NW_\infty(y)\ge\mathrm{OPT}/(\alpha+1)$ always be computed in time polynomial in $m,\tau,L$, or is attaining this guarantee NP-hard?

For finite additive societies, complete $\alpha$-EFX and EF1 allocations achieving $1/(\alpha+1)$ of optimal Nash welfare exist throughout this range; a polynomial-time construction is available given a maximum-Nash-welfare allocation ([Feldman–Mauras–Ponitka](https://arxiv.org/pdf/2302.09633)).
No result settling exactly this support-wise mass-allocation formulation was located.

Modeling choices made when packaging the task

Prover output (gpt-6.1-sol / high, Bolzano prover prompt)

Result and scope

Attaining the stated guarantee is $\mathrm{NP}$-hard when $\alpha$ is part of the input. This holds even with one valuation type, strictly positive integer item values, supplies all equal to $\frac12$, and strictly positive dyadic $\alpha$.

The reduction uses values of $\alpha$ approaching zero. It therefore settles the formulation in the question, but does not establish hardness for a prescribed positive constant $\alpha$.

The proof does not merely exploit the endpoint $\alpha=0$. Moreover, every instance constructed below admits a complete rational allocation satisfying the requested fairness and welfare conditions.

1. Encoding PARTITION with unrestricted integer bundles

We reduce from PARTITION: given positive integers $a_1,\ldots,a_n$, decide whether some subset sums to half their total. Its $\mathrm{NP}$-completeness is standard; see, for example, these [MIT lecture notes](https://people.csail.mit.edu/rrw/6.045-2020/lec17-color.pdf).

We may assume $n\ge2$ and that the total is even. The first restriction removes only immediately decidable instances; doubling every integer enforces the second without changing the answer. Write

$\displaystyle \sum_{i=1}^n a_i=2A,\qquad a_{\max}=\max_i a_i.$

Define the following positive integers:

$\displaystyle b=n+1,\qquad M=na_{\max}+1,\qquad D_i=Mb^{i-1},\qquad S=\sum_{i=1}^nD_i,$

$\displaystyle H=S+a_{\max}+A,\qquad K=nH+1,\qquad T=nK+S+A.$

There is one type, of mass $1$, and two item kinds $(i,0),(i,1)$ for each index $i$. Their values and supplies are

$\displaystyle w_{i,0}=K+D_i,\qquad w_{i,1}=K+D_i+a_i,\qquad q_{i,0}=q_{i,1}=\frac12.$

Thus $m=2n$ and $\tau=1$. Write $v(B)$ for this type’s utility and $|B|$ for a bundle’s total number of items, counting multiplicities.

For later use, put

$\displaystyle d=\max_iD_i+a_{\max},\qquad W=K+d.$

Every item value belongs to $[K,W]$. Also, $d\le S+a_{\max}<H$, so

$\displaystyle W<K+\frac Kn,\qquad S+A<K.$

Encoding lemma. An integer bundle $B$ satisfies $v(B)=T$ if and only if it contains exactly one item from every pair $(i,0),(i,1)$, and the indices for which it contains $(i,1)$ form a PARTITION solution.

Proof. First suppose $v(B)=T$.

If $|B|\ge n+1$, then

$\displaystyle v(B)\ge(n+1)K>T.$

If $|B|\le n-1$, then

$\displaystyle v(B)\le(n-1)W<(n-1)\left(K+\frac Kn\right)<nK\le T.$

Consequently, $|B|=n$. Let

$\displaystyle c_i=B_{i,0}+B_{i,1},\qquad h=\sum_i a_iB_{i,1}.$

Subtracting $nK$ from $v(B)=T$ gives

$\displaystyle M\sum_i c_ib^{i-1}+h=M\sum_i b^{i-1}+A.$

Because $B$ contains $n$ items,

$\displaystyle 0\le h\le na_{\max}<M,\qquad 0<A<M.$

Reduction modulo $M$ therefore gives $h=A$. Substitution yields

$\displaystyle \sum_i c_ib^{i-1}=\sum_i b^{i-1}.$

Each $c_i$ lies between $0$ and $n=b-1$. Uniqueness of base-$b$ representation implies $c_i=1$ for every $i$. Thus $B_{i,1}\in\{0,1\}$, and $h=A$ identifies a subset of sum $A$.

Conversely, choosing $(i,1)$ for the indices of a subset of sum $A$, and $(i,0)$ otherwise, gives utility $nK+S+A=T$. This proves the lemma, including its applicability to bundles with unrestricted multiplicities. $\square$

2. Mean utility and a quantitative welfare gap

For every complete allocation, the mass-weighted mean utility is fixed:

$\displaystyle \sum_B y_Bv(B)=\sum_{i,j}q_{i,j}w_{i,j}=nK+S+A=T.$

Since the total mass is $1$, concavity of the logarithm gives

$\displaystyle NW_\infty(y)\le T.$

This also holds when an occupied bundle has zero utility, because then the welfare is zero.

We need a strict bound when no occupied bundle has utility $T$.

Gap lemma. If $T\ge2$, all bundle utilities are nonnegative integers, their mass-weighted mean is $T$, and no occupied bundle has utility $T$, then

$\displaystyle NW_\infty(y)\le\sqrt{T^2-1}.$

Proof. An occupied zero-utility bundle makes the claim immediate. Otherwise all occupied utilities are positive integers, hence lie outside the open interval $(T-1,T+1)$.

Let $\ell$ be the affine function through the two points

$\displaystyle (T-1,\log(T-1)),\qquad (T+1,\log(T+1)).$

Concavity of $\log$ implies that its graph lies below the extension of this secant outside $[T-1,T+1]$. Explicitly, for $x<T-1$, express $T-1$ as a convex combination of $x$ and $T+1$, apply concavity, and rearrange to obtain $\log x\le\ell(x)$. For $x>T+1$, use the convex-combination expression of $T+1$ in terms of $T-1$ and $x$. Equality holds at the endpoints.

Therefore,

$\displaystyle \sum_B y_B\log v(B)\le\sum_B y_B\ell(v(B))=\ell(T)=\frac12\log(T^2-1),$

where the middle equality uses the mean-utility identity. Exponentiating proves the claim. $\square$

3. Choosing a strictly positive input parameter

Let $k$ be the binary bit length of $T$, and set

$\displaystyle \alpha=2^{-(2k+2)}.$

This is a strictly positive dyadic rational with polynomial encoding length, and

$\displaystyle 0<\alpha\le\frac1{4T^2}\le\frac1{16}<\varphi-1.$

The chosen parameter satisfies

$\displaystyle \frac{T}{1+\alpha}>\sqrt{T^2-1}.$

Indeed, put $x=T^{-2}$. Since $T\ge2$, we have $0<x<1$, and

$\displaystyle \frac1{1+\alpha}\ge1-\alpha\ge1-\frac x4>1-\frac x2\ge\sqrt{1-x}.$

The last inequality follows by squaring its nonnegative sides: $(1-x/2)^2\ge1-x$.

4. Yes-instances have optimal welfare $T$

Suppose the PARTITION instance has a solution. Let $B$ be its encoded bundle from the encoding lemma, and let $C$ choose the opposite item from every pair.

Both bundles have utility $T$, because the complementary subset also sums to $A$. Assign mass $\frac12$ to each bundle. This allocation is complete and rational, and its welfare equals $T$. The mean-utility upper bound therefore shows that

$\displaystyle \mathrm{OPT}=T.$

It also satisfies both requested fairness conditions. Every occupied bundle has utility $T$, while removing any item from either bundle leaves utility at most $T$. This verifies every ordered comparison, including comparisons within the same type.

Consequently, on a yes-instance, any output satisfying the requested welfare guarantee must have

$\displaystyle NW_\infty(y)\ge\frac{T}{1+\alpha}>\sqrt{T^2-1}.$

By the gap lemma, such an output must contain an occupied bundle of utility exactly $T$. The encoding lemma then extracts a PARTITION solution.

5. Every constructed instance admits a rational fair optimum

We now verify that the reduction does not rely on infeasible no-instances. In fact, every constructed instance has a rational allocation attaining $\mathrm{OPT}$, and this allocation satisfies EF1 and the chosen $\alpha$-EFX.

Attainment and rationality

For an integer $R\ge n+1$, restrict attention to nonempty bundles with $|B|\le R$. This gives a finite linear program:

$\displaystyle \max\sum_B y_B\log v(B),$

subject to the prescribed masses and supplies.

Its feasible set is nonempty: assign mass $\frac12$ to the bundle containing all $(i,0)$, and mass $\frac12$ to the bundle containing all $(i,1)$. Both bundles contain $n$ items. Its feasible set is compact, because $y_B\ge0$ and $\sum_B y_B=1$. Thus a maximum exists.

We claim that every maximizing allocation in this restricted problem uses only bundles of utility at most $T+W$.

Suppose instead that an occupied bundle $C$ has utility $w>T+W$. Since mean utility is $T$, some occupied bundle $B$ has utility $u\le T$. Choose an item $g$ in $C$, of value $z\in[K,W]$. Replace equal positive masses of $B,C$ by $B+e_g,C-e_g$.

This preserves every mass and supply constraint. It remains within the restricted bundle set: $u\le T<(n+1)K$ implies $|B|\le n$, so $|B+e_g|\le n+1\le R$. Also, $w>T+W>W\ge z$, so $C-e_g$ is nonempty.

The change strictly increases the objective, since

$\displaystyle (u+z)(w-z)-uw=z(w-u-z)>0,$

using $w-u>W\ge z$. This contradicts maximality.

Next,

$\displaystyle T+W=(n+1)K+S+A+d<(n+2)K.$

For the strict inequality, note that $S+A+d\le2H\le nH<K$. Every maximizing occupied bundle therefore contains at most $n+1$ items.

It follows that the optimal values of all these restricted problems, for $R\ge n+1$, coincide. Every finite-support allocation with positive welfare belongs to one such restricted problem; allocations with zero welfare cannot improve the positive feasible welfare exhibited above. Hence the common restricted optimum equals the unrestricted supremum $\mathrm{OPT}$, and attains it.

Choose an optimal vertex in the problem restricted to $|B|\le n+1$. Such a vertex exists even though the objective coefficients are real: a linear objective on a polytope attains its maximum at a vertex. The constraints are rational, so this vertex has rational masses. It has at most $m+1=2n+1$ positive entries, because there are $m+1$ equality constraints.

These entries also have polynomial encoding length. Bundle coordinates are at most $n+1$; the masses solve a nonsingular subsystem with integer coefficients bounded by $n+1$ and right-hand sides in $\{1,\frac12\}$. Cramer’s rule and determinant bounds give polynomial bit length.

EF1

Let $y^*$ be this global optimum. All occupied utilities are positive.

If an ordered pair $B,C$ violated EF1, then, writing $u=v(B)$ and $w=v(C)$, we would have

$\displaystyle u<w-w_g\qquad\text{for every item kind $g$ present in $C$}.\)

Choose any such item, of value $z=w_g>0$, and transfer it from an equal positive mass of $C$ to an equal positive mass of $B$. The resulting utilities remain positive, and

$\displaystyle (u+z)(w-z)-uw=z(w-u-z)>0.$

This strictly improves welfare while preserving completeness, contradicting global optimality. Thus $y^*$ is support-wise EF1.

The chosen $\alpha$-EFX

Let $u_{\min},u_{\max}$ be the minimum and maximum occupied utilities. EF1 and the bound $w_g\le W$ imply, for every occupied bundle $C$,

$\displaystyle u_{\min}\ge v(C)-W.$

Averaging gives $u_{\min}\ge T-W$. Applying EF1 to every occupied bundle against a bundle of maximum utility and averaging likewise gives $u_{\max}\le T+W$.

Moreover,

$\displaystyle W<K+\frac Kn\le\frac32K\le\frac34T.$

Consequently,

$\displaystyle T-W>\frac T4,\qquad T+W<\frac{7T}{4}.$

Since $\alpha\le\frac1{16}<\frac17$, every occupied ordered pair $B,C$, and every item $g$ in $C$, satisfies

$\displaystyle v(B)\ge T-W>\alpha(T+W)\ge\alpha v(C-e_g).$

Thus $y^*$ is support-wise $\alpha$-EFX. It attains $\mathrm{OPT}$, so it also satisfies the requested welfare guarantee.

This establishes feasible, polynomial-size rational outputs on both yes- and no-instances.

6. Polynomial reduction and conclusion

All constructed integers have polynomial binary encoding length. In particular,

$\displaystyle \log_2D_i=O(\log n+\log a_{\max}+n\log n),$

and $S,K,T$ have the same polynomial-order bit bound. The denominator encoding of $\alpha$ also has polynomial length. Hence the reduction is computable in polynomial time.

Suppose an algorithm computed the requested allocation in time polynomial in $m,\tau,L$, using the explicit finite list of rational masses and integer bundles specified in the question. Run it on the constructed instance and inspect whether any positive-mass bundle has utility $T$.

On a yes-instance, the welfare guarantee and the gap lemma force such a bundle to appear.
On a no-instance, the encoding lemma proves that no integer bundle of utility $T$ exists.

This inspection uses only exact integer arithmetic on a polynomial-length output. It would decide PARTITION in polynomial time.

Therefore attaining the requested guarantee is $\mathrm{NP}$-hard, and no such polynomial-time algorithm exists unless $\mathrm{P}=\mathrm{NP}$.

This is compatible with the [Feldman–Mauras–Ponitka finite-society theorem](https://arxiv.org/pdf/2302.09633), which gives the stated existence guarantee and a construction supplied with a maximum-Nash-welfare allocation. The obstruction proved here is computational and already occurs for one valuation type and strictly positive input-dependent $\alpha$.

⟨structured verdict parsed — rendered above⟩

Adversarial review (gpt-6.1-sol / medium, Bolzano verifier prompt)

Verdict: proved. The output establishes $\mathrm{NP}$-hardness for the stated problem with input-dependent, strictly positive $\alpha$. I found no major or minor issues. The argument also verifies that every constructed instance admits a polynomial-size rational allocation meeting the requested conditions.

1. Source problem and input restrictions

The source problem is correctly stated: PARTITION asks whether a list of positive integers has a subset summing to half its total. Its $\mathrm{NP}$-completeness is supported by the cited [MIT lecture notes](https://people.csail.mit.edu/rrw/6.045-2020/lec17-color.pdf).

The restrictions are legitimate:

Instances with fewer than two positive integers are immediately decidable.
Doubling every integer preserves the answer and makes the total even.
The resulting $A$ is a positive integer.

The constructed society satisfies the target’s input requirements: one positive-mass type, positive integer values, and rational nonnegative supplies.

2. Encoding lemma

The cardinality bounds are correct. From the definitions, $d<H<K/n$ and $S+A<K$. Consequently:

A bundle containing at least $n+1$ items has utility greater than $T$.
A bundle containing at most $n-1$ items has utility less than $nK$, hence less than $T$.

Thus any bundle of utility $T$ contains exactly $n$ items.

The modular argument is valid. Both $h$ and $A$ belong to $[0,M)$: in particular, $A\le na_{\max}/2<M$. Therefore their congruence modulo $M$ implies equality.

Each coefficient $c_i$ belongs to $\{0,\ldots,b-1\}$. Uniqueness of base-$b$ representation therefore applies exactly as stated and forces $c_i=1$. This rules out repeated copies and missing pairs even though bundles allow unrestricted multiplicities.

The converse follows directly from the utility formula. The lemma is proved in both directions.

3. Mean utility and welfare gap

Completeness fixes the mass-weighted mean utility at $T$. Jensen’s inequality applies because the support is finite, the masses sum to one, and all occupied utilities are positive whenever welfare is positive. Allocations containing an occupied zero-utility bundle are correctly handled separately.

The gap lemma is sound:

Utilities are integers, so excluding $T$ leaves only utilities at most $T-1$ or at least $T+1$.
Since $T\ge2$, both secant endpoints have positive arguments.
The extension of the logarithmic secant lies above the logarithm outside the endpoint interval; the provided concavity argument justifies the direction of the inequality.
Affineness and the mean-utility identity give the claimed bound $\sqrt{T^2-1}$.

The lemma permits arbitrary real masses. It does not require equal weights or rationality.

4. Choice of $\alpha$

The bit-length definition gives $T<2^k$, so the asserted bound $\alpha\le1/(4T^2)$ holds. The parameter is strictly positive, has polynomial binary encoding length, and belongs to the permitted interval.

The comparison
$\frac{T}{1+\alpha}>\sqrt{T^2-1}$
is correct. Every inequality in the displayed chain has the stated direction, and the strict inequality is justified by $x=T^{-2}>0$. Squaring the nonnegative expressions correctly establishes $1-x/2\ge\sqrt{1-x}$.

There is no precision assumption hidden in this step: the reduction uses an exact rational parameter.

5. Yes-instances and extraction

For a PARTITION solution, the encoded bundle and its complementary bundle both have utility $T$. Assigning mass $1/2$ to each supplies exactly $1/2$ of every item kind.

The allocation is complete, rational, and attains the mean-utility upper bound, establishing $\mathrm{OPT}=T$. Equal occupied utilities also satisfy every required fairness comparison, including comparisons within the single type.

Any output meeting the welfare guarantee on a yes-instance exceeds the gap bound. It must therefore contain a positive-mass bundle of utility exactly $T$, from which the encoding lemma extracts a PARTITION solution.

6. Attainment and rationality on all constructed instances

The restricted optimization argument is valid. For each $R\ge n+1$, the bundle set is finite, the feasible polytope is nonempty and compact, and all objective coefficients are finite real numbers.

The improving transfer respects every restriction:

The two source bundles have different utilities and are distinct.
Equal sufficiently small positive masses can be removed from both.
The receiving bundle initially contains at most $n$ items, so its replacement remains within the cardinality bound.
The donating bundle remains nonempty.
Mass and every supply constraint are preserved.
The positive product difference implies a strict increase in the logarithmic objective.

Thus a restricted optimizer cannot occupy a bundle of utility greater than $T+W$. The subsequent estimate $T+W<(n+2)K$ is correct, including at $n=2$, and forces every optimizing bundle to contain at most $n+1$ items.

The restricted optimal values therefore coincide. Every positive-welfare finite-support allocation belongs to some restricted problem, while zero-welfare allocations cannot improve on the exhibited positive feasible allocation. This correctly establishes attainment of the unrestricted supremum.

The vertex argument also satisfies its hypotheses. A real linear objective attains a maximum at a vertex of this nonempty bounded polytope. Rational constraints make that vertex rational. Its support has at most $m+1$ entries, and the stated determinant bounds give polynomial encoding length for the masses and bundles.

This is an existence argument; it does not claim that the exponentially large linear program can be solved in polynomial time.

7. Support-wise fairness of the optimum

The EF1 argument is correct. A violating ordered pair would satisfy $w-z>u>0$ for every item available for removal. The proposed transfer preserves completeness and strictly increases welfare, contradicting global optimality. Equal bundles cannot violate EF1, so no coincident-source issue arises.

The bounds derived from EF1 are also valid:

Comparing a minimum-utility bundle against every occupied bundle and averaging gives $u_{\min}\ge T-W$.
Comparing every occupied bundle against a maximum-utility bundle and averaging gives $u_{\max}\le T+W$.

The estimate $W<3T/4$ uses $n\ge2$ correctly. Together with $\alpha\le1/16<1/7$, it establishes the required inequality for every ordered pair and every removable item. All constructed bundles are nonempty and all item values are positive, so the target’s empty-bundle and zero-valued-item conventions cause no omitted cases.

The rational optimum consequently meets both fairness requirements and the welfare guarantee on no-instances as well as yes-instances.

8. Polynomial reduction and scope

All constructed numbers have polynomial binary length. The exponentially large numerical magnitudes do not invalidate a reduction from binary-encoded PARTITION.

Given a polynomial-time algorithm producing the requested explicit allocation, inspecting its positive-mass bundles for utility $T$ takes polynomial time using exact arithmetic. The extraction succeeds on every valid output for a yes-instance, and no such bundle exists on a no-instance. No computation or comparison of logarithms is required by the deciding algorithm.

This establishes the claimed hardness of producing an allocation. The output correctly limits its conclusion to input-dependent $\alpha$; it does not claim hardness for a prescribed positive constant.

The final compatibility statement accurately describes the finite-society result and its conditional polynomial-time construction. That theorem is contextual and is not used to establish mass-allocation feasibility here. See [Feldman–Mauras–Ponitka, Theorem 2 and computational remarks](https://arxiv.org/pdf/2302.09633).

Actionable feedback: No repair or additional clarification is required.