Theorem 12, p. 12 — no OSP mechanism for scheduling m = n = c² identical jobs on related machines with domains {L, M, H} is better than √n-approximate
ProvedOSPMech.SqrtLB.theorem_12Fix an integer and let , so . Consider scheduling identical jobs on related machines, where agent controls machine and has a processing time per job in the three-value domain , with
Let be any extensive-form mechanism, with implementation tree and payment function , that is obviously strategyproof on for the costs and whose outcome on every profile of assigns all jobs. Then there is a profile on which
where is the least makespan of a schedule of the jobs. Equivalently, no such mechanism is -approximate for any .
Obvious strategyproofness asks that truth-telling remain dominant for agents who reason only about what they have observed in the execution so far. The theorem shows that this costs a factor in makespan already for three-value domains, whereas with two-value domains an optimal OSP mechanism exists (Proposition 11), and a matching upper bound holds.
Formalization Note. The statement is posed in the instance family of the paper's proof (p. 12): with (the paper's ), and ; non-square is not claimed. reads the paper's non-negative costs with , and makes , so the conclusion is equivalent to "not -approximate for any ". Payments are a function of the declared profile, which allows more mechanisms and so strengthens the impossibility.
import Mathlib import Definitions.Def_OSPMech_SqrtLB_Model
namespace OSPMech.SqrtLB
theorem theorem_12 (c : ℕ) (hc : 2 ≤ c) (L Mid H : ℝ) (hL : 0 < L)
(hM : ((c ^ 2 : ℕ) : ℝ) * L ≤ Mid) (hH : ((c ^ 2 : ℕ) : ℝ) * c * Mid ≤ H)
(t : ImplTree (c ^ 2) (Fin (c ^ 2) → ℕ)) (p : (Fin (c ^ 2) → ℝ) → Fin (c ^ 2) → ℝ)
(hsched : IsSchedule (c ^ 2) (fun _ => {L, Mid, H}) t)
(hosp : IsOSP (fun _ => {L, Mid, H}) schedCost t p) :
∃ b : Fin (c ^ 2) → ℝ, InDomain (fun _ => {L, Mid, H}) b ∧
(c : ℝ) * optMakespan (c ^ 2) b ≤ makespan b (outcome t b) := by sorry
end OSPMech.SqrtLB
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.