Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Memory helps: a never-stopping 9-competitive behaviour strategy for two taxis

Open
AJOnline.KTaxi2.memory_helps

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

game-semanticsonline-algorithms

For every labelled start x0∈R2x_0\in\mathbb R^2x0​∈R2 there are a behaviour strategy β\betaβ on the 2-taxi game from x0x_0x0​ and a constant b≥0b\ge0b≥0 satisfying two conditions:

  1. β\betaβ never stops;
  2. for every request script,
E[alg]≤9 E[opt]+b.\mathbb E[\mathrm{alg}]\le 9\,\mathbb E[\mathrm{opt}]+b .E[alg]≤9E[opt]+b.

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.KTaxi2
Source
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 x0:{0,1}→Rx_0:\{0,1\}\to\mathbb{R}x0​:{0,1}→R there exist a behavioural strategy β\betaβ on G(x0)G(x_0)G(x0​) and a constant b∈R≥0b\in\mathbb{R}_{\ge 0}b∈R≥0​ such that

  1. β\betaβ is non-stopping: for every position sss of G(x0)G(x_0)G(x0​) whose last move exists and is a request (labelled OOO), β.next(s)\beta.\mathrm{next}(s)β.next(s) gives probability 000 to "no move"; and
  2. β\betaβ is (9,b)(9,b)(9,b)-randomised-competitive on the costed game for x0x_0x0​: for every finite move script rsrsrs, expAlg(β,rs)≤9Nothingissaidabout\mathrm{expAlg}(\beta, rs)\le 9 Nothing is said about expAlg(β,rs)≤9Nothingissaidabout\betabeyondthesetwoproperties:itisnotrequiredtodifferfrom,ortobe,astrategyoftheformbeyond these two properties: it is not required to differ from, or to be, a strategy of the formbeyondthesetwoproperties:itisnotrequiredtodifferfrom,ortobe,astrategyoftheform\mathrm{behOf}(A,x_0),anditmaydependonthewholehistory., and it may depend on the whole history. ,anditmaydependonthewholehistory.bmaydependonmay depend onmaydependonx_0.Non−stoppingconstrainsonlypositions;onnon−positions. Non-stopping constrains only positions; on non-positions .Non−stoppingconstrainsonlypositions;onnon−positions\betaisfree(subjecttolegality).Thecaseis free (subject to legality). The caseisfree(subjecttolegality).Thecasex_0(0)=x_0(1)$ is included.

Definitions used.

  • The game G(x0)G(x_0)G(x0​). Moves are requests req(q)\mathrm{req}(q)req(q), q=(q1,q2)∈R2q = (q_1,q_2)\in\mathbb{R}^2q=(q1​,q2​)∈R2 (labelled OOO), and serves serve(a)\mathrm{serve}(a)serve(a), a∈Ra\in\mathbb{R}a∈R (labelled PPP). Positions are the lists that alternate request, serve, request, serve, ..., possibly ending in an unanswered request, such that, starting from the multiset X0={x0(0),x0(1)}X_0 = \{x_0(0), x_0(1)\}X0​={x0​(0),x0​(1)}, each serve point aaa lies in the current multiset XXX, after which XXX becomes (X∖{a})+{q2}(X\setminus\{a\})+\{q_2\}(X∖{a})+{q2​} (one copy of aaa replaced by the request's second coordinate). The serve point need not equal q1q_1q1​. cfg(s)\mathrm{cfg}(s)cfg(s) is the multiset reached after the completed request/serve pairs of sss (a trailing unanswered request is ignored). The two entries of x0x_0x0​ may coincide.
  • Costs. alg(s)\mathrm{alg}(s)alg(s) is the sum over the completed pairs req(q) serve(a)\mathrm{req}(q)\,\mathrm{serve}(a)req(q)serve(a) of ∣a−q1∣|a-q_1|∣a−q1​∣ (relocation to q2q_2q2​ is free; a trailing request costs 000). opt(s)=optCost(x0,reqs(s))\mathrm{opt}(s) = \mathrm{optCost}(x_0, \mathrm{reqs}(s))opt(s)=optCost(x0​,reqs(s)), where reqs(s)\mathrm{reqs}(s)reqs(s) lists all requested pairs in sss (including a trailing one) and optCost(x0,(q(1),…,q(n)))\mathrm{optCost}(x_0, (q^{(1)},\dots,q^{(n)}))optCost(x0​,(q(1),…,q(n))) is the minimum over all 2n2^n2n assignments of requests to two labelled servers starting at x0(0),x0(1)x_0(0), x_0(1)x0​(0),x0​(1) of the total cost, where serving q(j)q^{(j)}q(j) with a server costs ∣server position−q1(j)∣|\text{server position} - q^{(j)}_1|∣server position−q1(j)​∣ and moves that server to q2(j)q^{(j)}_2q2(j)​ for free (it is 000 when n=0n=0n=0). All costs live in [0,∞][0,\infty][0,∞].
  • Behavioural strategy. A behavioural strategy β\betaβ on G(x0)G(x_0)G(x0​) assigns to every finite move list sss a discrete probability distribution β.next(s)\beta.\mathrm{next}(s)β.next(s) on {no move}∪Mv\{\text{no move}\}\cup\mathrm{Mv}{no move}∪Mv, subject to legality: positive probability on a move mmm only if the last move of sss exists and is a request, mmm is a serve, and (sss a position ⇒\Rightarrow⇒ s⋅ms\cdot ms⋅m a position).
  • Play-out. Given an opponent script rsrsrs (an arbitrary finite list of moves, requests or serves), playOutβ(s,rs)\mathrm{playOut}_\beta(s, rs)playOutβ​(s,rs) is the random final history defined by: if rsrsrs is empty, stop with sss; if rs=r⋅rs′rs = r\cdot rs'rs=r⋅rs′ and rrr is a request with s⋅rs\cdot rs⋅r a position, sample o∼β.next(s⋅r)o\sim\beta.\mathrm{next}(s\cdot r)o∼β.next(s⋅r); if ooo is "no move" stop with s⋅rs\cdot rs⋅r (the rest of the script is discarded); if o=mo = mo=m, continue from s⋅r⋅ms\cdot r\cdot ms⋅r⋅m with rs′rs'rs′. Otherwise (rrr is a serve, or s⋅rs\cdot rs⋅r is not a position) stop with sss, discarding rrr and the rest. Play starts from the empty history.
  • Expected costs. expAlg(β,rs)=∑sPr⁡[playOutβ([ ],rs)=s]⋅alg(s)\mathrm{expAlg}(\beta, rs) = \sum_s \Pr[\mathrm{playOut}_\beta([\,], rs) = s]\cdot\mathrm{alg}(s)expAlg(β,rs)=∑s​Pr[playOutβ​([],rs)=s]⋅alg(s) and expOpt(β,rs)=∑sPr⁡[playOutβ([ ],rs)=s]⋅opt(s)\mathrm{expOpt}(\beta, rs) = \sum_s \Pr[\mathrm{playOut}_\beta([\,], rs) = s]\cdot\mathrm{opt}(s)expOpt(β,rs)=∑s​Pr[playOutβ​([],rs)=s]⋅opt(s), sums in [0,∞][0,\infty][0,∞]. Note that expOpt\mathrm{expOpt}expOpt is the expected optimum of the requests actually absorbed into the play, which may be fewer than those in the script if β\betaβ stops or the script contains a serve.
  • Randomised competitiveness. For ρ,b∈R≥0\rho, b\in\mathbb{R}_{\ge 0}ρ,b∈R≥0​, β\betaβ is (ρ,b)(\rho,b)(ρ,b)-randomised-competitive iff for every finite move list rsrsrs,
expAlg(β,rs)≤ρ⋅expOpt(β,rs)+bin [0,∞].\mathrm{expAlg}(\beta, rs) \le \rho\cdot\mathrm{expOpt}(\beta, rs) + b \quad\text{in } [0,\infty].expAlg(β,rs)≤ρ⋅expOpt(β,rs)+bin [0,∞].
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