Theorem 4.6 — is an assortment problem under a regular choice model, with uniform pricing = revenue-ordered assortments
ProvedRevenueOrdered.UDPmin.udpmin_reductionassortment-optimizationdiscrete-choicep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1pricingreduction
Fix a instance with items , consumers (), interest sets and valuations , and let be the assortment instance of the proof of Theorem 4.6: , , . Then:
- is a regular discrete choice model;
- for every ;
- the two instances have the same optimal revenue: ;
- for each consumer , the assortment has the same revenue as the uniform price on every item;
- for each there is a consumer such that the assortment has the same revenue as the uniform price on every item.
Items 4 and 5 are the paper's two bullets: uniform pricing on the pricing instance and revenue-ordered assortments on the assortment instance are the same strategy.
Formalization Note The paper states Theorem 4.6 as "one can define an instance"; it is formalized here for the explicit instance of its proof, since the bare existence of a regular instance with the same optimum is met by a single product. In the paper's first bullet the threshold is for some ; item 4 names it, for any item .
Preamble
import Mathlib import Definitions.Def_RevenueOrdered_UDPmin_Model import Definitions.Def_RevenueOrdered_UDPmin_Pricing import Definitions.Def_RevenueOrdered_UDPmin_Reduction
Formal statement
namespace RevenueOrdered.UDPmin
/-- Theorem 4.6 (Berbeglia–Joret, arXiv:1606.01371v3, p. 17), for the explicit instance of its
proof: the choice model `redP I` on `𝒞 = X × {v_1, …, v_m}` with revenues `r((x, v)) = m·v` is
regular with positive revenues, has the same optimal revenue as the `UDP_min` instance, and
its threshold sets have exactly the revenues of the uniform valuation prices. -/
theorem udpmin_reduction {X M : Type*} [Fintype X] [DecidableEq X] [Fintype M] [Nonempty M]
(I : Instance X M) :
IsRegular (redP I) ∧
(∀ y : RedProd I, 0 < redRev I y) ∧
RevenueOrdered.Ratio.opt (redP I) (redRev I) = optUDP I ∧
(∀ i : M, RevenueOrdered.Tightness.rev (redP I) (redRev I)
(thresholdSet (redRev I) ((Fintype.card M : ℝ) * I.v i)) = revenue I (fun _ => I.v i)) ∧
(∀ y : RedProd I, ∃ i : M, RevenueOrdered.Tightness.rev (redP I) (redRev I)
(thresholdSet (redRev I) (redRev I y)) = revenue I (fun _ => I.v 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, Theorem 4.6 (proof pp. 17–19)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.