Nested fixed-point equations for finite parity games
Lax369799.ParityGameEquations · concepts/Lax369799/ParityGameEquations.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
At depth zero every position is stopped and tested by its controlled predecessor condition. Increasing the depth binds the next priority by a greatest fixed point for even priorities and a least fixed point for odd priorities. Once the depth exceeds every priority, these nested equations define precisely Eve's positional winning region. The free boundary valuation is then immaterial.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.ParityFixedPoints |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Nested fixed-point equations for finite parity games |
| 6 | type: theorem |
| 7 | --- |
| 8 | At depth zero every position is stopped and tested by its controlled |
| 9 | predecessor condition. Increasing the depth binds the next priority by a |
| 10 | greatest fixed point for even priorities and a least fixed point for odd |
| 11 | priorities. Once the depth exceeds every priority, these nested equations |
| 12 | define precisely Eve's positional winning region. The free boundary |
| 13 | valuation is then immaterial. |
| 14 | -/ |
| 15 | namespace Lax369799.ParityGameEquations |
| 16 | open FiniteParityGames ParityWinningRegions ParityFixedPoints |
| 17 | attribute [local instance] Classical.propDecidable |
| 18 | |
| 19 | noncomputable def cut {V : Type} (G : Game V) (n : ℕ) (ρ : ℕ → Set V) : Game V := |
| 20 | stop G {v | n ≤ G.priority v} {v | v ∈ pre G true (ρ (G.priority v))} |
| 21 | |
| 22 | noncomputable def solve {V : Type} (G : Game V) : ℕ → (ℕ → Set V) → Set V |
| 23 | | 0, ρ => {v | v ∈ pre G true (ρ (G.priority v))} |
| 24 | | n + 1, ρ => if Even n then |
| 25 | sSup {X : Set V | X ⊆ solve G n (Function.update ρ n X)} |
| 26 | else sInf {X : Set V | Set.Subset (solve G n (Function.update ρ n X)) X} |
| 27 | |
| 28 | axiom solve_cut {V : Type} [Finite V] (G : Game V) (n : ℕ) (ρ : ℕ → Set V) : |
| 29 | (Winning (cut G n ρ) true : Set V) = solve G n ρ |
| 30 | |
| 31 | axiom winning {V : Type} [Finite V] (G : Game V) (n : ℕ) |
| 32 | (hn : ∀ v, G.priority v < n) (ρ : ℕ → Set V) : |
| 33 | (Winning G true : Set V) = solve G n ρ |
| 34 | |
| 35 | end Lax369799.ParityGameEquations |
| 36 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments