Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

No memoryless 2-taxi policy is competitive as an AJ behaviour strategy

Open
AJOnline.KTaxi2.frontier

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

game-semanticsonline-algorithms

For every memoryless 2-taxi policy AAA, every labelled start x0∈R2x_0\in\mathbb R^2x0​∈R2, every ρ≥1\rho\ge1ρ≥1 and every b≥0b\ge0b≥0, the behaviour strategy βA\beta_AβA​ is not (ρ,b)(\rho,b)(ρ,b)-randomised-competitive on the 2-taxi game from x0x_0x0​. That is, some finite request script gives

E[alg]>ρ E[opt]+b.\mathbb E[\mathrm{alg}]>\rho\,\mathbb E[\mathrm{opt}]+b .E[alg]>ρE[opt]+b.

By the bridge, this statement is equivalent to the platform's KTaxi.Competitive.Supplement.theorem_1_3.

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

open AJGames KTaxi.Competitive.Supplement
open scoped ENNReal NNReal

/-- **Frontier: no memoryless 2-taxi policy is competitive, as an AJ behaviour strategy.** Open. It
reduces to the platform's open `KTaxi.Competitive.Supplement.theorem_1_3` through
`competitive_transfer` (see the sketch). AJ axioms used: none beyond the definitions. -/
theorem frontier (A : MemorylessPolicy) (x₀ : Fin 2 → ℝ) (ρ b : ℝ≥0) (hρ : 1 ≤ ρ) :
    ¬ RandCompetitive (costed x₀) (behOf A x₀) ρ b := by sorry

end AJOnline.KTaxi2
Source
AJ form 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, Theorem 1.3, PDF p. 23 (printed p. 22)
Read-back

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

Read-back: frontier

Statement. For every memoryless policy AAA, every starting placement x0:{0,1}→Rx_0:\{0,1\}\to\mathbb{R}x0​:{0,1}→R of two servers, and all ho,b∈R≥0 ho, b \in \mathbb{R}_{\ge 0}ho,b∈R≥0​ with ho≥1 ho \ge 1ho≥1, the behavioural strategy behOf(A,x0)\mathrm{behOf}(A,x_0)behOf(A,x0​) on the costed game for x0x_0x0​ is not (ho,b)( ho,b)(ho,b)-randomised-competitive. Equivalently: there exists a finite opponent script rsrsrs of moves with

ho Every $x_0$ is covered, including $x_0(0)=x_0(1)$. The case $ ho<1$ is not addressed. $b$ is a finite nonnegative real. No assumption on $A$ beyond being a memoryless policy. **Definitions used.** - *The game $G(x_0)$.* Moves are requests $\mathrm{req}(q)$, $q = (q_1,q_2)\in\mathbb{R}^2$ (labelled $O$), and serves $\mathrm{serve}(a)$, $a\in\mathbb{R}$ (labelled $P$). Positions are the lists that alternate request, serve, request, serve, ..., possibly ending in an unanswered request, such that, starting from the multiset $X_0 = \{x_0(0), x_0(1)\}$, each serve point $a$ lies in the current multiset $X$, after which $X$ becomes $(X\setminus\{a\})+\{q_2\}$ (one copy of $a$ replaced by the request's second coordinate). The serve point need not equal $q_1$. $\mathrm{cfg}(s)$ is the multiset reached after the completed request/serve pairs of $s$ (a trailing unanswered request is ignored). The two entries of $x_0$ may coincide. - *Costs.* $\mathrm{alg}(s)$ is the sum over the completed pairs $\mathrm{req}(q)\,\mathrm{serve}(a)$ of $|a-q_1|$ (relocation to $q_2$ is free; a trailing request costs $0$). $\mathrm{opt}(s) = \mathrm{optCost}(x_0, \mathrm{reqs}(s))$, where $\mathrm{reqs}(s)$ lists all requested pairs in $s$ (including a trailing one) and $\mathrm{optCost}(x_0, (q^{(1)},\dots,q^{(n)}))$ is the minimum over all $2^n$ assignments of requests to two labelled servers starting at $x_0(0), x_0(1)$ of the total cost, where serving $q^{(j)}$ with a server costs $|\text{server position} - q^{(j)}_1|$ and moves that server to $q^{(j)}_2$ for free (it is $0$ when $n=0$). All costs live in $[0,\infty]$. - *Behavioural strategy.* A behavioural strategy $\beta$ on $G(x_0)$ assigns to every finite move list $s$ a discrete probability distribution $\beta.\mathrm{next}(s)$ on $\{\text{no move}\}\cup\mathrm{Mv}$, subject to legality: positive probability on a move $m$ only if the last move of $s$ exists and is a request, $m$ is a serve, and ($s$ a position $\Rightarrow$ $s\cdot m$ a position). - *Play-out.* Given an opponent script $rs$ (an arbitrary finite list of moves, requests or serves), $\mathrm{playOut}_\beta(s, rs)$ is the random final history defined by: if $rs$ is empty, stop with $s$; if $rs = r\cdot rs'$ and $r$ is a request with $s\cdot r$ a position, sample $o\sim\beta.\mathrm{next}(s\cdot r)$; if $o$ is "no move" stop with $s\cdot r$ (the rest of the script is discarded); if $o = m$, continue from $s\cdot r\cdot m$ with $rs'$. Otherwise ($r$ is a serve, or $s\cdot r$ is not a position) stop with $s$, discarding $r$ and the rest. Play starts from the empty history. - *Expected costs.* $\mathrm{expAlg}(\beta, rs) = \sum_s \Pr[\mathrm{playOut}_\beta([\,], rs) = s]\cdot\mathrm{alg}(s)$ and $\mathrm{expOpt}(\beta, rs) = \sum_s \Pr[\mathrm{playOut}_\beta([\,], rs) = s]\cdot\mathrm{opt}(s)$, sums in $[0,\infty]$. Note that $\mathrm{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 $\rho, b\in\mathbb{R}_{\ge 0}$, $\beta$ is $(\rho,b)$-randomised-competitive iff for **every** finite move list $rs$,

\mathrm{expAlg}(\beta, rs) \le \rho\cdot\mathrm{expOpt}(\beta, rs) + b \quad\text{in } [0,\infty].

- *Memoryless policy.* $A$ assigns to every finite multiset $X$ of reals and every pair $q=(q_1,q_2)$ a discrete probability distribution $A_{X,q}$ on $\mathbb{R}$, such that whenever $|X| = 2$: (supported) $A_{X,q}(a)\neq 0 \Rightarrow a\in X$, and (lazy) $q_1\in X \Rightarrow A_{X,q}$ is the point mass at $q_1$. Nothing is required when $|X|\neq 2$. - *The strategy $\mathrm{behOf}(A,x_0)$.* On any list $s$ whose last move is $\mathrm{req}(q)$, it plays $\mathrm{serve}(a)$ with $a\sim A_{\mathrm{cfg}(s),q}$ (it never chooses "no move" there); on every other list (empty, or ending in a serve) it chooses "no move" with probability $1$.
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