The 2-taxi problem on as a costed AJ game
DefinitionAJOnline_KTaxi2Fix a labelled start , with configuration (a multiset).
- Moves. Opponent's moves are requests , with the pickup and drop-off. Player's moves are , , meaning the taxi standing at is sent.
- Legal plays. A legal play is a sequence , possibly ending with one unanswered request. Each must lie in the current configuration , and the configuration updates as
- Costs. The algorithm's cost of a play is , the empty drives. The offline optimum is the platform's of its requests.
- Policies as strategies. A memoryless policy (a law over serving locations for each configuration and request, supported on occupied locations and lazy) becomes the behaviour strategy . After a request in configuration , draws the serving location from 's law at . 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 . Serving from an unoccupied location is illegal; without this, serving from the pickup would cost nothing.
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
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 , a labelling , 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 is a function assigning to every finite multiset of reals and every pair a discrete probability distribution on (a probability mass function, so it has countable support). Two constraints hold, and only when (multiset cardinality): (supported) every with lies in ; (lazy) if then is the point mass at . For multisets of any other size the law is unconstrained.
- , for , is the two-element multiset . The two values may be equal, in which case it is .
- for reals is , read as an element of .
- , for a finite list of pairs, is the infimum (in ) over all assignments of the schedule cost: start with labelled servers at ; for the server pays and then moves, at no cost, to . For it is .
- A behavioural strategy for a game gives, for every finite move sequence (position or not), a probability distribution on "no move" () or a move . Legality: if gives positive probability to a move , then the last move of exists and is labelled , is labelled , and if is a position then is a position.
Mv. The type of moves: either for a pair , or for a real .
lab. Requests are labelled ; serves are labelled .
Valid. A predicate on a multiset of reals and a move list , defined by recursion:
and false for every other shape (a list starting with a serve, or with two requests in a row). Here removes one copy of . So a valid list alternates request, serve, request, serve, ..., possibly ending with an unanswered request; each serve point must belong to the current multiset, after which one copy of is replaced by the request's second coordinate . Note that the serve point is not required to equal or to relate to 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 ; consecutive moves of a valid list have different labels.
game. For , the game has moves , labelling lab, and positions exactly the lists with . The game-axioms are discharged by the three lemmas above.
cfg. follows the same recursion as Valid without checking membership: , and for any other shape (empty list, a lone trailing request, or a malformed list). If , 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. , and 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 is free.
reqs. is the list of the pairs of all request moves in , in order (serves deleted). A trailing unanswered request is included.
costed. The costed game for : underlying game , algorithm cost , and optimum cost , both in , both defined on all move lists.
cfg_card (lemma). If and then .
valid_snoc_serve (lemma). If , the last move of is , and , then is valid.
nextOf. For a memoryless policy and , and any list : if the last move of is , then is the distribution of with (always a move, never "no move"); otherwise (empty , 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). .
nextOf_legal (lemma). nextOf satisfies the behavioural-strategy legality condition for .
behOf. The behavioural strategy on whose next-move distribution is for .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.