Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The choice probabilities pi(S,μ)p_i(S,\mu)pi​(S,μ), i∈Si\in Si∈S, and p0(S,μ)p_0(S,\mu)p0​(S,μ) sum to one

Proved
DynamicAssortment.Separation.choice_probabilities_sum_to_one

by tianyipeng · Nov 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

choice-modeldynamic-assortmentrandom-utility

Consider the random-utility choice model of Sauré–Zeevi (§3.2): a customer facing an assortment S⊆{1,…,N}S\subseteq\{1,\dots,N\}S⊆{1,…,N} has utilities Ui=μi+ζiU_i=\mu_i+\zeta_iUi​=μi​+ζi​ for i∈Si\in Si∈S and U0=ζ0U_0=\zeta_0U0​=ζ0​ for the no-purchase option (μ0=0\mu_0=0μ0​=0), where the shocks ζ0,ζi\zeta_0,\zeta_iζ0​,ζi​ are i.i.d. with a density fff that is integrable, everywhere positive and integrates to 111. Writing F(x)=∫−∞xfF(x)=\int_{-\infty}^x fF(x)=∫−∞x​f, the probability that product i∈Si\in Si∈S is chosen is

pi(S,μ)=∫R(∏j∈S∖{i}F(x−μj))F(x) f(x−μi) dx,p_i(S,\mu)=\int_{\mathbb R}\Big(\prod_{j\in S\setminus\{i\}}F(x-\mu_j)\Big)F(x)\,f(x-\mu_i)\,dx,pi​(S,μ)=∫R​(j∈S∖{i}∏​F(x−μj​))F(x)f(x−μi​)dx,

and the no-purchase probability is

p0(S,μ)=∫R(∏j∈SF(x−μj))f(x) dx.p_0(S,\mu)=\int_{\mathbb R}\Big(\prod_{j\in S}F(x-\mu_j)\Big)f(x)\,dx .p0​(S,μ)=∫R​(j∈S∏​F(x−μj​))f(x)dx.

Claim. These numbers form a probability distribution on S∪{0}S\cup\{0\}S∪{0}: for every finite SSS and every μ∈RN\mu\in\mathbb R^Nμ∈RN,

∑i∈Spi(S,μ)+p0(S,μ)=1.\sum_{i\in S}p_i(S,\mu)+p_0(S,\mu)=1 .i∈S∑​pi​(S,μ)+p0​(S,μ)=1.

Probabilistically, pkp_kpk​ is the probability that alternative kkk has the largest utility, and ties have probability zero because the utilities have densities. Analytically, the integrand of the sum is the a.e. derivative of x↦∏k∈S∪{0}F(x−μk)x\mapsto\prod_{k\in S\cup\{0\}}F(x-\mu_k)x↦∏k∈S∪{0}​F(x−μk​), which increases from 000 to 111.

Preamble
import Mathlib
import Definitions.Def_DynamicAssortment_Separation_ChoiceModel
Formal statement
namespace DynamicAssortment.Separation

/-- The choice probabilities of the random-utility model (p. 391, §3.2) form a probability
distribution on `S ∪ {0}`: `∑_{i ∈ S} p_i(S, μ) + p_0(S, μ) = 1` for every assortment `S` and
every mean-utility vector `μ`, when the shocks have a density. -/
theorem choice_probabilities_sum_to_one {N : ℕ} (f : ℝ → ℝ) (hf : IsNoiseDensity f)
    (μ : Fin N → ℝ) (S : Finset (Fin N)) :
    ∑ i ∈ S, choiceProb f μ S i + noPurchaseProb f μ S = 1 := by sorry

end DynamicAssortment.Separation
Source
Sauré, Zeevi, Optimal Dynamic Assortment Planning with Demand Learning, Manuf. Serv. Oper. Manag. 15(3), 2013, p. 391, §3.2 (choice probabilities p_i(S, μ) of the random-utility model, a distribution over S ∪ {0}); used implicitly in the proof of Theorem 2 (App. A, pp. 402–403) whenever probabilities are bounded by one

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