Corollary 4.7 — uniform pricing earns in
ProvedRevenueOrdered.UDPmin.uniform_pricing_log_ratio_boundapproximation-algorithmsenvy-free-pricingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1pricingrevenue-management
Consider a instance with items , consumers, interest sets and valuations . Let be the supremum of the seller's revenue over all positive price assignments and the supremum of the revenue over uniform prices . Then
that is, uniform pricing approximates the optimum revenue to within a factor of with .
The bound depends only on the spread of the valuations, not on or ; the paper obtains it by combining Theorem 4.6 with Theorem 3.2.
Formalization Note Valuations are positive (the paper says non-negative; requires ). and are the maximum and minimum valuations, so no sorting is assumed. The statement holds for any number of items, including none (both sides are then ).
Preamble
import Mathlib import Definitions.Def_RevenueOrdered_UDPmin_Pricing
Formal statement
namespace RevenueOrdered.UDPmin
/-- Corollary 4.7 (Berbeglia–Joret, arXiv:1606.01371v3, p. 20): uniform pricing approximates the
optimum revenue of `UDP_min` to within a factor of `1/(1 + ln ρ)`, `ρ := v_m / v_1`, in product
form: `OPT_UDP ≤ (1 + ln(v_m / v_1)) · UP`. -/
theorem uniform_pricing_log_ratio_bound {X M : Type*} [Fintype X] [Fintype M] [Nonempty M]
(I : Instance X M) :
optUDP I ≤ (1 + Real.log (vMax I / vMin I)) * uniformRevenue I := by sorry
end RevenueOrdered.UDPmin
Source
Berbeglia & Joret, Assortment Optimisation Under a General Discrete Choice Model: A Tight Analysis of Revenue-Ordered Assortments, arXiv:1606.01371v3, p. 20, Corollary 4.7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.