Remark 2 — Submodular menus and greedy approximation
ProvedFBMSP.remark2_submodular_greedyExpected menu revenue is zero for the empty set, nonnegative, monotone under inclusion, and submodular:
For any finite nonnegative candidate menu and , a greedy chain exists. Every such chain ends at a feasible -element menu satisfying
The optimum in this target is explicitly over . The separate discrete candidate-price target recovers the unrestricted finite-support pricing problem. No unconditional polynomial-time claim is made for an arbitrarily specified continuous error distribution.
import Definitions.Def_FBMSP_Model
namespace FBMSP
/-- Remark 2: expected menu revenue is a normalized nonnegative monotone
submodular set function. Greedy selection over a finite candidate menu
achieves at least 1-exp(-1) times the best k-element candidate sub-menu.
The benchmark here is explicitly the finite-candidate optimum.
Draft statement; proof remains open. -/
theorem remark2_submodular_greedy (ν η : MeasureTheory.Measure ℝ)
(hpred : ValidPredictions ν) (hnoise : ValidNoise η) :
menuRevenue ν η ∅ = 0 ∧
(∀ P : Finset ℝ, 0 ≤ menuRevenue ν η P) ∧
Monotone (menuRevenue ν η) ∧
IsSubmodular (menuRevenue ν η) ∧
∀ (P : Finset ℝ) (k : ℕ), k ≤ P.card → (∀ p ∈ P, 0 ≤ p) →
(∃ A : ℕ → Finset ℝ, IsGreedyChain (menuRevenue ν η) P k A) ∧
∀ A : ℕ → Finset ℝ, IsGreedyChain (menuRevenue ν η) P k A →
A k ⊆ P ∧ (A k).card = k ∧
(1 - Real.exp (-1)) * candidateOptimum (menuRevenue ν η) P k ≤
menuRevenue ν η (A k) := by sorry
end FBMSPRead-back
What the Lean code literally says, in plain math · gpt-6-astra
Let be probability measures on with integrable identity functions, with for -almost every and . For every finite real set , put . The assertion first states , for every finite real , whenever finite , and for every finite real ; these four clauses allow negative elements of the price sets. It further states that for every finite and natural , at least one greedy chain exists and every such chain satisfies , , and . A greedy chain here is an infinite sequence of finite real sets with and, for each , and a choice such that and for every ; its later terms are unrestricted. Ties may be resolved in any way satisfying that comparison. The benchmark is the finite candidate family of subsets of the specified , not a supremum over all real-price menus; it is a nonempty finite maximum because it includes the empty set. The cases and are allowed, giving and a zero benchmark when . There is no conclusion for , and no density, log-concavity, second-moment, or nonnegative-realized-sum assumption is made.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.