Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Deterministic competitiveness carries over to the randomised notion

Proved
AJOnline.ofStrategy_randCompetitive

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

game-semanticsonline-algorithms

Let CCC be a costed game, and let σ\sigmaσ be a strategy on CCC that is (ρ,b)(\rho,b)(ρ,b)-competitive:

alg(s)≤ρ opt(s)+bfor all s∈σ.\mathrm{alg}(s)\le\rho\,\mathrm{opt}(s)+b\quad\text{for all } s\in\sigma.alg(s)≤ρopt(s)+bfor all s∈σ.

Then σ\sigmaσ, read as a behaviour strategy, is (ρ,b)(\rho,b)(ρ,b)-randomised-competitive against oblivious adversaries.

The randomised notion therefore extends the deterministic one.

Preamble
import Mathlib
import Definitions.Def_AJOnline_CostedGame
Formal statement
namespace AJOnline

open AJGames
open scoped ENNReal NNReal

universe u

/-- **Deterministic competitiveness carries over.** If `σ` is `(ρ, b)`-competitive, the behaviour
strategy `ofStrategy σ` is `(ρ, b)`-competitive against oblivious adversaries: against any script, its
play-out is the single play of `σ`. AJ axioms used: strategy axioms (nil, receptive; first-O and
determinism through `ofStrategy`) and G3 through `ofStrategy`'s legality. No tensor axiom. -/
theorem ofStrategy_randCompetitive (C : CostedGame.{u}) (σ : Strategy C.G) (ρ b : ℝ≥0)
    (h : Competitive C σ ρ b) : RandCompetitive C (ofStrategy σ) ρ b := by sorry

end AJOnline
Source
New statement introduced by this mission (no prior source); competitiveness as in 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

Games and strategies. Players are PPP and OOO. A game G=(MG,λG,PosG)G=(M_G,\lambda_G,\mathrm{Pos}_G)G=(MG​,λG​,PosG​) has a move type 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 whose members alternate in label. A (deterministic) strategy σ⊆PosG\sigma\subseteq\mathrm{Pos}_Gσ⊆PosG​ contains ε\varepsilonε, is prefix-closed, has every nonempty member beginning with an OOO-move, is deterministic (sa,sb∈σsa, sb\in\sigmasa,sb∈σ with a,ba,ba,b both PPP-labelled implies a=ba=ba=b) and receptive (s∈σs\in\sigmas∈σ, λG(a)=O\lambda_G(a)=OλG​(a)=O, sa∈PosGsa\in\mathrm{Pos}_Gsa∈PosG​ implies sa∈σsa\in\sigmasa∈σ).

Costed games. A costed game C=(G,alg,opt)C=(G,\mathrm{alg},\mathrm{opt})C=(G,alg,opt) is a game GGG together with two arbitrary functions alg,opt\mathrm{alg},\mathrm{opt}alg,opt from finite move sequences (legal or not) to [0,∞][0,\infty][0,∞]. For ρ,b∈[0,∞)\rho,b\in[0,\infty)ρ,b∈[0,∞):

  • σ\sigmaσ is (ρ,b)(\rho,b)(ρ,b)-competitive if for every s∈σs\in\sigmas∈σ,
alg(s)≤ρ⋅opt(s)+b.\mathrm{alg}(s)\le \rho\cdot\mathrm{opt}(s)+b .alg(s)≤ρ⋅opt(s)+b.

Behaviour strategies and play-out. A behaviour strategy β\betaβ gives for every finite sequence sss a distribution βs\beta_sβs​ on MG∪{⊥}M_G\cup\{\bot\}MG​∪{⊥}, with the constraint that βs(a)≠0\beta_s(a)\neq0βs​(a)=0 forces sss nonempty with last move labelled OOO, λG(a)=P\lambda_G(a)=PλG​(a)=P, and s∈PosG⇒sa∈PosGs\in\mathrm{Pos}_G\Rightarrow sa\in\mathrm{Pos}_Gs∈PosG​⇒sa∈PosG​. For a script r\mathbf rr of moves, playOutβ(s,r)\mathrm{playOut}_\beta(s,\mathbf r)playOutβ​(s,r) is the distribution on sequences defined by: empty script gives the point mass at sss; for r=r1r′\mathbf r=r_1\mathbf r'r=r1​r′, if λG(r1)=O\lambda_G(r_1)=OλG​(r1​)=O and sr1∈PosGsr_1\in\mathrm{Pos}_Gsr1​∈PosG​, draw o∼βsr1o\sim\beta_{sr_1}o∼βsr1​​ and return the point mass at sr1sr_1sr1​ if o=⊥o=\boto=⊥, or continue with playOutβ(sr1a,r′)\mathrm{playOut}_\beta(sr_1a,\mathbf r')playOutβ​(sr1​a,r′) if o=ao=ao=a; otherwise return the point mass at sss. The expected costs over a run from the empty history are

Eβalg(r)=∑splayOutβ(ε,r)(s)⋅alg(s),Eβopt(r)=∑splayOutβ(ε,r)(s)⋅opt(s),\mathbb E_\beta^{\mathrm{alg}}(\mathbf r)=\sum_{s}\mathrm{playOut}_\beta(\varepsilon,\mathbf r)(s)\cdot\mathrm{alg}(s),\qquad \mathbb E_\beta^{\mathrm{opt}}(\mathbf r)=\sum_{s}\mathrm{playOut}_\beta(\varepsilon,\mathbf r)(s)\cdot\mathrm{opt}(s),Eβalg​(r)=s∑​playOutβ​(ε,r)(s)⋅alg(s),Eβopt​(r)=s∑​playOutβ​(ε,r)(s)⋅opt(s),

sums over all finite sequences, in [0,∞][0,\infty][0,∞] (with the convention 0⋅∞=00\cdot\infty=00⋅∞=0). β\betaβ is randomised (ρ,b)(\rho,b)(ρ,b)-competitive if for every finite script r\mathbf rr of moves (any moves at all, including PPP-labelled or illegal ones),

Eβalg(r)≤ρ⋅Eβopt(r)+b.\mathbb E_\beta^{\mathrm{alg}}(\mathbf r)\le\rho\cdot\mathbb E_\beta^{\mathrm{opt}}(\mathbf r)+b .Eβalg​(r)≤ρ⋅Eβopt​(r)+b.

Induced behaviour strategy. σ^=ofStrategy(σ)\hat\sigma=\mathrm{ofStrategy}(\sigma)σ^=ofStrategy(σ) puts, at history sss, the point mass on one PPP-labelled bbb with sb∈σsb\in\sigmasb∈σ (chosen by the axiom of choice) if such bbb exists, and the point mass on ⊥\bot⊥ otherwise.

Statement. For every costed game CCC (any universe), every strategy σ\sigmaσ on its game, and all ρ,b∈[0,∞)\rho,b\in[0,\infty)ρ,b∈[0,∞):

σ is (ρ,b)-competitive for C ⟹ σ^ is randomised (ρ,b)-competitive for C.\sigma \text{ is } (\rho,b)\text{-competitive for } C\ \Longrightarrow\ \hat\sigma \text{ is randomised } (\rho,b)\text{-competitive for } C .σ is (ρ,b)-competitive for C ⟹ σ^ is randomised (ρ,b)-competitive for C.

All arithmetic is in [0,∞][0,\infty][0,∞]: alg\mathrm{alg}alg and opt\mathrm{opt}opt may take the value ∞\infty∞, and with ρ=0\rho=0ρ=0 the term ρ⋅∞\rho\cdot\inftyρ⋅∞ equals 000. The hypothesis only constrains alg,opt\mathrm{alg},\mathrm{opt}alg,opt on members of σ\sigmaσ; values on other sequences are unconstrained.

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