§3.1 counterexample — optimal expected revenue 400
ProvedBidPriceControl.NonOptimal.bid_price_controls_not_optimalConsider the network of §3.1 and Table 1: two legs with one seat each, the through itinerary and the local itineraries and , 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 let be its expected revenue, and for bid prices let be the bid-price control of Definition 1. Then
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 , 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 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.
import Mathlib import Definitions.Def_BidPriceControl_NonOptimal_Model import Definitions.Def_BidPriceControl_NonOptimal_CounterExample
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
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:
- is a type whose elements are called controls. It depends on the two numerals and .
- (
ceA), (ceLaw) and (ceX) are fixed constants. - (
IsAdmissible ceA u) is a yes-or-no property of a control , relative to . - is a real number assigned to the control . The other arguments are fixed: , , the numeral and .
- (
bidPriceControl ceA μ) is a control built from and a function . Here takes a natural number and a pair of natural numbers , and returns a pair of real numbers .
The declaration asserts that all three of the following hold at once:
- Attainment of 440. At least one control is admissible and has
- Upper bound 440 on admissible controls. Every control that is admissible satisfies
Controls that are not admissible are not constrained by this clause.
- 400 is the largest value of a bid-price control. Define the set of real numbers
Then is the greatest element of . So there is some with , and every gives .
- The in 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 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 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 , , , , , and .
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 , and .
- 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 is nonempty, because functions always exist, for example . It is also asserted to contain and be bounded above by it.
- Default values may be counted. Nothing in the statement rules out that is computed through operations that return default values. Examples are an expectation or integral that returns for a non-integrable integrand, division by zero, or subtraction in that truncates at . If so, and are asserted about whatever value returns in those cases.
- Clause 3 covers every . This includes whose values at time indices or capacity vectors that never occur are arbitrary. It also includes for which might not be admissible.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.