Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 1, p. 11 — buying greedily in decreasing price-adjusted valuation maximizes the consumer's utility

Proved
AssortRotation.Concealment.lemma_1

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

assortmentconsumer-choicediminishing-marginal-utilityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Consider a fixed assortment of MMM products with prices p1,…,pMp_1,\dots,p_Mp1​,…,pM​ and realized shocks x1,…,xMx_1,\dots,x_Mx1​,…,xM​. Let vvv be a nonnegative, decreasing marginal-utility sequence, and let σ\sigmaσ be a permutation of the products such that

xσ(1)−pσ(1) ≥ xσ(2)−pσ(2) ≥ ⋯ ≥ xσ(M)−pσ(M).x_{\sigma(1)}-p_{\sigma(1)}\ \ge\ x_{\sigma(2)}-p_{\sigma(2)}\ \ge\ \cdots\ \ge\ x_{\sigma(M)}-p_{\sigma(M)} .xσ(1)​−pσ(1)​ ≥ xσ(2)​−pσ(2)​ ≥ ⋯ ≥ xσ(M)​−pσ(M)​.

Let Df=∣{j:v(j−1)+xσ(j)−pσ(j)≥0}∣D^f=|\{j: v(j-1)+x_{\sigma(j)}-p_{\sigma(j)}\ge 0\}|Df=∣{j:v(j−1)+xσ(j)​−pσ(j)​≥0}∣. Then buying the products σ(1),…,σ(Df)\sigma(1),\dots,\sigma(D^f)σ(1),…,σ(Df) maximizes the consumer's utility (3): for every subset SSS of the products,

u(S) ≤ u({σ(1),…,σ(Df)}),u(S)=∑j∈S(xj−pj)+∑j=0∣S∣−1v(j).u(S)\ \le\ u\big(\{\sigma(1),\dots,\sigma(D^f)\}\big),\qquad u(S)=\sum_{j\in S}(x_j-p_j)+\sum_{j=0}^{|S|-1}v(j).u(S) ≤ u({σ(1),…,σ(Df)}),u(S)=j∈S∑​(xj​−pj​)+j=0∑∣S∣−1​v(j).

This characterizes the consumer's purchase under a fixed assortment, and it is what justifies the revenue formula (4).

Formalization Note. Positions are 0-based in Lean, so the condition reads v(j)+xσ(j)−pσ(j)≥0v(j)+x_{\sigma(j)}-p_{\sigma(j)}\ge 0v(j)+xσ(j)​−pσ(j)​≥0 for j=0,…,M−1j=0,\dots,M-1j=0,…,M−1. The printed policy πif=1{σ(i)≤Df}\pi^f_i=\mathbb 1\{\sigma(i)\le D^f\}πif​=1{σ(i)≤Df} has an index slip. The proof (p. 35) and the surrounding text buy the product in position iii iff i≤Dfi\le D^fi≤Df, and the statement formalizes that.

Preamble
import Mathlib
import Definitions.Def_AssortRotation_Concealment_Model
Formal statement
namespace AssortRotation.Concealment

/-- Lemma 1, p. 11 (proof p. 35). For a fixed assortment of `M` products with prices `p`
and realized shocks `x`, let `σ` order the products by decreasing price-adjusted valuation
`x − p` (Definition 1). With 0-based positions, `D = #{j : v(j) + x_{σ j} − p_{σ j} ≥ 0}`
(the paper's `D^f`, whose 1-based condition is `v(j−1) + X_{σ(j)} − p_{σ(j)} ≥ 0`). Buying
the products at the first `D` positions of σ maximizes the utility (3) over all subsets. -/
theorem lemma_1 {M : ℕ} (v : ℕ → ℝ) (hv : MarginalUtility v) (p x : Fin M → ℝ)
    (σ : Equiv.Perm (Fin M)) (hσ : Antitone (fun i => x (σ i) - p (σ i))) (S : Finset (Fin M)) :
    utility v p x S ≤
      utility v p x
        ((Finset.univ.filter (fun j : Fin M =>
            (j : ℕ) < (Finset.univ.filter (fun i : Fin M =>
              0 ≤ v i + x (σ i) - p (σ i))).card)).map σ.toEmbedding) := by sorry

end AssortRotation.Concealment
Source
Ferreira & Goh, HBS Working Paper 17-041 (2020 revision), p. 11, Lemma 1 (proof p. 35); utility (3) p. 8; Definition 1 p. 10
Human review
  • Endorsed by Shuze Chen · Oct 22, 2026

    Confirmed by the moderator at approval.

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