d4-conf-ijcai-2017-0763 (d4-conf-ijcai-2017-0763)

Given a finite-support distribution \(\mu\) over responder types \(t=(w_t,P_t)\), where \(w_t\) is a resource capacity and \(P_t\) is that type’s finite menu of offers \((q_{tj},\pi_{tj})\), compute an aggregate response plan maximizing total payoff. For each type, feasible response sets are \(\mathcal F_t=\{S\subseteq P_t:\sum_{j\in S}q_{tj}\le w_t\}\). Choose \(\lambda_{t,S}\ge0\) with \(\sum_{S\in\mathcal F_t}\lambda_{t,S}=\mu_t\) to maximize \(\sum_t\sum_{S\in\mathcal F_t}\lambda_{t,S}\sum_{j\in S}\pi_{tj}\).

A society is given by its support: a list of \(\tau\) responder types with positive masses \(\mu_t\) given as binary rationals and satisfying \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type has a positive integer capacity \(w_t\) and a nonempty, explicitly listed menu \(P_t\) of individually indexed offers. Offer \(j\) requires a positive integer resource quantity \(q_{tj}\) and yields a positive rational payoff \(\pi_{tj}\); all numbers are binary encoded. Distinct offers may have identical quantities and payoffs.
Define \(\mathcal F_t=\{S\subseteq P_t:\sum_{j\in S}q_{tj}\le w_t\}\), including the empty set. A response plan assigns real masses \(\lambda_{t,S}\ge0\) satisfying \(\sum_{S\in\mathcal F_t}\lambda_{t,S}=\mu_t\). Its total payoff is \(\sum_t\sum_{S\in\mathcal F_t}\lambda_{t,S}\sum_{j\in S}\pi_{tj}\). Each selected offer is accepted in full by the mass assigned to that set; capacities apply separately to each set.
Let \(m=\sum_t|P_t|\), and let \(L\) be the total input bit length, including a nonnegative rational payoff threshold \(B\). State running times in \(m,\tau,L\).

Is deciding whether a feasible aggregate response plan has total payoff at least \(B\) solvable in polynomial time, or is it NP-hard?

For a single discrete responder, computing an optimal accepted subset is NP-hard; a pseudopolynomial knapsack algorithm is also available (Mamakos and Chalkiadakis, 2017). These discrete results do not establish a complexity classification for the distribution problem stated here.

Classification. The decision problem is \(\mathrm{NP}\)-complete, even with exactly two types of mass \(\frac12\) each and integer offer payoffs. Consequently, a polynomial-time algorithm in \((m,\tau,L)\) exists if and only if \(\mathrm{P}=\mathrm{NP}\).

1. Proven structural lemma: splitting mass does not improve the optimum.

For every type \(t\), define its subset payoff and maximum feasible payoff by

\(v_t(S)=\sum_{j\in S}\pi_{tj}\), and \(K_t=\max_{S\in\mathcal F_t}v_t(S)\).

The maximum exists because \(\mathcal F_t\) is finite and contains the empty set.

For any feasible response plan, nonnegativity of the assigned masses gives

\(\sum_{S\in\mathcal F_t}\lambda_{t,S}v_t(S)\le K_t\sum_{S\in\mathcal F_t}\lambda_{t,S}=\mu_tK_t\).

Summing over types proves that every feasible plan has total payoff at most \(\sum_{t=1}^{\tau}\mu_tK_t\).

Conversely, choose a maximizing subset \(S_t^*\in\mathcal F_t\) for every type. Assign \(\lambda_{t,S_t^*}=\mu_t\) and assign zero mass to its other subsets. This plan satisfies every mass constraint and attains the upper bound. Thus

\(\operatorname{OPT}=\sum_{t=1}^{\tau}\mu_tK_t\).

This equality holds for arbitrary support size. It uses the stated condition that capacities apply separately to each selected set and that there are no constraints coupling different types.

2. Proven hardness: a reduction with two positive-mass types.

We use the standard \(\mathrm{NP}\)-complete SUBSET SUM problem: given binary-encoded positive integers \(a_1,\ldots,a_n\) and a positive integer \(T\), decide whether some indexed subset has sum exactly \(T\). This is the classical equality version of knapsack; see [Karp, *Reducibility Among Combinatorial Problems*](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).

Construct the following society:

• Type \(1\) has mass \(\mu_1=\frac12\), capacity \(w_1=T\), and \(n\) individually indexed offers with \(q_{1j}=\pi_{1j}=a_j\).
• Type \(2\) has mass \(\mu_2=\frac12\), capacity \(w_2=1\), and one offer with quantity and payoff both equal to \(1\).
• Set \(B=\frac{T+1}{2}\).

All quantities and capacities are positive integers; both menus are nonempty; all payoffs are positive; and the masses sum to one. Repeated input integers remain distinct indexed offers. The construction has \(m=n+1\), \(\tau=2\), and output bit length linear in the source bit length, so it is a polynomial-time reduction.

For type \(1\),

\(K_1=\max\left\{\sum_{j\in S}a_j:S\subseteq\{1,\ldots,n\},\ \sum_{j\in S}a_j\le T\right\}\le T\).

For type \(2\), accepting its single offer is feasible, so \(K_2=1\). By the structural lemma,

\(\operatorname{OPT}=\frac{K_1+1}{2}\).

Therefore,

\(\operatorname{OPT}\ge B\iff K_1\ge T\iff K_1=T\).

Because the maximum defining \(K_1\) is attained, the last equality holds exactly when the original SUBSET SUM instance has a subset summing to \(T\). This proves \(\mathrm{NP}\)-hardness for the distribution problem itself.

3. Proven membership in \(\mathrm{NP}\), including exact arithmetic.

A certificate consists of one subset \(S_t\subseteq P_t\) for each type, encoded by one membership bit per offer. Its length is \(m\) bits. The verifier checks

\(\sum_{j\in S_t}q_{tj}\le w_t\) for every type, and \(\sum_{t=1}^{\tau}\mu_t\sum_{j\in S_t}\pi_{tj}\ge B\).

If these checks pass, assigning all of type \(t\)'s mass to \(S_t\) gives a qualifying plan. Conversely, if any qualifying plan exists, the structural lemma supplies qualifying maximizing subsets. Hence these certificates characterize exactly the yes-instances.

To justify polynomial-time verification with rational inputs, let \(D\) be the product of the encoded denominators of all masses, payoffs, and \(B\). Their total bit length is at most \(L\), so \(D\) has \(O(L)\) bits. Define integers

\(u_t=D\mu_t,\qquad p_{tj}=D\pi_{tj},\qquad b=DB\).

The payoff comparison becomes the integer comparison

\(\sum_{t=1}^{\tau}u_t\sum_{j\in S_t}p_{tj}\ge bD\).

All integers involved have \(O(L)\) bits: multiplication and summation increase bit lengths only by a constant factor and an additive \(O(\log m+\log\tau)\). Using schoolbook integer arithmetic, constructing the scaled integers and checking the certificate takes \(O((m+\tau)L^2)\) bit operations. Thus the problem belongs to \(\mathrm{NP}\).

Together with the reduction, this proves \(\mathrm{NP}\)-completeness.

4. Exact algorithmic bounds.

Write \(n_t=|P_t|\), so \(\sum_t n_t=m\). After the rational scaling above, enumerating all subsets separately for each type computes every \(K_t\) in

\(O\left((m+\tau)L^2+L\sum_{t=1}^{\tau}n_t2^{n_t}\right)\)

bit operations. Since every menu is nonempty, \(n_t\le m-\tau+1\); therefore this is at most

\(O\left((m+\tau)L^2+m\,2^{m-\tau+1}L\right)\).

A capacity-based dynamic program also applies independently to each type. For a fixed type, let \(A_i(c)\) be the maximum scaled payoff obtainable from its first \(i\) offers with total quantity at most \(c\). Initialize \(A_0(c)=0\). For offer \(i\), use \(A_i(c)=A_{i-1}(c)\) when \(q_{ti}>c\); otherwise use

\(A_i(c)=\max\{A_{i-1}(c),\,A_{i-1}(c-q_{ti})+p_{ti}\}\).

The two alternatives exhaust subsets that exclude or include offer \(i\), respectively, which proves the recurrence. Its terminal value is \(DK_t=A_{n_t}(w_t)\). Computing all types and comparing their weighted sum with \(B\) takes

\(O\left((m+\tau)L^2+L\sum_{t=1}^{\tau}n_t(w_t+1)\right)\)

bit operations. Since binary encoding permits capacities exponential in \(L\), this is pseudopolynomial, with the general bound \(O((m+\tau)L^2+m2^LL)\). It does not imply polynomial time in the input bit length.

⟨structured verdict parsed — rendered above⟩

The proof resolves the task correctly. It establishes \(\mathrm{NP}\)-completeness for the stated distribution problem, including the restriction to exactly two positive-mass types. The structural argument, reduction, certificate verification, and algorithmic bounds are sound. No repair is required.

• Structural lemma

Each \(\mathcal F_t\) is finite and nonempty, so its maximum payoff \(K_t\) exists and is attained. For every feasible plan, the inequality
\[ \sum_{S\in\mathcal F_t}\lambda_{t,S}v_t(S)\le \mu_tK_t \]
follows directly from \(v_t(S)\le K_t\), nonnegative masses, and the type’s mass constraint.

The proposed attaining plan is feasible: it places exactly \(\mu_t\) on one feasible maximizing subset for each type. There are no constraints coupling the choices across types. Consequently, the stated equality \(\operatorname{OPT}=\sum_t\mu_tK_t\) is valid.

This argument handles real-valued response masses directly; it does not assume that arbitrary feasible plans have rational descriptions.

• Hardness reduction

The invoked source problem is precisely the positive-integer, binary-encoded equality version of SUBSET SUM. Its \(\mathrm{NP}\)-completeness is standard, including the positivity restriction; see the [SUBSET SUM theorem in these university lecture notes](https://iccl.inf.tu-dresden.de/w/images/5/55/CT2021-Lecture-08-overlay.pdf). The usual nonempty source-list convention is sufficient for the construction’s nonempty first menu.

All constructed society data satisfy the target requirements. In particular, offers remain individually indexed, both masses are positive and sum to one, capacities and quantities are positive integers, and the threshold is a valid nonnegative rational.

The size claim is correct. The construction copies each source integer a constant number of times, adds constant-sized data, and forms \(T+1\), whose bit length grows by at most one. Thus the output length is linear in the source length.

For type \(1\), quantity and payoff coincide, so feasibility gives \(K_1\le T\). For type \(2\), its only offer is feasible and has payoff \(1\), giving \(K_2=1\). Substituting these values into the structural lemma validates every equivalence in
\[ \operatorname{OPT}\ge B\iff K_1\ge T\iff K_1=T. \]

Attainment of \(K_1\) justifies the final equivalence with existence of an indexed subset summing exactly to \(T\). Source integers exceeding \(T\), repeated integers, and instances with no qualifying subset cause no difficulty. The reduction establishes hardness for the distribution problem itself.

• Membership in \(\mathrm{NP}\)

One membership bit per offer gives a certificate of length \(m\). The feasibility and weighted-payoff checks are exactly the conditions needed for the corresponding plan that assigns each type’s entire mass to its certified subset.

Conversely, the structural lemma ensures that any yes-instance has such a certificate: maximizing subsets attain at least the payoff of the qualifying plan. This addresses the potentially exponential description of general plans and their real-valued masses.

The exact-arithmetic argument is correct. Every encoded denominator divides their product \(D\), so \(u_t\), \(p_{tj}\), and \(b\) are integers. Since \(D>0\), multiplying the original payoff comparison by \(D^2\) gives precisely
\[ \sum_tu_t\sum_{j\in S_t}p_{tj}\ge bD. \]

The product \(D\) has \(O(L)\) bits because denominator bit lengths are included in the total input length. Scaled values, subset sums, weighted products, and the final sum also have \(O(L)\) bits. The additive logarithmic growth from summation is absorbed because \(m\) and \(\tau\) are bounded by the explicit input length.

The claimed \(O((m+\tau)L^2)\) verification bound is valid using schoolbook integer arithmetic. Together with the reduction, this establishes \(\mathrm{NP}\)-completeness.

• Exhaustive-search bound

Enumerating each type’s subsets and computing their quantities and scaled payoffs costs \(O(n_t2^{n_t}L)\) bit operations. Preprocessing and the final weighted comparison fit within the stated \(O((m+\tau)L^2)\) term.

Nonempty menus give \(n_t\le m-\tau+1\). Therefore the stated bound
\[ O\!\left((m+\tau)L^2+m2^{m-\tau+1}L\right) \]
follows correctly. Enumeration counts distinct indexed offers separately, as required.

• Dynamic-programming bound

The initialization includes the empty subset. When an offer exceeds the current capacity, exclusion is mandatory. Otherwise, the recurrence correctly separates subsets that exclude the offer from those that include it. Using the preceding row in both branches ensures that each indexed offer can be selected at most once.

The terminal value \(A_{n_t}(w_t)=DK_t\) and the stated total running time are correct. Each state uses arithmetic on \(O(L)\)-bit values.

Binary-encoded capacities can be exponential in \(L\), so the algorithm is pseudopolynomial. The general bound \(O((m+\tau)L^2+m2^LL)\) is a valid upper bound and does not conflict with the hardness result.

The conclusion that a polynomial-time algorithm exists if and only if \(\mathrm P=\mathrm{NP}\) follows from the established completeness result. There are no major or minor issues requiring additional clarification.

⟨structured verdict parsed — rendered above⟩