Tensor of behaviour strategies; never-stopping strategies; open games
DefinitionAJGames_BehTensorFor behaviour strategies on and on , the behaviour strategy on answers in the component of the last move.
- If the last move is in , it draws from and embeds the result in the left component.
- If the last move is in , it does the same with in the right component.
- At the empty play it chooses .
The file proves that this satisfies the legality conditions of a behaviour strategy.
The file also defines two conditions:
- is never-stopping if, at every position where Player is to move, has probability ;
- a game is open to Opponent if, at every position where Player is not to move, every Opponent move extends it to a position.
These are the hypotheses of the randomised tensor milestone.
import Mathlib
import Definitions.Def_AJGames_Behaviour
/-!
# Tensor of behaviour strategies
Two behaviour strategies played side by side in `A ⊗ B` (Abramsky and Jagadeesan,
J. Symbolic Logic 59(2), 1994, §3.3, tensor of strategies, here for Kuhn behaviour strategies). In
`A ⊗ B` only Opponent switches component, so Player always answers in the component of the last
move, using that component's strategy on the restriction of the play to it.
Also: `NonStop` (the strategy never chooses `none` when Player is to move at a position) and
`OpenToOpponent` (Opponent may always play any of its moves when it is Opponent's turn).
-/
namespace AJGames
universe u
open scoped ENNReal
variable {A B : Game.{u}}
/-- `β` never stops: at every position where Player is to move, `none` has probability `0`. -/
def BehStrategy.NonStop (β : BehStrategy A) : Prop :=
∀ s ∈ A.pos, PlayerToMove A s → β.next s none = 0
/-- Opponent may always play any of its moves when it is Opponent's turn. -/
def OpenToOpponent (A : Game.{u}) : Prop :=
∀ s ∈ A.pos, ¬ PlayerToMove A s → ∀ m, A.lab m = Pl.O → s ++ [m] ∈ A.pos
/-- Next-move distribution of `βA ⊗ βB`: answer in the component of the last move. -/
noncomputable def tensorBNext (βA : BehStrategy A) (βB : BehStrategy B) (s : List (A.M ⊕ B.M)) :
PMF (Option (A.M ⊕ B.M)) :=
match s.getLast? with
| some (Sum.inl _) => (βA.next (projL s)).map (Option.map Sum.inl)
| some (Sum.inr _) => (βB.next (projR s)).map (Option.map Sum.inr)
| none => PMF.pure none
theorem getLast_projL_of_inl {s : List (A.M ⊕ B.M)} {m : A.M} (h : s.getLast? = some (Sum.inl m)) :
(projL s).getLast? = some m := by
obtain ⟨t, rfl⟩ : ∃ t, s = t ++ [Sum.inl m] := List.getLast?_eq_some_iff.1 h
simp [projL_snoc_inl]
theorem getLast_projR_of_inr {s : List (A.M ⊕ B.M)} {m : B.M} (h : s.getLast? = some (Sum.inr m)) :
(projR s).getLast? = some m := by
obtain ⟨t, rfl⟩ : ∃ t, s = t ++ [Sum.inr m] := List.getLast?_eq_some_iff.1 h
simp [projR_snoc_inr]
theorem tensorBNext_legal (βA : BehStrategy A) (βB : BehStrategy B) (s : List (A.M ⊕ B.M))
(a : A.M ⊕ B.M) (ha : tensorBNext βA βB s (some a) ≠ 0) :
PlayerToMove (Game.tensor A B) s ∧ (Game.tensor A B).lab a = Pl.P ∧
(s ∈ (Game.tensor A B).pos → s ++ [a] ∈ (Game.tensor A B).pos) := by
unfold tensorBNext at ha
cases hl : s.getLast? with
| none => simp [hl] at ha
| some m =>
cases m with
| inl m =>
rw [hl] at ha
obtain ⟨o, ho, hoa⟩ := (PMF.mem_support_map_iff _ _ _).1 ((PMF.mem_support_iff _ _).2 ha)
obtain ⟨x, rfl⟩ : ∃ x, o = some x := by
cases o with
| none => simp at hoa
| some x => exact ⟨x, rfl⟩
simp only [Option.map_some, Option.some.injEq] at hoa
subst hoa
obtain ⟨⟨m', hm', hO⟩, hP, hext⟩ := βA.legal _ x ((PMF.mem_support_iff _ _).1 ho)
rw [getLast_projL_of_inl hl] at hm'
cases hm'
refine ⟨⟨Sum.inl m, hl, hO⟩, hP, fun hs => ⟨?_, ?_, ?_⟩⟩
· show List.IsChain _ (s ++ [Sum.inl x])
rw [List.isChain_append]
refine ⟨hs.1, List.isChain_singleton _, ?_⟩
intro y hy z hz
rw [hl] at hy
simp at hy hz
subst hy; subst hz
refine ⟨?_, Or.inl rfl⟩
show A.lab m ≠ A.lab x
rw [hO, hP]; decide
· rw [projL_snoc_inl]; exact hext hs.2.1
· rw [projR_snoc_inl]; exact hs.2.2
| inr m =>
rw [hl] at ha
obtain ⟨o, ho, hoa⟩ := (PMF.mem_support_map_iff _ _ _).1 ((PMF.mem_support_iff _ _).2 ha)
obtain ⟨x, rfl⟩ : ∃ x, o = some x := by
cases o with
| none => simp at hoa
| some x => exact ⟨x, rfl⟩
simp only [Option.map_some, Option.some.injEq] at hoa
subst hoa
obtain ⟨⟨m', hm', hO⟩, hP, hext⟩ := βB.legal _ x ((PMF.mem_support_iff _ _).1 ho)
rw [getLast_projR_of_inr hl] at hm'
cases hm'
refine ⟨⟨Sum.inr m, hl, hO⟩, hP, fun hs => ⟨?_, ?_, ?_⟩⟩
· show List.IsChain _ (s ++ [Sum.inr x])
rw [List.isChain_append]
refine ⟨hs.1, List.isChain_singleton _, ?_⟩
intro y hy z hz
rw [hl] at hy
simp at hy hz
subst hy; subst hz
refine ⟨?_, Or.inl rfl⟩
show B.lab m ≠ B.lab x
rw [hO, hP]; decide
· rw [projL_snoc_inr]; exact hs.2.1
· rw [projR_snoc_inr]; exact hext hs.2.2
/-- The tensor `βA ⊗ βB` of behaviour strategies. -/
noncomputable def tensorB (βA : BehStrategy A) (βB : BehStrategy B) :
BehStrategy (Game.tensor A B) where
next := tensorBNext βA βB
legal := tensorBNext_legal βA βB
end AJGames
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Read-back: Def_AJGames_BehTensor
Background (from the context files)
A game : move type , labelling , set of finite move sequences containing the empty play , prefix-closed, every position alternating (consecutive moves have different labels; no requirement that the first move is ).
Tensor : moves are the disjoint union (left moves , right moves ), labels inherited from the component. A sequence is a position of iff (i) every pair of consecutive moves satisfies and ( lie in the same component, or ) — so a switch of component can only happen at an -move; (ii) the left projection (the subsequence of left moves) is in ; (iii) the right projection is in .
PlayerToMove: is non-empty and its last move has label (false at ).
Behavioural strategy on : a map from all finite sequences (position or not) to probability distributions on , such that positive mass on a move at implies: , , and (). Mass on none is unconstrained; at and after a -move all mass is on none.
below are arbitrary games in the same universe.
BehStrategy.NonStop
is non-stopping iff for every position with (non-empty, last move ), . So at such positions all mass is on moves, which by legality are -moves extending to positions. In particular at such a position there must exist at least one legal -reply; if some position ending in an -move has no -extension, no behavioural strategy on is non-stopping. Nothing is required at non-positions, at , or after -moves.
OpenToOpponent
A game is open to the opponent iff for every position that is not (i.e. or ends with a -move) and every move with , . At this says every -labelled move is a legal first move. If has no -labelled moves the condition is vacuous.
tensorBNext
For behavioural strategies on , on and a sequence over , the distribution on is determined by the last move of only through its component:
- last move is a left move: the push-forward of under , ;
- last move is a right move: the push-forward of under , ;
- : the point mass on none.
So the reply is always in the component of the last move, and mass that a component strategy puts on none passes through as none. The label of the last move is not inspected: if the last move is a -move in , then ends in that -move, so (by its legality) puts all mass on none, and so does the tensor.
getLast_projL_of_inl, getLast_projR_of_inr (theorems)
For any sequence over and : if the last move of is , then the last move of is . Symmetrically, if the last move of is with , the last move of is .
tensorBNext_legal (theorem)
For all , every sequence over and every move : if then (1) ; (2) ; (3) if then . This is exactly the legality condition for a behavioural strategy on .
tensorB
is the behavioural strategy on whose next-move distribution is above, with legality supplied by the preceding theorem. No independence or product-measure structure is involved beyond this: at each step only the component of the last move is consulted, with that component's projected history.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.