Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Tensor of behaviour strategies; never-stopping strategies; open games

Definition
AJGames_BehTensor

by martelus trismortuus · Nov 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

game-semanticsonline-algorithms

For behaviour strategies βA\beta_AβA​ on AAA and βB\beta_BβB​ on BBB, the behaviour strategy βA⊗βB\beta_A\otimes\beta_BβA​⊗βB​ on A⊗BA\otimes BA⊗B answers in the component of the last move.

  • If the last move is in AAA, it draws from βA(s↾A)\beta_A(s{\restriction}A)βA​(s↾A) and embeds the result in the left component.
  • If the last move is in BBB, it does the same with βB(s↾B)\beta_B(s{\restriction}B)βB​(s↾B) in the right component.
  • At the empty play it chooses none\mathrm{none}none.

The file proves that this satisfies the legality conditions of a behaviour strategy.

The file also defines two conditions:

  1. β\betaβ is never-stopping if, at every position where Player is to move, none\mathrm{none}none has probability 000;
  2. 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.

Definition code
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
Source
S. Abramsky, R. Jagadeesan, Games and full completeness for multiplicative linear logic, J. Symbolic Logic 59(2) (1994) 543-574, https://arxiv.org/abs/1311.6057, §3.3 (tensor of strategies), here for behaviour strategies in the sense of H. W. Kuhn, Extensive games and the problem of information, Contributions to the Theory of Games II, Annals of Mathematics Studies 28 (1953) 193-216
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 AAA: move type MAM_AMA​, labelling λA:MA→{P,O}\lambda_A : M_A \to \{P, O\}λA​:MA​→{P,O}, set posA\mathrm{pos}_AposA​ of finite move sequences containing the empty play ε\varepsilonε, prefix-closed, every position alternating (consecutive moves have different labels; no requirement that the first move is OOO).

Tensor A⊗BA \otimes BA⊗B: moves are the disjoint union MA⊔MBM_A \sqcup M_BMA​⊔MB​ (left moves inl(x)\mathrm{inl}(x)inl(x), right moves inr(y)\mathrm{inr}(y)inr(y)), labels inherited from the component. A sequence sss is a position of A⊗BA \otimes BA⊗B iff (i) every pair of consecutive moves m,m′m, m'm,m′ satisfies λ(m)≠λ(m′)\lambda(m) \neq \lambda(m')λ(m)=λ(m′) and (m,m′m, m'm,m′ lie in the same component, or λ(m′)=O\lambda(m') = Oλ(m′)=O) — so a switch of component can only happen at an OOO-move; (ii) the left projection s∣As|_As∣A​ (the subsequence of left moves) is in posA\mathrm{pos}_AposA​; (iii) the right projection s∣Bs|_Bs∣B​ is in posB\mathrm{pos}_BposB​.

PlayerToMoveA(s)_A(s)A​(s): sss is non-empty and its last move has label OOO (false at ε\varepsilonε).

Behavioural strategy β\betaβ on AAA: a map nextβ\mathrm{next}_\betanextβ​ from all finite sequences (position or not) to probability distributions on MA∪{none}M_A \cup \{\mathrm{none}\}MA​∪{none}, such that positive mass on a move aaa at sss implies: PlayerToMoveA(s)\mathrm{PlayerToMove}_A(s)PlayerToMoveA​(s), λA(a)=P\lambda_A(a) = PλA​(a)=P, and (s∈posA⇒s⋅a∈posAs \in \mathrm{pos}_A \Rightarrow s\cdot a \in \mathrm{pos}_As∈posA​⇒s⋅a∈posA​). Mass on none is unconstrained; at ε\varepsilonε and after a PPP-move all mass is on none.

A,BA, BA,B below are arbitrary games in the same universe.

BehStrategy.NonStop

β\betaβ is non-stopping iff for every position s∈posAs \in \mathrm{pos}_As∈posA​ with PlayerToMoveA(s)\mathrm{PlayerToMove}_A(s)PlayerToMoveA​(s) (non-empty, last move OOO), nextβ(s)(none)=0\mathrm{next}_\beta(s)(\mathrm{none}) = 0nextβ​(s)(none)=0. So at such positions all mass is on moves, which by legality are PPP-moves extending sss to positions. In particular at such a position there must exist at least one legal PPP-reply; if some position ending in an OOO-move has no PPP-extension, no behavioural strategy on AAA is non-stopping. Nothing is required at non-positions, at ε\varepsilonε, or after PPP-moves.

OpenToOpponent

A game AAA is open to the opponent iff for every position s∈posAs \in \mathrm{pos}_As∈posA​ that is not PlayerToMoveA\mathrm{PlayerToMove}_APlayerToMoveA​ (i.e. s=εs = \varepsilons=ε or sss ends with a PPP-move) and every move mmm with λA(m)=O\lambda_A(m) = OλA​(m)=O, s⋅m∈posAs \cdot m \in \mathrm{pos}_As⋅m∈posA​. At s=εs = \varepsilons=ε this says every OOO-labelled move is a legal first move. If AAA has no OOO-labelled moves the condition is vacuous.

tensorBNext

For behavioural strategies βA\beta_AβA​ on AAA, βB\beta_BβB​ on BBB and a sequence sss over MA⊔MBM_A \sqcup M_BMA​⊔MB​, the distribution tensorBNext(βA,βB)(s)\mathrm{tensorBNext}(\beta_A, \beta_B)(s)tensorBNext(βA​,βB​)(s) on (MA⊔MB)∪{none}(M_A \sqcup M_B) \cup \{\mathrm{none}\}(MA​⊔MB​)∪{none} is determined by the last move of sss only through its component:

  • last move is a left move: the push-forward of nextβA(s∣A)\mathrm{next}_{\beta_A}(s|_A)nextβA​​(s∣A​) under a↦inl(a)a \mapsto \mathrm{inl}(a)a↦inl(a), none↦none\mathrm{none} \mapsto \mathrm{none}none↦none;
  • last move is a right move: the push-forward of nextβB(s∣B)\mathrm{next}_{\beta_B}(s|_B)nextβB​​(s∣B​) under b↦inr(b)b \mapsto \mathrm{inr}(b)b↦inr(b), none↦none\mathrm{none} \mapsto \mathrm{none}none↦none;
  • s=εs = \varepsilons=ε: 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 PPP-move in AAA, then s∣As|_As∣A​ ends in that PPP-move, so βA\beta_AβA​ (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 sss over MA⊔MBM_A \sqcup M_BMA​⊔MB​ and m∈MAm \in M_Am∈MA​: if the last move of sss is inl(m)\mathrm{inl}(m)inl(m), then the last move of s∣As|_As∣A​ is mmm. Symmetrically, if the last move of sss is inr(m)\mathrm{inr}(m)inr(m) with m∈MBm \in M_Bm∈MB​, the last move of s∣Bs|_Bs∣B​ is mmm.

tensorBNext_legal (theorem)

For all βA,βB\beta_A, \beta_BβA​,βB​, every sequence sss over MA⊔MBM_A \sqcup M_BMA​⊔MB​ and every move aaa: if tensorBNext(βA,βB)(s)(a)≠0\mathrm{tensorBNext}(\beta_A,\beta_B)(s)(a) \neq 0tensorBNext(βA​,βB​)(s)(a)=0 then (1) PlayerToMoveA⊗B(s)\mathrm{PlayerToMove}_{A\otimes B}(s)PlayerToMoveA⊗B​(s); (2) λA⊗B(a)=P\lambda_{A\otimes B}(a) = PλA⊗B​(a)=P; (3) if s∈posA⊗Bs \in \mathrm{pos}_{A \otimes B}s∈posA⊗B​ then s⋅a∈posA⊗Bs\cdot a \in \mathrm{pos}_{A\otimes B}s⋅a∈posA⊗B​. This is exactly the legality condition for a behavioural strategy on A⊗BA \otimes BA⊗B.

tensorB

tensorB(βA,βB)\mathrm{tensorB}(\beta_A, \beta_B)tensorB(βA​,βB​) is the behavioural strategy on A⊗BA \otimes BA⊗B whose next-move distribution is tensorBNext(βA,βB)\mathrm{tensorBNext}(\beta_A,\beta_B)tensorBNext(βA​,βB​) 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.

Human review
  • Endorsed by Shuze Chen · Nov 18, 2026

    Confirmed by the moderator at approval.

  • Endorsed by martelus trismortuus · Nov 18, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me