Lemma 10, p. 58 (corrected: R_2 > 0) — for w_1 = R_2τ + zq_{1→2}(τ) and z/R_2 in the window, r(u, 1, w, σ) > 0 for all u, σ_1; the window is nonempty
ProvedDriverSurge.IC.lemma_10incentive-compatibilityp2o-batch-pfp2ap2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1surge-pricing
Fix a 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 10 makes accepting every non-surge trip optimal; with Lemma 9 it yields the incentive-compatible prices of Theorem 3, and the constant is what its window imposes on .
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: for an arbitrary and , of any sign; the window divides by → assumed; reason: for the lemma fails: lies in the window (its lower end is negative, its upper end positive) and Remark 2 gives for every and every ; e.g. all rates , , , (so ) and , where state 2 dominates state 1 because for every while ; at the quotient is undefined (Lean's would be junk)
- 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 meaning in the proof of Lemma 9, mirrored
- 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 (p. 66) is algebra on and does not use them (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 10 (p. 58). Fix a surge policy `s₂` (state 2 = Lean `1`) and a payment `w_2` integrable on it,
with `Q_2 = Q_2(s₂)`, `T_2 = T_2(s₂)` and `R_2 = R_2(w_2, s₂) > 0`; let `Q̄_1`, `T̄_1` be the non-surge
values at `(0, ∞)`, and `w_1(τ) = mτ + zq_{1→2}(τ)` with `m = R_2`. If
`−(T_2λ_{1→2} + Q_2) / [Q_2(λ_{1→2}T̄_1 − Q̄_1) + λ_{1→2}(T_2λ_{1→2} + Q_2)] < z/R_2 < 1/(Q̄_1 − λ_{1→2})`,
then `r(u, 1, 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_10 (P : Primitives) (hmean : FiniteMean P) (w : Fin 2 → ℝ → ℝ) (s₂ : Set ℝ)
(hs₂ : IsAdmissible s₂) (hw1 : IntegrableOn (w 1) s₂ (P.F 1)) (z : ℝ)
(hR : 0 < stateRate P 1 (w 1) s₂)
(hw0 : w 0 = fun τ => stateRate P 1 (w 1) s₂ * τ + z * q P 0 τ) :
(-(Tn P 1 s₂ * P.sw 0 + Qn P 1 s₂) /
(Qn P 1 s₂ * (P.sw 0 * Tn P 0 (Ioi 0) - Qn P 0 (Ioi 0)) +
P.sw 0 * (Tn P 1 s₂ * P.sw 0 + Qn P 1 s₂)) <
z / stateRate P 1 (w 1) s₂ →
z / stateRate P 1 (w 1) s₂ < 1 / (Qn P 0 (Ioi 0) - P.sw 0) →
∀ s₁ : Set ℝ, IsAdmissible s₁ → ∀ u : ℝ, 0 < u → 0 < rFun P w ![s₁, s₂] 0 u) ∧
-(Tn P 1 s₂ * P.sw 0 + Qn P 1 s₂) /
(Qn P 1 s₂ * (P.sw 0 * Tn P 0 (Ioi 0) - Qn P 0 (Ioi 0)) +
P.sw 0 * (Tn P 1 s₂ * P.sw 0 + Qn P 1 s₂)) <
1 / (Qn P 0 (Ioi 0) - P.sw 0) := by sorry
end DriverSurge.IC
Source
Garg, Nazerzadeh, Driver Surge Pricing, arXiv:1905.07544v4, p. 58, Lemma 10 (proof pp. 66–67)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.