Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Theorem 4.2, p. 17 — on a low-moreishness, near-constant-value manifold, E[S(ω_T)] ≥ E[S(ω_S)] − 2βE[T(ω_S)] − α(v₀ + β)/(1 − α)

Proved
EngagementOpt.Salad.theorem_4_2

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

behavioral-economicsengagement-optimizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1recommender-systems

Let W>0W>0W>0 be the outside option and let M⊆Ω=[0,1)×[0,1)×R+\mathcal M\subseteq\Omega=[0,1)\times[0,1)\times\mathbb R_+M⊆Ω=[0,1)×[0,1)×R+​ be a content manifold containing at least one point with strictly positive expected utility, gS(ω)>0g_S(\omega)>0gS​(ω)>0. Let ωS=(pS,qS,vˉS)\omega_S=(p_S,q_S,\bar v_S)ωS​=(pS​,qS​,vˉS​) be a maximizer of gSg_SgS​ over M\mathcal MM (3), and let ωT=(pT,qT,vˉT)\omega_T=(p_T,q_T,\bar v_T)ωT​=(pT​,qT​,vˉT​) be a maximizer of gTg_TgT​ over {ω∈M:gS(ω)≥0}\{\omega\in\mathcal M: g_S(\omega)\ge0\}{ω∈M:gS​(ω)≥0} with gS(ωT)≥0g_S(\omega_T)\ge0gS​(ωT​)≥0 (4). Suppose that

  1. p≤αp\le\alphap≤α for all (p,q,vˉ)∈M(p,q,\bar v)\in\mathcal M(p,q,vˉ)∈M, where α<1\alpha<1α<1;
  2. for some v0v_0v0​, ∣vˉ−v0∣<β|\bar v-v_0|<\beta∣vˉ−v0​∣<β for all (p,q,vˉ)∈M(p,q,\bar v)\in\mathcal M(p,q,vˉ)∈M.

Then the user's utility at ωT\omega_TωT​ is not much less than its utility at ωS\omega_SωS​:

E[S(ωT)] ≥ E[S(ωS)]−2β E[T(ωS)]−α(v0+β)1−α.\mathbb E[S(\omega_T)]\ \ge\ \mathbb E[S(\omega_S)]-2\beta\,\mathbb E[T(\omega_S)]-\frac{\alpha(v_0+\beta)}{1-\alpha}.E[S(ωT​)] ≥ E[S(ωS​)]−2βE[T(ωS​)]−1−αα(v0​+β)​.

Here E[S(ω)]=max⁡(gS(ω),0)\mathbb E[S(\omega)]=\max(g_S(\omega),0)E[S(ω)]=max(gS​(ω),0) is system 2's expected utility (1), and E[T(ω)]\mathbb E[T(\omega)]E[T(ω)] is the expected session length (2), which is 000 when gS(ω)<0g_S(\omega)<0gS​(ω)<0. When α\alphaα and β\betaβ are close to 000, maximizing engagement is near-optimal for the user.

Formalization Note Three hypotheses implicit in the paper are explicit: W>0W>0W>0 (§2.1 normalizes W=1W=1W=1), α<1\alpha<1α<1 (without it condition 1 is vacuous on Ω\OmegaΩ and the bound fails), and the paper's standing assumption (p. 16) that M\mathcal MM contains a point with E[S]>0\mathbb E[S]>0E[S]>0. "For some v0v_0v0​" is expressed by taking v0v_0v0​ as a parameter satisfying condition 2, which is equivalent because v0v_0v0​ appears in the conclusion. The theorem holds for every pair of maximizers, so no tie-breaking rule and no closedness of M\mathcal MM are needed.

Preamble
import Mathlib
import Definitions.Def_EngagementOpt_Salad_Model
Formal statement
namespace EngagementOpt.Salad

/-- Theorem 4.2, p. 17. Let `M ⊆ Ω` be a content manifold containing a point with `g_S > 0`, let
`ω_S` maximize `g_S` over `M` (3) and `ω_T` maximize `g_T` over `{ω ∈ M : g_S(ω) ≥ 0}` (4).
If `p ≤ α < 1` and `|v̄ − v₀| < β` on all of `M`, then
`E[S(ω_T)] ≥ E[S(ω_S)] − 2βE[T(ω_S)] − α(v₀ + β)/(1 − α)`. -/
theorem theorem_4_2 (W : ℝ) (hW : 0 < W) (M : Set EngagementOpt.Misalign.Params) (hM : ∀ ω ∈ M, EngagementOpt.Misalign.InOmega ω)
    (hpos : ∃ ω ∈ M, 0 < EngagementOpt.Misalign.gS W ω)
    (ωS ωT : EngagementOpt.Misalign.Params) (hωS : EngagementOpt.Misalign.IsUtilityMaximizer W M ωS) (hωT : EngagementOpt.Misalign.IsEngagementMaximizer W M ωT)
    (α : ℝ) (hα : α < 1) (h1 : ∀ ω ∈ M, ω.p ≤ α)
    (v0 β : ℝ) (h2 : ∀ ω ∈ M, |ω.v - v0| < β) :
    ES W ωT ≥ ES W ωS - 2 * β * ET W ωS - α * (v0 + β) / (1 - α) := by sorry

end EngagementOpt.Salad
Source
Kleinberg, Mullainathan, Raghavan, The Challenge of Understanding What Users Want, arXiv:2202.11776v3, p. 17, Theorem 4.2 (with (1), (2) pp. 7–8 and (3), (4) p. 16)
Human review
  • Endorsed by Shuze Chen · Oct 16, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 16, 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 paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me