d4-conf-sagt-2015-0015 (d4-conf-sagt-2015-0015)

Given goods \(G=[m]\), finitely many additive types \(T\) with rational masses \(\mu_t\ge 0\) summing to \(1\), values \(v_{tj}\), per-capita supplies \(q_j\), and fixed nonnegative rational prices \(p_j\), does there exist a mass allocation \(y_{t,S}\ge 0\) over integral bundles \(S\subseteq G\) such that \(\sum_{S\subseteq G}y_{t,S}=\mu_t\) for each \(t\); every bundle with \(y_{t,S}>0\) spends exactly the unit budget and maximizes \(\sum_{j\in S}v_{tj}\) among bundles with price at most \(1\); and total use of each good is at most \(q_j\), with equality whenever \(p_j>0\)?

Let \(G=\{1,\ldots,m\}\), with \(m\ge1\). A society is given by its support: the list of the \(\tau\ge1\) additive types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
The input also specifies binary rational values \(v_{tj}\ge0\), per-capita supplies \(q_j\ge0\), and fixed prices \(p_j\ge0\). Each individual has budget \(1\) and may consume any integral bundle \(S\subseteq G\), containing at most one unit of each good. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
A mass allocation consists of real numbers \(y_{t,S}\ge0\) satisfying \(\sum_{S\subseteq G}y_{t,S}=\mu_t\) for every type.
Whenever \(y_{t,S}>0\), require \(\sum_{j\in S}p_j=1\) and \(S\in\operatorname*{arg\,max}_{R\subseteq G:\,\sum_{j\in R}p_j\le1}\sum_{j\in R}v_{tj}\). All utility ties are permitted; alternatives are evaluated without aggregate supply restrictions.
For every good require \(\sum_t\sum_{S\ni j}y_{t,S}\le q_j\), with equality whenever \(p_j>0\).

Is deciding whether such a mass allocation exists in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?

For a finite list of buyers and one unit of each good, existence of an equilibrium allocation at fixed prices is \(\mathrm{coNP}\)-hard, even with two additive buyers ([source](https://arxiv.org/pdf/1503.06855v2)).
With prices also unspecified, discrete additive equilibrium computation is strongly \(\mathrm{NP}\)-hard ([source](https://arxiv.org/pdf/1501.06627)). No result settling the exact mass-allocation problem above was located.

Result

The problem is \(\mathrm{NP}\)-hard under polynomial-time many-one reductions, even when \(\tau=1\), all prices, values, and supplies are strictly positive dyadic rationals, and an optimal bundle costing exactly \(1\) always exists.

The proof directly addresses mass allocations, including arbitrary splitting of type mass.

1. Source problem and padding

We reduce from the \(\mathrm{NP}\)-complete problem PARTITION: given positive binary integers \(a_1,\ldots,a_n\), decide whether some \(I\subseteq\{1,\ldots,n\}\) satisfies
\[ 2\sum_{i\in I}a_i=\sum_{i=1}^n a_i. \]
This is a standard \(\mathrm{NP}\)-complete problem from [Karp’s reduction theorem](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).

Write \(A=\sum_{i=1}^n a_i\), and let \(D\) be the smallest power of two strictly larger than \(2A\). Define \(n+2\) positive integers by
\[ b_i=2a_i\quad(1\le i\le n),\qquad b_{n+1}=b_{n+2}=D-A. \]
Their sum is \(2D\).

Padding lemma. There is a subset \(T\subseteq\{1,\ldots,n+2\}\) with \(\sum_{j\in T}b_j=D\) if and only if the original PARTITION instance is a yes-instance.

To prove this, observe that the first \(n\) integers sum to \(2A<D\), while each padding integer \(D-A\) exceeds \(D/2\). A subset summing to \(D\) must therefore contain exactly one padding integer. Its remaining indices form a set \(I\subseteq\{1,\ldots,n\}\) satisfying
\[ 2\sum_{i\in I}a_i=D-(D-A)=A. \]
Conversely, any such \(I\), together with one padding index, gives a subset summing to \(D\).

2. Construction of the society

There is one type, with mass \(\mu_1=1\). Set \(m=n+3\). The first \(n+2\) goods correspond to the padded integers; the last good, denoted \(h\), is an additional good.

For every padded good \(j\), set
\[ p_j=v_{1j}=\frac{b_j}{D},\qquad q_j=\frac14. \]
For the additional good, set
\[ p_h=v_{1h}=1,\qquad q_h=\frac12. \]

Every price, value, and supply is strictly positive. Because \(D\) is a power of two, every number used is dyadic. Moreover,
\[ \sum_{j=1}^{n+2}p_j=2,\qquad \sum_{j\in G}p_jq_j=\frac14\cdot2+\frac12=1. \]
Thus the supplies satisfy the necessary aggregate expenditure identity.

For every bundle \(R\), utility equals expenditure:
\[ \sum_{j\in R}v_{1j}=\sum_{j\in R}p_j. \]
Every affordable bundle consequently has utility at most \(1\), and the bundle \(\{h\}\) attains utility \(1\). Hence the optimal utility is always \(1\), and a bundle is optimal exactly when its price is \(1\).

Since every other price is strictly positive, the only affordable bundle containing \(h\) is \(\{h\}\).

3. A partition gives a mass allocation

Suppose the original PARTITION instance is a yes-instance. By the padding lemma, choose \(T\subseteq\{1,\ldots,n+2\}\) with price \(1\).

Let \(T^c=\{1,\ldots,n+2\}\setminus T\). Since the padded goods have total price \(2\), the complement \(T^c\) also has price \(1\).

Define the allocation by
\[ y_{1,\{h\}}=\frac12,\qquad y_{1,T}=\frac14,\qquad y_{1,T^c}=\frac14, \]
and assign zero mass to every other bundle.

These masses sum to \(1\). All three bundles cost exactly \(1\) and attain optimal utility \(1\).

The consumption of \(h\) is \(1/2=q_h\). Each padded good lies in exactly one of \(T\) and \(T^c\), so its consumption is \(1/4=q_j\). Every supply constraint therefore holds with equality, as required because all prices are positive.

4. A mass allocation gives a partition

Conversely, suppose a feasible mass allocation exists.

Because \(p_h>0\), its supply constraint requires
\[ \sum_{S\ni h}y_{1,S}=\frac12. \]
Any bundle assigned positive mass must cost exactly \(1\). The only such bundle containing \(h\) is \(\{h\}\), so
\[ y_{1,\{h\}}=\frac12. \]
The type has total mass \(1\); therefore the total mass assigned to bundles avoiding \(h\) is \(1/2\).

There are finitely many bundles. Consequently, at least one bundle \(T\subseteq\{1,\ldots,n+2\}\) avoiding \(h\) receives positive mass. The budget-exhaustion requirement implies
\[ \sum_{j\in T}p_j=1, \]
or equivalently \(\sum_{j\in T}b_j=D\). The padding lemma now gives a partition of the original integers.

This argument permits arbitrary real allocation masses; no integrality assumption on those masses is used.

5. Encoding size and running times

If the PARTITION input has bit length \(N\), then \(\log D=O(N)\). The constructed instance has \(m=n+3\), \(\tau=1\), and total bit length
\[ L=O\bigl(m(1+\log A)\bigr)=O(N^2). \]
Computing and writing the construction takes polynomial time, with a conservative bound \(O(mL)\) bit operations.

For completeness, the general problem admits an exact algorithm in
\[ 2^{O(m)}\operatorname{poly}(m,\tau,L) \]
time. Enumerate all \(2^m\) bundles, compute each type’s optimal affordable utility using exact rational arithmetic, and retain precisely its optimal bundles costing \(1\). Feasibility is then a rational linear program with at most \(\tau2^m\) variables and \(\tau+m\) type-mass and supply constraints, together with nonnegativity. Its coefficients have polynomial bit length, so polynomial-time rational linear programming gives the stated bound.

The reduction proves the requested \(\mathrm{NP}\)-hardness. In particular, a polynomial-time algorithm in \(m,\tau,L\), even restricted to \(\tau=1\), would imply \(\mathrm{P}=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

The output resolves the task correctly. The reduction establishes \(\mathrm{NP}\)-hardness for the exact mass-allocation problem, including arbitrary real splitting of type mass. I found no major or minor mathematical issues.

• Source problem and padding. The stated source is binary-encoded PARTITION on positive integers, a standard \(\mathrm{NP}\)-complete problem. The encoding restriction matters: the corresponding unary problem admits a polynomial-time algorithm. The cited source is appropriate; the integer problem’s classification is also confirmed in [Wojtczak’s discussion of the classical problems](https://arxiv.org/html/1802.09465).

Since the integers are positive, \(A>0\). The choice of \(D\) gives \(2A<D\), so \(D-A>D/2>0\). The padded sum is correctly computed as \(2A+2(D-A)=2D\).

A subset of padded integers totaling \(D\) cannot contain zero padding integers, because the original entries total less than \(D\). It cannot contain both padding integers, because their sum exceeds \(D\). Thus it contains exactly one, and the remaining entries total \(A\), precisely the stated PARTITION condition. The converse follows directly from the same equality. The lemma also handles odd \(A\): its required equality then cannot hold.

• Validity of the constructed input. The construction has \(m=n+3\) and exactly one positive-mass type, with mass \(1\). All prices, values, and supplies are strictly positive dyadic rationals. Hence it satisfies every input restriction in USER_TASK.

Both expenditure calculations are correct: the padded prices total \(2\), and the price-weighted supplies total \(1\). This identity is presented as a consistency check, not used as a sufficient condition for feasibility.

• Characterization of optimal bundles. Because values equal prices coordinatewise, utility equals expenditure for every bundle. Every affordable bundle therefore has utility at most \(1\), while \(\{h\}\) achieves \(1\). Among affordable bundles, optimality is consequently equivalent to costing exactly \(1\).

The statement that “a bundle is optimal exactly when its price is \(1\)” is valid: a bundle costing \(1\) is automatically affordable, and no unaffordable bundle belongs to the specified argmax.

Strict positivity of every other price ensures that any bundle containing \(h\) and another good costs more than \(1\). Thus \(\{h\}\) is the unique affordable bundle containing \(h\). Aggregate supplies play no role in this utility comparison, as required.

• Forward implication. A padded subset \(T\) of price \(1\) has complement \(T^c\) of price \(1\), since the padded total is \(2\). Both are nonempty and distinct, and neither contains \(h\); consequently, the three assigned allocation coordinates do not conflict.

The proposed masses total \(1\). Each occupied bundle is affordable, budget-exhausting, and utility-maximizing. Good \(h\) receives consumption \(1/2\); each padded good receives consumption \(1/4\), because it belongs to exactly one of \(T\) and \(T^c\). Every positive-price supply equality holds.

• Reverse implication and real mass splitting. The positive price of \(h\) requires consumption exactly \(1/2\). Every positive-mass bundle containing \(h\) must be \(\{h\}\), so its assigned mass is exactly \(1/2\).

Mass conservation leaves exactly \(1/2\) on bundles avoiding \(h\). There are finitely many such bundles, and all assigned masses are nonnegative; therefore at least one receives positive mass. Its price must equal \(1\), giving a padded subset totaling \(D\). The padding lemma then yields a source partition.

This reasoning uses neither integrality nor rationality of allocation masses. Arbitrary real splitting cannot circumvent the required subset.

• Encoding and construction time. Minimality of the chosen power of two gives \(D\le4A\), so its binary length is \(O(1+\log A)\). Every constructed numerator and denominator has this order of bit length. The bounds \(L=O(m(1+\log A))=O(N^2)\) are valid.

Summation, power-of-two selection, subtraction, and writing the rational entries all take polynomial bit time. The stated conservative \(O(mL)\) construction bound is consistent with these operations.

• General exact algorithm. Enumerating all bundles and computing affordable utility maxima exactly is valid. The empty bundle guarantees that each type’s affordable set is nonempty. Retaining precisely the optimal bundles costing \(1\) implements both individual requirements.

The remaining allocation conditions form a finite rational linear feasibility problem with at most \(\tau2^m\) variables. Its coefficients and right-hand sides have polynomial bit length. The invoked theorem—feasibility of an explicitly encoded rational linear system is decidable in polynomial bit time—applies; see [Nemirovski’s treatment of linear-programming feasibility](https://www2.isye.gatech.edu/~nemirovs/Lec_EMCO.pdf). Polynomial time in the expanded system size yields the claimed \(2^{O(m)}\operatorname{poly}(m,\tau,L)\) bound.

No repair or additional clarification is needed. The proof establishes the claimed restricted hardness and does not overclaim membership in \(\mathrm{NP}\) or strong \(\mathrm{NP}\)-hardness.

⟨structured verdict parsed — rendered above⟩