Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Competitive ratios across the tensor: max⁡(ρ1,ρ2)\max(\rho_1,\rho_2)max(ρ1​,ρ2​)

Proved
AJOnline.tensor_competitive

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

game-semanticsonline-algorithms

Let CCC and DDD be costed games. Let σ\sigmaσ be (ρ1,b1)(\rho_1,b_1)(ρ1​,b1​)-competitive on CCC and τ\tauτ be (ρ2,b2)(\rho_2,b_2)(ρ2​,b2​)-competitive on DDD. Then σ⊗τ\sigma\otimes\tauσ⊗τ is

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

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.

Preamble
import Mathlib
import Definitions.Def_AJOnline_CostedGame
Formal statement
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 AJOnline
Source
New statement introduced by this mission (no prior source); games and tensor of strategies from 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; competitiveness from A. Borodin, R. El-Yaniv, Online Computation and Competitive Analysis, CUP 1998, Definition 1.1
Read-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 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 that contains the empty sequence ε\varepsilonε, is prefix-closed, and in which consecutive moves always have different labels. A strategy σ\sigmaσ on GGG is a set of sequences with ε∈σ⊆PosG\varepsilon \in \sigma \subseteq \mathrm{Pos}_Gε∈σ⊆PosG​, prefix-closed, whose nonempty members start with an OOO-move, deterministic (sa,sb∈σs a, s b \in \sigmasa,sb∈σ with a,ba, ba,b both PPP-labelled imply a=ba = ba=b) and receptive (s∈σs \in \sigmas∈σ, aaa OOO-labelled, sa∈PosGs a \in \mathrm{Pos}_Gsa∈PosG​ imply sa∈σs a \in \sigmasa∈σ). A strategy need not answer every OOO-move.

Tensor. For games A,BA, BA,B, the game A⊗BA \otimes BA⊗B has moves MA⊔MBM_A \sqcup M_BMA​⊔MB​ (disjoint union), each move keeping its label. For a sequence sss over MA⊔MBM_A \sqcup M_BMA​⊔MB​ let s∣As|_As∣A​ and s∣Bs|_Bs∣B​ be the subsequences of AAA-moves and BBB-moves. A sequence sss is a position of A⊗BA \otimes BA⊗B iff s∣A∈PosAs|_A \in \mathrm{Pos}_As∣A​∈PosA​, s∣B∈PosBs|_B \in \mathrm{Pos}_Bs∣B​∈PosB​, and every pair of consecutive moves m,m′m, m'm,m′ in sss has different labels and either lies in the same component or m′m'm′ is OOO-labelled (only OOO may switch component). For strategies σ\sigmaσ on AAA and τ\tauτ on BBB, the strategy σ⊗τ\sigma \otimes \tauσ⊗τ on A⊗BA \otimes BA⊗B has carrier

σ⊗τ={ s∈PosA⊗B:s∣A∈σ, s∣B∈τ }.\sigma\otimes\tau = \{\, s \in \mathrm{Pos}_{A\otimes B} : s|_A \in \sigma,\ s|_B \in \tau \,\}.σ⊗τ={s∈PosA⊗B​:s∣A​∈σ, s∣B​∈τ}.

Costed games. A costed game CCC is a game GCG_CGC​ together with two arbitrary functions algC,optC\mathrm{alg}_C, \mathrm{opt}_CalgC​,optC​ from finite move sequences to [0,∞][0, \infty][0,∞] (no monotonicity, additivity or relation between them is assumed; they are defined on all sequences, not only positions). For nonnegative reals ρ,β\rho, \betaρ,β, a strategy σ\sigmaσ on GCG_CGC​ is (ρ,β)(\rho, \beta)(ρ,β)-competitive iff

∀s∈σ:algC(s)≤ρ⋅optC(s)+β,\forall s \in \sigma:\quad \mathrm{alg}_C(s) \le \rho\cdot \mathrm{opt}_C(s) + \beta,∀s∈σ:algC​(s)≤ρ⋅optC​(s)+β,

computed in [0,∞][0,\infty][0,∞] (so 0⋅∞=00 \cdot \infty = 00⋅∞=0). This is required at every sequence of the carrier, including ε\varepsilonε, prefixes, and sequences ending with an OOO-move to which σ\sigmaσ has not (yet) replied. The tensor C⊗DC \otimes DC⊗D of costed games is the costed game on GC⊗GDG_C \otimes G_DGC​⊗GD​ with

algC⊗D(s)=algC(s∣C)+algD(s∣D),optC⊗D(s)=optC(s∣C)+optD(s∣D).\mathrm{alg}_{C\otimes D}(s) = \mathrm{alg}_C(s|_C) + \mathrm{alg}_D(s|_D),\qquad \mathrm{opt}_{C\otimes D}(s) = \mathrm{opt}_C(s|_C) + \mathrm{opt}_D(s|_D).algC⊗D​(s)=algC​(s∣C​)+algD​(s∣D​),optC⊗D​(s)=optC​(s∣C​)+optD​(s∣D​).

Statement. For all costed games C,DC, DC,D, every strategy σ\sigmaσ on GCG_CGC​, every strategy τ\tauτ on GDG_DGD​, and all nonnegative reals ρ1,β1,ρ2,β2\rho_1, \beta_1, \rho_2, \beta_2ρ1​,β1​,ρ2​,β2​: if σ\sigmaσ is (ρ1,β1)(\rho_1, \beta_1)(ρ1​,β1​)-competitive on CCC and τ\tauτ is (ρ2,β2)(\rho_2, \beta_2)(ρ2​,β2​)-competitive on DDD, then σ⊗τ\sigma \otimes \tauσ⊗τ is (max⁡(ρ1,ρ2), β1+β2)(\max(\rho_1, \rho_2),\ \beta_1 + \beta_2)(max(ρ1​,ρ2​), β1​+β2​)-competitive on C⊗DC \otimes DC⊗D; that is, for every s∈σ⊗τs \in \sigma \otimes \taus∈σ⊗τ,

algC(s∣C)+algD(s∣D)  ≤  max⁡(ρ1,ρ2) (optC(s∣C)+optD(s∣D))+β1+β2.\mathrm{alg}_C(s|_C) + \mathrm{alg}_D(s|_D) \;\le\; \max(\rho_1,\rho_2)\,\bigl(\mathrm{opt}_C(s|_C) + \mathrm{opt}_D(s|_D)\bigr) + \beta_1 + \beta_2 .algC​(s∣C​)+algD​(s∣D​)≤max(ρ1​,ρ2​)(optC​(s∣C​)+optD​(s∣D​))+β1​+β2​.

Edge cases. Cost values may be ∞\infty∞; then the inequality holds automatically whenever the right side is ∞\infty∞. If ρ1=ρ2=0\rho_1 = \rho_2 = 0ρ1​=ρ2​=0 the hypotheses say alg≤βi\mathrm{alg} \le \beta_ialg≤βi​ on the carriers. If the games have only the empty position, the carriers are {ε}\{\varepsilon\}{ε} and the statement is about ε\varepsilonε alone. The cost functions on sequences outside the carriers play no role.

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