Randomized bundle selection and the allocation LP (19), (22a)–(22e)
DefinitionLinMatroidSecretary_Online_Supplement_BundleLPWork in with a labelled vector family . The span is the span of the vectors indexed by a finite bundle ; different labels remain different items. Reuse the published finitely supported subspace distributions , their expectations, and the dimension invariant. The real-parameter condition (19) is
A selection rule describes, after observing , the conditional probability of choosing . Validity requires nonnegative entries summing to one on 's powerset for each in the support of , and zero probability unless . Its marginal for and its expectation of a function are
For agents , let , , eligibility sets , bundles , sample size , and predecessor laws . Set . The LP uses one rule per , with variables only for and . It imposes all five families:
- Nonnegativity of every variable.
- .
- unless .
- Each has marginal .
- For every , , where
Unused coordinates outside these variable ranges are unconstrained and never enter the formulas. Uses of in Lemma 7 assume , so the denominator is positive. These definitions supply the shared interfaces for Lemmas 6, 9 and 7 without assuming their conclusions.
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