Lemma 9, p. 58 (corrected: R_1 ≥ 0) — for w_2 = mτ + zq_{2→1}(τ), m > R_1, and z/(m − R_1) in the window, r(u, 2, w, σ) > 0 for all u, σ_2; the window is nonempty
ProvedDriverSurge.IC.lemma_9incentive-compatibilityp2o-batch-pfp2ap2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1surge-pricing
Fix a non-surge policy and a payment integrable on it, with , and . Let , be the values of , at , assume finite means, and let with . If
then for every and every open ; hence wherever . Furthermore the constraint set is feasible regardless of the primitives: the lower bound is strictly below the upper bound.
Lemma 9 makes accepting every surge trip optimal; it is one half of the incentive-compatibility argument of Theorem 3.
Formalization Note Lean state 0 is the paper's non-surge state 1 and Lean state 1 the surge state 2; other i is the state . The denominators are positive: and (Remark 4).
Differences from the source:
- correction: arbitrary → assumed; reason: the proof's step "" (p. 66) needs , and the lemma fails without it, even under D.3.1's standing assumptions: with , , , , , (so ), , inside the window , and , one gets ; state 2 dominates state 1 there, since for every while (
checks/lemma9_counterexample_surge.py) - reading: ", for all " → for every ; reason: D.3.1 fixes as "same sign except where "; the proof (p. 65) establishes positivity of the expression
- reading: "the constraint set is feasible" → the lower end of the window is strictly below the upper end; reason: the proof (p. 66) shows exactly this inequality
- encoding: implicitly finite → finite means; -integrable on ; reason: , are undefined otherwise; only undefined cases are excluded
- generalization: D.3.1's standing assumptions (p. 56): has a bounded density, and state 2 dominates state 1 ( with for all ) → not assumed; reason: the proof (pp. 65–66) is algebra on and does not use them (with the lemma held on every one of 300 random primitives × 30 random ,
checks/lemma9_10_check.py), so it specializes to the source
Preamble
import Mathlib import Definitions.Def_DriverSurge_IC_Pricing
Formal statement
namespace DriverSurge.IC
open MeasureTheory Set
/-- Lemma 9 (p. 58; corrected: `R_1 ≥ 0`). Fix a non-surge policy `s₁` (state 1 = Lean `0`) and a
payment `w_1` integrable on it, with `Q_1 = Q_1(s₁)`, `T_1 = T_1(s₁)`, `R_1 = R_1(w_1, s₁) ≥ 0`; let
`Q̄_2`, `T̄_2` be the surge-state values at `(0, ∞)`, and `w_2(τ) = mτ + zq_{2→1}(τ)` with `m > R_1`. If
`[T_1(λ_{2→1}T̄_2 − Q̄_2) − (Q_1 + T_1λ_{2→1})] / [Q_1(λ_{2→1}T̄_2 − Q̄_2) + λ_{2→1}(Q_1 + T_1λ_{2→1})] < z/(m − R_1) < (Q̄_2T_1 + Q_1)/(Q_1(Q̄_2 − λ_{2→1}))`,
then `r(u, 2, w, {s₁, s₂}) > 0` for every `u > 0` and every open `s₂ ⊆ (0, ∞)` (so `∂/∂u R(w, σ) > 0` in
the `∝` sense of D.3.1). Moreover the lower bound is below the upper bound (the constraint set is
feasible). -/
theorem lemma_9 (P : Primitives) (hmean : FiniteMean P) (w : Fin 2 → ℝ → ℝ) (s₁ : Set ℝ)
(hs₁ : IsAdmissible s₁) (hw0 : IntegrableOn (w 0) s₁ (P.F 0)) (m z : ℝ)
(hw1 : w 1 = fun τ => m * τ + z * q P 1 τ)
(hR : 0 ≤ stateRate P 0 (w 0) s₁) (hm : stateRate P 0 (w 0) s₁ < m) :
((Tn P 0 s₁ * (P.sw 1 * Tn P 1 (Ioi 0) - Qn P 1 (Ioi 0)) - (Qn P 0 s₁ + Tn P 0 s₁ * P.sw 1)) /
(Qn P 0 s₁ * (P.sw 1 * Tn P 1 (Ioi 0) - Qn P 1 (Ioi 0)) +
P.sw 1 * (Qn P 0 s₁ + Tn P 0 s₁ * P.sw 1)) <
z / (m - stateRate P 0 (w 0) s₁) →
z / (m - stateRate P 0 (w 0) s₁) <
(Qn P 1 (Ioi 0) * Tn P 0 s₁ + Qn P 0 s₁) / (Qn P 0 s₁ * (Qn P 1 (Ioi 0) - P.sw 1)) →
∀ s₂ : Set ℝ, IsAdmissible s₂ → ∀ u : ℝ, 0 < u → 0 < rFun P w ![s₁, s₂] 1 u) ∧
(Tn P 0 s₁ * (P.sw 1 * Tn P 1 (Ioi 0) - Qn P 1 (Ioi 0)) - (Qn P 0 s₁ + Tn P 0 s₁ * P.sw 1)) /
(Qn P 0 s₁ * (P.sw 1 * Tn P 1 (Ioi 0) - Qn P 1 (Ioi 0)) +
P.sw 1 * (Qn P 0 s₁ + Tn P 0 s₁ * P.sw 1)) <
(Qn P 1 (Ioi 0) * Tn P 0 s₁ + Qn P 0 s₁) / (Qn P 0 s₁ * (Qn P 1 (Ioi 0) - P.sw 1)) := by sorry
end DriverSurge.IC
Source
Garg, Nazerzadeh, Driver Surge Pricing, arXiv:1905.07544v4, p. 58, Lemma 9 (proof pp. 65–66)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.