Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 10, p. 16 — balanced demand implies equal availabilities at all nodes, for every m and for m = ∞ (corrected: support of q strongly connected)

Proved
SharedVehicleApprox.Pricing.lemma_10

by mikedeng1 · Oct 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

availabilityclosed-queueing-networkp2o-batch-pfp2ap2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-v1pricing

Let φij≥0\varphi_{ij}\ge0φij​≥0 be arrival rates on n≥1n\ge1n≥1 nodes and let q∈[0,1]n×nq\in[0,1]^{n\times n}q∈[0,1]n×n be a state-independent quantile matrix with balanced demand, ∑kφkiqki=∑jφijqij\sum_k\varphi_{ki}q_{ki}=\sum_j\varphi_{ij}q_{ij}∑k​φki​qki​=∑j​φij​qij​ for every iii, whose support graph {(a,b):a≠b, φabqab>0}\{(a,b):a\ne b,\ \varphi_{ab}q_{ab}>0\}{(a,b):a=b, φab​qab​>0} is strongly connected. Then

  1. for every mmm and every stationary law π\piπ of the mmm-unit system run under qqq, the availabilities Ai,m=∑x∈Sn,mπ(x)1{xi>0}A_{i,m}=\sum_{x\in S_{n,m}}\pi(x)\mathbf 1\{x_i>0\}Ai,m​=∑x∈Sn,m​​π(x)1{xi​>0} are equal at all nodes;
  2. for every positive solution rrr of the traffic equations of qqq, the infinite-unit availabilities Ai,∞=ri/max⁡jrjA_{i,\infty}=r_i/\max_jr_jAi,∞​=ri​/maxj​rj​ are equal at all nodes.

Combined with Proposition 6 this shows that every node of a balanced policy has infinite-unit availability 111 (Lemma 11).

Differences from the source:

  • correction: no connectivity hypothesis (the proof invokes "the assumption that our system is irreducible (see Appendix A)") → hypothesis SupportConnected φ q; reason: the printed statement is false without it: n = 2, m = 2, φ_ij = 1 for all i, j, q = (q_11, q_12, q_21, q_22) = (1, 0, 0, 1): q is balanced; under q no ride changes the state, so every law on S_{2,2} satisfies (1), and δ_{(2,0)} gives A_1 = 1 ≠ 0 = A_2
  • encoding: "for any m (including ∞)" → clause 1 for every finite m and every stationary law; clause 2 for A_{i,∞} = r_i/max_j r_j with r any positive traffic solution; reason: the infinite-unit availabilities are r_i/max_j r_j by Proposition 6; under connectivity every positive traffic solution is a multiple of r(q)
  • 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
Preamble
import Mathlib
import Definitions.Def_QueueingFundamentals_Networks_ClosedJackson
import Definitions.Def_SharedVehicleApprox_Pricing_Model

open Finset QueueingFundamentals.Networks Filter Topology
Formal statement
namespace SharedVehicleApprox.Pricing

/-- Lemma 10, p. 16: if a state-independent `q` with strongly connected support satisfies balanced
demand, then (a) for every `m`, every stationary law of the `m`-unit system gives all nodes the
same availability, and (b) the infinite-unit availabilities `r_i / r_max` are all equal. -/
theorem lemma_10 {n : ℕ} [NeZero n] (φ : Fin n → Fin n → ℝ) (hφ : ∀ i j, 0 ≤ φ i j)
    (q : Fin n → Fin n → ℝ) (hq : ∀ i j, 0 ≤ q i j ∧ q i j ≤ 1) (hbal : IsBalanced φ q)
    (hconn : SupportConnected φ q) :
    (∀ (m : ℕ) (π : (Fin n → ℕ) → ℝ), IsStationary n m φ (toPolicy q) π →
      ∀ i j, availability m π i = availability m π j) ∧
    (∀ r : Fin n → ℝ, (∀ i, 0 < r i) → IsTraffic φ q r →
      ∀ i j, availInf r i = availInf r j) := by sorry

end SharedVehicleApprox.Pricing
Source
Banerjee, Freund & Lykouris, Pricing and Optimization in Shared Vehicle Systems: An Approximation Framework, arXiv:1608.06819v4, p. 16 (PDF 17), Lemma 10
Human review
  • Endorsed by Shuze Chen · Oct 24, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 24, 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