Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Randomized bundle selection and the allocation LP (19), (22a)–(22e)

Definition
LinMatroidSecretary_Online_Supplement_BundleLP

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

matroidsonline-allocationp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1secretary-problemxos-valuations

Work in V=FdV=F^dV=Fd with a labelled vector family v:E→Vv:E\to Vv:E→V. The span ⟨B⟩\langle B\rangle⟨B⟩ is the span of the vectors indexed by a finite bundle BBB; different labels remain different items. Reuse the published finitely supported subspace distributions ν\nuν, their expectations, and the dimension invariant. The real-parameter condition (19) is

EW∼νdim⁡(W∩L)≤(1−α)dim⁡L(L≤V).\mathbb E_{W\sim\nu}\dim(W\cap L)\le(1-\alpha)\dim L\quad(L\le V).EW∼ν​dim(W∩L)≤(1−α)dimL(L≤V).

A selection rule ρ(W,T)\rho(W,T)ρ(W,T) describes, after observing WWW, the conditional probability of choosing T⊆BT\subseteq BT⊆B. Validity requires nonnegative entries summing to one on BBB's powerset for each WWW in the support of ν\nuν, and zero probability unless dim⁡(W+⟨T⟩)=dim⁡W+∣T∣\dim(W+\langle T\rangle)=\dim W+|T|dim(W+⟨T⟩)=dimW+∣T∣. Its marginal for eee and its expectation of a function ggg are

Pr⁡[e∈T]=∑Wν(W)∑T⊆B:e∈Tρ(W,T),E[g(W,T)]=∑Wν(W)∑T⊆Bρ(W,T)g(W,T).\Pr[e\in T]=\sum_W\nu(W)\sum_{T\subseteq B:e\in T}\rho(W,T),\qquad \mathbb E[g(W,T)]=\sum_W\nu(W)\sum_{T\subseteq B}\rho(W,T)g(W,T).Pr[e∈T]=W∑​ν(W)T⊆B:e∈T∑​ρ(W,T),E[g(W,T)]=W∑​ν(W)T⊆B∑​ρ(W,T)g(W,T).

For agents N={0,…,n−1}N=\{0,\ldots,n-1\}N={0,…,n−1}, let X⊆NX\subseteq NX⊆N, i=∣X∣i=|X|i=∣X∣, eligibility sets EaE_aEa​, bundles BaB_aBa​, sample size kkk, and predecessor laws μa\mu_aμa​. Set VX=⟨⋃a∈XEa⟩V_X=\langle\bigcup_{a\in X}E_a\rangleVX​=⟨⋃a∈X​Ea​⟩. The LP uses one rule p(a,W,T)p(a,W,T)p(a,W,T) per a∈Xa\in Xa∈X, with variables only for W∈supp⁡μaW\in\operatorname{supp}\mu_aW∈suppμa​ and T⊆BaT\subseteq B_aT⊆Ba​. It imposes all five families:

  1. Nonnegativity of every variable.
  2. ∑T⊆Bap(a,W,T)=1\sum_{T\subseteq B_a}p(a,W,T)=1∑T⊆Ba​​p(a,W,T)=1.
  3. p(a,W,T)=0p(a,W,T)=0p(a,W,T)=0 unless dim⁡(W+⟨T⟩)=dim⁡W+∣T∣\dim(W+\langle T\rangle)=\dim W+|T|dim(W+⟨T⟩)=dimW+∣T∣.
  4. Each e∈Bae\in B_ae∈Ba​ has marginal k/(i−1)k/(i-1)k/(i−1).
  5. For every L≤VXL\le V_XL≤VX​, gp(L)≤0g_p(L)\le0gp​(L)≤0, where
gp(L)=−(i−k)dim⁡L+∑a∈X∑Wμa(W)∑T⊆Bap(a,W,T)dim⁡((W+⟨T⟩)∩L).g_p(L)=-(i-k)\dim L+\sum_{a\in X}\sum_W\mu_a(W)\sum_{T\subseteq B_a}p(a,W,T)\dim((W+\langle T\rangle)\cap L).gp​(L)=−(i−k)dimL+a∈X∑​W∑​μa​(W)T⊆Ba​∑​p(a,W,T)dim((W+⟨T⟩)∩L).

Unused coordinates outside these variable ranges are unconstrained and never enter the formulas. Uses of k/(i−1)k/(i-1)k/(i−1) in Lemma 7 assume 1≤k<i1\le k<i1≤k<i, so the denominator is positive. These definitions supply the shared interfaces for Lemmas 6, 9 and 7 without assuming their conclusions.

Definition code
import Mathlib
import Definitions.Def_LinMatroidSecretary_Online_DimensionLP

/-!
§5.1–§5.3 (PDF pp. 22–27): randomized subset rules and LP_XOS, (19), (22a)–(22e).
Subsets are sets of labels: equal vectors do not identify distinct elements.
-/
namespace LinMatroidSecretary.Online.Supplement

open Finset
noncomputable section

variable {F : Type} [Field F] {d : ℕ}
variable {E : Type} [DecidableEq E]

/-- Span of a finite set of labelled vectors, with no order on the labels. -/
def bundleSpan (v : E → Fin d → F) (B : Finset E) : Submodule F (Fin d → F) :=
  Submodule.span F (v '' (B : Set E))

/-- The real-parameter dimension inequality (19), for every ambient subspace. -/
def DimIneqAlpha (ν : Dist F d) (α : ℝ) : Prop :=
  ∀ L : Submodule F (Fin d → F),
    expect ν (fun W => dimInter W L) ≤ (1 - α) * (Module.finrank F L : ℝ)

/-- Conditional probabilities after observing `W`; only subsets of the fixed bundle are used. -/
abbrev SelectionRule (F : Type) [Field F] (d : ℕ) (E : Type) :=
  Submodule F (Fin d → F) → Finset E → ℝ

/-- For every positive-mass subspace, a distribution on subsets independent modulo `W`.
Values off `B.powerset` or off `ν.support` do not participate in the experiment. -/
def SelectionValid (v : E → Fin d → F) (ν : Dist F d) (B : Finset E)
    (ρ : SelectionRule F d E) : Prop :=
  ∀ W ∈ ν.support,
    (∀ T ∈ B.powerset, 0 ≤ ρ W T) ∧
    (∑ T ∈ B.powerset, ρ W T) = 1 ∧
    (∀ T ∈ B.powerset,
      Module.finrank F ↥(W ⊔ bundleSpan v T) ≠ Module.finrank F ↥W + T.card → ρ W T = 0)

/-- Marginal inclusion probability, averaged over `W` and the conditional subset rule. -/
def selectionMarginal (ν : Dist F d) (B : Finset E) (ρ : SelectionRule F d E) (e : E) : ℝ := by
  classical
  exact expect ν fun W => ∑ T ∈ B.powerset, if e ∈ T then ρ W T else 0

/-- Expectation of a function of the observed subspace and selected bundle. -/
def selectionExpect (ν : Dist F d) (B : Finset E) (ρ : SelectionRule F d E)
    (g : Submodule F (Fin d → F) → Finset E → ℝ) : ℝ :=
  expect ν fun W => ∑ T ∈ B.powerset, ρ W T * g W T

variable {n : ℕ}

/-- `V_X`, the span of the eligibility sets of `X`, not merely its allocated bundles. -/
def eligibilitySpan (v : E → Fin d → F) (elig : Fin n → Finset E)
    (X : Finset (Fin n)) : Submodule F (Fin d → F) :=
  bundleSpan v (X.biUnion elig)

/-- Expanded `g_p` preceding (22), with no extra factor `1/i` in the sum over agents. -/
def bundleGp (v : E → Fin d → F) (X : Finset (Fin n)) (k : ℕ)
    (B : Fin n → Finset E) (μ : Fin n → Dist F d)
    (p : Fin n → SelectionRule F d E) (L : Submodule F (Fin d → F)) : ℝ :=
  -((X.card : ℝ) - (k : ℝ)) * (Module.finrank F L : ℝ) +
    ∑ a ∈ X, selectionExpect (μ a) (B a) (p a)
      (fun W T => dimInter (W ⊔ bundleSpan v T) L)

/-- All five constraint families of LP_XOS(X). The variables outside `a ∈ X`,
`W ∈ supp μ_a`, `T ⊆ B_a` are irrelevant unconstrained coordinates. -/
def BundleLPFeasible (v : E → Fin d → F) (elig : Fin n → Finset E)
    (X : Finset (Fin n)) (k : ℕ) (B : Fin n → Finset E)
    (μ : Fin n → Dist F d) (p : Fin n → SelectionRule F d E) : Prop :=
  (∀ a ∈ X, SelectionValid v (μ a) (B a) (p a)) ∧
  (∀ a ∈ X, ∀ e ∈ B a,
    selectionMarginal (μ a) (B a) (p a) e = (k : ℝ) / ((X.card : ℝ) - 1)) ∧
  (∀ L : Submodule F (Fin d → F), L ≤ eligibilitySpan v elig X →
    bundleGp v X k B μ p L ≤ 0)

end
end LinMatroidSecretary.Online.Supplement
Source
Kristóf Bérczi, Shaddin Dughmi, Vasilis Livanos, Jose Soto, Victor Verdugo, The Strong Secretary Conjecture is True for Linear Matroids, STOC 2027 submission #608 (October 2026), https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/608.pdf, §§5.1–5.3, (19), (22a)–(22e), PDF pp. 22–27 (printed pp. 20–25)

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