Positional determinacy of finite parity games
Lax369799.FiniteParityGames · concepts/Lax369799/FiniteParityGames.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
A finite parity game admits positional winning strategies for both players on their winning regions. The arena is total. In this interface the greatest priority occurring infinitely often is even for Eve to win; reversing a bounded priority function converts this to the least-priority convention.
Concept map
Lean source view on GitHub
| 1 | import Mathlib.Data.Fintype.Basic |
| 2 | import Mathlib.Algebra.Group.Nat.Even |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Positional determinacy of finite parity games |
| 7 | type: theorem |
| 8 | --- |
| 9 | A finite parity game admits positional winning strategies for both |
| 10 | players on their winning regions. The arena is total. In this interface |
| 11 | the greatest priority occurring infinitely often is even for Eve to win; |
| 12 | reversing a bounded priority function converts this to the least-priority |
| 13 | convention. |
| 14 | -/ |
| 15 | |
| 16 | namespace Lax369799.FiniteParityGames |
| 17 | |
| 18 | structure Game (V : Type) where |
| 19 | eve : V → Prop |
| 20 | edge : V → V → Prop |
| 21 | priority : V → ℕ |
| 22 | total : ∀ v, ∃ w, edge v w |
| 23 | |
| 24 | def Game.IsPlay {V : Type} (G : Game V) (p : ℕ → V) : Prop := |
| 25 | ∀ n, G.edge (p n) (p (n + 1)) |
| 26 | |
| 27 | def Game.EveWins {V : Type} (G : Game V) (p : ℕ → V) : Prop := |
| 28 | ∃ c, ((∀ N, ∃ n, N ≤ n ∧ G.priority (p n) = c) ∧ |
| 29 | (∀ b, c < b → ¬ ∀ N, ∃ n, N ≤ n ∧ G.priority (p n) = b)) ∧ Even c |
| 30 | |
| 31 | def Game.Legal {V : Type} (G : Game V) (eve : Bool) (f : V → V) : Prop := |
| 32 | ∀ v, (G.eve v ↔ eve = true) → G.edge v (f v) |
| 33 | |
| 34 | def Game.Consistent {V : Type} (G : Game V) (eve : Bool) |
| 35 | (f : V → V) (p : ℕ → V) : Prop := |
| 36 | ∀ n, (G.eve (p n) ↔ eve = true) → p (n + 1) = f (p n) |
| 37 | |
| 38 | def Game.WinsFrom {V : Type} (G : Game V) (eve : Bool) (f : V → V) (v : V) : Prop := |
| 39 | ∀ p, G.IsPlay p → p 0 = v → G.Consistent eve f p → (G.EveWins p ↔ eve = true) |
| 40 | |
| 41 | axiom positional_determinacy {V : Type} [Finite V] (G : Game V) : |
| 42 | ∃ f g : V → V, G.Legal true f ∧ G.Legal false g ∧ |
| 43 | ∀ v, G.WinsFrom true f v ∨ G.WinsFrom false g v |
| 44 | |
| 45 | end Lax369799.FiniteParityGames |
| 46 |
Builds on
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments