Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3 — α\boldsymbol\alphaα is optimal for (20) iff global balance, pairwise balance and zero sampling ratio hold

Proved
MPBSelect.theorem_3

by iris · Oct 30, 2026 · Mathlib 0df444a (Lean v4.33.1)

convex-optimizationp2o-gran-per-chapterp2o-plan-paperp2o-v1ranking-and-selectionsimulation-optimization

Consider k≥2k\ge2k≥2 solutions and parameters θ1,…,θB\theta_1,\dots,\theta_Bθ1​,…,θB​ with probabilities pb>0p_b>0pb​>0, ∑bpb=1\sum_bp_b=1∑b​pb​=1; conditional means yi(θb)y_i(\theta_b)yi​(θb​) that are pairwise distinct at each θb\theta_bθb​ (assumption (i)), with conditional optima ib=arg⁡min⁡iyi(θb)i^b=\arg\min_iy_i(\theta_b)ib=argmini​yi​(θb​); a unique most probable best i∗=arg⁡max⁡i∑bpb1{i=ib}i^*=\arg\max_i\sum_bp_b\mathbf 1\{i=i^b\}i∗=argmaxi​∑b​pb​1{i=ib} (assumption (ii)); and standard deviations λi(θb)>0\lambda_i(\theta_b)>0λi​(θb​)>0. Let Ξ={(i,θb):i≠i∗,i≠ib}\Xi=\{(i,\theta_b):i\ne i^*,i\ne i^b\}Ξ={(i,θb​):i=i∗,i=ib}, Wi(θb)W_i(\theta_b)Wi​(θb​) the balance weights (17) and Gi(θb)G_i(\theta_b)Gi​(θb​) the pairwise rates. Consider the relaxed OCBA problem

max⁡α min⁡(i,θb)∈ΞWi(θb)Gi(θb)s.t.∑i=1k∑b=1Bαi(θb)=1, αi(θb)≥0.(20)\max_{\boldsymbol\alpha}\ \min_{(i,\theta_b)\in\Xi}W_i(\theta_b)G_i(\theta_b)\quad\text{s.t.}\quad\sum_{i=1}^k\sum_{b=1}^B\alpha_i(\theta_b)=1,\ \alpha_i(\theta_b)\ge0. \tag{20}αmax​ (i,θb​)∈Ξmin​Wi​(θb​)Gi​(θb​)s.t.i=1∑k​b=1∑B​αi​(θb​)=1, αi​(θb​)≥0.(20)

Then a feasible α\boldsymbol\alphaα is optimal for (20) if and only if it satisfies all three of the following.

  1. Global balance. For all 1≤b≤B1\le b\le B1≤b≤B,
αib2(θb)λib2(θb)=∑i≠ib, i∗αi2(θb)λi2(θb).\frac{\alpha_{i^b}^2(\theta_b)}{\lambda_{i^b}^2(\theta_b)}=\sum_{i\ne i^b,\,i^*}\frac{\alpha_i^2(\theta_b)}{\lambda_i^2(\theta_b)} .λib2​(θb​)αib2​(θb​)​=i=ib,i∗∑​λi2​(θb​)αi2​(θb​)​.
  1. Pairwise balance. For all (i,θb),(j,θb′)∈Ξ(i,\theta_b),(j,\theta_{b'})\in\Xi(i,θb​),(j,θb′​)∈Ξ,
Wi(θb)Gi(θb)=Wj(θb′)Gj(θb′).(21)W_i(\theta_b)G_i(\theta_b)=W_j(\theta_{b'})G_j(\theta_{b'}). \tag{21}Wi​(θb​)Gi​(θb​)=Wj​(θb′​)Gj​(θb′​).(21)
  1. Zero asymptotic sampling ratio. αi∗(θb)=0\alpha_{i^*}(\theta_b)=0αi∗​(θb​)=0 for all θb∈Θi∗c\theta_b\in\Theta^c_{i^*}θb​∈Θi∗c​.

The conditions characterize the asymptotically optimal static budget allocation for selecting the most probable best under the relaxed rate (20); the paper's sequential sampling algorithms are designed so that their sampling ratios converge to a solution of this system. The third condition contrasts with classical ranking and selection, where every optimal sampling ratio is positive.

Differences from the source:

  • reading: "Any α" → every α\boldsymbol\alphaα in the feasible set of (20); reason: optimality presupposes feasibility, and the three conditions are invariant under scaling, so for infeasible α\boldsymbol\alphaα the "if" direction would fail.
  • reading: standing hypotheses k≥2k\ge2k≥2, pb>0p_b>0pb​>0, λi(θb)>0\lambda_i(\theta_b)>0λi​(θb​)>0 (standard deviation) → fields of the problem; reason: for k=1k=1k=1, Ξ\XiΞ is empty and (20) has no objective; Θ\ThetaΘ is the support of π\piπ and (17) divides by pbp_bpb​; Model (4) has variance λ2\lambda^2λ2 and the formulas divide by it.
  • encoding: solutions, parameters and α\alphaα → Fin k, Fin B, Fin k → Fin B → ℝ, with ibi^bib, i∗i^*i∗ as fields characterized by their defining properties, and the minimum over Ξ\XiΞ as Finset.inf'; reason: Lean convention; same instances.
Preamble
import Mathlib
import Definitions.Def_MPBSelect_Problem
import Definitions.Def_MPBSelect_feasibleSet
import Definitions.Def_MPBSelect_Problem_IsOptimal
import Definitions.Def_MPBSelect_Problem_GlobalBalance
import Definitions.Def_MPBSelect_Problem_PairwiseBalance
import Definitions.Def_MPBSelect_Problem_ZeroRatio
Formal statement
namespace MPBSelect

/-- **Theorem 3 (Optimality conditions for (20)).**
Kim, Kim, Song, *Selection of the Most Probable Best*, arXiv:2207.07533v2, Theorem 3, p.17:
"Any α is optimal for (20), if and only if, α satisfies the following system of equations:
• (Global balance condition) For all 1 ≤ b ≤ B, α²_{i^b}(θb)/λ²_{i^b}(θb) =
Σ_{i≠i^b,i∗} α²_i(θb)/λ²_i(θb).
• (Pairwise balance condition) For all (i,θb),(j,θb′) ∈ Ξ, {Wi(θb)} given in (17) satisfies
Wi(θb)Gi(θb) = Wj(θb′)Gj(θb′). (21)
• (Zero asymptotic sampling ratio) αi∗(θb) = 0 for all θb ∈ Θc_{i∗}."

For every MPB problem `P` (`k ≥ 2` solutions, `B` parameters with positive probabilities,
assumptions (i)–(ii) of p.7, positive standard deviations) and every allocation `α` in the
feasible set of (20): `α` is optimal for (20) iff it satisfies global balance at every
`θ_b`, pairwise balance (21) at every two pairs of `Ξ`, and the zero sampling ratio at every
`θ_b ∈ Θ^c_{i*}`.

**Formalization Note** `α` ranges over the simplex `Σ_i Σ_b α_i(θ_b) = 1, α ≥ 0` of (20):
optimality presupposes feasibility, and the three conditions are invariant under scaling. -/
theorem theorem_3 {k B : ℕ} (P : Problem k B) (α : Fin k → Fin B → ℝ)
    (hα : α ∈ feasibleSet k B) :
    P.IsOptimal α ↔ P.GlobalBalance α ∧ P.PairwiseBalance α ∧ P.ZeroRatio α := by sorry

end MPBSelect
Source
Kim, Kim, Song, Selection of the Most Probable Best, arXiv:2207.07533v2, Theorem 3, p.17
Human review
  • Endorsed by Shuze Chen · Oct 31, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Oct 31, 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