Converse bridge: history-free lazy strategies come from memoryless policies
OpenAJOnline.KTaxi2.converse_bridgeFix , and let be a behaviour strategy on the 2-taxi game satisfying three conditions at legal positions:
- depends only on the current configuration and the last move;
- after a request, never chooses ;
- is lazy: after a request whose pickup is occupied, it serves from with probability .
Then there is a memoryless policy such that and agree at every legal position.
Together with the bridge, this identifies the platform's memoryless policies with the AJ behaviour strategies of this form.
import Mathlib import Definitions.Def_AJOnline_KTaxi2
namespace AJOnline.KTaxi2
open AJGames KTaxi.Competitive.Supplement
open scoped ENNReal NNReal
/-- **Converse bridge.** A behaviour strategy on the 2-taxi game that, at legal positions, depends
only on (current configuration, last move), never stops after a request, and is lazy (serves from
the pickup when a taxi already stands there) agrees at every legal position with a memoryless
policy read as a behaviour strategy. -/
theorem converse_bridge (x₀ : Fin 2 → ℝ) (β : BehStrategy (game x₀))
(hdep : ∀ s ∈ (game x₀).pos, ∀ t ∈ (game x₀).pos,
cfg (locations x₀) s = cfg (locations x₀) t → s.getLast? = t.getLast? → β.next s = β.next t)
(hstop : ∀ s ∈ (game x₀).pos, ∀ q, s.getLast? = some (Mv.req q) → β.next s none = 0)
(hlazy : ∀ s ∈ (game x₀).pos, ∀ q, s.getLast? = some (Mv.req q) →
q.1 ∈ cfg (locations x₀) s → β.next s = PMF.pure (some (Mv.serve q.1))) :
∃ A : MemorylessPolicy, ∀ s ∈ (game x₀).pos, (behOf A x₀).next s = β.next s := by sorry
end AJOnline.KTaxi2Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Read-back: converse_bridge
Statement. Fix , write , and let be any behavioural strategy on . Assume:
- (dep) for all positions of with and the same last move (both empty, or both ending in the identical move), ;
- (stop) for every position whose last move is (any ), gives probability to "no move";
- (lazy) for every position whose last move is with , is the point mass on .
Then there exists a memoryless policy such that for every position of , (equality of distributions). Agreement is asserted only on positions, not on arbitrary lists, and is only required to exist (its values on multisets or pairs never reached by a position are unconstrained by the conclusion, though must still satisfy the policy conditions everywhere).
Here is the multiset reached after the completed request/serve pairs of (a trailing unanswered request is ignored). On positions that are empty or end in a serve, chooses "no move" with probability ; the legality condition on forces the same there.
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).
- 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 .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.