Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The 2-taxi problem on R\mathbb RR as a costed AJ game

Definition
AJOnline_KTaxi2

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

game-semanticsonline-algorithms

Fix a labelled start x0∈R2x_0\in\mathbb R^2x0​∈R2, with configuration X0={x0(0),x0(1)}X_0=\{x_0(0),x_0(1)\}X0​={x0​(0),x0​(1)} (a multiset).

  • Moves. Opponent's moves are requests req(q)\mathrm{req}(q)req(q), with q=(q1,q2)∈R2q=(q_1,q_2)\in\mathbb R^2q=(q1​,q2​)∈R2 the pickup and drop-off. Player's moves are serve(a)\mathrm{serve}(a)serve(a), a∈Ra\in\mathbb Ra∈R, meaning the taxi standing at aaa is sent.
  • Legal plays. A legal play is a sequence req(q1),serve(a1),req(q2),serve(a2),…\mathrm{req}(q^1),\mathrm{serve}(a^1),\mathrm{req}(q^2),\mathrm{serve}(a^2),\dotsreq(q1),serve(a1),req(q2),serve(a2),…, possibly ending with one unanswered request. Each aia^iai must lie in the current configuration Xi−1X_{i-1}Xi−1​, and the configuration updates as
Xi={q2i}+(Xi−1−{ai}).X_i=\{q^i_2\}+(X_{i-1}-\{a^i\}).Xi​={q2i​}+(Xi−1​−{ai}).
  • Costs. The algorithm's cost of a play is ∑i∣ai−q1i∣\sum_i|a^i-q^i_1|∑i​∣ai−q1i​∣, the empty drives. The offline optimum is the platform's optCostx0\mathrm{optCost}_{x_0}optCostx0​​ of its requests.
  • Policies as strategies. A memoryless policy AAA (a law over serving locations for each configuration and request, supported on occupied locations and lazy) becomes the behaviour strategy βA\beta_AβA​. After a request qqq in configuration XXX, βA\beta_AβA​ draws the serving location from AAA's law at (X,q)(X,q)(X,q). Otherwise it does not move.

This arena connects the AJ vocabulary to the platform's memoryless 2-taxi results.

Formalization Note The arena depends on x0x_0x0​. Serving from an unoccupied location is illegal; without this, serving from the pickup would cost nothing.

Definition code
import Mathlib
import Definitions.Def_AJOnline_CostedGame
import Definitions.Def_KTaxi_Competitive_Supplement_Memoryless

/-!
# The 2-taxi problem as a costed AJ game

Bridge from the platform's memoryless 2-taxi model
(`KTaxi.Competitive.Supplement.MemorylessPolicy`, `memorylessCost`, `optCost`) to
Abramsky–Jagadeesan games. Opponent's moves are requests `req q` (pickup `q.1`, drop-off `q.2`).
Player's moves are `serve a`, sending the taxi that stands at location `a`. After `req q, serve a`
the configuration `X` becomes `q.2 ::ₘ X.erase a`, as in `memorylessCost`.

**Formalization Note.** The arena depends on the labelled start `x₀`. A play is legal when it
alternates request, service, request, …, opens with a request, and every service sends a taxi from
an occupied location (`a ∈ X`). The algorithm's cost of a play is the sum of the empty-drive
distances `|a - q.1|`; serving the passenger from `q.1` to `q.2` is free, as in the platform's model.
The offline optimum of a play is `optCost x₀` of its requests.
-/

namespace AJOnline.KTaxi2

open AJGames KTaxi.Competitive.Supplement
open scoped ENNReal NNReal

/-- Moves: a request (Opponent) or the location of the taxi sent to serve it (Player). -/
inductive Mv
  | req (q : ℝ × ℝ)
  | serve (a : ℝ)

/-- Requests are Opponent moves, services are Player moves. -/
def lab : Mv → Pl
  | .req _ => Pl.O
  | .serve _ => Pl.P

/-- Legal plays from configuration `X`: request/service pairs, each service from an occupied
location, possibly followed by one unanswered request. -/
def Valid : Multiset ℝ → List Mv → Prop
  | _, [] => True
  | _, [.req _] => True
  | X, .req q :: .serve a :: rest => a ∈ X ∧ Valid ((X.erase a).cons q.2) rest
  | _, _ => False

theorem valid_prefix : ∀ (X : Multiset ℝ) (t s : List Mv), s <+: t → Valid X t → Valid X s
  | X, [], s, h, _ => by rw [List.prefix_nil.1 h]; trivial
  | X, [.req q], s, h, _ => by
    rcases List.prefix_cons_iff.1 h with h' | ⟨u, hu, hu'⟩
    · rw [h']; trivial
    · subst hu; rw [List.prefix_nil.1 hu']; trivial
  | X, .req q :: .serve a :: rest, s, h, ht => by
    rcases List.prefix_cons_iff.1 h with h' | ⟨u, hu, hu'⟩
    · rw [h']; trivial
    · subst hu
      rcases List.prefix_cons_iff.1 hu' with h'' | ⟨v, hv, hv'⟩
      · rw [h'']; trivial
      · subst hv
        exact ⟨ht.1, valid_prefix _ rest v hv' ht.2⟩
  | X, .req _ :: .req _ :: _, _, _, ht => ht.elim
  | X, .serve _ :: _, _, _, ht => ht.elim

theorem valid_head : ∀ (X : Multiset ℝ) (s : List Mv), Valid X s → ∀ m, s.head? = some m → lab m = Pl.O
  | _, [], _, m, hm => by simp at hm
  | _, [.req _], _, m, hm => by simp at hm; subst hm; rfl
  | _, .req _ :: .serve _ :: _, _, m, hm => by simp at hm; subst hm; rfl
  | _, .req _ :: .req _ :: _, ht, _, _ => ht.elim
  | _, .serve _ :: _, ht, _, _ => ht.elim

theorem valid_alt : ∀ (X : Multiset ℝ) (s : List Mv), Valid X s → Alt lab s
  | _, [], _ => List.isChain_nil
  | _, [.req _], _ => List.isChain_singleton _
  | X, .req q :: .serve a :: rest, ht => by
    have ih := valid_alt _ rest ht.2
    have hh := valid_head _ rest ht.2
    unfold Alt at ih ⊢
    refine List.IsChain.cons_cons (by simp [lab]) ?_
    cases rest with
    | nil => exact List.isChain_singleton _
    | cons m rest' =>
      refine List.IsChain.cons_cons ?_ ih
      rw [hh m rfl]; simp [lab]
  | _, .req _ :: .req _ :: _, ht => ht.elim
  | _, .serve _ :: _, ht => ht.elim

/-- The 2-taxi game from the labelled start `x₀`. -/
@[reducible] def game (x₀ : Fin 2 → ℝ) : AJGames.Game.{0} where
  M := Mv
  lab := lab
  pos := {s | Valid (locations x₀) s}
  nil_mem := trivial
  prefix_closed := fun s t h ht => valid_prefix _ t s h ht
  alt := fun s hs => valid_alt _ s hs

/-- The taxi configuration after a play, starting from `X`. -/
noncomputable def cfg : Multiset ℝ → List Mv → Multiset ℝ
  | X, .req q :: .serve a :: rest => cfg ((X.erase a).cons q.2) rest
  | X, _ => X

/-- The algorithm's cost of a play: the sum of the empty-drive distances. -/
noncomputable def algCost : List Mv → ℝ≥0∞
  | .req q :: .serve a :: rest => edist a q.1 + algCost rest
  | _ => 0

/-- The requests of a play. -/
def reqs (s : List Mv) : List (ℝ × ℝ) :=
  s.filterMap fun
    | .req q => some q
    | .serve _ => none

/-- The 2-taxi problem from the labelled start `x₀`, as a costed game. -/
noncomputable def costed (x₀ : Fin 2 → ℝ) : CostedGame.{0} where
  G := game x₀
  alg := algCost
  opt s := optCost x₀ (reqs s)

theorem cfg_card : ∀ (X : Multiset ℝ) (s : List Mv), Valid X s → X.card = 2 → (cfg X s).card = 2
  | _, [], _, h => h
  | _, [.req _], _, h => h
  | X, .req q :: .serve a :: rest, ht, h => by
    refine cfg_card _ rest ht.2 ?_
    rw [Multiset.card_cons, Multiset.card_erase_of_mem ht.1, h]; rfl
  | _, .req _ :: .req _ :: _, ht, _ => ht.elim
  | _, .serve _ :: _, ht, _ => ht.elim

theorem valid_snoc_serve : ∀ (X : Multiset ℝ) (s : List Mv) (q : ℝ × ℝ) (c : ℝ),
    Valid X s → s.getLast? = some (Mv.req q) → c ∈ cfg X s → Valid X (s ++ [Mv.serve c])
  | _, [], _, _, _, hl, _ => by simp at hl
  | X, [.req q'], q, c, _, hl, hc => ⟨hc, trivial⟩
  | X, .req q' :: .serve a :: rest, q, c, ht, hl, hc => by
    refine ⟨ht.1, valid_snoc_serve _ rest q c ht.2 ?_ hc⟩
    cases rest with
    | nil => simp at hl
    | cons m rest' => simpa using hl
  | _, .req _ :: .req _ :: _, _, _, ht, _, _ => ht.elim
  | _, .serve _ :: _, _, _, ht, _, _ => ht.elim

/-- The next-move distribution of a memoryless policy, read off the history. -/
noncomputable def nextOf (A : MemorylessPolicy) (x₀ : Fin 2 → ℝ) (s : List Mv) : PMF (Option Mv) :=
  match s.getLast? with
  | some (.req q) => (A.law (cfg (locations x₀) s) q).bind fun a => PMF.pure (some (Mv.serve a))
  | _ => PMF.pure none

theorem card_locations (x₀ : Fin 2 → ℝ) : (locations x₀).card = 2 := by
  simp [locations]

theorem nextOf_legal (A : MemorylessPolicy) (x₀ : Fin 2 → ℝ) (s : List Mv) (a : Mv)
    (ha : nextOf A x₀ s (some a) ≠ 0) :
    PlayerToMove (game x₀) s ∧ (game x₀).lab a = Pl.P ∧
      (s ∈ (game x₀).pos → s ++ [a] ∈ (game x₀).pos) := by
  unfold nextOf at ha
  cases hl : s.getLast? with
  | none => simp [hl] at ha
  | some m =>
    cases m with
    | serve b => simp [hl] at ha
    | req q =>
      simp only [hl, PMF.bind_apply, PMF.pure_apply] at ha
      obtain ⟨c, rfl, hc⟩ : ∃ c, a = Mv.serve c ∧ A.law (cfg (locations x₀) s) q c ≠ 0 := by
        by_contra hne
        push Not at hne
        apply ha
        apply ENNReal.tsum_eq_zero.2
        intro c
        by_cases h : some a = some (Mv.serve c)
        · rw [hne c (Option.some.inj h), zero_mul]
        · rw [if_neg h, mul_zero]
      refine ⟨⟨Mv.req q, hl, rfl⟩, rfl, fun hs => ?_⟩
      have hcard := cfg_card _ s hs (card_locations x₀)
      exact valid_snoc_serve _ s q c hs hl (A.supported _ q c hcard hc)

/-- A memoryless policy as a behaviour strategy: after a request `q` it draws the serving location
from `law (current configuration) q`; otherwise it does not move. -/
noncomputable def behOf (A : MemorylessPolicy) (x₀ : Fin 2 → ℝ) : BehStrategy (game x₀) where
  next := nextOf A x₀
  legal := nextOf_legal A x₀

end AJOnline.KTaxi2
Source
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, §1 and Appendix C (hard 2-taxi model, memoryless policies), as formalized on this platform in KTaxi.Competitive.Supplement (MemorylessPolicy, memorylessCost, optCost)
Read-back

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

Read-back: Def_AJOnline_KTaxi2 (definition file)

This file builds a two-player game (in the platform's game framework) whose moves are taxi requests and server choices, equips it with an online cost and an offline-optimum cost, and turns any "memoryless policy" into a randomised behavioural strategy of that game. Declarations, in order:

Background from the context files (used throughout).

  • A game consists of a type of moves MMM, a labelling λ:M→{P,O}\lambda : M \to \{P, O\}λ:M→{P,O}, and a set of positions (finite move sequences) that contains the empty sequence, is closed under taking prefixes, and in which consecutive moves always have different labels.
  • A memoryless policy AAA is a function assigning to every finite multiset XXX of reals and every pair q=(q1,q2)∈R2q = (q_1, q_2) \in \mathbb{R}^2q=(q1​,q2​)∈R2 a discrete probability distribution AX,qA_{X,q}AX,q​ on R\mathbb{R}R (a probability mass function, so it has countable support). Two constraints hold, and only when ∣X∣=2|X| = 2∣X∣=2 (multiset cardinality): (supported) every aaa with AX,q(a)≠0A_{X,q}(a) \neq 0AX,q​(a)=0 lies in XXX; (lazy) if q1∈Xq_1 \in Xq1​∈X then AX,qA_{X,q}AX,q​ is the point mass at q1q_1q1​. For multisets of any other size the law is unconstrained.
  • locations(x0)\mathrm{locations}(x_0)locations(x0​), for x0:{0,1}→Rx_0 : \{0,1\} \to \mathbb{R}x0​:{0,1}→R, is the two-element multiset {x0(0),x0(1)}\{x_0(0), x_0(1)\}{x0​(0),x0​(1)}. The two values may be equal, in which case it is {x,x}\{x, x\}{x,x}.
  • edist(a,b)\mathrm{edist}(a,b)edist(a,b) for reals is ∣a−b∣|a-b|∣a−b∣, read as an element of [0,∞][0,\infty][0,∞].
  • optCost(x0,qs)\mathrm{optCost}(x_0, qs)optCost(x0​,qs), for a finite list qs=(q(1),…,q(n))qs = (q^{(1)},\dots,q^{(n)})qs=(q(1),…,q(n)) of pairs, is the infimum (in [0,∞][0,\infty][0,∞]) over all 2n2^n2n assignments a:{1,…,n}→{0,1}a : \{1,\dots,n\} \to \{0,1\}a:{1,…,n}→{0,1} of the schedule cost: start with labelled servers at x0(0),x0(1)x_0(0), x_0(1)x0​(0),x0​(1); for j=1,…,nj = 1,\dots,nj=1,…,n the server a(j)a(j)a(j) pays ∣(its current position)−q1(j)∣|(\text{its current position}) - q^{(j)}_1|∣(its current position)−q1(j)​∣ and then moves, at no cost, to q2(j)q^{(j)}_2q2(j)​. For n=0n = 0n=0 it is 000.
  • A behavioural strategy β\betaβ for a game gives, for every finite move sequence sss (position or not), a probability distribution β.next(s)\beta.\mathrm{next}(s)β.next(s) on "no move" (none\mathrm{none}none) or a move mmm. Legality: if β.next(s)\beta.\mathrm{next}(s)β.next(s) gives positive probability to a move mmm, then the last move of sss exists and is labelled OOO, mmm is labelled PPP, and if sss is a position then s⋅ms\cdot ms⋅m is a position.

Mv. The type of moves: either req(q)\mathrm{req}(q)req(q) for a pair q=(q1,q2)∈R×Rq = (q_1, q_2) \in \mathbb{R}\times\mathbb{R}q=(q1​,q2​)∈R×R, or serve(a)\mathrm{serve}(a)serve(a) for a real aaa.

lab. Requests are labelled OOO; serves are labelled PPP.

Valid. A predicate Valid(X,s)\mathrm{Valid}(X, s)Valid(X,s) on a multiset XXX of reals and a move list sss, defined by recursion:

Valid(X,[ ])=Valid(X,[req(q)])=true,\mathrm{Valid}(X, [\,]) = \mathrm{Valid}(X, [\mathrm{req}(q)]) = \text{true},Valid(X,[])=Valid(X,[req(q)])=true, Valid(X,req(q) serve(a) r)  ⟺  a∈X ∧ Valid((X∖{a})+{q2}, r),\mathrm{Valid}(X, \mathrm{req}(q)\,\mathrm{serve}(a)\,r) \iff a \in X \ \wedge\ \mathrm{Valid}\big((X \setminus\{a\}) + \{q_2\},\ r\big),Valid(X,req(q)serve(a)r)⟺a∈X ∧ Valid((X∖{a})+{q2​}, r),

and false for every other shape (a list starting with a serve, or with two requests in a row). Here X∖{a}X\setminus\{a\}X∖{a} removes one copy of aaa. So a valid list alternates request, serve, request, serve, ..., possibly ending with an unanswered request; each serve point aaa must belong to the current multiset, after which one copy of aaa is replaced by the request's second coordinate q2q_2q2​. Note that the serve point aaa is not required to equal q1q_1q1​ or to relate to qqq in any way; it is only required to be in the current multiset.

valid_prefix, valid_head, valid_alt (lemmas). Every prefix of a valid list is valid; the first move of a nonempty valid list is labelled OOO; consecutive moves of a valid list have different labels.

game. For x0:{0,1}→Rx_0 : \{0,1\}\to\mathbb{R}x0​:{0,1}→R, the game G(x0)G(x_0)G(x0​) has moves Mv\mathrm{Mv}Mv, labelling lab, and positions exactly the lists sss with Valid(locations(x0),s)\mathrm{Valid}(\mathrm{locations}(x_0), s)Valid(locations(x0​),s). The game-axioms are discharged by the three lemmas above.

cfg. cfg(X,s)\mathrm{cfg}(X, s)cfg(X,s) follows the same recursion as Valid without checking membership: 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 any other shape (empty list, a lone trailing request, or a malformed list). If a∉Xa \notin Xa∈/X, the removal does nothing. Thus on a position ending in an unanswered request it returns the multiset reached after all completed request/serve pairs, ignoring the trailing request.

algCost. algCost(req(q) serve(a) r)=∣a−q1∣+algCost(r)\mathrm{algCost}(\mathrm{req}(q)\,\mathrm{serve}(a)\,r) = |a - q_1| + \mathrm{algCost}(r)algCost(req(q)serve(a)r)=∣a−q1​∣+algCost(r), and 000 on every other shape. So it sums, over the leading completed request/serve pairs, the distance from the serve point to the request's first coordinate; a trailing unanswered request costs nothing, and summation stops at the first malformed spot. Relocation to q2q_2q2​ is free.

reqs. reqs(s)\mathrm{reqs}(s)reqs(s) is the list of the pairs qqq of all request moves in sss, in order (serves deleted). A trailing unanswered request is included.

costed. The costed game for x0x_0x0​: underlying game G(x0)G(x_0)G(x0​), algorithm cost alg(s)=algCost(s)\mathrm{alg}(s) = \mathrm{algCost}(s)alg(s)=algCost(s), and optimum cost opt(s)=optCost(x0,reqs(s))\mathrm{opt}(s) = \mathrm{optCost}(x_0, \mathrm{reqs}(s))opt(s)=optCost(x0​,reqs(s)), both in [0,∞][0,\infty][0,∞], both defined on all move lists.

cfg_card (lemma). If Valid(X,s)\mathrm{Valid}(X,s)Valid(X,s) and ∣X∣=2|X| = 2∣X∣=2 then ∣cfg(X,s)∣=2|\mathrm{cfg}(X,s)| = 2∣cfg(X,s)∣=2.

valid_snoc_serve (lemma). If Valid(X,s)\mathrm{Valid}(X,s)Valid(X,s), the last move of sss is req(q)\mathrm{req}(q)req(q), and c∈cfg(X,s)c \in \mathrm{cfg}(X,s)c∈cfg(X,s), then s⋅serve(c)s\cdot\mathrm{serve}(c)s⋅serve(c) is valid.

nextOf. For a memoryless policy AAA and x0x_0x0​, and any list sss: if the last move of sss is req(q)\mathrm{req}(q)req(q), then nextOf(s)\mathrm{nextOf}(s)nextOf(s) is the distribution of serve(a)\mathrm{serve}(a)serve(a) with a∼Acfg(locations(x0),s), qa \sim A_{\mathrm{cfg}(\mathrm{locations}(x_0), s),\, q}a∼Acfg(locations(x0​),s),q​ (always a move, never "no move"); otherwise (empty sss, or last move a serve) it is the point mass on "no move". This is applied to every list, valid or not.

card_locations (lemma). ∣locations(x0)∣=2|\mathrm{locations}(x_0)| = 2∣locations(x0​)∣=2.

nextOf_legal (lemma). nextOf satisfies the behavioural-strategy legality condition for G(x0)G(x_0)G(x0​).

behOf. The behavioural strategy on G(x0)G(x_0)G(x0​) whose next-move distribution is nextOf\mathrm{nextOf}nextOf for A,x0A, x_0A,x0​.

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