Maxileximin Envy Allocations and Connected Goods

NEW RESULT — discrete: hard → 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 a star goods graph, rational masses over finitely many complete additive utility types, and rational capacities $q_v$ representing normalized multiplicities of indivisible copies of each role $v$, assign type mass $x_{t,B}$ to whole connected bundles $B$ so capacities and type masses are met; lexicographically minimize the population-mass distribution of each agent's maximum envy over bundles used in the allocation, then maximize total welfare.

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

Let $G=(V,E)$ be a star and $\mathcal B(G)=\{\emptyset\}\cup\{B\subseteq V:G[B]\text{ is connected}\}$. Each type $t\in T$ has additive utility $u_t(B)=\sum_{v\in B}u_t(v)$. A mass assignment is $\lambda_{t,B}\ge0$ with $\sum_{B\in\mathcal B(G)}\lambda_{t,B}=\mu_t$ and $\sum_{t\in T}\sum_{B\ni v}\lambda_{t,B}=\rho_v$. It is envy-free if $\lambda_{t,B}>0$ and $\sum_{t'}\lambda_{t',B'}>0$ imply $u_t(B)\ge u_t(B')$.

Target. Under the promise that an envy-free mass assignment exists, is computing an envy-free mass assignment maximizing $\sum_{t,B}\lambda_{t,B}u_t(B)$ solvable in polynomial time, or is it NP-hard?

Nearest known results. For finite agents with indivisible goods, maximizing social welfare over envy-free complete connected allocations is $F\Delta_2^P$-hard even when the goods graph is a star and an envy-free allocation is guaranteed to exist. No result for the exact distribution-over-types mass-assignment problem above is stated here.

Prover output (gpt-5.6-sol / xhigh, Bolzano prover prompt)

Theorem

Under the model as stated, computing a welfare-maximizing envy-free mass assignment is $\mathrm{NP}$-hard, even when:

there are only two types;
both type masses equal $1$;
all supplies belong to $\{1,\tfrac12\}$;
an envy-free assignment with support size three is guaranteed to exist.

The proof uses signed additive utilities. The statement imposes no nonnegativity restriction.

A support lemma

Let $\lambda$ be envy-free and fix a type $t$ with $\mu_t>0$. If $\lambda_{t,B}>0$ and $\lambda_{t,C}>0$, then

\[ u_t(B)\ge u_t(C) \]

by applying envy-freeness to $B$ and the globally used bundle $C$. Reversing $B$ and $C$ gives $u_t(C)\ge u_t(B)$. Hence all bundles assigned positive mass to $t$ have the same utility. Denote it by $z_t$. Consequently, type $t$'s welfare contribution is exactly $\mu_tz_t$.

Reduction from $\mathrm{PARTITION}$

Take a $\mathrm{PARTITION}$ instance consisting of positive integers $b_1,\ldots,b_n$, encoded in binary. Set

\[ a_i=2b_i,\qquad W=\sum_{i=1}^n a_i. \]

Thus $W$ is even. There exists $S\subseteq\{1,\ldots,n\}$ with

\[ \sum_{i\in S}a_i=\frac W2 \]

if and only if the original instance is a yes-instance of $\mathrm{PARTITION}$.

Construct a star with center $c$, ordinary leaves $\ell_1,\ldots,\ell_n$, and one additional leaf $q$. There are two types, $A$ and $D$, with

\[ \mu_A=\mu_D=1. \]

Set the supplies to

\[ \rho_c=\rho_q=1,\qquad \rho_{\ell_i}=\frac12 \]

for every $i$.

Type $D$ has zero utility for every vertex. Type $A$'s vertex utilities are

\[ u_A(c)=\frac W2+1,\qquad u_A(q)=-\left(\frac W2+1\right),\qquad u_A(\ell_i)=-a_i. \]

All numbers have encoding length polynomial in that of the $\mathrm{PARTITION}$ instance.

The promise is always satisfied

Consider the assignment

\[ \lambda_{A,\emptyset}=1, \]

and

\[ \lambda_{D,\{c,q\}}=\frac12,\qquad \lambda_{D,\{c,q,\ell_1,\ldots,\ell_n\}}=\frac12. \]

All three bundles are feasible connected bundles, with the empty bundle explicitly allowed.

The center and $q$ are each consumed with mass $1$, while every ordinary leaf is consumed with mass $\tfrac12$. Thus all mass and supply constraints hold.

The three relevant utilities for type $A$ are

\[ u_A(\emptyset)=0,\qquad u_A(\{c,q\})=0,\qquad u_A(\{c,q,\ell_1,\ldots,\ell_n\})=-W. \]

Therefore type $A$, which receives the empty bundle, envies none of the used bundles. Type $D$ assigns utility $0$ to every bundle, so it also envies none. Hence the assignment is envy-free and has welfare $0$.

Thus every constructed instance satisfies the promised existence condition.

A partition yields welfare $1$

Suppose $S\subseteq\{1,\ldots,n\}$ satisfies $\sum_{i\in S}a_i=W/2$. Assign

\[ \lambda_{A,\{c\}\cup\{\ell_i:i\in S\}}=\frac12, \]

\[ \lambda_{A,\{c\}\cup\{\ell_i:i\notin S\}}=\frac12, \]

and

\[ \lambda_{D,\{q\}}=1. \]

Every ordinary leaf occurs in exactly one of the two bundles assigned to $A$, so its total consumption is $\tfrac12$. The center and $q$ have consumption $1$.

Both bundles assigned to $A$ have utility

\[ \frac W2+1-\frac W2=1. \]

The only other used bundle is $\{q\}$, whose utility to $A$ is negative. Type $D$ values all used bundles at $0$. The assignment is therefore envy-free and has welfare $1$.

Positive welfare forces a partition

Let $\lambda$ be any envy-free assignment for the constructed instance. By the support lemma, all bundles assigned to $A$ have a common utility $z_A$. Since type $D$ always contributes zero welfare and $\mu_A=1$, the total welfare equals $z_A$.

Suppose the welfare is positive, so $z_A>0$. Every bundle assigned positive mass to $A$ must then have positive $A$-utility.

A connected bundle not containing $c$ is either empty or a singleton leaf. Its $A$-utility is respectively $0$, $-a_i$, or $-(\tfrac W2+1)$, and hence is never positive.

A center-containing bundle that also contains $q$ has the form

\[ \{c,q\}\cup\{\ell_i:i\in R\} \]

and has utility

\[ \left(\frac W2+1\right) -\left(\frac W2+1\right) -\sum_{i\in R}a_i = -\sum_{i\in R}a_i \le 0. \]

Consequently, every bundle assigned to $A$ contains $c$ and omits $q$.

Because $A$ has total mass $1$, it consumes the center with total mass $1$. Since $\rho_c=1$, type $D$ consumes no center. Similarly, $A$ consumes no $q$, so $D$ must consume $q$ with total mass $1$. As $\mu_D=1$, every bundle assigned positive mass to $D$ must contain $q$. A connected bundle containing $q$ but not $c$ can only be the singleton $\{q\}$. Thus $D$ receives only $\{q\}$ and consumes none of the ordinary leaves.

It follows that type $A$ consumes every $\ell_i$ with total mass exactly $\tfrac12$. Using additivity and the mass constraints,

\[ \begin{aligned} z_A &=\sum_B\lambda_{A,B}u_A(B)\\ &=\left(\frac W2+1\right)\sum_B\lambda_{A,B} -\sum_{i=1}^n a_i\sum_{B\ni\ell_i}\lambda_{A,B}\\ &=\frac W2+1-\frac12\sum_{i=1}^n a_i\\ &=1. \end{aligned} \]

Choose any bundle assigned positive mass to $A$; one exists because $\mu_A=1$. It has the form $\{c\}\cup\{\ell_i:i\in S\}$. Its utility is $z_A=1$, and hence

\[ \frac W2+1-\sum_{i\in S}a_i=1. \]

Therefore

\[ \sum_{i\in S}a_i=\frac W2, \]

which is a partition.

Complexity consequence

The optimum welfare of the constructed promised instance is therefore exactly

\[ \begin{cases} 1,&\text{if the original $\mathrm{PARTITION}$ instance is a yes-instance},\\ 0,&\text{otherwise}. \end{cases} \]

Thus an exact polynomial-time algorithm computing a welfare-maximizing envy-free mass assignment would decide $\mathrm{PARTITION}$ in polynomial time. The optimization problem is consequently $\mathrm{NP}$-hard under the guaranteed-existence promise.

This proof does not rely on the finite-agent hardness result and directly handles the support-based envy condition of the mass-assignment formulation.

⟨structured verdict parsed — rendered above⟩

Adversarial review (gpt-5.6-sol / high, Bolzano verifier prompt)

Verification report

Overall assessment

The reduction correctly establishes NP-hardness under the promised existence of an envy-free mass assignment. The argument accounts for signed utilities, connectivity on a star, exact supply constraints, and the support-dependent envy condition. No substantive gaps or false steps were found.

Step-by-step audit

Support lemma

For two bundles $B$ and $C$ receiving positive mass from the same type $t$, each is globally used. Envy-freeness therefore gives both $u_t(B)\geq u_t(C)$ and $u_t(C)\geq u_t(B)$. Hence all bundles in type $t$'s support have common utility $z_t$.

The welfare contribution is consequently $\sum_B\lambda_{t,B}u_t(B)=\mu_tz_t$. This is correct.

Reduction size and source problem

The transformation $a_i=2b_i$, $W=\sum_i a_i$ is polynomial-time and preserves the partition condition:

$\sum_{i\in S}a_i=W/2$ is equivalent to $2\sum_{i\in S}b_i=\sum_i b_i$.

All constructed utilities and supplies have polynomial binary encoding length. Using PARTITION proves ordinary, though weak, NP-hardness; this is sufficient for the theorem claimed.

Guaranteed feasible envy-free assignment

The proposed bundles $\emptyset$, $\{c,q\}$, and $\{c,q,\ell_1,\ldots,\ell_n\}$ are allowed connected bundles, with the empty bundle explicitly permitted.

The mass constraints and every supply equality are satisfied. Type $A$ evaluates the globally used bundles as $0$, $0$, and $-W$, while type $D$ evaluates all bundles as $0$. Thus the assignment is envy-free and has welfare $0$.

This proves that every reduced instance satisfies the promise.

Yes-instance construction

Given a partition $S$, the two center-containing bundles assigned to $A$ each have utility $1$. Their half-masses consume the center with total mass $1$ and each ordinary leaf with mass $1/2$. Type $D$'s singleton $\{q\}$ supplies the required mass on $q$.

Type $A$ weakly prefers each of its utility-$1$ bundles to every globally used bundle, including $\{q\}$, which has negative $A$-utility. Type $D$ is indifferent. The assignment is therefore envy-free with welfare $1$.

Consequences of positive welfare

Since only type $A$ contributes welfare and $\mu_A=1$, positive welfare implies $z_A>0$. The classification of connected star bundles is complete:

A bundle omitting $c$ is empty or a singleton leaf.
Such bundles have nonpositive $A$-utility.
A center-containing bundle that includes $q$ also has nonpositive $A$-utility.

Therefore every bundle in $A$'s support contains $c$ and omits $q$.

Forced allocation to type $D$

Because all of $A$'s unit mass is placed on bundles containing $c$, type $A$ consumes the full center supply. Hence $D$ consumes no center.

Since $A$ never consumes $q$, type $D$ must consume $q$ with total mass $1$. As $D$'s total mass is also $1$, every bundle in its support contains $q$. A connected bundle containing $q$ but not $c$ can only be $\{q\}$. Thus $D$ consumes no ordinary leaf.

These deductions correctly use nonnegativity of the mass variables and exact supply equalities.

Forced welfare value

Type $A$ must consume each ordinary leaf with mass $1/2$. Additivity then gives

$z_A=(W/2+1)-\frac12\sum_i a_i=1$.

This calculation is correct because every $A$-bundle contains $c$, omits $q$, and the total $A$-mass is $1$.

Extraction of a partition

Any positive-mass bundle assigned to $A$ has the form $\{c\}\cup\{\ell_i:i\in S\}$ and utility $z_A=1$. Therefore

$W/2+1-\sum_{i\in S}a_i=1$,

so $\sum_{i\in S}a_i=W/2$. Positive welfare therefore implies that the original PARTITION instance is positive.

Optimality gap and complexity conclusion

A yes-instance admits welfare $1$, and every positive-welfare assignment necessarily has welfare exactly $1$. A no-instance admits the promised welfare-$0$ assignment but admits no positive-welfare assignment. Hence the optimum is exactly $1$ in yes-instances and $0$ in no-instances.

An exact polynomial-time optimizer would therefore decide PARTITION by evaluating the returned assignment's welfare. The claimed NP-hardness follows.

Final adjudication

The proof fully resolves the stated target for the model as written. Its dependence on signed utilities is explicitly disclosed and is compatible with the absence of a nonnegativity assumption in the task.