Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Randomised tensor of competitive behaviour strategies

Open
AJOnline.rand_tensor_competitive

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

game-semanticsonline-algorithms

Let C,DC,DC,D be costed games whose underlying games are open to Opponent. Let βA\beta_AβA​ on CCC and βB\beta_BβB​ on DDD be never-stopping behaviour strategies, (ρ1,b1)(\rho_1,b_1)(ρ1​,b1​)- and (ρ2,b2)(\rho_2,b_2)(ρ2​,b2​)-randomised-competitive respectively. Then βA⊗βB\beta_A\otimes\beta_BβA​⊗βB​ is

(max⁡(ρ1,ρ2), b1+b2)-randomised-competitive on C⊗D.(\max(\rho_1,\rho_2),\ b_1+b_2)\text{-randomised-competitive on } C\otimes D .(max(ρ1​,ρ2​), b1​+b2​)-randomised-competitive on C⊗D.

This is the randomised counterpart of the deterministic tensor law.

Preamble
import Mathlib
import Definitions.Def_AJOnline_CostedGame
import Definitions.Def_AJGames_BehTensor
Formal statement
namespace AJOnline

open AJGames
open scoped ENNReal NNReal

universe u

/-- **Randomised tensor.** If the behaviour strategies `βA` and `βB` never stop, are `(ρ₁, b₁)`- and
`(ρ₂, b₂)`-competitive against oblivious adversaries, and Opponent may always move in both games,
then `βA ⊗ βB` is `(max ρ₁ ρ₂, b₁ + b₂)`-competitive on `C ⊗ D`. -/
theorem rand_tensor_competitive (C D : CostedGame.{u}) (βA : BehStrategy C.G) (βB : BehStrategy D.G)
    (ρ₁ b₁ ρ₂ b₂ : ℝ≥0) (hA : RandCompetitive C βA ρ₁ b₁) (hB : RandCompetitive D βB ρ₂ b₂)
    (hsA : βA.NonStop) (hsB : βB.NonStop) (hoA : OpenToOpponent C.G) (hoB : OpenToOpponent D.G) :
    RandCompetitive (C.tensor D) (tensorB βA βB) (max ρ₁ ρ₂) (b₁ + b₂) := by sorry

end AJOnline
Source
New statement introduced by this mission (no prior source); randomised counterpart of AJOnline.tensor_competitive
Read-back

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

Read-back of rand_tensor_competitive (expected competitive ratios compose under the tensor of behavioural strategies).

Games. A game GGG has a type of moves MGM_GMG​, a labelling λG:MG→{P,O}\lambda_G : M_G \to \{P, O\}λG​:MG​→{P,O}, and a set PosG\mathrm{Pos}_GPosG​ of finite move sequences containing the empty sequence ε\varepsilonε, prefix-closed, with consecutive moves always differently labelled (positions need not start with OOO). Write LastO(s)\mathrm{Last}_O(s)LastO​(s) for "sss is nonempty and its last move is OOO-labelled" (Lean name PlayerToMove).

Behavioural strategies. A behavioural strategy β\betaβ on GGG assigns to every finite sequence sss a probability distribution β(s)\beta(s)β(s) on MG∪{⊥}M_G \cup \{\bot\}MG​∪{⊥} (⊥\bot⊥ = no move / stop) such that β(s)(a)>0\beta(s)(a) > 0β(s)(a)>0 implies LastO(s)\mathrm{Last}_O(s)LastO​(s), λG(a)=P\lambda_G(a) = PλG​(a)=P, and (s∈PosG⇒sa∈PosGs \in \mathrm{Pos}_G \Rightarrow s a \in \mathrm{Pos}_Gs∈PosG​⇒sa∈PosG​). So β(s)\beta(s)β(s) is the point mass at ⊥\bot⊥ whenever sss is empty or ends with a PPP-move. β\betaβ may depend on the whole history.

Play against a script. An opponent script is a fixed finite list r=(r1,…,rk)r = (r_1,\dots,r_k)r=(r1​,…,rk​) of moves, chosen in advance (it does not react to β\betaβ's moves). The outcome distribution Outβ(s,r)\mathrm{Out}_\beta(s, r)Outβ​(s,r) is: sss with probability 111 if rrr is empty; if r=r1::r′r = r_1 :: r'r=r1​::r′ with r1r_1r1​ OOO-labelled and sr1∈PosGs r_1 \in \mathrm{Pos}_Gsr1​∈PosG​, draw o∼β(sr1)o \sim \beta(s r_1)o∼β(sr1​) and stop at sr1s r_1sr1​ if o=⊥o = \boto=⊥, otherwise continue with Outβ(sr1o,r′)\mathrm{Out}_\beta(s r_1 o, r')Outβ​(sr1​o,r′); in any other case (next script move PPP-labelled or illegal) stop at sss, discarding the rest of the script.

Costs. A costed game CCC is a game GCG_CGC​ with arbitrary functions algC,optC\mathrm{alg}_C, \mathrm{opt}_CalgC​,optC​ from finite sequences to [0,∞][0, \infty][0,∞]. The expected costs of β\betaβ against script rrr are

EalgC(β,r)=∑sPr⁡[Outβ(ε,r)=s] algC(s),EoptC(β,r)=∑sPr⁡[Outβ(ε,r)=s] optC(s),\mathbb{E}\mathrm{alg}_C(\beta, r) = \sum_{s} \Pr[\mathrm{Out}_\beta(\varepsilon, r) = s]\,\mathrm{alg}_C(s),\qquad \mathbb{E}\mathrm{opt}_C(\beta, r) = \sum_{s} \Pr[\mathrm{Out}_\beta(\varepsilon, r) = s]\,\mathrm{opt}_C(s),EalgC​(β,r)=s∑​Pr[Outβ​(ε,r)=s]algC​(s),EoptC​(β,r)=s∑​Pr[Outβ​(ε,r)=s]optC​(s),

in [0,∞][0,\infty][0,∞] with 0⋅∞=00\cdot\infty = 00⋅∞=0. Note that the "optimum" is averaged over the outcomes produced by β\betaβ itself, not computed from the script alone. For nonnegative reals ρ,b\rho, bρ,b, β\betaβ is randomised (ρ,b)(\rho, b)(ρ,b)-competitive on CCC iff for every script rrr over MGCM_{G_C}MGC​​,

EalgC(β,r)≤ρ⋅EoptC(β,r)+b.\mathbb{E}\mathrm{alg}_C(\beta, r) \le \rho\cdot\mathbb{E}\mathrm{opt}_C(\beta, r) + b .EalgC​(β,r)≤ρ⋅EoptC​(β,r)+b.

Side conditions. β\betaβ is non-stopping iff β(s)(⊥)=0\beta(s)(\bot) = 0β(s)(⊥)=0 for every s∈PosGs \in \mathrm{Pos}_Gs∈PosG​ with LastO(s)\mathrm{Last}_O(s)LastO​(s). A game GGG is open to the opponent iff for every s∈PosGs \in \mathrm{Pos}_Gs∈PosG​ that is empty or ends with a PPP-move, and every OOO-labelled move mmm, sm∈PosGs m \in \mathrm{Pos}_Gsm∈PosG​.

Tensor. GC⊗GDG_C \otimes G_DGC​⊗GD​ has moves MC⊔MDM_C \sqcup M_DMC​⊔MD​ with inherited labels; sss is a position iff s∣C∈PosGCs|_C \in \mathrm{Pos}_{G_C}s∣C​∈PosGC​​, s∣D∈PosGDs|_D \in \mathrm{Pos}_{G_D}s∣D​∈PosGD​​ (restrictions to each component) and each consecutive pair m,m′m, m'm,m′ is differently labelled and either in the same component or has m′m'm′ OOO-labelled. The costed tensor has algC⊗D(s)=algC(s∣C)+algD(s∣D)\mathrm{alg}_{C\otimes D}(s) = \mathrm{alg}_C(s|_C) + \mathrm{alg}_D(s|_D)algC⊗D​(s)=algC​(s∣C​)+algD​(s∣D​) and likewise for opt\mathrm{opt}opt. The behavioural tensor βA⊗βB\beta_A \otimes \beta_BβA​⊗βB​ is: on sss whose last move is from CCC, apply βA\beta_AβA​ to s∣Cs|_Cs∣C​ and tag the result as a CCC-move (⊥\bot⊥ stays ⊥\bot⊥); on sss whose last move is from DDD, apply βB\beta_BβB​ to s∣Ds|_Ds∣D​ and tag as a DDD-move; on ε\varepsilonε, the point mass at ⊥\bot⊥.

Statement. For all costed games C,DC, DC,D, behavioural strategies βA\beta_AβA​ on GCG_CGC​ and βB\beta_BβB​ on GDG_DGD​, and nonnegative reals ρ1,b1,ρ2,b2\rho_1, b_1, \rho_2, b_2ρ1​,b1​,ρ2​,b2​, assume:

  • βA\beta_AβA​ is randomised (ρ1,b1)(\rho_1, b_1)(ρ1​,b1​)-competitive on CCC, and βB\beta_BβB​ is randomised (ρ2,b2)(\rho_2, b_2)(ρ2​,b2​)-competitive on DDD;
  • βA\beta_AβA​ and βB\beta_BβB​ are non-stopping;
  • GCG_CGC​ and GDG_DGD​ are open to the opponent.

Then βA⊗βB\beta_A \otimes \beta_BβA​⊗βB​ is randomised (max⁡(ρ1,ρ2), b1+b2)(\max(\rho_1,\rho_2),\ b_1 + b_2)(max(ρ1​,ρ2​), b1​+b2​)-competitive on C⊗DC \otimes DC⊗D: for every script rrr over MC⊔MDM_C \sqcup M_DMC​⊔MD​,

EalgC⊗D(βA⊗βB,r)≤max⁡(ρ1,ρ2)⋅EoptC⊗D(βA⊗βB,r)+b1+b2.\mathbb{E}\mathrm{alg}_{C\otimes D}(\beta_A\otimes\beta_B, r) \le \max(\rho_1,\rho_2)\cdot\mathbb{E}\mathrm{opt}_{C\otimes D}(\beta_A\otimes\beta_B, r) + b_1 + b_2 .EalgC⊗D​(βA​⊗βB​,r)≤max(ρ1​,ρ2​)⋅EoptC⊗D​(βA​⊗βB​,r)+b1​+b2​.

Degenerate and restrictive cases. Non-stopping, together with the legality condition, can only hold if every position of the game ending in an OOO-move has at least one PPP-labelled extension in Pos\mathrm{Pos}Pos (otherwise β(s)\beta(s)β(s) would have to give total mass 000); for any game with such a dead-end position the hypothesis is unsatisfiable and the statement vacuous. Combined with openness, if a game has any OOO-labelled move then it has arbitrarily long positions. If a game has no OOO-labelled moves, openness holds trivially and every script yields outcome ε\varepsilonε. The competitiveness hypotheses quantify over all scripts, including scripts that become illegal and truncate play. Costs may be ∞\infty∞.

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