§4, pp. 154–155 — in S₁ of J′(F) the bookkeeper sets z = |2y − x| on (4.1) and z = fr(x) = min{x, 1 − x} on (4.6)
ProvedJeroslowMLP.Value.bookkeeper_in_S1gadgetmultilevel-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1reduction
In the game , let , i.e. a point after the bookkeeper (player ) has moved. Then:
- every (4.1) gadget on (that is, or for an atom of a block ) has ;
- every (4.6) gadget on an atom of block has ;
- the (4.6) gadget on has .
These identities turn the linear criteria of players into the piecewise-linear functions of (4.4)–(4.8).
Formalization Note Lean's block k : Fin p is the paper's ; gArg x g s is .
Preamble
import Mathlib import Definitions.Def_JeroslowMLP_Value_Game
Formal statement
namespace JeroslowMLP.Value
open MultilevelProgram GVar
theorem bookkeeper_in_S1 (p : ℕ) (n : Fin p → ℕ) (F : Formula (Atom p n))
(x : GVar p n F → ℝ) (hx : x ∈ (jGame p n F).solSet 1) :
(∀ g s, x (gz g s) = |2 * x (gy g s) - gArg x g s|) ∧
(∀ a, x (fz a) = min (x (atom a.1)) (1 - x (atom a.1))) ∧
x fzF = min (xF x) (1 - xF x) := by sorry
end JeroslowMLP.Value
Source
Jeroslow, The polynomial hierarchy and a simple model for competitive analysis, Math. Programming 32 (1985), p. 154 (after (4.1)) and p. 155 (after (4.6))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.