Randomised tensor of competitive behaviour strategies
OpenAJOnline.rand_tensor_competitiveLet be costed games whose underlying games are open to Opponent. Let on and on be never-stopping behaviour strategies, - and -randomised-competitive respectively. Then is
This is the randomised counterpart of the deterministic tensor law.
import Mathlib import Definitions.Def_AJOnline_CostedGame import Definitions.Def_AJGames_BehTensor
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 AJOnlineRead-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 has a type of moves , a labelling , and a set of finite move sequences containing the empty sequence , prefix-closed, with consecutive moves always differently labelled (positions need not start with ). Write for " is nonempty and its last move is -labelled" (Lean name PlayerToMove).
Behavioural strategies. A behavioural strategy on assigns to every finite sequence a probability distribution on ( = no move / stop) such that implies , , and (). So is the point mass at whenever is empty or ends with a -move. may depend on the whole history.
Play against a script. An opponent script is a fixed finite list of moves, chosen in advance (it does not react to 's moves). The outcome distribution is: with probability if is empty; if with -labelled and , draw and stop at if , otherwise continue with ; in any other case (next script move -labelled or illegal) stop at , discarding the rest of the script.
Costs. A costed game is a game with arbitrary functions from finite sequences to . The expected costs of against script are
in with . Note that the "optimum" is averaged over the outcomes produced by itself, not computed from the script alone. For nonnegative reals , is randomised -competitive on iff for every script over ,
Side conditions. is non-stopping iff for every with . A game is open to the opponent iff for every that is empty or ends with a -move, and every -labelled move , .
Tensor. has moves with inherited labels; is a position iff , (restrictions to each component) and each consecutive pair is differently labelled and either in the same component or has -labelled. The costed tensor has and likewise for . The behavioural tensor is: on whose last move is from , apply to and tag the result as a -move ( stays ); on whose last move is from , apply to and tag as a -move; on , the point mass at .
Statement. For all costed games , behavioural strategies on and on , and nonnegative reals , assume:
- is randomised -competitive on , and is randomised -competitive on ;
- and are non-stopping;
- and are open to the opponent.
Then is randomised -competitive on : for every script over ,
Degenerate and restrictive cases. Non-stopping, together with the legality condition, can only hold if every position of the game ending in an -move has at least one -labelled extension in (otherwise would have to give total mass ); 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 -labelled move then it has arbitrarily long positions. If a game has no -labelled moves, openness holds trivially and every script yields outcome . The competitiveness hypotheses quantify over all scripts, including scripts that become illegal and truncate play. Costs may be .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.