Lemma 13, part 2, p. 13 — for i ≤ n − √n, an agent answering H at u_i receives no job
ProvedOSPMech.SqrtLB.lemma_13_part_2Fix 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 for every profile compatible with in which agent has type , the mechanism assigns no job to machine :
Applied to the all- profile, this leaves all jobs to at most machines, which is how Theorem 12 is concluded.
Formalization Note. Agents are ranked from : the paper's agent has rank , and the condition is . "Takes an action compatible with her type being , regardless of the actions taken by the other agents" is read as: every profile of compatible with with . The lemma is stated for agents that really diverge on the all- path. 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_2 (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)
(hdiv : IsKthDiverger (fun _ => {L, Mid, H}) t H r i pos) :
∀ x : Fin (c ^ 2) → ℝ, InDomain (fun _ => {L, Mid, H}) x → Compatible t pos x → x i = H →
outcome t x i = 0 := by sorry
end OSPMech.SqrtLB
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.