Lemma 13, part 1, p. 13 — for i ≤ n − √n + 1, an agent diverging at u_i diverges on M and H
ProvedOSPMech.SqrtLB.lemma_13_part_1Fix an integer and let , so . Consider scheduling identical jobs on related machines with the three-value domain for every agent, where
Let be an OSP mechanism whose outcomes on schedule all jobs, and suppose it is -approximate on for some .
Let agent be the -th agent that diverges along the execution of the all- profile, and let be the vertex where she first diverges. If
then diverges on and at : the types and of agent lead to different children of .
This is the first step of the proof of Theorem 12: it rules out that the early diverging agents separate only from .
Formalization Note. Agents are ranked from : the paper's agent has rank , and the condition is . The lemma is stated for agents that really diverge on the all- path (the paper's "dummy nodes" for agents that never diverge are not used). The assumption reads the paper's non-negative costs with ; payments are a function of the declared profile. As in the paper, the lemma is a step of the proof by contradiction of Theorem 12: by that theorem no mechanism meets its hypotheses (an OSP mechanism that is -approximate with ), so its content is the implication itself, which the paper derives from OSP CMON.
import Mathlib import Definitions.Def_OSPMech_SqrtLB_Model
namespace OSPMech.SqrtLB
theorem lemma_13_part_1 (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)
(k : ℝ) (hk : k < c) (happrox : IsKApprox (c ^ 2) k (fun _ => {L, Mid, H}) t)
(r : ℕ) (i : Fin (c ^ 2)) (pos : List ℕ) (hr : r + 1 ≤ c ^ 2 - c + 1)
(hdiv : IsKthDiverger (fun _ => {L, Mid, H}) t H r i pos) :
∃ act ch, subtreeAt t pos = some (.node i act ch) ∧ act Mid ≠ act H := by sorry
end OSPMech.SqrtLB
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.