d4-conf-ijcai-2022-0515 (d4-conf-ijcai-2022-0515)

Given \(m\) item categories, a finite set \(\mathcal T\) of buyer types with rational masses \(\mu_t\) summing to one, rational per-capita supplies \(q_j\), and a WHT-sparse value function \(\tilde v_t:\{0,1\}^m\to\mathbb R_{\ge 0}\) for each type, find an optimal allocation of type mass to integral bundles. Equivalently, maximize \(\sum_{t\in\mathcal T}\sum_{x\in\{0,1\}^m} z_{t,x}\tilde v_t(x)\), subject to \(\sum_x z_{t,x}=\mu_t\), \(\sum_{t,x}x_jz_{t,x}\le q_j\) for each category \(j\), and \(z_{t,x}\ge0\).

A society is given by its support: a list \(\mathcal T\) of \(\tau\ge1\) buyer types with positive binary-rational masses \(\mu_t\), summing to one. Here \(\tau\) is the support size, not the number of possible types.
There are \(m\ge1\) item categories with binary-rational per-capita supplies \(q_j\ge0\); each buyer receives an integral bundle \(x\in\{0,1\}^m\), including the empty bundle.
Each valuation is supplied explicitly by distinct frequencies \(S_t\subseteq\{0,1\}^m\) and nonzero signed binary-rational coefficients \(c_{t,y}\): \(\tilde v_t(x)=\sum_{y\in S_t}c_{t,y}(-1)^{\sum_{j=1}^m y_jx_j}\). These are normalized Walsh–Hadamard coefficients, and \(\tilde v_t(x)\ge0\) for every bundle is promised; neither monotonicity nor \(\tilde v_t(0)=0\) is required.
Let \(k=\max_t|S_t|\) and let \(L\) be the total binary input length. Type mass may be split arbitrarily among bundles.
Find an exact welfare-maximizing allocation, represented by its positive bundle masses, for \(\max_{z\ge0}\sum_{t\in\mathcal T}\sum_{x\in\{0,1\}^m}z_{t,x}\tilde v_t(x)\), subject to \(\sum_xz_{t,x}=\mu_t\) and \(\sum_{t,x}x_jz_{t,x}\le q_j\) for every category.

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

For finitely many buyers and one unit of each item, Fourier-sparse welfare maximization has an exact mixed-integer formulation; this establishes no polynomial-time bound ([source](https://arxiv.org/pdf/2009.10749)).
Related fractional configuration LPs are polynomial-time solvable with demand-oracle access ([source](https://theory.stanford.edu/~jvondrak/data/robust-welfare.pdf)); that access is not supplied here. No result settling this explicit-coefficient mass problem was located.

Result. The problem is NP-hard, even with \(\tau=1\), all supplies equal to \(\tfrac12\), and every nonconstant frequency supported on exactly two coordinates. The reduction below also satisfies \(\tilde v(0)=0\).

Taking all supplies equal to one would already embed unconstrained valuation maximization. We instead prove hardness with genuinely scarce supplies.

1. Source problem and construction. We reduce from unweighted Max-Cut: given a simple undirected graph \(G=(V,E)\) and an integer \(B\), decide whether some partition of \(V\) cuts at least \(B\) edges. This problem is NP-complete. [Garey, Johnson, and Stockmeyer, *Some simplified NP-complete graph problems*](https://www.math.ucdavis.edu/~deloera/MISC/LA-BIBLIO/trunk/JohnsonDavid2.pdf).

We may restrict to graphs with at least one edge, since edgeless instances are directly decidable. Label the vertices by \(V=\{1,\ldots,m\}\). Construct one buyer type of mass \(\mu=1\), and set \(q_j=\tfrac12\) for every category.

Write \(e_j\) for the binary vector with a single one in coordinate \(j\). Supply the following frequency list and coefficients:

• The zero frequency, with coefficient \(c_0=|E|/2\).
• For each edge \(\{u,v\}\in E\), the frequency \(e_u+e_v\), with coefficient \(c_{e_u+e_v}=-\tfrac12\).

Here \(e_u+e_v\) is a binary vector because the endpoints are distinct. Simplicity of the graph ensures that all listed frequencies are distinct. Every coefficient is nonzero, and the sparsity is \(k=|E|+1\).

The resulting valuation is exactly
\(\displaystyle \tilde v(x)=\frac{|E|}{2}-\frac12\sum_{\{u,v\}\in E}(-1)^{x_u+x_v}=\sum_{\{u,v\}\in E}\frac{1-(-1)^{x_u+x_v}}2.\)

For each edge, its summand is one when \(x_u\ne x_v\), and zero otherwise. Thus \(\tilde v(x)\) counts the edges crossing the partition encoded by \(x\). In particular, \(\tilde v(x)\ge0\) for every bundle, so the nonnegativity promise holds, and \(\tilde v(0)=0\).

This is precisely the stipulated Walsh–Hadamard character expansion; no additional normalization factor is needed.

2. The allocation optimum equals the maximum cut size. Define
\(\displaystyle C(G)=\max_{x\in\{0,1\}^m}\tilde v(x).\)

For our single type, write \(z_x\) for its bundle masses. Every feasible allocation satisfies \(z_x\ge0\) and \(\sum_xz_x=1\). Consequently,
\(\displaystyle \sum_xz_x\tilde v(x)\le\sum_xz_xC(G)=C(G).\)

This upper bound applies to every fractional allocation.

For the reverse bound, choose a maximum-cut vector \(x^\star\), and let \(\bar x^\star=\mathbf1-x^\star\) be its coordinatewise complement. Complementation preserves whether the endpoints of each edge differ, so
\(\tilde v(\bar x^\star)=\tilde v(x^\star)=C(G)\).

Allocate mass \(\tfrac12\) to each of \(x^\star\) and \(\bar x^\star\), and zero to every other bundle. These two bundles are distinct because \(m\ge1\). Their masses sum to one, and for every category \(j\), consumption is
\(\displaystyle \frac12x^\star_j+\frac12(1-x^\star_j)=\frac12=q_j.\)

Hence this allocation is feasible and has welfare \(C(G)\). Together with the upper bound, this proves
\(\operatorname{OPT}=C(G)\).

In particular, arbitrary splitting of buyer mass does not increase the optimum beyond the largest cut, and it permits that largest cut value despite the supply constraints.

3. Polynomial reduction and recovery from an allocation. The constructed instance has \(m=|V|\), \(\tau=1\), and \(k=|E|+1\). Each frequency uses \(m\) bits. All numerical inputs are integers or halves, and the constant coefficient requires \(O(\log(|E|+1))\) bits. Thus the total encoding length and construction time are polynomial in the graph input length.

Using threshold \(B\), the proved equality gives
\(\operatorname{OPT}\ge B\) if and only if \(G\) has a cut of size at least \(B\). Therefore even deciding whether the optimum reaches a given threshold is NP-hard.

The requested allocation output also reveals a maximum cut directly. For any optimal allocation,
\(\displaystyle 0=C(G)-\sum_xz_x\tilde v(x)=\sum_xz_x\bigl(C(G)-\tilde v(x)\bigr).\)

Each summand is nonnegative. Thus every bundle with positive mass satisfies \(\tilde v(x)=C(G)\). Since the masses sum to one, at least one such bundle exists. Reading any positive bundle from the returned list therefore yields a maximum cut.

A polynomial-time exact allocation algorithm would consequently solve Max-Cut in polynomial time. This argument does not depend on large output: the constructed instance always admits an optimal allocation with exactly two positive masses, both equal to \(\tfrac12\).

4. Relation to demand-oracle algorithms. For these valuations, a demand query at zero prices asks for a bundle maximizing \(\tilde v(x)\), which is exactly a maximum cut. Thus polynomial-time solvability with a supplied demand oracle does not give a polynomial-time algorithm from these explicit Fourier coefficients.

The target problem is therefore NP-hard; a polynomial-time exact algorithm in \(m,\tau,k,L\) would imply \(\mathrm P=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

The proof is correct and resolves the target: the continuous allocation problem is NP-hard under the stated explicit-coefficient representation. No major or minor mathematical issues were found.

• Source problem and restriction.

The prover states the relevant decision problem precisely: given a simple unweighted undirected graph and an integer threshold, determine whether a cut reaches that threshold. The cited NP-completeness result applies to this problem; the [original paper’s publisher record](https://doi.org/10.1016/0304-3975(76)90059-1) explicitly confirms NP-completeness of Simple Max Cut with unit edge weights.

Restricting to graphs with at least one edge is legitimate: the excluded edgeless instances are directly decidable. This restriction ensures that the constant Fourier coefficient is nonzero and that the constructed instance has at least one category.

• Validity of the constructed input.

Every requirement of USER_TASK is satisfied:

• There is exactly one supported type, with positive binary-rational mass \(\mu=1\).
• Every supply is the allowed binary rational \(\tfrac12\).
• Each edge frequency has exactly two nonzero coordinates because graph edges have distinct endpoints.
• Distinct edges yield distinct frequencies, and none equals the zero frequency.
• The constant coefficient \(|E|/2\) is positive; every edge coefficient is the nonzero binary rational \(-\tfrac12\).
• The frequency-list size is exactly \(k=|E|+1\).

The addition notation \(e_u+e_v\) is unambiguous here: the supports are disjoint, so ordinary coordinatewise addition produces a binary vector.

• Valuation identity and promises.

The displayed character expansion is exactly the representation prescribed by the task. Its coefficients need no further normalization factor.

For each edge, the exponent \(x_u+x_v\) is odd precisely when the endpoints lie on opposite sides of the cut. Consequently, the displayed summand is exactly its cut indicator. The valuation therefore equals the cut size for every bundle.

This verifies the nonnegativity promise on the entire bundle domain, including the empty bundle, and verifies the additional claim \(\tilde v(0)=0\). No monotonicity assumption is used.

• Upper bound for every feasible allocation.

The definition of \(C(G)\) is valid because the bundle domain is finite and nonempty.

For the single type, feasibility implies nonnegative masses summing to one. Since every bundle value is at most \(C(G)\), the welfare inequality
\[ \sum_x z_x\tilde v(x)\le C(G) \]
follows directly.

This bound applies to every allowed fractional allocation, regardless of its support size. No integrality assumption is introduced.

• Attainment under the scarce supplies.

A maximizing bundle exists by finiteness. Complementing all coordinates preserves each edge’s cut indicator, so its complement has the same value.

The two bundles are distinct because there is at least one coordinate. Giving each mass \(\tfrac12\) satisfies the type-mass equality. The prover’s coordinatewise consumption calculation is correct: every category receives total consumption exactly \(\tfrac12\), satisfying its supply constraint.

Both supported bundles have value \(C(G)\), so the constructed allocation attains the upper bound. Thus the equality \(\operatorname{OPT}=C(G)\) is fully established.

• Polynomial encoding and threshold reduction.

The construction explicitly lists \(|E|+1\) frequencies, each of length \(m\), together with polynomial-length numerical data. The constant coefficient requires only logarithmically many bits in \(|E|+1\). Under the ordinary explicit graph representation used by the source problem, both construction time and output length are polynomial.

The proved equality preserves the answer to the threshold question for every integer \(B\), including thresholds outside the possible cut-size range. Hence the decision hardness conclusion follows.

• Recovery from the requested allocation output.

For any optimal allocation, the prover expresses the difference from \(C(G)\) as a finite sum of nonnegative terms. A zero sum forces every term corresponding to positive mass to vanish. Therefore every listed positive-mass bundle encodes a maximum cut.

At least one such bundle exists because total mass is one. A polynomial-time algorithm returning the requested explicit allocation list would therefore provide a maximum cut in polynomial time. This recovery does not require computing or comparing the returned masses beyond their stipulated positivity.

The two-bundle allocation also verifies the stated compact-output claim. The proof does not assume that every optimal allocation has two bundles.

• Ancillary observations and scope.

The observation about supplies equal to one is correct: those constraints allow concentration of all mass on any bundle.

The demand-oracle observation is also correct: at zero prices, demand maximization for the constructed valuation is precisely maximum-cut optimization. It explains why oracle-based algorithms do not supply the missing algorithm for the explicit representation.

The conclusion establishes NP-hardness, without claiming NP-completeness or unconditional exclusion of polynomial-time algorithms. Its qualification concerning \(\mathrm P=\mathrm{NP}\) is correct.

Required repairs: None. The construction, optimum equality, and allocation-recovery argument are all verifiable as written.

⟨structured verdict parsed — rendered above⟩