Bridge: memoryless 2-taxi policies are AJ behaviour strategies with the same costs
ProvedAJOnline.KTaxi2.bridgegame-semanticsonline-algorithms
Let be a memoryless 2-taxi policy and a labelled start. Then:
- the behaviour strategy depends on the history only through the pair (current configuration, last move);
- for every finite list of requests, played as the script ,
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.KTaxi2Source
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 and every , both of the following hold (with and ):
- depends only on : for all finite move lists (positions or not) with and equal last move (both empty, or both ending in the same move), . Here is computed by the recursion and for every other shape, without checking (removing an absent element does nothing).
- For every finite list of pairs, with the script , the two equalities in
Here and $\mathrm{memorylessCost}_A(X, q 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 ,
- Memoryless policy. assigns to every finite multiset of reals and every pair a discrete probability distribution on , such that whenever : (supported) , and (lazy) is the point mass at . Nothing is required when .
- The strategy . On any list whose last move is , it plays with (it never chooses "no move" there); on every other list (empty, or ending in a serve) it chooses "no move" with probability .
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.