Competitive ratios across the tensor:
ProvedAJOnline.tensor_competitiveLet and be costed games. Let be -competitive on and be -competitive on . Then is
where Opponent interleaves the two request streams freely.
This is a composition law for competitive ratios. The tensor of strategies is well defined only because only Opponent switches component.
import Mathlib import Definitions.Def_AJOnline_CostedGame
namespace AJOnline
open AJGames
open scoped ENNReal NNReal
universe u
/-- **Competitive ratios across the tensor.** If `σ` is `(ρ₁, β₁)`-competitive on the online problem
`C` and `τ` is `(ρ₂, β₂)`-competitive on `D`, then playing them side by side, `σ ⊗ τ`, is
`(max ρ₁ ρ₂, β₁ + β₂)`-competitive on `C ⊗ D`, where Opponent interleaves the two request streams.
AJ axioms used: T2 (only Opponent switches component), through the fact that `σ ⊗ τ` is a strategy
(`tensorS`, determinism); the inequality itself uses only the definition of `σ ⊗ τ`. -/
theorem tensor_competitive (C D : CostedGame.{u}) (σ : Strategy C.G) (τ : Strategy D.G)
(ρ₁ β₁ ρ₂ β₂ : ℝ≥0) (hσ : Competitive C σ ρ₁ β₁) (hτ : Competitive D τ ρ₂ β₂) :
Competitive (C.tensor D) (tensorS σ τ) (max ρ₁ ρ₂) (β₁ + β₂) := by sorry
end AJOnlineRead-back
What the Lean code literally says, in plain math · claude-opus-5-5
Read-back of tensor_competitive (competitive ratios compose under the tensor).
Games and strategies. A game has a type of moves , a labelling , and a set of finite move sequences that contains the empty sequence , is prefix-closed, and in which consecutive moves always have different labels. A strategy on is a set of sequences with , prefix-closed, whose nonempty members start with an -move, deterministic ( with both -labelled imply ) and receptive (, -labelled, imply ). A strategy need not answer every -move.
Tensor. For games , the game has moves (disjoint union), each move keeping its label. For a sequence over let and be the subsequences of -moves and -moves. A sequence is a position of iff , , and every pair of consecutive moves in has different labels and either lies in the same component or is -labelled (only may switch component). For strategies on and on , the strategy on has carrier
Costed games. A costed game is a game together with two arbitrary functions from finite move sequences to (no monotonicity, additivity or relation between them is assumed; they are defined on all sequences, not only positions). For nonnegative reals , a strategy on is -competitive iff
computed in (so ). This is required at every sequence of the carrier, including , prefixes, and sequences ending with an -move to which has not (yet) replied. The tensor of costed games is the costed game on with
Statement. For all costed games , every strategy on , every strategy on , and all nonnegative reals : if is -competitive on and is -competitive on , then is -competitive on ; that is, for every ,
Edge cases. Cost values may be ; then the inequality holds automatically whenever the right side is . If the hypotheses say on the carriers. If the games have only the empty position, the carriers are and the statement is about alone. The cost functions on sequences outside the carriers play no role.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.