(4.3), §4, p. 154 — at the level of player k ≥ 2, y = p(x) with p(x) = 1 on [0,1) and p(1) = 0
ProvedJeroslowMLP.Value.eq_4_3gadgetmultilevel-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1reduction
In the game , let be a player, one of its atoms, and (the set after player has moved). For both gadgets of (on and on ) the variable equals
and consequently
The term in player 's criterion therefore penalises fractional choices.
Formalization Note Lean block k : Fin p with 1 ≤ k.val is the paper's block and player , whose level is k.val + 2; since atoms lie in , is written if ξ < 1 then 1 else 0.
Preamble
import Mathlib import Definitions.Def_JeroslowMLP_Value_Game
Formal statement
namespace JeroslowMLP.Value
open MultilevelProgram GVar
theorem eq_4_3 (p : ℕ) (n : Fin p → ℕ) (F : Formula (Atom p n)) (k : Fin p) (hk : 1 ≤ k.val)
(x : GVar p n F → ℝ) (hx : x ∈ (jGame p n F).solSet (k.val + 2)) (j : Fin (n k)) :
(∀ s : Bool, x (gy ⟨⟨k, j⟩, hk⟩ s) = if gArg x ⟨⟨k, j⟩, hk⟩ s < 1 then 1 else 0) ∧
x (gy ⟨⟨k, j⟩, hk⟩ false) + x (gy ⟨⟨k, j⟩, hk⟩ true) =
if x (atom ⟨k, j⟩) = 0 ∨ x (atom ⟨k, j⟩) = 1 then 1 else 2 := by sorry
end JeroslowMLP.Value
Source
Jeroslow, The polynomial hierarchy and a simple model for competitive analysis, Math. Programming 32 (1985), p. 154, §4, (4.3), and P(x) = p(x) + p(1 − x), Fig. 1b, pp. 154–155
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.