To Give or Not to Give: Fair Division for Single Minded Valuations (d4-conf-ijcai-2016-0484)

Given rational divisible-good supplies \(q_j\), finitely many demand types \(T\) with masses \(\mu_t\), demand vectors \(v_t\), and unit budgets, choose common prices \(p\) and a probability measure \(\lambda_t\) over bundles for each type such that every supported bundle is utility-maximizing under the explicitly fixed CEEI convention, each supported bundle exhausts its budget, \(\sum_t \mu_t\int z_j\,d\lambda_t(z)=q_j\) for every good, and the mass-weighted welfare \(\sum_t\mu_t\int u_t(z)\,d\lambda_t(z)\) is maximized; decide whether it reaches a given threshold.

There are \(m\geq1\) divisible goods with positive rational supplies \(q_j\). A society is given by its support: a list \(T\) of \(\tau\geq1\) distinct demand types with positive binary rational masses \(\mu_t\); \(\tau\) counts listed types, not possible types. Total mass \(M=\sum_t\mu_t\) is unrestricted, rather than normalized to one.
Each type has a rational demand vector \(v_t\in B=\prod_{j=1}^m[0,q_j]\) and utility \(u_t(z)=1\) when \(z_j\geq v_{t,j}\) for every good, and \(u_t(z)=0\) otherwise. Every individual has budget \(1\).
A CEEI consists of common prices \(p\in\mathbb R_{\geq0}^m\) and a Borel probability measure \(\lambda_t\) on \(B\) for each type. Every \(z\in\operatorname{supp}(\lambda_t)\) must satisfy \(p\cdot z=1\) and \(u_t(z)=\max\{u_t(y):y\in B,\ p\cdot y\leq1\}\); any utility-maximizing bundle is allowed, with no further tie-breaking.
All goods must clear exactly: \(\sum_t\mu_t\int_B z_j\,d\lambda_t(z)=q_j\) for every good. Welfare is \(W=\sum_t\mu_t\int_B u_t(z)\,d\lambda_t(z)\). The input includes a binary rational threshold \(0<K\leq M\); \(L\) is the total binary input length.

Is deciding whether a CEEI with \(W\geq K\) exists solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?

For finitely many agents and unit supplies, welfare-maximizing CEEI with these single-minded utilities is NP-hard. Welfare-maximizing CAEI, which allows unspent budgets, is polynomial-time solvable for a fixed number of demand types ([Brânzei–Lv–Mehta](https://www.ijcai.org/Proceedings/16/Papers/025.pdf)).
No result settling the precise mass-model decision problem above was located in the literature search.

Result

The decision problem is \(\mathrm{NP\text{-}hard}\), even when every supply and every type mass equals \(1\), and every demand coordinate belongs to \(\{0,1\}\).

The proof below verifies full expenditure, exact clearing, and the treatment of probability measures directly.

1. Affordability determines satisfaction

Fix nonnegative prices \(p\). A type \(t\) can obtain utility \(1\) within its budget if and only if
\[ p\cdot v_t\leq 1. \]
Indeed, if this inequality holds, the bundle \(v_t\in B\) is affordable and satisfies its demand. Conversely, any satisfying bundle \(y\) has \(y\geq v_t\) coordinatewise, so nonnegative prices imply \(p\cdot y\geq p\cdot v_t\).

Consequently, in any CEEI, every bundle in the support of \(\lambda_t\) has utility
\[ u_t(z)= \begin{cases} 1,&p\cdot v_t\leq 1,\\ 0,&p\cdot v_t>1. \end{cases} \]
A Borel probability measure on the compact Euclidean box \(B\) gives its support probability \(1\). Therefore, writing
\[ H(p)=\{t:p\cdot v_t\leq 1\}, \]
we obtain
\[ W=\sum_{t\in H(p)}\mu_t. \]
In particular, randomization cannot satisfy only a fraction of a type.

For completeness, randomization can also be eliminated entirely. Define the mean bundle
\[ x_t=\int_B z\,d\lambda_t(z). \]
Because \(B\) is a box, \(x_t\in B\), and full expenditure gives \(p\cdot x_t=1\). If \(t\in H(p)\), every supported bundle dominates \(v_t\), hence \(x_t\geq v_t\). If \(t\notin H(p)\), no affordable bundle can satisfy its demand, so \(u_t(x_t)=0\). Replacing \(\lambda_t\) by the Dirac measure \(\delta_{x_t}\) therefore preserves individual optimality, full expenditure, clearing, and welfare.

2. The reduction

We reduce from Set Packing: given explicitly listed subsets \(C_1,\ldots,C_n\) of a finite universe \(U\) and an integer \(1\leq k\leq n\), decide whether at least \(k\) of these sets are pairwise disjoint. This is the standard NP-complete source problem also used in the finite-agent hardness argument of [Brânzei–Lv–Mehta, Theorem 2](https://arxiv.org/pdf/1602.09088).

We may require every \(C_i\) to be nonempty. To enforce this restriction, append to each set its own fresh element, appearing in no other set. This preserves every pairwise intersection and therefore preserves the answer.

Relabel the universe as \(U=\{1,\ldots,r\}\), discarding elements appearing in no set. Construct the following market:

• There are \(m=r+n\) goods, each with supply \(q_j=1\).
• There are \(\tau=n\) types, each with mass \(\mu_i=1\).
• Type \(i\) demands one unit of every good in \(C_i\), and one unit of its private good \(r+i\):

\[ v_{i,j}= \begin{cases} 1,&j\in C_i\ \text{or}\ j=r+i,\\ 0,&\text{otherwise}. \end{cases} \]

• Set the welfare threshold to \(K=k\).

The demand vectors are distinct because each type demands its own private good. All demands lie in \(B=[0,1]^{r+n}\), and \(0<K\leq M=n\).

The construction has polynomial size: it writes \(n(r+n)\) binary demand coordinates, unit supplies and masses, and the binary integer \(k\).

3. A high-welfare CEEI yields a packing

Suppose the constructed market has a CEEI with \(W\geq k\). By Section 1 and the unit masses, its satisfied set \(H\) has
\[ |H|=W\geq k. \]

Take distinct \(i,h\in H\). If \(C_i\cap C_h\) contained an element \(j\), both types would require one unit of good \(j\). Every supported bundle of either type would therefore have coordinate \(j\) equal to \(1\), since the coordinate is bounded above by \(q_j=1\).

Their combined consumption of this good would consequently be
\[ \mu_i\int_B z_j\,d\lambda_i(z) +\mu_h\int_B z_j\,d\lambda_h(z)=2. \]
All other consumption is nonnegative, contradicting exact clearing at supply \(1\).

Thus the sets indexed by \(H\) are pairwise disjoint. They form a packing of size at least \(k\).

4. A packing yields a fully spending CEEI

Suppose there is a packing of size at least \(k\). Extend it to an inclusion-maximal packing, and let \(S\subseteq\{1,\ldots,n\}\) be its index set. Then \(|S|\geq k\).

Maximality implies that every \(i\notin S\) intersects a selected set:
\[ C_i\cap\bigcup_{h\in S}C_h\neq\varnothing. \]
Otherwise \(C_i\) could be added to the packing.

Prices

For an original good \(j\in U\), set
\[ p_j= \begin{cases} 1/|C_h|,&j\in C_h\text{ for some }h\in S,\\ 0,&j\notin\displaystyle\bigcup_{h\in S}C_h. \end{cases} \]
This is well-defined because the selected sets are pairwise disjoint and nonempty.

For private goods, set
\[ p_{r+i}= \begin{cases} 0,&i\in S,\\ 1,&i\notin S. \end{cases} \]

Every selected type \(h\in S\) has demand cost exactly
\[ p\cdot v_h=\sum_{j\in C_h}\frac{1}{|C_h|}=1. \]

Every excluded type \(i\notin S\) has demand cost
\[ p\cdot v_i=1+\sum_{j\in C_i}p_j>1. \]
The strict inequality follows because maximality gives an element of \(C_i\) belonging to a selected set, and that element has strictly positive price.

Allocation

Give each type its entire private good. Give each selected type \(h\in S\) all original goods in \(C_h\). Give every remaining original good to any one type.

These assignments produce bundles \(z_i\in[0,1]^{r+n}\). Every good is assigned exactly once, so setting \(\lambda_i=\delta_{z_i}\) clears every good exactly.

Every remaining original good has price zero. Therefore:

• A selected type spends exactly \(1\) on its original demanded goods and receives its private good for free.
• An excluded type spends exactly \(1\) on its private good.

Selected types receive their complete demands and hence maximize utility at \(1\). Excluded types cannot afford their complete demands, so their maximum attainable utility is \(0\); their allocated bundles are consequently utility-maximizing. Any additional free goods are permitted by the stated absence of tie-breaking.

Thus these prices and Dirac measures constitute a CEEI satisfying every required condition. Its welfare is
\[ W=|S|\geq k. \]

5. Conclusion

The polynomial construction satisfies
\[ \text{the Set Packing instance has a packing of size at least }k \quad\Longleftrightarrow\quad \text{the constructed market has a CEEI with }W\geq K. \]

Hence the precise mass-model decision problem is \(\mathrm{NP\text{-}hard}\). A polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\). This settles the requested hardness alternative; no assumption about restricted tie-breaking or unspent budgets is used.

⟨structured verdict parsed — rendered above⟩

The prover’s claim is proved. The reduction establishes \(\mathrm{NP\text{-}hardness}\) for the precise mass-model decision problem, including full expenditure, exact clearing, and the permitted probability measures. I found no major or minor mathematical issues.

1. Affordability and welfare

The equivalence between attainable utility \(1\) and \(p\cdot v_t\leq1\) is correct:

• If \(p\cdot v_t\leq1\), the demand vector itself belongs to \(B\) and is affordable.
• If a bundle satisfies the demand, it dominates \(v_t\) coordinatewise. Nonnegative prices therefore make its cost at least \(p\cdot v_t\).

The distinction at equality is handled correctly: a demand costing exactly \(1\) is affordable.

The CEEI optimality condition consequently forces every supported bundle of a type to have the same utility. The stated fact that a Borel probability measure on the compact Euclidean box gives its support probability \(1\) applies here. Thus the welfare identity
\[ W=\sum_{t\in H(p)}\mu_t \]
is justified. In particular, a type cannot be partially satisfied through randomization.

2. Elimination of randomization

Each coordinate is bounded and Borel measurable, so the mean bundle is well-defined and belongs to \(B\). Linearity of integration preserves expenditure and clearing.

For affordable types, supported bundles dominate the demand, and their means do as well. For unaffordable types, the mean has expenditure exactly \(1\), so it cannot satisfy a demand costing strictly more than \(1\). Its utility is therefore the attainable maximum, namely \(0\).

Replacing each measure by the Dirac measure at its mean preserves every required condition. This argument is valid for arbitrary positive rational masses, although the reduction subsequently uses unit masses.

3. Source problem and preprocessing

The source problem is stated precisely: an explicitly listed collection of finite sets and a threshold \(1\leq k\leq n\), asking for at least \(k\) pairwise disjoint sets. The cited paper’s Theorem 2 uses this same NP-complete Set Packing problem. [Brânzei–Lv–Mehta, Theorem 2](https://arxiv.org/pdf/1602.09088)

Adding a different fresh element to each set preserves intersections between distinct indexed sets. Consequently, it preserves every feasible packing while ensuring nonempty sets. Discarding unused universe elements also preserves the answer.

The prover supplies its own equilibrium construction; the mass-model conclusion does not depend on importing the cited finite-agent equilibrium proof.

4. Construction and input validity

All constructed inputs satisfy the task’s restrictions:

• Supplies and masses equal \(1\), hence are positive rationals.
• Demand coordinates belong to \(\{0,1\}\) and lie within the supply box.
• Private goods distinguish all listed demand vectors, so there are exactly \(n\) distinct types.
• Total mass is \(M=n\), and the threshold satisfies \(0<K=k\leq M\).

After unused elements are discarded, the universe size is bounded by the explicit set-list encoding size. Adding fresh elements increases it by at most \(n\). Writing the stated \(n(r+n)\) demand coordinates therefore takes polynomial space and time.

5. Equilibrium implies a packing

Unit masses and the welfare identity give \(W=|H|\).

If two satisfied types share an original demanded good, every supported bundle of both types has coordinate exactly \(1\): satisfaction requires at least \(1\), and the box permits at most \(1\). Their combined consumption is therefore \(2\).

Since all remaining consumption is nonnegative, exact clearing at supply \(1\) is impossible. Thus satisfied types correspond to pairwise disjoint sets, and welfare at least \(k\) yields the required packing.

This direction applies to arbitrary admissible probability measures, not merely deterministic allocations.

6. Packing implies an equilibrium

Extending the given packing to an inclusion-maximal packing preserves its size lower bound. Maximality gives exactly the intersection property used for every excluded type.

The price construction is well-defined because selected sets are nonempty and pairwise disjoint. Selected demands cost exactly \(1\). Each excluded demand includes its private good costing \(1\) and at least one original good with strictly positive price, so its demand costs strictly more than \(1\).

The allocation assigns every good exactly once. Because masses equal \(1\), this gives exact clearing. Each resulting bundle belongs to the box.

Every unassigned original good has price zero. Hence assigning these remaining goods arbitrarily preserves expenditure:

• Selected types spend exactly \(1\) on their original demanded goods.
• Excluded types spend exactly \(1\) on their private goods.

Selected types receive their complete demands. Excluded types cannot attain utility \(1\) within budget, so their allocated bundles maximize utility at \(0\). The task expressly permits the additional free goods.

The construction also covers the boundary cases \(n=1\) and \(S=\{1,\ldots,n\}\). Nonemptiness prevents zero denominators, and there is always a type to receive remaining goods.

7. Conclusion and required feedback

Both directions of the polynomial reduction are established. The claimed hardness restriction is valid, and the argument settles the requested hardness alternative. It does not claim NP membership or NP-completeness.

No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩