Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2 — existence of an optimal forward threshold policy

Disproved
FreemiumActions.Threshold.theorem_2

by Shuze Chen · Oct 29, 2026 · Mathlib 0df444a (Lean v4.33.1)

dynamic-programmingoperations-researchp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let N≥0N\ge0N≥0 and E={0,…,N}E=\{0,\ldots,N\}E={0,…,N}. The publisher chooses a deterministic stationary policy y:E→{0,1}y:E\to\{0,1\}y:E→{0,1}. At each level the player probabilities satisfy pM+pI+pQ=qM+qQ=1p_M+p_I+p_Q=q_M+q_Q=1pM​+pI​+pQ​=qM​+qQ​=1, with all probabilities and α\alphaα in [0,1][0,1][0,1]. Removing the offer gives qM=pM+αpIq_M=p_M+\alpha p_IqM​=pM​+αpI​ and qQ=pQ+(1−α)pIq_Q=p_Q+(1-\alpha)p_IqQ​=pQ​+(1−α)pI​. Conditional on action a∈{M,I}a\in\{M,I\}a∈{M,I} the player advances one level with constant probability τa∈[0,1]\tau_a\in[0,1]τa​∈[0,1] or stays, and stays at level NNN if already there; quitting is absorbing. Assume pM,qM,αp_M,q_M,\alphapM​,qM​,α are nondecreasing, pQ,qQ,pIp_Q,q_Q,p_IpQ​,qQ​,pI​ nonincreasing, both quitting probabilities strictly positive, τI<τM\tau_I<\tau_MτI​<τM​, and 0≤μI<μM0\le\mu_I<\mu_M0≤μI​<μM​. The immediate revenues are r(e,1)=pM(e)μM+pI(e)μIr(e,1)=p_M(e)\mu_M+p_I(e)\mu_Ir(e,1)=pM​(e)μM​+pI​(e)μI​ and r(e,0)=qM(e)μMr(e,0)=q_M(e)\mu_Mr(e,0)=qM​(e)μM​, with zero revenue after quitting. Let ny(e,j)=∑t≥0(Syt)e,jn_y(e,j)=\sum_{t\ge0}(S_y^t)_{e,j}ny​(e,j)=∑t≥0​(Syt​)e,j​ and Wy(e)=∑jny(e,j)r(j,y(j))W_y(e)=\sum_j n_y(e,j)r(j,y(j))Wy​(e)=∑j​ny​(e,j)r(j,y(j)). These are Assumptions 1–4 with the standing probability and revenue conventions.

Assume further α(N)=1\alpha(N)=1α(N)=1, the adjacent-pair inequalities α(e+1)−α(e)>qM(e+1)−qM(e)\alpha(e+1)-\alpha(e)>q_M(e+1)-q_M(e)α(e+1)−α(e)>qM​(e+1)−qM​(e) for 0≤e<N0\le e<N0≤e<N, and precisely the printed Assumption 7:

1−α(e+1)≤(1−α(e))pM(e+1)τM+pI(e+1)τIpQ(e+1)+pM(e+1)τM+pI(e+1)τI(1≤e<N).1-\alpha(e+1)\le(1-\alpha(e))\frac{p_M(e+1)\tau_M+p_I(e+1)\tau_I}{p_Q(e+1)+p_M(e+1)\tau_M+p_I(e+1)\tau_I}\quad(1\le e<N).1−α(e+1)≤(1−α(e))pQ​(e+1)+pM​(e+1)τM​+pI​(e+1)τI​pM​(e+1)τM​+pI​(e+1)τI​​(1≤e<N).

The source asserts that there exist one stationary policy y∗y^*y∗ and a cutoff e∗∈{−1,…,N}e^*\in\{-1,\ldots,N\}e∗∈{−1,…,N} such that

∀y:E→{0,1}, ∀e∈E,Wy(e)≤Wy∗(e),\forall y:E\to\{0,1\},\ \forall e\in E,\quad W_y(e)\le W_{y^*}(e),∀y:E→{0,1}, ∀e∈E,Wy​(e)≤Wy∗​(e), y∗(e)=1 (e≤e∗),y∗(e)=0 (e>e∗).y^*(e)=1\ (e\le e^*),\qquad y^*(e)=0\ (e>e^*).y∗(e)=1 (e≤e∗),y∗(e)=0 (e>e∗).

The same policy works for every starting level, against every stationary competitor. No uniqueness or tie-breaking is asserted. The printed Assumption 7 excludes e=0e=0e=0; the resulting counterexample is retained in the source findings rather than repaired in this target.

Differences from the source:

  • encoding: engagement levels 0 through N, quit state −1 and controls 0 or 1 → Fin (N+1), Option with none for quitting, and Bool controls; reason: order-preserving state labels and true = offer; N=0 is retained
  • reading: increase, decrease and increasing in Assumption 3 → weak monotonicity, with quitting positivity and tauM > tauI still strict; reason: the appendix uses nondecreasing and nonincreasing comparisons
  • encoding: earns revenue, with muI < muM in Assumption 4 → 0 ≤ muI < muM; reason: makes the model’s implicit nonnegative-revenue convention explicit without normalizing either revenue
  • encoding: real expected infinite-horizon total reward and visit counts → nonnegative infinite sums in ENNReal; policy values are finite sums of visits times rewards; reason: positive quitting on the finite state set makes these values finite; no truncation, discount or conversion of an infinite value to zero is used
  • reading: Assumption 6 says all e in E although e+1 is undefined at N → all adjacent pairs e,f in E with f=e+1; reason: states precisely the domain where the printed expression is defined
  • encoding: threshold cutoff e* from −1 through N → initial-segment length k in Fin (N+2), offering exactly when e<k; reason: k=e*+1 preserves both boundary policies and both sides of the cutoff
Preamble
import Definitions.Def_FreemiumActions_Threshold_ThresholdPolicy
Formal statement
namespace FreemiumActions.Threshold

theorem theorem_2 {N : ℕ} (d : Data N) (h : Assumptions17 d) :
    ∃ y : Policy N, IsOptimal d y ∧ IsThreshold y := by sorry

end FreemiumActions.Threshold
Source
Sheng, Ryan and Nagarajan, Incentivized actions in freemium games, supplied source.pdf dated October 8, 2016, §5, Theorem 2, p. 21 (PDF p. 21); Assumptions 5–7, pp. 19–20; A.8, pp. 35–36; catalog DOI 10.1287/msom.2020.0925.
Human review
  • Endorsed by Community (Bot) · Oct 29, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Oct 29, 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