d4-conf-atal-2018-0127 (d4-conf-atal-2018-0127)

Given jobs with positive integer durations and a distribution \(\mu\) over supported preferred orderings, choose a permutation \(\pi\) minimizing \((\sum_t \mu_t f_t^g(\pi)^p)^{1/p}\), for fixed \(p>1\) and \(g\in\{T,E,D\}\). Here \(f_t^g(\pi)=\sum_j g(C_j(\pi),C_j(t))\), where \(C_j(t)\) is job \(j\)'s completion time in type \(t\)'s preferred ordering. Theorem 12 establishes NP-hardness already for two types of mass \(1/2\) each.

There are \(m\geq 1\) independent jobs with positive integer durations \(d_j\), encoded in binary. All jobs are available at time zero and run without preemption on one machine. Both preferred and collective schedules are strict permutations, executed from time zero without idle time; \(C_j(\rho)\) denotes job \(j\)'s completion time in permutation \(\rho\).
A society is given by its support: the list of the \(\tau\geq 1\) distinct preferred permutations with positive masses \(\mu_t\), each a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible permutations. Let \(L\) be the total input bit length.
Define \(T(c,a)=\max\{0,c-a\}\), \(E(c,a)=\max\{0,a-c\}\), and \(D(c,a)=|c-a|\). For fixed \(p\in\mathbb R\), \(1<p<\infty\), and fixed \(g\in\{T,E,D\}\), put \(f_t^g(\pi)=\sum_{j=1}^m g(C_j(\pi),C_j(t))\) and \(F_{p,g}(\pi)=(\sum_{t=1}^{\tau}\mu_t f_t^g(\pi)^p)^{1/p}\). The output is any permutation minimizing this objective; ties require no prescribed resolution.

For each fixed \(p>1\) and \(g\in\{T,E,D\}\), is finding a permutation minimizing \(F_{p,g}\) solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?

Known discrete result: minimizing the unweighted \(L_p\) aggregation of these costs is NP-hard for every fixed \(p>1\) and each of the three costs, even with two agents. [Source](https://arxiv.org/pdf/1803.07484).
The supplied distributional question already identifies the equal-mass, two-type case as covered by this hardness result; an unresolved status for this exact target cannot be claimed.

Result

For every fixed \(p\in(1,\infty)\) and every fixed \(g\in\{T,E,D\}\), finding an optimal permutation is NP-hard, already when \(\tau=2\) and \(\mu_1=\mu_2=\tfrac12\).

Known theorem and applicable hypotheses

Use the discrete hardness theorem supplied in the question: for each such fixed \(p\) and \(g\), finding a permutation minimizing the unweighted objective

\(H_{p,g}(\pi)=\bigl(f_a^g(\pi)^p+f_b^g(\pi)^p\bigr)^{1/p}\)

is NP-hard with two agents. This is Theorem 12 of [Pascual, Rzadca, and Skowron, *Collective Schedules: Scheduling Meets Computational Social Choice*](https://arxiv.org/pdf/1803.07484#page=16).

Its scheduling model uses positive integer processing times, independent jobs available initially, and nonpreemptive execution on one machine. The agent costs are precisely the sums of tardiness, earliness, or absolute completion-time deviation used here. The hardness construction specifies two distinct preferred job orders, so it also meets the requirement that support permutations be distinct.

We invoke this given theorem; the proof below establishes the transfer to the distributional input.

Polynomial reduction and preservation of all optimizers

Fix \(p\in(1,\infty)\) and \(g\in\{T,E,D\}\). Take an instance of the hard two-agent problem, with preferred permutations \(a,b\). Keep every job and its duration unchanged, and construct the support

\(\tau=2,\qquad t_1=a,\qquad t_2=b,\qquad \mu_1=\mu_2=\tfrac12.\)

This is a valid distributional instance: both masses are positive binary rationals and their sum is one. The feasible collective permutations and all completion times remain identical to those in the original instance.

Consequently, for every feasible permutation \(\pi\),

\(F_{p,g}(\pi)=\bigl(\tfrac12 f_a^g(\pi)^p+\tfrac12 f_b^g(\pi)^p\bigr)^{1/p}=2^{-1/p}H_{p,g}(\pi).\)

The factor \(2^{-1/p}\) is positive and independent of \(\pi\). Therefore, for any two feasible permutations \(\pi,\sigma\),

\(F_{p,g}(\pi)\leq F_{p,g}(\sigma)\quad\Longleftrightarrow\quad H_{p,g}(\pi)\leq H_{p,g}(\sigma).\)

In particular, the sets of minimizing permutations coincide exactly. Thus any optimizer returned for the distributional instance solves the original instance; arbitrary tie resolution causes no difficulty.

The construction copies the binary durations and two explicit permutations and adds only constant-size masses. Its output bit length is polynomial in the original input bit length. Since \(\tau=2\), an algorithm polynomial in \(m,\tau,L\) would therefore give a polynomial-time algorithm for the known NP-hard problem.

This reduction requires no numerical evaluation of \(2^{-1/p}\): it transforms the encoded instance and uses the returned permutation directly. Hence the argument applies to every fixed real \(p\) stipulated in the question.

Conclusion

All three optimization problems are NP-hard for every fixed \(p>1\), even with two equally weighted support types. A polynomial-time exact algorithm would imply \(\mathrm{P}=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

Verdict: proved. The output resolves every case requested in USER_TASK. The transfer from the supplied discrete hardness theorem is correct, preserves every optimizer, and has polynomial encoding size. No major or minor issues were found.

• The cited theorem matches the required source problem. Theorem 12 asserts hardness of finding an optimal schedule for each fixed \(p>1\) and each of \(T,E,D\), with two agents. The paper’s definitions use the same completion-time penalties summed over jobs and the same unweighted aggregation. These agree with the theorem expressly supplied in USER_TASK, which may therefore be invoked without reproving its hardness construction. [Source, Sections 2 and 3.2](https://arxiv.org/pdf/1803.07484#page=16).

• The scheduling and support hypotheses are satisfied. The cited model uses integer durations, independent available jobs, nonpreemptive execution, and schedules represented by job orders without gaps. The hardness construction’s two preferred permutations are distinct: they reverse the order within each pair of labeled equal-duration jobs. Thus the prover’s use of two distinct support types is justified. [Source, scheduling model and Theorem 12 construction](https://arxiv.org/pdf/1803.07484).

• The constructed distribution is valid. Copying the jobs and preferred permutations preserves their input restrictions. The masses \(\mu_1=\mu_2=\tfrac12\) are positive binary rationals and sum to one. The construction leaves the feasible collective permutations and their completion times unchanged.

• The objective identity is correct for every feasible permutation. Substitution of the masses yields

\[ F_{p,g}(\pi)=2^{-1/p}H_{p,g}(\pi). \]
All costs are nonnegative, so the real powers are well-defined, including when a cost is zero. The factor is positive and independent of the permutation for every stipulated fixed real \(p\).

• All optimizers and ties are preserved. Multiplication by that positive constant preserves both inequalities and equalities between objective values. Consequently, the two objectives have exactly the same minimizing permutations. Any optimizer returned by the target algorithm solves the source optimization instance, regardless of tie resolution.

• The reduction is polynomial in the encoded input size. It copies the binary durations and explicit permutations and adds constant-size masses. Both the construction time and output length are polynomial. With \(\tau=2\), a target algorithm polynomial in \(m,\tau,L\) would give a polynomial-time source algorithm.

• No numerical representation assumption is hidden. The reduction neither encodes nor evaluates \(2^{-1/p}\), and it requests only a minimizing permutation. Its validity therefore does not require exact numerical evaluation of real powers. The argument establishes NP-hardness; it does not assert membership in NP or strong NP-hardness.

Repair feedback: None required. The conclusion and its stated qualification concerning polynomial-time exact algorithms follow from the supplied theorem and the verified reduction.

⟨structured verdict parsed — rendered above⟩