d4-conf-atal-2021-0177 (d4-conf-atal-2021-0177)

Given finitely many demand-menu types \(T\), rational masses \(\mu_t>0\) summing to \(1\), a per-capita budget \(b>0\), and explicit menus \(D_t\) of positive rational demands with each demand at most \(b\) and \(v(D_t)>b\), let \(d_t^*=\max D_t\) and \(q_0=b\min_{t\in T}\rho_1(d_t^*/b)\). Compute masses \(x_{t,S}\ge 0\) assigned to integral bundles \(S\subseteq D_t\), such that \(\sum_{S\subseteq D_t}x_{t,S}=\mu_t\), \(\sum_{t\in T}\sum_{S\subseteq D_t}x_{t,S}v(S)\le b\), and \(x_{t,S}>0\) only if \(v(S)\ge q_0\).

A society is given by its support: a nonempty list \(T\) of \(\tau\) demand-menu types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
Each explicitly listed menu \(D_t\) consists of indexed demands, allowing repeated values. Given a positive binary-rational per-capita budget \(b\), every demand satisfies \(0<d\le b\), and \(v(D_t)>b\), where \(v(S)=\sum_{d\in S}d\). Bundles select demand indices integrally.
Let \(m=\sum_{t\in T}|D_t|\), and let \(L\) be the total binary input length. Set \(d_t^*=\max D_t\). For \(0<\alpha\le1\), define \(\rho_1(\alpha)=(k-1+\alpha)/k\), where \(k\ge1\) is the unique integer satisfying \(1/(k+1)<\alpha\le1/k\). Set \(q_0=b\min_{t\in T}\rho_1(d_t^*/b)\).
The construction problem asks for nonnegative rational bundle masses \(x_{t,S}\), represented by listing their positive entries, satisfying \(\sum_{S\subseteq D_t}x_{t,S}=\mu_t\) for every \(t\), \(\sum_{t\in T}\sum_{S\subseteq D_t}x_{t,S}v(S)\le b\), and \(x_{t,S}>0\Rightarrow v(S)\ge q_0\).

Can this bundle-mass construction problem be solved in time polynomial in \(m\), \(\tau\), and \(L\), or is it NP-hard?

For a finite single-agent menu with positive demands at most \(B\) and total demand exceeding \(B\), a polynomial-time algorithm constructs an integral bundle of value between \(B\rho_1(d^*/B)\) and \(B\), where \(d^*\) is the largest demand. This discrete result does not classify the bundle-mass construction problem.

Classification

The construction problem is polynomial-time solvable, using the single-agent algorithm supplied in the question. One bundle per support type suffices.

For this construction, the supplied discrete result does imply the classification: the common required threshold is the minimum of the individual guarantees.

Construction and feasibility

For each listed type \(t\in T\), define
\[ q_t=b\,\rho_1(d_t^*/b). \]
Apply the supplied single-agent algorithm to the indexed menu \(D_t\), with budget \(B=b\). Its hypotheses hold: the menu is finite, every demand satisfies \(0<d\le b\), and \(v(D_t)>b\). Consequently, it returns an integral indexed bundle \(S_t\subseteq D_t\) satisfying
\[ q_t\le v(S_t)\le b. \]

Output exactly the following positive entries:
\[ x_{t,S_t}=\mu_t\qquad(t\in T). \]
All unlisted entries are zero. Repeated demand values cause no ambiguity because each bundle specifies demand indices.

We verify all three requirements.

• Type masses. Each type has exactly one positive entry, so

\[ \sum_{S\subseteq D_t}x_{t,S}=\mu_t. \]

• Budget. Using \(v(S_t)\le b\), positivity of the masses, and their prescribed sum,

\[ \sum_{t\in T}\sum_{S\subseteq D_t}x_{t,S}v(S) =\sum_{t\in T}\mu_t v(S_t) \le b\sum_{t\in T}\mu_t=b. \]

• Required bundle values. By the definition of the minimum,

\[ q_0=\min_{u\in T}q_u\le q_t\le v(S_t). \]
Thus every positive entry is assigned to a bundle whose value is at least \(q_0\).

This proves feasibility of the construction.

Running time and representation

Let \(P\) be a polynomial bounding the supplied single-agent algorithm’s running time in the explicit binary input length. Each instance consisting of \(D_t\) and \(b\) has length at most \(L+O(1)\). There are \(\tau\) calls, so their total running time is at most \(\tau P(L+O(1))\), which is polynomial in the requested parameters.

The output has exactly \(\tau\) positive entries. Their masses are the original binary-rational numbers \(\mu_t\), so no new mass arithmetic or increase in their bit lengths is needed. Across all output bundles, at most \(m\) demand indices are listed; these require at most \(O(m\log(m+1))\) bits. Hence the output length and the time needed to write it are polynomial in \(m\), \(\tau\), and \(L\).

Therefore the stated single-agent algorithm yields a complete polynomial-time solution to the bundle-mass construction problem.

⟨structured verdict parsed — rendered above⟩

The prover’s claim is correct: the stated discrete algorithm gives a polynomial-time solution to this particular bundle-mass construction problem. No mathematical or computational gaps were found.

Step-by-step verification

• Applicability of the supplied algorithm. For every listed type \(t\), the input menu is finite, all demands satisfy \(0<d\le b\), and its total value exceeds \(b\). These are exactly the hypotheses of the supplied single-agent result with \(B=b\). Its conclusion therefore provides an integral indexed bundle \(S_t\) with

\[ b\rho_1(d_t^*/b)\le v(S_t)\le b. \]
Treating bundles as selections of indices correctly accommodates repeated demand values.

• Definition of the output. Assigning \(x_{t,S_t}=\mu_t\) and setting all other entries to zero gives nonnegative rational masses. Each listed entry is positive because the input masses are positive. Entries belonging to different types remain distinct even if their selected bundles have identical demand values.

• Type-mass constraints. Exactly one bundle receives positive mass for each type. Thus its total assigned mass is exactly \(\mu_t\), as required.

• Aggregate budget constraint. The displayed calculation is valid: \(v(S_t)\le b\), multiplication by the positive mass \(\mu_t\) preserves this inequality, and \(\sum_t\mu_t=1\). Consequently, the aggregate expenditure is at most \(b\).

• Common threshold constraint. Writing \(q_t=b\rho_1(d_t^*/b)\), the identity \(q_0=\min_t q_t\) follows because \(b>0\). The support is finite and nonempty, so this minimum exists. Hence \(v(S_t)\ge q_t\ge q_0\) for every positive output entry.

• Running time. Under the supplied polynomial-time guarantee, interpreted in the standard binary-input model, each call has input length at most \(L+O(1)\). Making \(\tau\) such calls takes polynomial time in the requested parameters. No computation of \(q_0\) is needed by the construction.

• Output representation. The output copies the original rational masses and lists at most \(m\) selected demand indices across all types. The claimed bound for encoding those indices is valid. Encoding the type identifiers and other record information also requires only polynomial space and writing time.

Scope and repair feedback

The task’s statement that the discrete result does not classify the bundle-mass problem does not invalidate this argument. The prover explicitly supplies the necessary connection: each individual guarantee exceeds the common minimum threshold, while each individual bundle respects the per-capita budget. These verified properties settle the stated construction problem.

No additional clarification or repair is required.

⟨structured verdict parsed — rendered above⟩