Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Strategies in AJ games and the tensor of strategies

Definition
AJGames_Strategy

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

game-semanticsonline-algorithms

A strategy σ\sigmaσ for Player in AAA is a set of positions of AAA satisfying five conditions:

  1. it contains the empty sequence;
  2. it is prefix-closed;
  3. Opponent opens: every nonempty element starts with an Opponent move;
  4. it is deterministic: if sasasa and sbsbsb are in σ\sigmaσ with a,ba,ba,b Player moves, then a=ba=ba=b;
  5. it is receptive: if s∈σs\in\sigmas∈σ, aaa is an Opponent move and sasasa is a position, then sa∈σsa\in\sigmasa∈σ.

For strategies σ\sigmaσ on AAA and τ\tauτ on BBB, the tensor σ⊗τ\sigma\otimes\tauσ⊗τ is the set of positions sss of A⊗BA\otimes BA⊗B with s↾A∈σs{\restriction}A\in\sigmas↾A∈σ and s↾B∈τs{\restriction}B\in\taus↾B∈τ; the file proves that it is again a strategy.

The tensor of strategies runs two strategies side by side; the online-algorithm milestones about the tensor are stated for it.

Formalization Note That σ⊗τ\sigma\otimes\tauσ⊗τ is deterministic uses the tensor's switching rule: a Player move stays in the component of the move before it.

Definition code
import Mathlib
import Definitions.Def_AJGames_Game
import Definitions.Def_AJGames_Tensor

/-!
# Strategies in Abramsky–Jagadeesan games, and their tensor

Abramsky and Jagadeesan, *Games and Full Completeness for Multiplicative Linear Logic*,
J. Symbolic Logic 59(2) (1994), 543–574: Definition 3 (strategies) and §3.3 (tensor of strategies,
`σ ⊗ τ = {s ∈ P_{A⊗B} | s↾A ∈ σ, s↾B ∈ τ}`).

**Formalization Note.** Finite-play (safety) fragment: winning conditions on infinite plays are
omitted. That `σ ⊗ τ` is again a strategy uses that in a tensor only Opponent switches component,
so a Player move stays in the component of the move before it.
-/

namespace AJGames

universe u

open Game

/-- A strategy for Player in `A` (Definition 3): non-empty, prefix-closed, a subset of the
positions, with Opponent opening, determinism on Player moves, and receptiveness to Opponent moves. -/
structure Strategy (A : Game.{u}) where
  carrier : Set (List A.M)
  nil_mem : [] ∈ carrier
  subset_pos : carrier ⊆ A.pos
  prefix_closed : ∀ s t : List A.M, s <+: t → t ∈ carrier → s ∈ carrier
  first_O : ∀ a s, a :: s ∈ carrier → A.lab a = Pl.O
  deterministic : ∀ s a b, s ++ [a] ∈ carrier → s ++ [b] ∈ carrier →
    A.lab a = Pl.P → A.lab b = Pl.P → a = b
  receptive : ∀ s a, s ∈ carrier → A.lab a = Pl.O → s ++ [a] ∈ A.pos → s ++ [a] ∈ carrier

section Proj

variable {α β : Type u}

theorem projL_append (s t : List (α ⊕ β)) : projL (s ++ t) = projL s ++ projL t := by
  simp [projL, List.filterMap_append]
theorem projR_append (s t : List (α ⊕ β)) : projR (s ++ t) = projR s ++ projR t := by
  simp [projR, List.filterMap_append]
@[simp] theorem projL_nil' : projL ([] : List (α ⊕ β)) = [] := rfl
@[simp] theorem projR_nil' : projR ([] : List (α ⊕ β)) = [] := rfl
@[simp] theorem projL_cons_inl (a : α) (s : List (α ⊕ β)) : projL (Sum.inl a :: s) = a :: projL s := by
  simp [projL]
@[simp] theorem projL_cons_inr (b : β) (s : List (α ⊕ β)) : projL (Sum.inr b :: s) = projL s := by
  simp [projL, List.filterMap_cons, Sum.getLeft?]
@[simp] theorem projR_cons_inl (a : α) (s : List (α ⊕ β)) : projR (Sum.inl a :: s) = projR s := by
  simp [projR, List.filterMap_cons, Sum.getRight?]
@[simp] theorem projR_cons_inr (b : β) (s : List (α ⊕ β)) : projR (Sum.inr b :: s) = b :: projR s := by
  simp [projR]
theorem projL_snoc_inl (s : List (α ⊕ β)) (x : α) : projL (s ++ [Sum.inl x]) = projL s ++ [x] := by
  simp [projL_append]
theorem projL_snoc_inr (s : List (α ⊕ β)) (y : β) : projL (s ++ [Sum.inr y]) = projL s := by
  simp [projL_append]
theorem projR_snoc_inl (s : List (α ⊕ β)) (x : α) : projR (s ++ [Sum.inl x]) = projR s := by
  simp [projR_append]
theorem projR_snoc_inr (s : List (α ⊕ β)) (y : β) : projR (s ++ [Sum.inr y]) = projR s ++ [y] := by
  simp [projR_append]

end Proj

variable {A B : Game.{u}}

/-- In a tensor sequence, a Player move continues in the component of the move before it. -/
theorem tensor_P_same_component {s : List (A.M ⊕ B.M)} {m a : A.M ⊕ B.M}
    (h : (Game.tensor A B).pos (s ++ [a])) (hm : s.getLast? = some m)
    (ha : Sum.elim A.lab B.lab a = Pl.P) : m.isLeft = a.isLeft := by
  have hch : List.IsChain (TR A.lab B.lab) (s ++ [a]) := h.1
  have hTR : TR A.lab B.lab m a := (List.isChain_append.1 hch).2.2 m hm a (by simp)
  rcases hTR.2 with h' | h'
  · exact h'
  · rw [ha] at h'; cases h'

/-- The tensor of strategies `σ ⊗ τ` (§3.3). -/
def tensorS (σ : Strategy A) (τ : Strategy B) : Strategy (Game.tensor A B) where
  carrier := {s | s ∈ (Game.tensor A B).pos ∧ projL s ∈ σ.carrier ∧ projR s ∈ τ.carrier}
  nil_mem := ⟨(Game.tensor A B).nil_mem, by simpa using σ.nil_mem, by simpa using τ.nil_mem⟩
  subset_pos := fun _ h => h.1
  prefix_closed := by
    intro s t hst ht
    exact ⟨(Game.tensor A B).prefix_closed s t hst ht.1,
      σ.prefix_closed _ _ (hst.filterMap Sum.getLeft?) ht.2.1,
      τ.prefix_closed _ _ (hst.filterMap Sum.getRight?) ht.2.2⟩
  first_O := by
    intro a s h
    cases a with
    | inl x => have := σ.first_O x (projL s) (by simpa using h.2.1); simpa using this
    | inr y => have := τ.first_O y (projR s) (by simpa using h.2.2); simpa using this
  deterministic := by
    intro s a b ha hb hPa hPb
    have hPa' : Sum.elim A.lab B.lab a = Pl.P := hPa
    have hPb' : Sum.elim A.lab B.lab b = Pl.P := hPb
    cases hl : s.getLast? with
    | none =>
      have : s = [] := List.getLast?_eq_none_iff.1 hl
      subst this
      cases a with
      | inl x =>
        have h2 : projL ([] ++ [Sum.inl x]) ∈ σ.carrier := ha.2.1
        have := σ.first_O x [] (by simpa using h2)
        exact absurd (this.symm.trans (show A.lab x = Pl.P from hPa')) (by decide)
      | inr y =>
        have h2 : projR ([] ++ [Sum.inr y]) ∈ τ.carrier := ha.2.2
        have := τ.first_O y [] (by simpa using h2)
        exact absurd (this.symm.trans (show B.lab y = Pl.P from hPa')) (by decide)
    | some m =>
      have e1 := tensor_P_same_component ha.1 hl hPa'
      have e2 := tensor_P_same_component hb.1 hl hPb'
      cases a with
      | inl x =>
        cases b with
        | inl y =>
          have ha2 : projL (s ++ [Sum.inl x]) ∈ σ.carrier := ha.2.1
          have hb2 : projL (s ++ [Sum.inl y]) ∈ σ.carrier := hb.2.1
          rw [projL_snoc_inl] at ha2 hb2
          have := σ.deterministic (projL s) x y ha2 hb2 hPa hPb
          rw [this]
        | inr y => cases m <;> simp_all
      | inr x =>
        cases b with
        | inl y => cases m <;> simp_all
        | inr y =>
          have ha2 : projR (s ++ [Sum.inr x]) ∈ τ.carrier := ha.2.2
          have hb2 : projR (s ++ [Sum.inr y]) ∈ τ.carrier := hb.2.2
          rw [projR_snoc_inr] at ha2 hb2
          have := τ.deterministic (projR s) x y ha2 hb2 hPa hPb
          rw [this]
  receptive := by
    intro s a hs hO hpos
    refine ⟨hpos, ?_, ?_⟩
    · cases a with
      | inl x =>
        have hpos' : projL (s ++ [Sum.inl x]) ∈ A.pos := hpos.2.1
        rw [projL_snoc_inl] at hpos' ⊢
        exact σ.receptive _ x hs.2.1 hO hpos'
      | inr y => rw [projL_snoc_inr]; exact hs.2.1
    · cases a with
      | inl x => rw [projR_snoc_inl]; exact hs.2.2
      | inr y =>
        have hpos' : projR (s ++ [Sum.inr y]) ∈ B.pos := hpos.2.2
        rw [projR_snoc_inr] at hpos' ⊢
        exact τ.receptive _ y hs.2.2 hO hpos'

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.1 Definition 3 (strategies) and §3.3 (tensor of strategies)
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Read-back: Def_AJGames_Strategy

This file uses the notions of the Game and Tensor files:

  • labels Pl={P,O}\mathsf{Pl} = \{P, O\}Pl={P,O};
  • a game AAA with moves MAM_AMA​, move labels λA\lambda_AλA​, and a prefix-closed set posA\mathrm{pos}_AposA​ of alternating finite lists that contains [ ][\,][];
  • for the tensor A⊗BA \otimes BA⊗B: moves MA⊕MBM_A \oplus M_BMA​⊕MB​, labels [λA,λB][\lambda_A, \lambda_B][λA​,λB​], and positions the lists sss such that consecutive moves have different labels and switch side only into an OOO-labelled move, with πL(s)∈posA\pi_L(s) \in \mathrm{pos}_AπL​(s)∈posA​ and πR(s)∈posB\pi_R(s) \in \mathrm{pos}_BπR​(s)∈posB​;
  • πL\pi_LπL​ and πR\pi_RπR​, which keep only the left (respectively right) entries of a list, in order.

All games here are over one universe uuu.

Strategy on AAA. A strategy σ\sigmaσ on a game AAA is a set σ\sigmaσ of finite lists of moves of AAA with the following properties.

  1. The empty list belongs to σ\sigmaσ.
  2. σ⊆posA\sigma \subseteq \mathrm{pos}_Aσ⊆posA​.
  3. σ\sigmaσ is prefix-closed: if t∈σt \in \sigmat∈σ and sss is a prefix of ttt, then s∈σs \in \sigmas∈σ.
  4. First move OOO: every non-empty a::s∈σa :: s \in \sigmaa::s∈σ (first move aaa, then the rest sss) has λA(a)=O\lambda_A(a) = OλA​(a)=O.
  5. Determinacy on PPP-moves: for all lists sss and moves a,ba, ba,b,
s a∈σ,  s b∈σ,  λA(a)=P,  λA(b)=P  ⟹  a=b.s\,a \in \sigma,\; s\,b \in \sigma,\; \lambda_A(a) = P,\; \lambda_A(b) = P \implies a = b.sa∈σ,sb∈σ,λA​(a)=P,λA​(b)=P⟹a=b.
  1. Receptivity to OOO-moves: for every s∈σs \in \sigmas∈σ and every move aaa with λA(a)=O\lambda_A(a) = OλA​(a)=O and s a∈posAs\,a \in \mathrm{pos}_Asa∈posA​, we have s a∈σs\,a \in \sigmasa∈σ.

Here s as\,asa denotes the list sss with the move aaa appended at the end.

The properties combine as follows. Since positions alternate and the first move must be OOO, every non-empty play in σ\sigmaσ has its 1st, 3rd, 5th, … moves labelled OOO and its 2nd, 4th, … moves labelled PPP. Any position of AAA that starts with a PPP-move is excluded from every strategy.

Several things are not imposed:

  • No condition says that a PPP-reply exists. The strategy need not be total. The set of all positions of length at most 111 that start with an OOO-move (together with [ ][\,][]) is always a strategy, so every game has at least one strategy.
  • If no move of AAA is labelled OOO, or no length-one position starts with OOO, then {[ ]}\{[\,]\}{[]} is a strategy.
  • Determinacy concerns only extensions by PPP-moves. Two OOO-extensions of the same sss may both lie in σ\sigmaσ; indeed, receptivity forces every legal OOO-extension in.

Projection lemmas. For lists s,ts, ts,t over α⊕β\alpha \oplus \betaα⊕β and elements a∈αa \in \alphaa∈α, b∈βb \in \betab∈β, the file proves:

  • πL(s+ ⁣ ⁣+t)=πL(s)+ ⁣ ⁣+πL(t)\pi_L(s \mathbin{+\!\!+} t) = \pi_L(s) \mathbin{+\!\!+} \pi_L(t)πL​(s++t)=πL​(s)++πL​(t), and the same for πR\pi_RπR​;
  • πL([ ])=[ ]\pi_L([\,]) = [\,]πL​([])=[] and πR([ ])=[ ]\pi_R([\,]) = [\,]πR​([])=[];
  • πL(inl(a)::s)=a::πL(s)\pi_L(\mathrm{inl}(a) :: s) = a :: \pi_L(s)πL​(inl(a)::s)=a::πL​(s) and πL(inr(b)::s)=πL(s)\pi_L(\mathrm{inr}(b) :: s) = \pi_L(s)πL​(inr(b)::s)=πL​(s);
  • πR(inl(a)::s)=πR(s)\pi_R(\mathrm{inl}(a) :: s) = \pi_R(s)πR​(inl(a)::s)=πR​(s) and πR(inr(b)::s)=b::πR(s)\pi_R(\mathrm{inr}(b) :: s) = b :: \pi_R(s)πR​(inr(b)::s)=b::πR​(s);
  • πL(s inl(a))=πL(s) a\pi_L(s\,\mathrm{inl}(a)) = \pi_L(s)\,aπL​(sinl(a))=πL​(s)a and πL(s inr(b))=πL(s)\pi_L(s\,\mathrm{inr}(b)) = \pi_L(s)πL​(sinr(b))=πL​(s);
  • πR(s inl(a))=πR(s)\pi_R(s\,\mathrm{inl}(a)) = \pi_R(s)πR​(sinl(a))=πR​(s) and πR(s inr(b))=πR(s) b\pi_R(s\,\mathrm{inr}(b)) = \pi_R(s)\,bπR​(sinr(b))=πR​(s)b.

The four π(…::s)\pi(\ldots :: s)π(…::s) identities and the two empty-list identities are registered as simplification rules.

Lemma: a PPP-move stays on the same side. Let A,BA, BA,B be games, sss a list over MA⊕MBM_A \oplus M_BMA​⊕MB​, and m,am, am,a moves. Assume:

  • s as\,asa is a position of A⊗BA \otimes BA⊗B;
  • the last entry of sss is mmm, so sss is non-empty;
  • [λA,λB](a)=P[\lambda_A, \lambda_B](a) = P[λA​,λB​](a)=P.

Then mmm and aaa are on the same side: both are left moves or both are right moves.

Tensor of strategies σ⊗τ\sigma \otimes \tauσ⊗τ. For strategies σ\sigmaσ on AAA and τ\tauτ on BBB,

σ⊗τ={ s  :  s∈posA⊗B,  πL(s)∈σ,  πR(s)∈τ }.\sigma \otimes \tau = \{\, s \;:\; s \in \mathrm{pos}_{A \otimes B},\; \pi_L(s) \in \sigma,\; \pi_R(s) \in \tau \,\}.σ⊗τ={s:s∈posA⊗B​,πL​(s)∈σ,πR​(s)∈τ}.

The file proves that this set satisfies all six strategy conditions on A⊗BA \otimes BA⊗B, so it is a strategy there. That the conditions hold is a proved part of the construction, not an assumption. For instance, determinacy uses the lemma above: two PPP-extensions of a non-empty sss are on the side of the last move of sss. For s=[ ]s = [\,]s=[], determinacy holds vacuously, because a PPP-move cannot be first in either component strategy.

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