Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Deterministic strategies embed conservatively into behaviour strategies

Proved
AJGames.ofStrategy_playProb

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

game-semanticsonline-algorithms

Let σ\sigmaσ be a strategy on a game AAA, read as a behaviour strategy. For every position sss of AAA, the probability of sss under it is

Pr⁡(s)={1s∈σ,0s∉σ.\Pr(s)=\begin{cases}1 & s\in\sigma,\\ 0 & s\notin\sigma.\end{cases}Pr(s)={10​s∈σ,s∈/σ.​

So behaviour strategies extend deterministic ones without changing them.

Preamble
import Mathlib
import Definitions.Def_AJGames_Behaviour
Formal statement
namespace AJGames

open scoped ENNReal

universe u

open Classical in
/-- **Behaviour strategies extend deterministic ones conservatively.** Read as a behaviour strategy,
a deterministic strategy `σ` gives every position probability `1` if it lies in `σ` and `0`
otherwise. AJ axioms used: G2 (prefix closure) and G3 (alternation, to see that Player is to move
before a Player move); the strategy axioms first-O, determinism and receptiveness. No tensor axiom. -/
theorem ofStrategy_playProb {A : Game.{u}} (σ : Strategy A) (s : List A.M) (hs : s ∈ A.pos) :
    playProb (ofStrategy σ) s = if s ∈ σ.carrier then 1 else 0 := by sorry

end AJGames
Source
New statement introduced by this mission (no prior source); the notion of behaviour strategy is from 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

Games. Players are PPP and OOO. A game A=(MA,λA,PosA)A=(M_A,\lambda_A,\mathrm{Pos}_A)A=(MA​,λA​,PosA​) has a move type 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 move sequences that contains the empty sequence, is prefix-closed, and whose members alternate (consecutive moves have different labels).

Strategies. A (deterministic) strategy σ\sigmaσ on AAA is a set σ⊆PosA\sigma\subseteq\mathrm{Pos}_Aσ⊆PosA​ of positions such that: ε∈σ\varepsilon\in\sigmaε∈σ (empty sequence); σ\sigmaσ is prefix-closed; every nonempty member of σ\sigmaσ begins with a move labelled OOO; determinism: if sa∈σsa\in\sigmasa∈σ and sb∈σsb\in\sigmasb∈σ with λA(a)=λA(b)=P\lambda_A(a)=\lambda_A(b)=PλA​(a)=λA​(b)=P then a=ba=ba=b; receptivity: if s∈σs\in\sigmas∈σ, λA(a)=O\lambda_A(a)=OλA​(a)=O and sa∈PosAsa\in\mathrm{Pos}_Asa∈PosA​, then sa∈σsa\in\sigmasa∈σ.

Behaviour strategies. A behaviour strategy β\betaβ on AAA assigns to every finite sequence sss (legal or not) a probability distribution βs\beta_sβs​ on MA∪{⊥}M_A\cup\{\bot\}MA​∪{⊥} (⊥\bot⊥ = "no move"), subject to: if βs(a)≠0\beta_s(a)\neq 0βs​(a)=0 then sss is nonempty with last move labelled OOO, λA(a)=P\lambda_A(a)=PλA​(a)=P, and s∈PosA⇒sa∈PosAs\in\mathrm{Pos}_A\Rightarrow sa\in\mathrm{Pos}_As∈PosA​⇒sa∈PosA​.

The play probability of s=(a1,…,an)s=(a_1,\dots,a_n)s=(a1​,…,an​) under β\betaβ is the extended nonnegative real

Pr⁡β(s)  =  ∏1≤i≤nλA(ai)=Pβ(a1,…,ai−1)(ai) ∈[0,∞],\Pr_\beta(s) \;=\; \prod_{\substack{1\le i\le n\\ \lambda_A(a_i)=P}} \beta_{(a_1,\dots,a_{i-1})}(a_i)\ \in[0,\infty],βPr​(s)=1≤i≤nλA​(ai​)=P​∏​β(a1​,…,ai−1​)​(ai​) ∈[0,∞],

i.e. the product, over the PPP-labelled moves of sss, of the probability β\betaβ gives to that move after the preceding prefix; OOO-labelled moves contribute the factor 111, and the empty product (in particular s=εs=\varepsilons=ε) is 111.

The induced behaviour strategy. For a strategy σ\sigmaσ, σ^=ofStrategy(σ)\hat\sigma=\mathrm{ofStrategy}(\sigma)σ^=ofStrategy(σ) is defined by: if there is some bbb with sb∈σsb\in\sigmasb∈σ and λA(b)=P\lambda_A(b)=PλA​(b)=P, then σ^s\hat\sigma_sσ^s​ is the point mass at one such bbb, chosen by the axiom of choice; otherwise σ^s\hat\sigma_sσ^s​ is the point mass at ⊥\bot⊥.

Statement. For every game AAA, every strategy σ\sigmaσ on AAA, and every finite sequence sss of moves with s∈PosAs\in\mathrm{Pos}_As∈PosA​,

Pr⁡σ^(s)  =  {1if s∈σ,0if s∉σ.\Pr_{\hat\sigma}(s) \;=\; \begin{cases} 1 & \text{if } s\in\sigma,\\ 0 & \text{if } s\notin\sigma.\end{cases}σ^Pr​(s)={10​if s∈σ,if s∈/σ.​

The hypothesis s∈PosAs\in\mathrm{Pos}_As∈PosA​ is required; nothing is asserted for illegal sequences. The case s=εs=\varepsilons=ε is included (then s∈σs\in\sigmas∈σ and the value is 111). The membership test "s∈σs\in\sigmas∈σ" is decided classically.

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