Lemma 4.5 — some optimal price assignment uses only valuations as prices
ProvedRevenueOrdered.UDPmin.exists_optimal_valuation_pricesenvy-free-pricingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1pricingunit-demand
Consider a instance with items , at least one consumer, interest sets and valuations . Then there is a price assignment with
that is optimal: for every positive price assignment , and . In particular the supremum defining is attained.
The lemma reduces the uncountable search over prices to a finite one; it is what makes the assortment instance of Theorem 4.6 reach the pricing optimum.
Formalization Note The price is positive because valuations are. The paper's proof starts from an optimal assignment; here its existence is part of the statement.
Preamble
import Mathlib import Definitions.Def_RevenueOrdered_UDPmin_Pricing
Formal statement
namespace RevenueOrdered.UDPmin
/-- Lemma 4.5 (Berbeglia–Joret, arXiv:1606.01371v3, p. 17; proof in App. B, p. 30): some optimal
price assignment takes only valuations as prices. -/
theorem exists_optimal_valuation_prices {X M : Type*} [Fintype X] [Fintype M] [Nonempty M]
(I : Instance X M) :
∃ p : X → ℝ, (∀ x, ∃ i, p x = I.v i) ∧
(∀ p' : X → ℝ, (∀ x, 0 < p' x) → revenue I p' ≤ revenue I p) ∧
revenue I p = optUDP 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. 17, Lemma 4.5 (proof in Appendix B, p. 30)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.