d4-conf-atal-2010-0306 (d4-conf-atal-2010-0306)

Given rational type masses \(\mu_t\), rational costs \(c_{tj}\), per-agent workload bounds, per-capita job-supply bounds, and rational \(\alpha,\epsilon>0\), let each type \(t\) distribute its mass among feasible integral bundles \(B\), with \(x_{tB}\ge 0\) and \(\sum_B x_{tB}=\mu_t\). Each bundle has cost \(c_t(B)=\sum_j c_{tj}B_j\), and the resulting cost distribution is \(\nu_x=\sum_{t,B}x_{tB}\delta_{c_t(B)}\). With \(\widehat\Phi(\nu_x)=\frac{\pi}{2}\int_0^1\sin\!\left(\frac{\pi}{2}(1-u)\right)Q^\downarrow_{\nu_x}(u)\,du\), distinguish the promised cases \(\operatorname{OPT}\le\alpha\) and \(\operatorname{OPT}\ge\alpha+\epsilon\), where \(\operatorname{OPT}=\min_x\widehat\Phi(\nu_x)\).

A society is given by its support: the list of the \(\tau\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
There are \(m\ge1\) jobs. Type \(t\) has nonnegative rational costs \(c_{tj}\) and integer workload bounds \(0\le\ell_t\le u_t\le m\). Job \(j\) has rational per-capita supply bounds \(0\le a_j\le b_j\le1\).
The feasible bundles for type \(t\) are \(\mathcal B_t=\{B\in\{0,1\}^m:\ell_t\le\sum_jB_j\le u_t\}\), specified implicitly by these bounds. Each agent receives at most one copy of each job.
An allocation consists of real masses \(x_{tB}\ge0\) satisfying \(\sum_{B\in\mathcal B_t}x_{tB}=\mu_t\) and \(a_j\le\sum_t\sum_{B\in\mathcal B_t}x_{tB}B_j\le b_j\) for every job. Assume a feasible allocation exists.
Set \(c_t(B)=\sum_jc_{tj}B_j\) and \(\nu_x=\sum_t\sum_{B\in\mathcal B_t}x_{tB}\delta_{c_t(B)}\). Let \(Q^\downarrow_{\nu_x}\) be its decreasing quantile function; choices at atom boundaries do not affect the integral.
Define \(\widehat\Phi(\nu_x)=\frac{\pi}{2}\int_0^1\sin\!\left(\frac{\pi}{2}(1-u)\right)Q^\downarrow_{\nu_x}(u)\,du\) and \(\operatorname{OPT}=\min_x\widehat\Phi(\nu_x)\). The input includes binary-rational \(\alpha,\epsilon>0\), and \(L\) is its total bit length.

Is distinguishing the promised cases \(\operatorname{OPT}\le\alpha\) and \(\operatorname{OPT}\ge\alpha+\epsilon\) solvable in polynomial time in \(m,\tau,L\), or is this promise problem NP-hard?

For finite agents with the corresponding binary assignments and count bounds, deciding whether \(\sum_{k=1}^n\sin\!\left(\frac{(n+1-k)\pi}{2n+1}\right)y_{(k)}\le\alpha\), where individual costs \(y_{(k)}\) are sorted decreasingly, is reported NP-complete by [Golden and Perny](https://borisgolden.com/research/AAMAS10.pdf).
No result settling the exact continuous promise problem above was located in the literature search.

Result

The promise problem is \(\mathrm{NP}\text{-hard}\), even with one supported type, integer costs, no workload restrictions, every job’s supply fixed to \(1/2\), and the fixed promise gap \(\epsilon=1/4\).

The proof applies directly to allocations with arbitrary real masses.

1. A quantitative bound for the objective

Let \(Y\) be a nonnegative random variable with finite support, distribution \(\nu\), and survival function \(S(z)=\Pr(Y>z)\). Write \(\kappa=\pi/2\). Since \(\sin(\kappa(1-u))=\cos(\kappa u)\), the objective is

\(\displaystyle \widehat\Phi(\nu)=\int_0^1\kappa\cos(\kappa u)Q^\downarrow_\nu(u)\,du.\)

For each \(z\), the set where \(Q^\downarrow_\nu(u)>z\) is, up to endpoints, the interval of length \(S(z)\) beginning at zero. Applying Tonelli’s theorem to the nonnegative integrand gives

\(\displaystyle \widehat\Phi(\nu)=\int_0^\infty\int_0^{S(z)}\kappa\cos(\kappa u)\,du\,dz=\int_0^\infty\sin(\kappa S(z))\,dz.\)

The usual tail formula also gives \(\mathbb EY=\int_0^\infty S(z)\,dz\). Consequently,

\(\displaystyle \widehat\Phi(\nu)-\mathbb EY=\int_0^\infty h(S(z))\,dz,\qquad h(p)=\sin(\pi p/2)-p.\)

The function \(h\) is concave on \([0,1]\), because

\(\displaystyle h''(p)=-\frac{\pi^2}{4}\sin(\pi p/2)\le0.\)

Furthermore, \(h(0)=h(1)=0\) and \(h(1/2)=(\sqrt2-1)/2\). Concavity places \(h\) above the chords connecting these three points, so

\(\displaystyle h(p)\ge(\sqrt2-1)\min\{p,1-p\}\qquad(0\le p\le1).\)

In particular, \(\widehat\Phi(\nu)\ge\mathbb EY\).

Choose a median \(q\) belonging to the support of \(Y\). Such a median exists: take the smallest support value whose cumulative probability is at least \(1/2\). It satisfies both \(\Pr(Y<q)\le1/2\) and \(\Pr(Y>q)\le1/2\). Thus \(S(z)\ge1/2\) for \(z<q\), and \(S(z)\le1/2\) for \(z\ge q\). Therefore,

\(\displaystyle \int_0^\infty\min\{S(z),1-S(z)\}\,dz =\int_0^q(1-S(z))\,dz+\int_q^\infty S(z)\,dz =\mathbb E|Y-q|.\)

The last equality follows by integrating the probabilities defining \((q-Y)_+\) and \((Y-q)_+\); atom boundaries have no effect. We have proved

\(\displaystyle \boxed{\widehat\Phi(\nu)-\mathbb EY\ge(\sqrt2-1)\mathbb E|Y-q|.}\)

In particular, suppose \(Y\) is integer-valued, \(\mathbb EY=T\) is an integer, and \(T\) does not belong to its support. The chosen median \(q\) is then an integer different from \(T\). By the triangle inequality for expectations,

\(\displaystyle \mathbb E|Y-q|\ge|\mathbb E(Y-q)|=|T-q|\ge1.\)

Hence

\(\displaystyle \boxed{\widehat\Phi(\nu)\ge T+\sqrt2-1.}\)

This bound holds for arbitrary real probabilities on the support.

2. Construction from PARTITION

We reduce from PARTITION on positive integers encoded in binary, a classical \(\mathrm{NP}\)-complete problem. See [Karp, *Reducibility Among Combinatorial Problems*](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).

Let the source instance be positive integers \(d_1,\ldots,d_m\), and define \(T=\sum_{j=1}^m d_j\). Its question is whether there exists a subset \(I\subseteq\{1,\ldots,m\}\) with

\(\displaystyle 2\sum_{j\in I}d_j=T.\)

Construct the society as follows:

• One supported type, with \(\mu_1=1\).
• Costs \(c_{1j}=2d_j\).
• Workload bounds \(\ell_1=0\) and \(u_1=m\).
• Supply bounds \(a_j=b_j=1/2\) for every job.
• Threshold \(\alpha=T\) and promise gap \(\epsilon=1/4\).

All these data satisfy the required hypotheses. In particular, feasibility is guaranteed: assign mass \(1/2\) to the empty bundle and mass \(1/2\) to the full bundle.

For any feasible allocation \(x\), let \(Y\) denote its random bundle cost. Since the sole type has mass one, the allocation masses are probabilities. The exact supply constraints imply

\(\displaystyle \mathbb EY =\sum_Bx_{1B}\sum_j2d_jB_j =\sum_j2d_j\sum_Bx_{1B}B_j =\sum_j2d_j\cdot\frac12 =T.\)

Thus every feasible allocation has the same mean cost.

3. Correctness of the reduction

A partition gives the low promised case

Suppose \(I\) satisfies \(2\sum_{j\in I}d_j=T\). Both its bundle and the complementary bundle have cost \(T\).

Assign mass \(1/2\) to each of these two bundles. Every job appears in exactly one of them, so every supply constraint is satisfied. The resulting cost distribution is \(\delta_T\), and therefore

\(\displaystyle \widehat\Phi(\delta_T) =T\int_0^1\kappa\cos(\kappa u)\,du=T.\)

Every feasible allocation has objective at least its mean \(T\), by Section 1. Consequently,

\(\displaystyle \operatorname{OPT}=T=\alpha.\)

Absence of a partition gives the high promised case

Suppose the PARTITION instance has no solution. A bundle \(B\) has cost

\(\displaystyle c_1(B)=2\sum_jd_jB_j.\)

This is an integer, and it equals \(T\) precisely when the selected jobs form a solution of the source instance. Hence every bundle cost differs from \(T\).

For every feasible allocation, \(Y\) is therefore integer-valued, has mean \(T\), and has no support value equal to \(T\). The quantitative bound in Section 1 yields

\(\displaystyle \widehat\Phi(\nu_x)\ge T+\sqrt2-1.\)

Since \(\sqrt2-1>1/4\), it follows that

\(\displaystyle \operatorname{OPT}\ge T+\sqrt2-1>T+\frac14=\alpha+\epsilon.\)

The argument covers every feasible allocation, including those using arbitrary real masses.

4. Encoding and complexity

The construction uses \(m\) jobs and support size \(\tau=1\). Doubling the source integers increases their bit lengths by at most one, and the bit length of \(T\) is polynomial in the source input length. All other numerical data have constant bit length. The reduction is therefore computable in polynomial time and produces an instance of polynomial total bit length \(L\).

Every source instance maps into one of the two promised cases, with the correct answer. Thus an algorithm polynomial in \(m,\tau,L\) for the stated promise problem would decide PARTITION in polynomial time.

This proves the requested \(\mathrm{NP}\)-hardness, even for the fixed gap \(\epsilon=1/4\).

⟨structured verdict parsed — rendered above⟩

Verification report

The argument establishes the requested \(\mathrm{NP}\)-hardness for the continuous promise problem, including allocations with arbitrary real masses. The mathematical proof is correct. There is one minor error in the encoding discussion: the workload upper bound \(u_1=m\) does not have constant bit length. This does not affect polynomiality.

1. Objective identity

The substitution \(\kappa=\pi/2\) and identity \(\sin(\kappa(1-u))=\cos(\kappa u)\) correctly reproduce the stated objective.

For a decreasing quantile, the set of \(u\) for which \(Q^\downarrow_\nu(u)>z\) is an initial interval of length \(S(z)\), up to endpoints. The layer-cake representation and Tonelli interchange are justified: \(Y\) is nonnegative, and \(\kappa\cos(\kappa u)\ge0\) on the integration domain. Finite support ensures all resulting integrals are finite.

Thus the asserted identity
\[ \widehat\Phi(\nu)=\int_0^\infty\sin(\kappa S(z))\,dz \]
is correct, as is the subtraction of the tail formula for \(\mathbb EY\).

2. Quantitative inequality

The derivative calculation
\[ h''(p)=-\frac{\pi^2}{4}\sin(\pi p/2)\le0 \]
is correct on \([0,1]\). The stated endpoint and midpoint values are also correct.

The two chords have values \((\sqrt2-1)p\) on \([0,1/2]\) and \((\sqrt2-1)(1-p)\) on \([1/2,1]\). Concavity therefore gives exactly the claimed lower bound. In particular, the objective is at least the mean.

The specified support median exists. Its defining cumulative-probability property yields both required median inequalities. Consequently, the asserted choices of the minimum below and above \(q\) are valid. Integrating these two tails gives \(\mathbb E|Y-q|\); strict versus non-strict inequalities at atoms do not change the integrals. This also covers \(q=0\).

The resulting bound
\[ \widehat\Phi(\nu)-\mathbb EY\ge(\sqrt2-1)\mathbb E|Y-q| \]
is established.

When \(Y\) is integer-valued, its mean \(T\) is an integer, and \(T\) is absent from its support, the chosen support median is an integer distinct from \(T\). The expectation triangle inequality therefore gives the stated lower bound of \(1\). No rationality assumption on the probabilities is used.

3. Reduction and feasibility

The source problem is precisely positive-integer PARTITION with binary encoding, an NP-complete problem. Its use is valid; the binary-encoding distinction is also confirmed in [MIT’s computational intractability text](https://hardness.mit.edu/drafts/2025-01-05.pdf).

All constructed data meet the target restrictions:

• The single supported type has positive normalized mass \(1\).
• Costs \(2d_j\) are nonnegative integers.
• The workload bounds allow every binary bundle.
• Fixed supplies \(1/2\) satisfy the supply-bound restrictions.
• Both \(\alpha=T\) and \(\epsilon=1/4\) are positive binary-rational values.

The empty/full allocation explicitly establishes feasibility. Its supply totals are exactly \(1/2\).

The mean calculation follows from finite summation and the exact supply equalities. It establishes \(\mathbb EY=T\) for every feasible allocation, including those with arbitrary real masses.

4. Both promised cases

YES direction. A partition subset and its complement both have cost \(T\). Giving each mass \(1/2\) satisfies every supply constraint and produces \(\delta_T\). The objective integral evaluates to \(T\), since the weight integrates to \(1\). The previously proved mean lower bound establishes \(\operatorname{OPT}=T=\alpha\).

NO direction. A bundle has cost \(T\) exactly when its selected jobs solve PARTITION. Hence, in a NO instance, every feasible cost distribution has integer support excluding \(T\), while retaining mean \(T\). The quantitative inequality applies to every such distribution and yields the uniform lower bound \(T+\sqrt2-1\).

The comparison \(\sqrt2-1>1/4\) is correct. Thus every NO instance satisfies the high promise. This uniform bound rules out approaching the low threshold through increasingly small real allocation masses.

Odd totals and single-job instances cause no exception: the same bundle-cost characterization and lower-bound argument apply.

5. Encoding and conclusion

Doubling the source integers adds at most one bit per cost. The sum \(T\) has polynomial bit length, and the output explicitly contains only one type and \(m\) jobs. The mapping is computable in polynomial time and maps every source instance into the promise.

Minor issue: Section 4 says, “All other numerical data have constant bit length.” The value \(u_1=m\) requires \(O(\log(m+1))\) bits.

Minimum clarification: Replace that sentence with a statement that the remaining numerical data have constant bit length except \(u_1=m\), which has logarithmic bit length. No mathematical repair is needed.

The reduction proves NP-hardness. It does not claim membership in NP or strong NP-hardness, and neither is required by the task. There are no blocking issues.

⟨structured verdict parsed — rendered above⟩