AFTD Auto-Formalizing Theoretical Domains

GameTree.Kuhn_exists_NE

theoremverifiedformalizationimported Lean

Kuhn's theorem, NE form: every finite perfect-information game without chance has a pure-strategy Nash equilibrium.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open GameTree in
variable {N U : Type*} [TotalPreorder U] in
theorem GameTree.Kuhn_exists_NE [DecidableLE U] (g : GameTree N U) :
    ∃ σ : Strategy N U, GameTree.IsNashEquilibrium σ g
Formalizes
EconCSLib, `GameTree.Kuhn_exists_NE`
Lean proof
By xbei (from the file's git history), from github.com/gametheoryinlean/EconCSLib at 1a88f809b538 (Copyright (c) 2026 EconCSLib contributors. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.30.0.
What was changed in GameTree.Kuhn_exists_NE
--- EconCSLib/GameTheory/ExtensiveGame/GameTreeNE.lean:110 (GameTree.Kuhn_exists_NE)
+++ as compiled here
@@ -1,5 +1,7 @@
-/-- **Kuhn's theorem, NE form**: every finite perfect-information game
-    without chance has a pure-strategy Nash equilibrium. -/
-theorem Kuhn_exists_NE [DecidableLE U] (g : GameTree N U) :
-    ∃ σ : Strategy N U, IsNashEquilibrium σ g := by
+set_option autoImplicit true in
+set_option relaxedAutoImplicit true in
+open GameTree in
+variable {N U : Type*} [TotalPreorder U] in
+theorem GameTree.Kuhn_exists_NE [DecidableLE U] (g : GameTree N U) :
+    ∃ σ : Strategy N U, GameTree.IsNashEquilibrium σ g := by
   obtain ⟨σ, hspe⟩ := Kuhn_exists_SPE (N := N) (U := U)
Verified
08 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 14
Used by 1
  • GameTree.zermelo_exists_pure_NEPure root Nash existence for a finite two-player game on ℚ: the Fin 2 / ℚ instance of Kuhn_exists_NE. Zero-sum is not needed.

Lean source view module on GitHub

set_option autoImplicit true inset_option relaxedAutoImplicit true inopen GameTree invariable {N U : Type*} [TotalPreorder U] in/-- **Kuhn's theorem, NE form**: every finite perfect-information game without chance has a pure-strategy Nash equilibrium. -/theorem GameTree.Kuhn_exists_NE [DecidableLE U] (g : GameTree N U) :    ∃ σ : Strategy N U, GameTree.IsNashEquilibrium σ g := by  obtain ⟨σ, hspe⟩ := Kuhn_exists_SPE (N := N) (U := U)  exact ⟨σ, hspe.toNE g⟩
See it in the graphDiscuss this resultChallenge it