Theorem 15, p. 18 — elevated-flow-relaxation prices earn at least m/(m+n−1) of the optimal state-dependent objective (corrected: q̃'s support graph strongly connected)
ProvedSharedVehicleApprox.Pricing.theorem_15Consider the shared vehicle system with nodes, units and arrival rates , and per-ride rewards whose reward curves are concave on . Let be an optimal solution of the elevated flow relaxation program (Algorithm 1),
whose support graph is strongly connected, and let be a stationary law of the -unit system in which is quoted at every non-empty station. Then for every state-dependent quantile policy and every stationary law of it,
where is the steady-state objective (2) under the respective law. In the paper's notation, (10).
The guarantee covers throughput, social welfare and revenue with regular value distributions simultaneously, and shows that a single convex program yields state-independent prices within a factor of the best state-dependent policy, whose description is exponential in .
Formalization Note The state-independent is run as the state-dependent policy ; since this gives the paper's (6). The ratio is written as a product, so no division by occurs.
Differences from the source:
- correction: no connectivity hypothesis on q̃ (the paper treats π as unique, p. 7, and assumes irreducibility, p. 16 and App. A) → hypothesis SupportConnected φ q̃; reason: the printed statement is false without it: n = 2, m = 2, φ ≡ 1, I_11 = I_22 = 1, I_12 = I_21 = 0; balanced demand forces q_12 = q_21, so q̃ = (1, 0, 0, 1) is optimal with value 2; every law on S_{2,2} is stationary under q̃, and π̃ = δ_{(2,0)} gives Obj_2(q̃) = 1, while the state-dependent policy x ↦ q̃·1{x_i > 0} with π = δ_{(1,1)} earns 2, and 2/3 · 2 = 4/3 > 1
- encoding: Opt_m, the objective of the optimal state-dependent policy → the bound is stated against every state-dependent policy q (IsPolicy) and every stationary law π of it; reason: a bound against every (policy, law) pair is exactly a bound against their supremum, with no sSup and no attainment needed; p. 7 measures upper bounds against the best-possible steady-state distribution
- encoding: Obj_m(q̃), with "the" stationary distribution of q̃ and the ratio m/(m+n−1)·Opt_m → any stationary law π̃ of toPolicy q̃, and (m/(m+n−1))·Obj_m(q, π) ≤ Obj_m(toPolicy q̃, π̃); reason: under the connectivity hypothesis the stationary law is unique, and quantifying over all laws avoids assuming it; toPolicy builds in q̃_ij(x) = 0 at empty stations
- encoding: π is the steady-state distribution of the policy, treated as unique (p. 7) → π is any probability vector on S_{n,m}, zero off S_{n,m}, satisfying the balance equation (1) at every state; reason: p. 7: "our upper bounds are all with respect to the best-possible steady-state distribution"; (1) is the paper's characterization of stationarity, and Mathlib has no continuous-time Markov chains
- generalization: per-ride rewards I_ij(p_ij) of prices, with value distributions F_ij and I_ij(q) := I_ij(F_ij^{-1}(1 − q)) (pp. 6–8) → arbitrary real functions I_ij of the quantile q ∈ [0, 1], with R_ij(q) := q · I_ij(q); no F_ij; reason: every I_ij induced by value distributions is such a function, so the statement specializes to the paper's; the density and F_ij(0) < 1 assumptions of p. 6 only make the price–quantile map a bijection
import Mathlib import Definitions.Def_QueueingFundamentals_Networks_ClosedJackson import Definitions.Def_SharedVehicleApprox_Pricing_Model open Finset QueueingFundamentals.Networks Filter Topology
namespace SharedVehicleApprox.Pricing
/-- Theorem 15, p. 18 (corrected: the support graph of `q̃` is strongly connected): for
concave reward curves, the state-independent quantiles `q̃` returned by Algorithm 1 earn, under
any stationary law of the `m`-unit system, at least `m/(m+n−1)` times the objective of every
state-dependent policy under every stationary law of it: `Obj_m(q̃) ≥ m/(m+n−1) · Opt_m`. -/
theorem theorem_15 {n m : ℕ} (φ : Fin n → Fin n → ℝ) (hφ : ∀ i j, 0 ≤ φ i j)
(I : Fin n → Fin n → ℝ → ℝ)
(hR : ∀ i j, ConcaveOn ℝ (Set.Icc (0 : ℝ) 1) (rewardCurve I i j))
(qt : Fin n → Fin n → ℝ) (hopt : IsRelaxOptimal φ I qt) (hconn : SupportConnected φ qt)
(πt : (Fin n → ℕ) → ℝ) (hπt : IsStationary n m φ (toPolicy qt) πt)
(q : (Fin n → ℕ) → Fin n → Fin n → ℝ) (π : (Fin n → ℕ) → ℝ)
(hq : IsPolicy n m q) (hπ : IsStationary n m φ q π) :
(m : ℝ) / ((m : ℝ) + n - 1) * obj n m φ I q π ≤ obj n m φ I (toPolicy qt) πt := by sorry
end SharedVehicleApprox.Pricing
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.