Memory helps: a never-stopping 9-competitive behaviour strategy for two taxis
OpenAJOnline.KTaxi2.memory_helpsgame-semanticsonline-algorithms
For every labelled start there are a behaviour strategy on the 2-taxi game from and a constant satisfying two conditions:
- never stops;
- for every request script,
Together with the goal, this separates history-dependent from history-free strategies in one game.
Preamble
import Mathlib import Definitions.Def_AJOnline_KTaxi2 import Definitions.Def_AJGames_BehTensor
Formal statement
namespace AJOnline.KTaxi2
open AJGames KTaxi.Competitive.Supplement
open scoped ENNReal NNReal
/-- **Memory helps.** From every labelled start `x₀` there is a behaviour strategy on the 2-taxi
game (using the whole history) that never stops and is randomised-competitive with ratio `9`
against oblivious adversaries. -/
theorem memory_helps (x₀ : Fin 2 → ℝ) :
∃ (β : BehStrategy (game x₀)) (b : ℝ≥0), β.NonStop ∧ RandCompetitive (costed x₀) β 9 b := by sorry
end AJOnline.KTaxi2Source
AJ form of C. Coester, Y. Huang, T.-Y. Poon, The k-Taxi Problem Is Competitive on All Metrics, STOC 2027 submission #96 (2026), https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/96.pdf, Theorem 1.1 (randomised 9^{k-1}-competitive algorithm on every metric, against adaptive online adversaries), at k = 2 on the real line; competitiveness against adaptive online adversaries implies it against oblivious ones
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Read-back: memory_helps
Statement. For every there exist a behavioural strategy on and a constant such that
- is non-stopping: for every position of whose last move exists and is a request (labelled ), gives probability to "no move"; and
- is -randomised-competitive on the costed game for : for every finite move script , \beta\mathrm{behOf}(A,x_0)bx_0\betax_0(0)=x_0(1)$ is included.
Definitions used.
- The game . Moves are requests , (labelled ), and serves , (labelled ). Positions are the lists that alternate request, serve, request, serve, ..., possibly ending in an unanswered request, such that, starting from the multiset , each serve point lies in the current multiset , after which becomes (one copy of replaced by the request's second coordinate). The serve point need not equal . is the multiset reached after the completed request/serve pairs of (a trailing unanswered request is ignored). The two entries of may coincide.
- Costs. is the sum over the completed pairs of (relocation to is free; a trailing request costs ). , where lists all requested pairs in (including a trailing one) and is the minimum over all assignments of requests to two labelled servers starting at of the total cost, where serving with a server costs and moves that server to for free (it is when ). All costs live in .
- Behavioural strategy. A behavioural strategy on assigns to every finite move list a discrete probability distribution on , subject to legality: positive probability on a move only if the last move of exists and is a request, is a serve, and ( a position a position).
- Play-out. Given an opponent script (an arbitrary finite list of moves, requests or serves), is the random final history defined by: if is empty, stop with ; if and is a request with a position, sample ; if is "no move" stop with (the rest of the script is discarded); if , continue from with . Otherwise ( is a serve, or is not a position) stop with , discarding and the rest. Play starts from the empty history.
- Expected costs. and , sums in . Note that is the expected optimum of the requests actually absorbed into the play, which may be fewer than those in the script if stops or the script contains a serve.
- Randomised competitiveness. For , is -randomised-competitive iff for every finite move list ,
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.