Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Bridge: memoryless 2-taxi policies are AJ behaviour strategies with the same costs

Proved
AJOnline.KTaxi2.bridge

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

game-semanticsonline-algorithms

Let AAA be a memoryless 2-taxi policy and x0x_0x0​ a labelled start. Then:

  1. the behaviour strategy βA\beta_AβA​ depends on the history only through the pair (current configuration, last move);
  2. for every finite list q\mathbf qq of requests, played as the script req(q1),…,req(qn)\mathrm{req}(q^1),\dots,\mathrm{req}(q^n)req(q1),…,req(qn),
E[alg]=memorylessCost(A,X0,q),E[opt]=optCostx0(q).\mathbb E[\mathrm{alg}]=\mathrm{memorylessCost}(A,X_0,\mathbf q),\qquad \mathbb E[\mathrm{opt}]=\mathrm{optCost}_{x_0}(\mathbf q).E[alg]=memorylessCost(A,X0​,q),E[opt]=optCostx0​​(q).

These are the platform's expected memoryless cost and offline optimum.

Preamble
import Mathlib
import Definitions.Def_AJOnline_KTaxi2
Formal statement
namespace AJOnline.KTaxi2

open AJGames KTaxi.Competitive.Supplement
open scoped ENNReal NNReal

/-- **Bridge to the platform's memoryless 2-taxi model.** A `MemorylessPolicy`, read as a behaviour
strategy on the 2-taxi AJ game, depends on the history only through (configuration, last move).
Against the request script `qs` its expected cost is `memorylessCost` and its expected offline optimum
is `optCost`. AJ axioms used: none beyond the definitions (the game's positions satisfy G1–G3 by
construction); no tensor axiom, no deterministic-strategy axiom. -/
theorem bridge (A : MemorylessPolicy) (x₀ : Fin 2 → ℝ) :
    (behOf A x₀).DependsOn (fun s => (cfg (locations x₀) s, s.getLast?)) ∧
    ∀ qs : List (ℝ × ℝ),
      expAlg (costed x₀) (behOf A x₀) (qs.map Mv.req) = memorylessCost A (locations x₀) qs ∧
      expOpt (costed x₀) (behOf A x₀) (qs.map Mv.req) = optCost x₀ qs := by sorry

end AJOnline.KTaxi2
Source
New statement introduced by this mission (no prior source); the 2-taxi model is that 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, Appendix C, as formalized in KTaxi.Competitive.Supplement
Read-back

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

Read-back: bridge

Statement. For every memoryless policy AAA and every x0:{0,1}→Rx_0:\{0,1\}\to\mathbb{R}x0​:{0,1}→R, both of the following hold (with X0={x0(0),x0(1)}X_0=\{x_0(0),x_0(1)\}X0​={x0​(0),x0​(1)} and β=behOf(A,x0)\beta=\mathrm{behOf}(A,x_0)β=behOf(A,x0​)):

  1. β\betaβ depends only on s↦(cfg(X0,s), last move of s)s\mapsto(\mathrm{cfg}(X_0,s),\ \text{last move of } s)s↦(cfg(X0​,s), last move of s): for all finite move lists s,ts,ts,t (positions or not) with cfg(X0,s)=cfg(X0,t)\mathrm{cfg}(X_0,s)=\mathrm{cfg}(X_0,t)cfg(X0​,s)=cfg(X0​,t) and equal last move (both empty, or both ending in the same move), β.next(s)=β.next(t)\beta.\mathrm{next}(s)=\beta.\mathrm{next}(t)β.next(s)=β.next(t). Here cfg\mathrm{cfg}cfg is computed by the recursion cfg(X,req(q) serve(a) r)=cfg((X∖{a})+{q2},r)\mathrm{cfg}(X,\mathrm{req}(q)\,\mathrm{serve}(a)\,r)=\mathrm{cfg}((X\setminus\{a\})+\{q_2\}, r)cfg(X,req(q)serve(a)r)=cfg((X∖{a})+{q2​},r) and cfg(X,s)=X\mathrm{cfg}(X,s)=Xcfg(X,s)=X for every other shape, without checking a∈Xa\in Xa∈X (removing an absent element does nothing).
  2. For every finite list qs=(q(1),…,q(n))qs=(q^{(1)},\dots,q^{(n)})qs=(q(1),…,q(n)) of pairs, with the script rs=(req(q(1)),…,req(q(n)))rs = (\mathrm{req}(q^{(1)}),\dots,\mathrm{req}(q^{(n)}))rs=(req(q(1)),…,req(q(n))), the two equalities in [0,∞][0,\infty][0,∞]
expAlg(β,rs)=memorylessCostA(X0,qs),expOpt(β,rs)=optCost(x0,qs).\mathrm{expAlg}(\beta, rs) = \mathrm{memorylessCost}_A(X_0, qs), \qquad \mathrm{expOpt}(\beta, rs) = \mathrm{optCost}(x_0, qs).expAlg(β,rs)=memorylessCostA​(X0​,qs),expOpt(β,rs)=optCost(x0​,qs).

Here memorylessCostA(X,[ ])=0\mathrm{memorylessCost}_A(X,[\,])=0memorylessCostA​(X,[])=0 and $\mathrm{memorylessCost}_A(X, q 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,∞].
  • Memoryless policy. AAA assigns to every finite multiset XXX of reals and every pair q=(q1,q2)q=(q_1,q_2)q=(q1​,q2​) a discrete probability distribution AX,qA_{X,q}AX,q​ on R\mathbb{R}R, such that whenever ∣X∣=2|X| = 2∣X∣=2: (supported) AX,q(a)≠0⇒a∈XA_{X,q}(a)\neq 0 \Rightarrow a\in XAX,q​(a)=0⇒a∈X, and (lazy) q1∈X⇒AX,qq_1\in X \Rightarrow A_{X,q}q1​∈X⇒AX,q​ is the point mass at q1q_1q1​. Nothing is required when ∣X∣≠2|X|\neq 2∣X∣=2.
  • The strategy behOf(A,x0)\mathrm{behOf}(A,x_0)behOf(A,x0​). On any list sss whose last move is req(q)\mathrm{req}(q)req(q), it plays serve(a)\mathrm{serve}(a)serve(a) with a∼Acfg(s),qa\sim A_{\mathrm{cfg}(s),q}a∼Acfg(s),q​ (it never chooses "no move" there); on every other list (empty, or ending in a serve) it chooses "no move" with probability 111.
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