Theorem 1.10, p. 5 (restated p. 16) — a (b, c)-selectable greedy OCRS gives E[f(S)] ≥ c·F(x), and E[f(S(1/2))] ≥ (c/4)·F(x) for non-monotone f
ProvedOnlineCRS.Submod.selectability_to_approximationLet be a finite ground set, a down-closed family of feasible sets and a relaxation of it. Let , let be a -selectable greedy OCRS for (deterministic or randomized), and let . Let be non-negative and submodular, with multilinear extension . The elements arrive in an order chosen by the almighty adversary, who knows the realized active set and the realized family before choosing it.
- If is moreover monotone, the set selected by satisfies
- Even if is not monotone, let contain every element of independently with probability , the coins being part of the algorithm and known to the adversary. Then
The theorem turns any selectability guarantee into an approximation guarantee for online submodular maximization, losing only the factor for monotone objectives and in general. It is how the paper derives its applications to prophet inequalities and Bayesian mechanism design from the OCRSs for matroids, matchings and knapsacks.
Formalization Note A deterministic greedy OCRS is the special case of a point-mass family distribution. The adversary is a function from all realized randomness (family, active set, and in part 2 the coins , with ) to arrival orders. The standing assumptions of Definition 1.3 (a down-closed , a relaxation of , ) are explicit hypotheses. Monotonicity is (footnote 6) and submodularity is (footnote 5).
import Mathlib import Definitions.Def_NonmonotoneSubmod_Shared_F import Definitions.Def_NonmonotoneSubmod_Shared_Submodular import Definitions.Def_OnlineCRS_Matroid_Basics import Definitions.Def_OnlineCRS_Submod_Model open scoped Pointwise
namespace OnlineCRS.Submod
/-- Theorem 1.10 (arXiv:1508.00142v2, p. 5, restated p. 16): let `P ⊆ [0,1]^N` be a relaxation of the
down-closed feasible sets `𝓕`, `w` a `(b, c)`-selectable (randomized) greedy OCRS for `P`, `x ∈ bP`, and
`f ≥ 0` submodular with multilinear extension `F`. Against every almighty adversary:
(i) if `f` is monotone, the selected set `S` satisfies `E[f(S)] ≥ c · F(x)`;
(ii) without monotonicity, `E[f(S(1/2))] ≥ (c/4) · F(x)`, where the coins defining `S(1/2)` are known to
the adversary. -/
theorem selectability_to_approximation {α : Type} [Fintype α] [DecidableEq α]
(𝓕 : Finset α → Prop) (P : Set (α → ℝ))
(hPoly : IsPolytope P) (hRel : IsRelaxation 𝓕 P)
(b c : ℝ) (hb0 : 0 ≤ b) (hb1 : b ≤ 1) (hc0 : 0 ≤ c) (hc1 : c ≤ 1)
(w : (α → ℝ) → Finset (Finset α) → ℝ) (hw : OnlineCRS.Matroid.IsSelectableRand 𝓕 P b c w)
(x : α → ℝ) (hx : x ∈ b • P)
(f : Finset α → ℝ) (hf0 : ∀ S, 0 ≤ f S) (hf : NonmonotoneSubmod.Shared.Submodular f) :
((∀ A B : Finset α, A ⊆ B → f A ≤ f B) →
∀ ord : Finset (Finset α) → Finset α → List α, (∀ Fam A, IsOrder (ord Fam A)) →
c * NonmonotoneSubmod.Shared.F f x ≤ expOutput w x ord f) ∧
(∀ ord : Finset (Finset α) → Finset α → Finset α → List α,
(∀ Fam A C, IsOrder (ord Fam A C)) →
c / 4 * NonmonotoneSubmod.Shared.F f x ≤ expOutputHalf w x ord f) := by sorry
end OnlineCRS.Submod
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.