Kuhn's theorem for finite AJ games
OpenAJGames.kuhnLet be a game with finitely many moves whose positions have bounded length.
- For every behaviour strategy there is a probability distribution on deterministic strategies such that, for every script and every play ,
- Conversely, every such distribution has a behaviour strategy with the same play-out distributions.
AJ plays record the whole history, so Player has perfect recall.
import Mathlib import Definitions.Def_AJGames_Behaviour
namespace AJGames
open scoped ENNReal
universe u
/-- **Kuhn's theorem for finite AJ games.** In a game with finitely many moves and plays of bounded
length, every behaviour strategy has a mixed strategy (a probability distribution on deterministic
strategies) with the same play-out distribution against every Opponent script, and every mixed
strategy has an equivalent behaviour strategy. -/
theorem kuhn {A : Game.{u}} [Finite A.M] (hfin : ∃ N : ℕ, ∀ s ∈ A.pos, s.length ≤ N) :
(∀ β : BehStrategy A, ∃ μ : PMF (Strategy A), ∀ rs p : List A.M,
playOut β [] rs p = ∑' σ, μ σ * playOut (ofStrategy σ) [] rs p) ∧
(∀ μ : PMF (Strategy A), ∃ β : BehStrategy A, ∀ rs p : List A.M,
playOut β [] rs p = ∑' σ, μ σ * playOut (ofStrategy σ) [] rs p) := by sorry
end AJGamesRead-back
What the Lean code literally says, in plain math · claude-opus-5-5
Read-back of kuhn (behavioural and mixed strategies give the same outcome distributions).
Setting. A game consists of a type of moves , a labelling , and a set of finite sequences of moves (the positions) such that: the empty sequence is a position; every prefix of a position is a position; and in every position consecutive moves carry different labels ( alternates). Nothing requires a position to start with an -move, and positions may be of any finite length.
A (deterministic) strategy on is a set of sequences (its carrier) such that: ; ; is prefix-closed; every nonempty sequence in begins with an -labelled move; determinism: if and with both -labelled then ; receptivity: if , is -labelled and , then . A strategy is not required to answer every -move (it may stop). Two strategies are equal iff their carriers are equal.
Write for " is nonempty and its last move is -labelled" (the Lean name is PlayerToMove). A behavioural strategy assigns to every finite sequence (not only positions) a probability distribution on , where means "make no move/stop", subject to: if for a move , then , , and (if ) . Consequently, whenever is empty or ends in a -move, is the point mass at . The distribution may depend on the whole history .
From a strategy one gets a behavioural strategy : is the point mass at if there is a -labelled with (some such chosen by choice; by determinism it is unique), and the point mass at otherwise.
Play against a script. For a behavioural strategy , a current sequence and an opponent script (a fixed finite list of moves, chosen in advance and not reacting to 's moves), the outcome distribution on finite sequences is defined recursively:
- if is empty, the outcome is with probability ;
- if and is -labelled and : draw ; if the outcome is (the rest of the script is discarded); if , continue with ;
- otherwise (the next script move is -labelled or illegal) the outcome is and the rest of the script is discarded.
The theorem uses only , i.e. play from the empty sequence.
Statement. Let be a game whose move type is finite, and suppose there is with for every . Then both of the following hold:
- For every behavioural strategy on there exists a probability distribution on the set of strategies on such that for every script and every finite sequence ,
- For every probability distribution on strategies on there exists a behavioural strategy on such that the same identity holds for every script and every finite sequence .
In both parts the witness (, resp. ) is chosen once and must work uniformly for all scripts and outcomes . The values are in and the sum is over all strategies (an unordered possibly infinite sum).
Degenerate cases. If (or has no -labelled move that starts a position), every outcome is with probability and both parts are trivially satisfied. Scripts whose first move is -labelled or not a legal opening yield outcome for every strategy. Under the hypotheses the set of positions is finite, so there are only finitely many strategies. The values of on sequences that are not positions never influence .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.