§4.1, pp.12–14 — every candidate, and of (5), lies in
ProvedVolunteerNotify.exAnte_feasiblecompetitive-analysiscrowdsourcingex-ante-solutiononline-matchingp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Each candidate for the ex ante solution is feasible for (LP):
- every optimal solution of (LP) lies in ;
- for every , every output of the Frank–Wolfe variant lies in , being an average of feasible solutions;
- every solution of the programs (SQ-) lies in ;
- consequently every of (5) lies in .
Feasibility is the hypothesis under which Lemma 3 applies to .
Differences from the source:
- generalization: x* is the argmax of f over the three candidates of (5) →
IsExAnte: every value of (5) over any optimizer of (LP), any m ≥ 1 and Frank–Wolfe run, any solution of (SQ-v), and any tie-break; reason: the candidates are not unique; each run of the source is one such value - encoding: indices in [a] = {1, …, a} →
Fin a, paper index = value + 1, a = 0 allowed; reason: Lean convention; at a = 0 the sums are empty and no instance of the source changes - encoding: Z > 0 with law g, τ ∈ ℕ →
g : ℕ → ℝwithg 0 = 0, τ ranges over positive integers; reason: ℕ is {1, 2, …} in the source; same instances
Preamble
import Mathlib import Definitions.Def_VolunteerNotify_IsExAnte
Formal statement
namespace VolunteerNotify
/-- Feasibility of the ex ante solution, Manshadi–Rodilitz, arXiv:2002.08474v7, pp.12–14: each
candidate `x*_LP`, `x*_AA`, `x*_SQ`, and so `x*` of (5), lies in `P`. -/
theorem exAnte_feasible {V S T : ℕ} (I : Instance V S T) :
(∀ x, IsLPSolution I x → x ∈ feasibleSet I) ∧
(∀ (m : ℕ) (x : Decision V S T), 1 ≤ m → IsFrankWolfeOutput I m x → x ∈ feasibleSet I) ∧
(∀ x, IsSQSolution I x → x ∈ feasibleSet I) ∧
(∀ x, IsExAnte I x → x ∈ feasibleSet I) := by sorry
end VolunteerNotify
Source
Manshadi, Rodilitz, Online Policies for Efficient Volunteer Crowdsourcing, arXiv:2002.08474v7, §4.1, p.12 ("x* ∈ P") and p.13 (Frank–Wolfe output is feasible)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.