Costed games, competitive and randomised-competitive strategies
DefinitionAJOnline_CostedGameA costed game is an AJ game together with two functions on finite plays, both with values in :
- , the cost paid by the algorithm (Player) along ;
- , the offline optimum for the requests in .
The file defines three notions.
- A deterministic strategy is -competitive if for every .
- The tensor is the costed game on with
- For a behaviour strategy and a script , and are the expectations over the play-out of from the empty play against . is -randomised-competitive if, for every script ,
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 , so existence statements in this mission also require the strategy never to stop.
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
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 : move type , labelling , set of finite move sequences containing the empty play , prefix-closed, every position alternating.
A strategy on : a prefix-closed set of positions containing , whose non-empty plays start with an -move, deterministic in -moves, and receptive to every legal -move. Plays in may end with an unanswered -move.
Tensor : moves , positions are sequences whose consecutive moves alternate in label and switch component only at an -move, and whose projections , (subsequences of left, resp. right, moves) are positions of , .
A behavioural strategy : a map from finite sequences to probability distributions on moves , positive mass on a move at only if is non-empty and ends with an -move, , and ; mass on none (stopping) is unconstrained.
playOut: a probability distribution on finite sequences. With it is the point mass at . With : if and , draw ; if return the point mass at (rest of script discarded), if continue with ; otherwise return the point mass at (rest discarded).
Values are extended non-negative reals, with the convention ; is the non-negative reals.
CostedGame
A costed game consists of a game and two arbitrary functions
They are defined on all sequences, not only positions, and no relation is imposed: no , no monotonicity along prefixes, no value at fixed, no connection to the game's structure, and both may take the value .
Competitive
For a costed game , a (deterministic) strategy on , and (here is a number, an additive constant):
The quantifier ranges over all plays of , including (so is required) and plays ending with an -move before answers. If and the inequality holds trivially at ; if then and the bound is .
CostedGame.tensor
For costed games , the costed game has game and
for every sequence over , where and are the left and right projections (the costs are additive over components; the interleaving is ignored).
expAlg, expOpt
For a costed game , a behavioural strategy on , and a finite list of moves (an opponent script),
the sums ranging over all finite sequences , computed in (always defined; may be ). These are the expected costs of the final play produced by running from the empty play against the script ; the final play may be truncated (stopping by none, a -labelled or illegal script entry), and costs are evaluated on that truncated play.
RandCompetitive
For a costed game , a behavioural strategy on , and :
Here ranges over all finite lists of moves of (any labels, legal or not), fixed in advance independently of 's random choices (an oblivious opponent). Both expectations are taken under the same distribution of outcomes, the one induced by ; is evaluated on the play actually produced, not on a separately optimised play. For (or any script whose first entry is -labelled or not a legal opening) the outcome is with probability , so the condition includes . If stops (all mass on none) at some point, the remaining script is ignored for that outcome.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.