Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Behaviour strategies, play probability and play-out against a script

Definition
AJGames_Behaviour

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

game-semanticsonline-algorithms

A behaviour strategy β\betaβ for Player in AAA assigns to every finite sequence sss a probability distribution β(s)\beta(s)β(s) on MA∪{none}M_A\cup\{\mathrm{none}\}MA​∪{none}. A move aaa may have positive probability only if three conditions hold:

  1. Player is to move at sss, meaning the last move of sss is an Opponent move;
  2. aaa is a Player move;
  3. sasasa is a position whenever sss is.

The file defines the following derived notions.

  1. The probability of a play sss is the product, over the Player moves aaa of sss, of the probability β\betaβ gave aaa after the prefix preceding it.
  2. β\betaβ depends on a function fff of histories when f(s)=f(t)f(s)=f(t)f(s)=f(t) implies β(s)=β(t)\beta(s)=\beta(t)β(s)=β(t); history-free is the case where fff returns the last move.
  3. A deterministic strategy σ\sigmaσ is read as a behaviour strategy by putting all mass on σ\sigmaσ's Player move when it has one, and on none\mathrm{none}none otherwise.
  4. The play-out of β\betaβ from a position sss against a script r1,…,rnr_1,\dots,r_nr1​,…,rn​ of moves is a distribution on finite plays. If r1r_1r1​ is an Opponent move and s r1s\,r_1sr1​ is a position, play it and draw from β(s r1)\beta(s\,r_1)β(sr1​). A move continues the play with r2,…,rnr_2,\dots,r_nr2​,…,rn​; none\mathrm{none}none stops it, and s r1s\,r_1sr1​ is the outcome. Otherwise, and when the script is exhausted, the outcome is sss.

The play-out is the semantics of a randomised online algorithm against an oblivious adversary.

Formalization Note Opponent's moves are not randomised; an oblivious adversary fixes them in advance. Distributions are Mathlib PMFs.

Definition code
import Mathlib
import Definitions.Def_AJGames_Strategy

/-!
# Behaviour strategies in Abramsky–Jagadeesan games

A *behaviour strategy* for Player gives, at every position, a probability distribution over Player's
next move, or `none` (no move). This is Kuhn's notion of behaviour strategy (H. W. Kuhn,
*Extensive games and the problem of information*, Contributions to the Theory of Games II, 1953)
placed on AJ games (Abramsky and Jagadeesan, J. Symbolic Logic 59(2), 1994, Definition 2). It is the
form in which randomised online algorithms, such as memoryless policies, appear as strategies.

**Formalization Note.** Finite-play (safety) fragment. Opponent moves are not randomised: an
oblivious adversary fixes them. `playProb β s` is the probability that Player, following `β`, makes
every Player move of `s` when Opponent plays the Opponent moves of `s`. A deterministic strategy
`σ` is read as the behaviour strategy `ofStrategy σ`, which puts all its mass on `σ`'s move when
`σ` has one and on `none` otherwise.
-/

namespace AJGames

universe u

open scoped ENNReal

variable {A : Game.{u}}

/-- Player is to move at `s`: the last move of `s` was an Opponent move. Opponent opens, so
Player is not to move at `[]`. -/
def PlayerToMove (A : Game.{u}) (s : List A.M) : Prop :=
  ∃ m, s.getLast? = some m ∧ A.lab m = Pl.O

/-- A behaviour strategy for Player in `A`: a distribution over Player's next move (or `none`) at
every position. Moves in the support are legal Player moves, offered only when Player is to move. -/
structure BehStrategy (A : Game.{u}) where
  next : List A.M → PMF (Option A.M)
  legal : ∀ s a, next s (some a) ≠ 0 →
    PlayerToMove A s ∧ A.lab a = Pl.P ∧ (s ∈ A.pos → s ++ [a] ∈ A.pos)

/-- Probability of a play, computed on the reversed play (last move first). -/
noncomputable def playProbRev (β : BehStrategy A) : List A.M → ℝ≥0∞
  | [] => 1
  | a :: r => playProbRev β r * (if A.lab a = Pl.P then β.next r.reverse (some a) else 1)

/-- The probability that Player, following `β`, makes every Player move of `s` when Opponent
plays the Opponent moves of `s`: the product of `β`'s probabilities of its own moves. -/
noncomputable def playProb (β : BehStrategy A) (s : List A.M) : ℝ≥0∞ :=
  playProbRev β s.reverse

/-- `β` is history-free: its next-move distribution depends only on the last move. -/
def BehStrategy.HistoryFree (β : BehStrategy A) : Prop :=
  ∀ s t : List A.M, s.getLast? = t.getLast? → β.next s = β.next t

/-- `β` depends on the history only through `f`. `HistoryFree` is the case `f = List.getLast?`;
a memoryless online policy depends on (current configuration, last request). -/
def BehStrategy.DependsOn {S : Type*} (β : BehStrategy A) (f : List A.M → S) : Prop :=
  ∀ s t : List A.M, f s = f t → β.next s = β.next t

/-- If `σ` has a Player move at `s`, then Player is to move at `s`. -/
theorem Strategy.playerToMove_of_move (σ : Strategy A) {s : List A.M} {b : A.M}
    (hb : s ++ [b] ∈ σ.carrier) (hP : A.lab b = Pl.P) : PlayerToMove A s := by
  cases hl : s.getLast? with
  | none =>
    have : s = [] := List.getLast?_eq_none_iff.1 hl
    subst this
    have := σ.first_O b [] (by simpa using hb)
    rw [hP] at this; cases this
  | some m =>
    refine ⟨m, hl, ?_⟩
    have halt := A.alt _ (σ.subset_pos hb)
    have hne : A.lab m ≠ A.lab b := (List.isChain_append.1 halt).2.2 m hl b (by simp)
    rw [hP] at hne
    cases h : A.lab m
    · exact absurd h hne
    · rfl

open Classical in
/-- A deterministic strategy read as a behaviour strategy: all mass on `σ`'s move when it has one,
otherwise on `none`. -/
noncomputable def ofStrategy (σ : Strategy A) : BehStrategy A where
  next s := if h : ∃ b, s ++ [b] ∈ σ.carrier ∧ A.lab b = Pl.P then PMF.pure (some h.choose)
    else PMF.pure none
  legal := by
    intro s a ha
    by_cases h : ∃ b, s ++ [b] ∈ σ.carrier ∧ A.lab b = Pl.P
    · rw [dif_pos h, PMF.pure_apply] at ha
      have hab : some a = some h.choose := by
        by_contra hne; exact ha (if_neg hne)
      cases hab
      obtain ⟨hmem, hP⟩ := h.choose_spec
      exact ⟨σ.playerToMove_of_move hmem hP, hP, fun _ => σ.subset_pos hmem⟩
    · rw [dif_neg h, PMF.pure_apply] at ha
      exact absurd (if_neg (by simp)) ha

open Classical in
/-- **Play-out against an oblivious adversary** (stop-counts semantics). From position `s`, the
adversary's remaining script is `rs`. The next request `r` is played if it is a legal Opponent move;
Player then draws from `β.next`. A move `a` continues the play; `none` stops it, and the play so far
is an outcome with that probability. The play also stops when the script runs out or the next
request is not a legal Opponent move. -/
noncomputable def playOut (β : BehStrategy A) : List A.M → List A.M → PMF (List A.M)
  | s, [] => PMF.pure s
  | s, r :: rs =>
    if A.lab r = Pl.O ∧ s ++ [r] ∈ A.pos then
      (β.next (s ++ [r])).bind fun o =>
        o.elim (PMF.pure (s ++ [r])) fun a => playOut β (s ++ [r] ++ [a]) rs
    else PMF.pure s

end AJGames
Source
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 (behaviour strategies), placed on the games of 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
Read-back

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

Read-back: Def_AJGames_Behaviour

Background (from the context files)

A game AAA consists of a type of moves MAM_AMA​, a labelling λA:MA→{P,O}\lambda_A : M_A \to \{P, O\}λA​:MA​→{P,O}, and a set posA\mathrm{pos}_AposA​ of finite sequences of moves (the positions) such that: the empty sequence ε\varepsilonε is a position; every prefix of a position is a position; and every position is alternating, i.e. any two consecutive moves in it have different labels. Nothing requires the first move of a position to have label OOO.

A (deterministic) strategy σ\sigmaσ on AAA is a set σ⊆posA\sigma \subseteq \mathrm{pos}_Aσ⊆posA​ of positions which contains ε\varepsilonε, is prefix-closed, in which every non-empty play starts with an OOO-labelled move, which is deterministic (if s⋅a∈σs\cdot a \in \sigmas⋅a∈σ and s⋅b∈σs \cdot b \in \sigmas⋅b∈σ with λ(a)=λ(b)=P\lambda(a) = \lambda(b) = Pλ(a)=λ(b)=P, then a=ba = ba=b), and receptive (if s∈σs \in \sigmas∈σ, λ(a)=O\lambda(a) = Oλ(a)=O and s⋅a∈posAs\cdot a \in \mathrm{pos}_As⋅a∈posA​, then s⋅a∈σs \cdot a \in \sigmas⋅a∈σ). Plays in σ\sigmaσ may end on an OOO-move with no PPP-answer in σ\sigmaσ.

Throughout, AAA is an arbitrary game (in a fixed universe). "Sequence" below means an arbitrary finite list of moves of AAA, not necessarily a position. s⋅as \cdot as⋅a is sss with aaa appended; last(s)\mathrm{last}(s)last(s) is the last move of sss if s≠εs \neq \varepsilons=ε and undefined ("none") if s=εs = \varepsilons=ε.

PlayerToMove

For a game AAA and a sequence sss, PlayerToMoveA(s)\mathrm{PlayerToMove}_A(s)PlayerToMoveA​(s) holds iff sss is non-empty and its last move has label OOO:

PlayerToMoveA(s)  ⟺  ∃m, last(s)=m ∧ λA(m)=O.\mathrm{PlayerToMove}_A(s) \iff \exists m,\ \mathrm{last}(s) = m \ \wedge\ \lambda_A(m) = O.PlayerToMoveA​(s)⟺∃m, last(s)=m ∧ λA​(m)=O.

It is false at the empty play ε\varepsilonε, and false whenever sss ends with a PPP-move. It does not require s∈posAs \in \mathrm{pos}_As∈posA​.

BehStrategy (behavioural strategy)

A behavioural strategy β\betaβ on AAA consists of:

  • a map nextβ\mathrm{next}_\betanextβ​ assigning to every finite sequence sss of moves (position or not) a probability distribution nextβ(s)\mathrm{next}_\beta(s)nextβ​(s) on MA∪{none}M_A \cup \{\mathrm{none}\}MA​∪{none} (a probability mass function on the option type, total mass 111);
  • a legality condition: for every sequence sss and every move aaa, if nextβ(s)(a)≠0\mathrm{next}_\beta(s)(a) \neq 0nextβ​(s)(a)=0 then
    1. PlayerToMoveA(s)\mathrm{PlayerToMove}_A(s)PlayerToMoveA​(s) (so sss is non-empty and ends with an OOO-move),
    2. λA(a)=P\lambda_A(a) = PλA​(a)=P, and
    3. if s∈posAs \in \mathrm{pos}_As∈posA​ then s⋅a∈posAs \cdot a \in \mathrm{pos}_As⋅a∈posA​.

The value "none" represents not moving (stopping). There is no constraint on the mass placed on none: it may be anything from 000 to 111 at any sss. Consequences of the condition: at the empty play ε\varepsilonε, and at every sequence ending with a PPP-move, nextβ(s)\mathrm{next}_\beta(s)nextβ​(s) is the point mass on none. For sequences s∉posAs \notin \mathrm{pos}_As∈/posA​ ending in an OOO-move, positive mass may sit on any PPP-labelled move with no positional constraint.

playProbRev and playProb

playProbRevβ\mathrm{playProbRev}_\betaplayProbRevβ​ is defined by recursion on a list written in reverse order (most recent move first), with values in [0,∞][0, \infty][0,∞]:

playProbRevβ(ε)=1,playProbRevβ(a::r)=playProbRevβ(r)⋅{nextβ(rev(r))(a)λA(a)=P,1λA(a)=O.\mathrm{playProbRev}_\beta(\varepsilon) = 1,\qquad \mathrm{playProbRev}_\beta(a :: r) = \mathrm{playProbRev}_\beta(r)\cdot \begin{cases}\mathrm{next}_\beta(\mathrm{rev}(r))(a) & \lambda_A(a) = P,\\ 1 & \lambda_A(a) = O.\end{cases}playProbRevβ​(ε)=1,playProbRevβ​(a::r)=playProbRevβ​(r)⋅{nextβ​(rev(r))(a)1​λA​(a)=P,λA​(a)=O.​

Then playProbβ(s)=playProbRevβ(rev(s))\mathrm{playProb}_\beta(s) = \mathrm{playProbRev}_\beta(\mathrm{rev}(s))playProbβ​(s)=playProbRevβ​(rev(s)). Unfolded, for s=s1s2⋯sns = s_1 s_2 \cdots s_ns=s1​s2​⋯sn​:

playProbβ(s)=∏1≤i≤nλA(si)=Pnextβ(s1⋯si−1)(si).\mathrm{playProb}_\beta(s) = \prod_{\substack{1 \le i \le n \\ \lambda_A(s_i) = P}} \mathrm{next}_\beta(s_1 \cdots s_{i-1})(s_i).playProbβ​(s)=1≤i≤nλA​(si​)=P​∏​nextβ​(s1​⋯si−1​)(si​).

OOO-moves contribute factor 111; the empty play has probability 111; a sequence with no PPP-moves has probability 111. No membership in posA\mathrm{pos}_AposA​ is checked, and no factor accounts for stopping (mass on none is never used).

BehStrategy.HistoryFree

β\betaβ is history-free iff for all sequences s,ts, ts,t with last(s)=last(t)\mathrm{last}(s) = \mathrm{last}(t)last(s)=last(t) (where both being empty counts as equal, and a non-empty sequence never matches an empty one), nextβ(s)=nextβ(t)\mathrm{next}_\beta(s) = \mathrm{next}_\beta(t)nextβ​(s)=nextβ​(t). The condition ranges over all sequences, not only positions.

BehStrategy.DependsOn

For any type SSS and any function fff from sequences to SSS, β\betaβ depends on fff iff for all sequences s,ts, ts,t, f(s)=f(t)f(s) = f(t)f(s)=f(t) implies nextβ(s)=nextβ(t)\mathrm{next}_\beta(s) = \mathrm{next}_\beta(t)nextβ​(s)=nextβ​(t) (i.e. nextβ\mathrm{next}_\betanextβ​ factors through fff). For constant fff this forces nextβ\mathrm{next}_\betanextβ​ to be constant, hence (by legality at ε\varepsilonε) everywhere the point mass on none.

Strategy.playerToMove_of_move (theorem)

For every strategy σ\sigmaσ on AAA, every sequence sss and every move bbb: if s⋅b∈σs \cdot b \in \sigmas⋅b∈σ and λA(b)=P\lambda_A(b) = PλA​(b)=P, then PlayerToMoveA(s)\mathrm{PlayerToMove}_A(s)PlayerToMoveA​(s), i.e. sss is non-empty and its last move has label OOO.

ofStrategy

Given a strategy σ\sigmaσ on AAA, ofStrategy(σ)\mathrm{ofStrategy}(\sigma)ofStrategy(σ) is the behavioural strategy with

next(s)={δb∗if ∃b, s⋅b∈σ∧λA(b)=P,δnoneotherwise,\mathrm{next}(s) = \begin{cases} \delta_{b^*} & \text{if } \exists b,\ s\cdot b \in \sigma \wedge \lambda_A(b) = P,\\ \delta_{\mathrm{none}} & \text{otherwise,}\end{cases}next(s)={δb∗​δnone​​if ∃b, s⋅b∈σ∧λA​(b)=P,otherwise,​

where b∗b^*b∗ is a witness selected by the axiom of choice among such bbb (by determinism of σ\sigmaσ the witness is in fact unique), and δ\deltaδ denotes a point mass. Thus it is deterministic; it stops (none) at every sss where σ\sigmaσ has no PPP-extension, including s=εs = \varepsilons=ε, sequences ending with a PPP-move, sequences not in σ\sigmaσ, and plays in σ\sigmaσ ending with an OOO-move that σ\sigmaσ leaves unanswered. Legality holds by the theorem above and σ⊆posA\sigma \subseteq \mathrm{pos}_Aσ⊆posA​.

playOut

playOutβ(s,rs)\mathrm{playOut}_\beta(s, rs)playOutβ​(s,rs), for a current sequence sss and a finite list rsrsrs of moves (an opponent script fixed in advance), is a probability distribution on finite sequences, defined by recursion on rsrsrs:

  • playOutβ(s,ε)=δs\mathrm{playOut}_\beta(s, \varepsilon) = \delta_splayOutβ​(s,ε)=δs​.
  • playOutβ(s,r::rs′)\mathrm{playOut}_\beta(s, r :: rs')playOutβ​(s,r::rs′):
    • if λA(r)=O\lambda_A(r) = OλA​(r)=O and s⋅r∈posAs \cdot r \in \mathrm{pos}_As⋅r∈posA​: draw o∼nextβ(s⋅r)o \sim \mathrm{next}_\beta(s\cdot r)o∼nextβ​(s⋅r); if o=noneo = \mathrm{none}o=none, the result is δs⋅r\delta_{s \cdot r}δs⋅r​ (the play stops after rrr and the rest rs′rs'rs′ of the script is discarded); if o=ao = ao=a, continue with playOutβ(s⋅r⋅a,rs′)\mathrm{playOut}_\beta(s\cdot r \cdot a, rs')playOutβ​(s⋅r⋅a,rs′);
    • otherwise (if rrr is PPP-labelled or s⋅rs \cdot rs⋅r is not a position) the result is δs\delta_sδs​: rrr and the rest of the script are discarded and the play stops at sss.

Remarks: the script entries are not adapted to the random replies; an entry that is illegal after a particular reply stops the play there. No check that s⋅r⋅a∈posAs\cdot r\cdot a \in \mathrm{pos}_As⋅r⋅a∈posA​ is made in the recursion (legality of β\betaβ supplies it when s⋅rs\cdot rs⋅r is a position). The starting sss itself is not checked to be a position. Outcomes can end on a PPP-reply (script exhausted after a reply), on an OOO-move (stop by none), or earlier (illegal or PPP-labelled script entry). With rs=εrs = \varepsilonrs=ε the outcome is sss with probability 111.

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