Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§3.1 counterexample — optimal expected revenue 440,bestbid−pricecontrol440, best bid-price control 440,bestbid−pricecontrol400

Proved
BidPriceControl.NonOptimal.bid_price_controls_not_optimal

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

counterexampledynamic-programmingp2o-batch-rm-cafterp2o-gran-per-chapterp2o-plan-paperp2o-v1revenue-management

Consider the network of §3.1 and Table 1: two legs with one seat each, the through itinerary (1,1)(1,1)(1,1) and the local itineraries (1,0)(1,0)(1,0) and (0,1)(0,1)(0,1), and two periods to go. In period 2 a through request with fare $500 arrives with probability 0.4 and a request for each local itinerary with fare $250 with probability 0.3; in period 1 a through request with fare $500 arrives with probability 0.8 and nothing arrives with probability 0.2. For an admissible control uuu let V2u(1,1)V^u_2(1,1)V2u​(1,1) be its expected revenue, and for bid prices μ\muμ let uμu^\muuμ be the bid-price control of Definition 1. Then

max⁡u admissibleV2u(1,1)=440andmax⁡μV2uμ(1,1)=400,\max_{u \text{ admissible}} V^u_2(1,1) = 440 \qquad\text{and}\qquad \max_{\mu} V^{u^\mu}_2(1,1) = 400,u admissiblemax​V2u​(1,1)=440andμmax​V2uμ​(1,1)=400,

both maxima being attained: some admissible control earns exactly 440 and none earns more, some bid prices earn exactly 400 and none earn more.

The optimal policy thus earns 10% more expected revenue than the best bid-price policy, so bid-price controls are not optimal in general, even though Proposition 1 shows that the optimal policy compares each fare with an opportunity cost.

Formalization Note. The maximum over bid-price controls ranges over all real bid prices μti(y)\mu_t^i(y)μti​(y), positive or negative, depending on the period and the remaining capacity; the maximum over admissible controls ranges over all Markov controls whose decisions lie in U(y)\mathcal{U}(y)U(y) and are measurable in the request. A bid-price control accepts only the arriving request, at most one itinerary per period. The instance has deterministic fares, which the paper notes violates its continuity assumption; continuity is not assumed anywhere in this mission.

Preamble
import Mathlib
import Definitions.Def_BidPriceControl_NonOptimal_Model
import Definitions.Def_BidPriceControl_NonOptimal_CounterExample
Formal statement
namespace BidPriceControl.NonOptimal

open MeasureTheory

/-- The counterexample of §3.1 (pp. 1581–1582): in the two-leg, two-period instance of Table 1
with one seat on each leg, the optimal expected revenue over all admissible controls is $440, and
it is attained, while the best bid-price control (Definition 1, with arbitrary real bid prices
depending on time and capacity) earns exactly $400. -/
theorem bid_price_controls_not_optimal :
    (∃ u : Control 2 3, IsAdmissible ceA u ∧ controlValue ceA ceLaw u 2 ceX = 440) ∧
    (∀ u : Control 2 3, IsAdmissible ceA u → controlValue ceA ceLaw u 2 ceX ≤ 440) ∧
    IsGreatest {v : ℝ | ∃ μ : ℕ → (Fin 2 → ℕ) → Fin 2 → ℝ,
      v = controlValue ceA ceLaw (bidPriceControl ceA μ) 2 ceX} 400 := by sorry

end BidPriceControl.NonOptimal
Source
Talluri, van Ryzin, An Analysis of Bid-Price Controls for Network Revenue Management, Management Sci. 44(11), 1998, pp. 1581–1582, §3.1 (counterexample to bid-price optimality) and Table 1
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

The statement makes a single closed claim with no hypotheses or free variables. It uses one type family and several constants defined in imported files that are not shown here. The read-back gives each of them only the role its type and use reveal. Their meaning is not unfolded here:

  • Control2,3\mathsf{Control}_{2,3}Control2,3​ is a type whose elements are called controls. It depends on the two numerals 222 and 333.
  • A\mathcal{A}A (ceA), P\mathbb{P}P (ceLaw) and x0x_0x0​ (ceX) are fixed constants.
  • AdmA(u)\mathrm{Adm}_{\mathcal{A}}(u)AdmA​(u) (IsAdmissible ceA u) is a yes-or-no property of a control uuu, relative to A\mathcal{A}A.
  • V(u):=controlValue(A,P,u,2,x0)V(u) := \mathrm{controlValue}(\mathcal{A}, \mathbb{P}, u, 2, x_0)V(u):=controlValue(A,P,u,2,x0​) is a real number assigned to the control uuu. The other arguments are fixed: A\mathcal{A}A, P\mathbb{P}P, the numeral 222 and x0x_0x0​.
  • BPA(μ)\mathrm{BP}_{\mathcal{A}}(\mu)BPA​(μ) (bidPriceControl ceA μ) is a control built from A\mathcal{A}A and a function μ\muμ. Here μ\muμ takes a natural number ttt and a pair of natural numbers c=(c1,c2)∈N2c = (c_1, c_2) \in \mathbb{N}^2c=(c1​,c2​)∈N2, and returns a pair of real numbers μ(t,c)=(μ1(t,c),μ2(t,c))∈R2\mu(t, c) = (\mu_1(t,c), \mu_2(t,c)) \in \mathbb{R}^2μ(t,c)=(μ1​(t,c),μ2​(t,c))∈R2.

The declaration asserts that all three of the following hold at once:

  1. Attainment of 440. At least one control u∈Control2,3u \in \mathsf{Control}_{2,3}u∈Control2,3​ is admissible and has
V(u)=440.V(u) = 440.V(u)=440.
  1. Upper bound 440 on admissible controls. Every control u∈Control2,3u \in \mathsf{Control}_{2,3}u∈Control2,3​ that is admissible satisfies
V(u)≤440.V(u) \le 440.V(u)≤440.

Controls that are not admissible are not constrained by this clause.

  1. 400 is the largest value of a bid-price control. Define the set of real numbers
S={ V(BPA(μ))  :  μ:N×N2→R2 arbitrary }.S = \bigl\{\, V(\mathrm{BP}_{\mathcal{A}}(\mu)) \;:\; \mu : \mathbb{N} \times \mathbb{N}^2 \to \mathbb{R}^2 \text{ arbitrary} \,\bigr\}.S={V(BPA​(μ)):μ:N×N2→R2 arbitrary}.

Then 400400400 is the greatest element of SSS. So there is some μ\muμ with V(BPA(μ))=400V(\mathrm{BP}_{\mathcal{A}}(\mu)) = 400V(BPA​(μ))=400, and every μ\muμ gives V(BPA(μ))≤400V(\mathrm{BP}_{\mathcal{A}}(\mu)) \le 400V(BPA​(μ))≤400.

  • The μ\muμ in SSS range over all real-valued functions. Values may be negative, zero or arbitrarily large, and there is no condition of monotonicity, measurability or boundedness.
  • Clause 3 does not require BPA(μ)\mathrm{BP}_{\mathcal{A}}(\mu)BPA​(μ) to be admissible, and it says nothing either way about whether it is.
  • The statement never links clause 3 to clauses 1–2. The strict gap 400<440400 < 440400<440 therefore compares the best bid-price value against the best admissible value only as two separate numbers. It is not stated as a comparison over one common class of controls.

The accompanying documentation comment is not part of the assertion. Nothing in the statement itself fixes what the "two legs", "two periods", "one seat" or "revenue" in that comment correspond to. That depends entirely on the unseen definitions of Control\mathsf{Control}Control, Adm\mathrm{Adm}Adm, VVV, BP\mathrm{BP}BP, A\mathcal{A}A, P\mathbb{P}P and x0x_0x0​.

Degenerate cases. The statement has no binders or hypotheses of its own, so it has no empty-type or zero-count instances. Its only parameters are the fixed numerals 222, 333 and 222.

  • Admissibility cannot be vacuous. Clause 1 asserts that an admissible control exists, so clause 2 is not vacuously true.
  • Clause 3 is not vacuous either. Its set SSS is nonempty, because functions μ\muμ always exist, for example μ≡0\mu \equiv 0μ≡0. It is also asserted to contain 400400400 and be bounded above by it.
  • Default values may be counted. Nothing in the statement rules out that VVV is computed through operations that return default values. Examples are an expectation or integral that returns 000 for a non-integrable integrand, division by zero, or subtraction in N\mathbb{N}N that truncates at 000. If so, 440440440 and 400400400 are asserted about whatever value VVV returns in those cases.
  • Clause 3 covers every μ\muμ. This includes μ\muμ whose values at time indices ttt or capacity vectors ccc that never occur are arbitrary. It also includes μ\muμ for which BPA(μ)\mathrm{BP}_{\mathcal{A}}(\mu)BPA​(μ) might not be admissible.
Human review
  • Endorsed by Shuze Chen · Oct 21, 2026

    Confirmed by the moderator at approval.

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