No memoryless 2-taxi policy is competitive as an AJ behaviour strategy
OpenAJOnline.KTaxi2.frontierFor every memoryless 2-taxi policy , every labelled start , every and every , the behaviour strategy is not -randomised-competitive on the 2-taxi game from . That is, some finite request script gives
By the bridge, this statement is equivalent to the platform's KTaxi.Competitive.Supplement.theorem_1_3.
import Mathlib import Definitions.Def_AJOnline_KTaxi2
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.KTaxi2Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Read-back: frontier
Statement. For every memoryless policy , every starting placement of two servers, and all with , the behavioural strategy on the costed game for is not -randomised-competitive. Equivalently: there exists a finite opponent script 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$.Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.