Proof of Theorem 5.2, Eq. (1) — a KNAPSACK solution yields a schedule meeting and
ProvedTwoAgentSched.Knapsack.eq_1Let be a KNAPSACK instance with items and consider the two-agent instance of the proof of Theorem 5.2: -jobs with , , one -job with , and thresholds , , where , .
Let solve KNAPSACK, i.e. and , and let be any sequence of all jobs in which the -jobs sequenced before the -job are exactly those with . Then
This is the "KNAPSACK yes schedule yes" direction of the reduction.
Formalization Note The paper writes the two estimates on the terms of (1) as strict ("smaller than"); they hold only with (with , , , , the cost equals ), and only is needed, so the statement uses . The statement holds for every order of the jobs within and within its complement. No positivity assumption is needed in this direction.
import Mathlib import Definitions.Def_TwoAgentSched_Knapsack_Construction
namespace TwoAgentSched.Knapsack
/-- Proof of Theorem 5.2, Eq. (1) (Agnetis et al. 2004, p. 233): from a KNAPSACK solution `S`
(`∑_{i∈S} u_i ≤ b`, `∑_{i∈S} w_i ≥ W`), every sequence of the constructed instance in which the
A-jobs placed before the B-job are exactly those of `S` meets both thresholds `Q_A` and `Q_B`. -/
theorem eq_1 {n : ℕ} (u w : Fin n → ℕ) (b W : ℤ) (S : Finset (Fin n))
(hu : ((∑ i ∈ S, u i : ℕ) : ℤ) ≤ b) (hw : W ≤ ((∑ i ∈ S, w i : ℕ) : ℤ))
(l : List (Fin (construction u w).nA ⊕ Fin (construction u w).nB))
(hl : MooreLateJobs.Shared.IsSchedule Finset.univ l)
(hS : ∀ i : Fin n, i ∈ S ↔ l.idxOf (aJob u w i) < l.idxOf (bJob u w)) :
(construction u w).Meets ((QA u w W : ℤ) : ℝ) ((QB u w b : ℤ) : ℝ) l := by sorry
end TwoAgentSched.Knapsack
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.