Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Costed games, competitive and randomised-competitive strategies

Definition
AJOnline_CostedGame

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

game-semanticsonline-algorithms

A costed game CCC is an AJ game C.GC.GC.G together with two functions on finite plays, both with values in [0,∞][0,\infty][0,∞]:

  • alg(s)\mathrm{alg}(s)alg(s), the cost paid by the algorithm (Player) along sss;
  • opt(s)\mathrm{opt}(s)opt(s), the offline optimum for the requests in sss.

The file defines three notions.

  1. A deterministic strategy σ\sigmaσ is (ρ,b)(\rho,b)(ρ,b)-competitive if alg(s)≤ρ opt(s)+b\mathrm{alg}(s)\le\rho\,\mathrm{opt}(s)+balg(s)≤ρopt(s)+b for every s∈σs\in\sigmas∈σ.
  2. The tensor C⊗DC\otimes DC⊗D is the costed game on C.G⊗D.GC.G\otimes D.GC.G⊗D.G with
alg(s)=algC(s↾C)+algD(s↾D),opt(s)=optC(s↾C)+optD(s↾D).\mathrm{alg}(s)=\mathrm{alg}_C(s{\restriction}C)+\mathrm{alg}_D(s{\restriction}D),\qquad \mathrm{opt}(s)=\mathrm{opt}_C(s{\restriction}C)+\mathrm{opt}_D(s{\restriction}D).alg(s)=algC​(s↾C)+algD​(s↾D),opt(s)=optC​(s↾C)+optD​(s↾D).
  1. For a behaviour strategy β\betaβ and a script rrr, E[alg]\mathbb E[\mathrm{alg}]E[alg] and E[opt]\mathbb E[\mathrm{opt}]E[opt] are the expectations over the play-out of β\betaβ from the empty play against rrr. β\betaβ is (ρ,b)(\rho,b)(ρ,b)-randomised-competitive if, for every script rrr,
E[alg]≤ρ E[opt]+b.\mathbb E[\mathrm{alg}]\le\rho\,\mathbb E[\mathrm{opt}]+b .E[alg]≤ρE[opt]+b.

Formalization Note Offline optima add over the components of a tensor: the two problems are independent instances. A strategy that stops at once has expected cost 000, so existence statements in this mission also require the strategy never to stop.

Definition code
import Mathlib
import Definitions.Def_AJGames_Behaviour

/-!
# Online problems as Abramsky–Jagadeesan games

An online problem is read as an AJ game in which Opponent issues requests and Player serves them.
A *costed game* attaches to every finite play `s` the cost `alg s` that Player has paid along `s`,
and the offline optimum `opt s` for the requests that occur in `s`. A Player strategy is
`(ρ, β)`-competitive when every play it allows satisfies `alg s ≤ ρ · opt s + β` (Borodin and
El-Yaniv, *Online Computation and Competitive Analysis*, CUP 1998, Definition 1.1, for an oblivious
adversary; here the adversary's moves are the Opponent moves of the game).

**Formalization Note.** Costs are `ℝ≥0∞`-valued functions of finite plays, so the finite-play
(safety) fragment of AJ games suffices. In the tensor `A ⊗ B` the two problems run side by side and
Opponent decides which one receives the next request (AJ: only Opponent switches component).
Costs and offline optima add over the components: the two instances are independent.
-/

namespace AJOnline

open AJGames
open scoped ENNReal NNReal

universe u

/-- An online problem as an AJ game with costs on finite plays. -/
structure CostedGame where
  G : AJGames.Game.{u}
  alg : List G.M → ℝ≥0∞
  opt : List G.M → ℝ≥0∞

/-- `σ` is `(ρ, β)`-competitive: on every finite play it allows, its cost is at most
`ρ` times the offline optimum plus `β`. -/
def Competitive (C : CostedGame.{u}) (σ : Strategy C.G) (ρ β : ℝ≥0) : Prop :=
  ∀ s ∈ σ.carrier, C.alg s ≤ (ρ : ℝ≥0∞) * C.opt s + β

/-- Two independent online problems side by side: the AJ tensor of the games, with costs and
offline optima added over the components. -/
def CostedGame.tensor (C D : CostedGame.{u}) : CostedGame.{u} where
  G := AJGames.Game.tensor C.G D.G
  alg s := C.alg (projL s) + D.alg (projR s)
  opt s := C.opt (projL s) + D.opt (projR s)

/-- Expected cost to Player of the behaviour strategy `β` against the oblivious script `rs`
(stop-counts semantics, `AJGames.playOut`). -/
noncomputable def expAlg (C : CostedGame.{u}) (β : BehStrategy C.G) (rs : List C.G.M) : ℝ≥0∞ :=
  ∑' s, playOut β [] rs s * C.alg s

/-- Expected offline optimum over the same outcomes. -/
noncomputable def expOpt (C : CostedGame.{u}) (β : BehStrategy C.G) (rs : List C.G.M) : ℝ≥0∞ :=
  ∑' s, playOut β [] rs s * C.opt s

/-- `β` is `(ρ, b)`-competitive against oblivious adversaries: for every script,
`E[alg] ≤ ρ · E[opt] + b`. -/
def RandCompetitive (C : CostedGame.{u}) (β : BehStrategy C.G) (ρ b : ℝ≥0) : Prop :=
  ∀ rs : List C.G.M, expAlg C β rs ≤ (ρ : ℝ≥0∞) * expOpt C β rs + b

end AJOnline
Source
A. Borodin, R. El-Yaniv, Online Computation and Competitive Analysis, CUP 1998, Definition 1.1 (competitive ratio against an oblivious adversary), on the games of 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
Read-back

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

Read-back: Def_AJOnline_CostedGame

Background (from the context files)

A game GGG: move type MGM_GMG​, labelling λG:MG→{P,O}\lambda_G : M_G \to \{P, O\}λG​:MG​→{P,O}, set posG\mathrm{pos}_GposG​ of finite move sequences containing the empty play ε\varepsilonε, prefix-closed, every position alternating.

A strategy σ\sigmaσ on GGG: a prefix-closed set of positions containing ε\varepsilonε, whose non-empty plays start with an OOO-move, deterministic in PPP-moves, and receptive to every legal OOO-move. Plays in σ\sigmaσ may end with an unanswered OOO-move.

Tensor G⊗HG \otimes HG⊗H: moves MG⊔MHM_G \sqcup M_HMG​⊔MH​, positions are sequences whose consecutive moves alternate in label and switch component only at an OOO-move, and whose projections s∣Gs|_Gs∣G​, s∣Hs|_Hs∣H​ (subsequences of left, resp. right, moves) are positions of GGG, HHH.

A behavioural strategy β\betaβ: a map nextβ\mathrm{next}_\betanextβ​ from finite sequences to probability distributions on moves ∪{none}\cup\{\mathrm{none}\}∪{none}, positive mass on a move aaa at sss only if sss is non-empty and ends with an OOO-move, λ(a)=P\lambda(a) = Pλ(a)=P, and s∈pos⇒s⋅a∈poss \in \mathrm{pos} \Rightarrow s\cdot a \in \mathrm{pos}s∈pos⇒s⋅a∈pos; mass on none (stopping) is unconstrained.

playOutβ(s,rs)_\beta(s, rs)β​(s,rs): a probability distribution on finite sequences. With rs=εrs = \varepsilonrs=ε it is the point mass at sss. With rs=r::rs′rs = r :: rs'rs=r::rs′: if λ(r)=O\lambda(r) = Oλ(r)=O and s⋅r∈poss\cdot r \in \mathrm{pos}s⋅r∈pos, draw o∼nextβ(s⋅r)o \sim \mathrm{next}_\beta(s \cdot r)o∼nextβ​(s⋅r); if o=noneo = \mathrm{none}o=none return the point mass at s⋅rs\cdot rs⋅r (rest of script discarded), if o=ao = ao=a continue with playOutβ(s⋅r⋅a,rs′)\mathrm{playOut}_\beta(s\cdot r\cdot a, rs')playOutβ​(s⋅r⋅a,rs′); otherwise return the point mass at sss (rest discarded).

Values [0,∞][0,\infty][0,∞] are extended non-negative reals, with the convention 0⋅∞=00 \cdot \infty = 00⋅∞=0; R≥0\mathbb{R}_{\ge 0}R≥0​ is the non-negative reals.

CostedGame

A costed game CCC consists of a game GCG_CGC​ and two arbitrary functions

algC, optC:{finite sequences of moves of GC}→[0,∞].\mathrm{alg}_C,\ \mathrm{opt}_C : \{\text{finite sequences of moves of } G_C\} \to [0, \infty].algC​, optC​:{finite sequences of moves of GC​}→[0,∞].

They are defined on all sequences, not only positions, and no relation is imposed: no opt≤alg\mathrm{opt} \le \mathrm{alg}opt≤alg, no monotonicity along prefixes, no value at ε\varepsilonε fixed, no connection to the game's structure, and both may take the value ∞\infty∞.

Competitive

For a costed game CCC, a (deterministic) strategy σ\sigmaσ on GCG_CGC​, and ρ,β∈R≥0\rho, \beta \in \mathbb{R}_{\ge 0}ρ,β∈R≥0​ (here β\betaβ is a number, an additive constant):

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

The quantifier ranges over all plays of σ\sigmaσ, including ε\varepsilonε (so algC(ε)≤ρ optC(ε)+β\mathrm{alg}_C(\varepsilon) \le \rho\,\mathrm{opt}_C(\varepsilon) + \betaalgC​(ε)≤ρoptC​(ε)+β is required) and plays ending with an OOO-move before σ\sigmaσ answers. If optC(s)=∞\mathrm{opt}_C(s) = \inftyoptC​(s)=∞ and ρ>0\rho > 0ρ>0 the inequality holds trivially at sss; if ρ=0\rho = 0ρ=0 then ρ⋅∞=0\rho\cdot\infty = 0ρ⋅∞=0 and the bound is algC(s)≤β\mathrm{alg}_C(s) \le \betaalgC​(s)≤β.

CostedGame.tensor

For costed games C,DC, DC,D, the costed game C⊗DC \otimes DC⊗D has game GC⊗GDG_C \otimes G_DGC​⊗GD​ and

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

for every sequence sss over MGC⊔MGDM_{G_C} \sqcup M_{G_D}MGC​​⊔MGD​​, where s∣GCs|_{G_C}s∣GC​​ and s∣GDs|_{G_D}s∣GD​​ are the left and right projections (the costs are additive over components; the interleaving is ignored).

expAlg, expOpt

For a costed game CCC, a behavioural strategy β\betaβ on GCG_CGC​, and a finite list rsrsrs of moves (an opponent script),

expAlg(C,β,rs)=∑sPr⁡[playOutβ(ε,rs)=s]⋅algC(s),expOpt(C,β,rs)=∑sPr⁡[playOutβ(ε,rs)=s]⋅optC(s),\mathrm{expAlg}(C, \beta, rs) = \sum_{s} \Pr[\mathrm{playOut}_\beta(\varepsilon, rs) = s]\cdot \mathrm{alg}_C(s),\qquad \mathrm{expOpt}(C,\beta,rs) = \sum_s \Pr[\mathrm{playOut}_\beta(\varepsilon, rs) = s]\cdot \mathrm{opt}_C(s),expAlg(C,β,rs)=s∑​Pr[playOutβ​(ε,rs)=s]⋅algC​(s),expOpt(C,β,rs)=s∑​Pr[playOutβ​(ε,rs)=s]⋅optC​(s),

the sums ranging over all finite sequences sss, computed in [0,∞][0,\infty][0,∞] (always defined; may be ∞\infty∞). These are the expected costs of the final play produced by running β\betaβ from the empty play against the script rsrsrs; the final play may be truncated (stopping by none, a PPP-labelled or illegal script entry), and costs are evaluated on that truncated play.

RandCompetitive

For a costed game CCC, a behavioural strategy β\betaβ on GCG_CGC​, and ρ,b∈R≥0\rho, b \in \mathbb{R}_{\ge 0}ρ,b∈R≥0​:

RandCompetitive(C,β,ρ,b)  ⟺  ∀rs,  expAlg(C,β,rs)≤ρ⋅expOpt(C,β,rs)+b.\mathrm{RandCompetitive}(C, \beta, \rho, b) \iff \forall rs,\ \ \mathrm{expAlg}(C,\beta,rs) \le \rho\cdot \mathrm{expOpt}(C,\beta,rs) + b.RandCompetitive(C,β,ρ,b)⟺∀rs,  expAlg(C,β,rs)≤ρ⋅expOpt(C,β,rs)+b.

Here rsrsrs ranges over all finite lists of moves of GCG_CGC​ (any labels, legal or not), fixed in advance independently of β\betaβ's random choices (an oblivious opponent). Both expectations are taken under the same distribution of outcomes, the one induced by β\betaβ; opt\mathrm{opt}opt is evaluated on the play β\betaβ actually produced, not on a separately optimised play. For rs=εrs = \varepsilonrs=ε (or any script whose first entry is PPP-labelled or not a legal opening) the outcome is ε\varepsilonε with probability 111, so the condition includes algC(ε)≤ρ optC(ε)+b\mathrm{alg}_C(\varepsilon) \le \rho\,\mathrm{opt}_C(\varepsilon) + balgC​(ε)≤ρoptC​(ε)+b. If β\betaβ stops (all mass on none) at some point, the remaining script is ignored for that outcome.

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