Display (17), p.20 — weak duality:
ProvedVolunteerNotify.display_17competitive-analysiscrowdsourcinglinear-programming-dualityonline-matchingp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let , let be a volunteer and the MDHR of . Let be any reals, and let be reals with that satisfy, for all , the first two constraint sets of (J-LP):
Then
This bound holds for the worst-case per-stage rewards, which is what allows the rewards of (6) to be plugged in.
Differences from the source:
- reading: Table 1 lists variables J̄_{v,t} for t ∈ [T] and uses J̄_{v,T+1} →
Jbaron T + 1 slots withJbar (Fin.last T) = 0; reason: J_{v,T+1} = 0 on p.16 is the terminal value of the recursion that (J-LP) relaxes - generalization: q is the minimum over τ ∈ ℕ of the hazard rates (Definition 1) → q is their infimum (
mdhr); reason: the minimum need not exist, e.g. hazards 1/2 + 1/(τ+2); the infimum equals the minimum whenever it exists, so the statement specializes to the source - encoding: sums over s = 0, …, S → sums over
Fin S; reason: variables of type 0 are 0 (fn. 18, p.16), so the s = 0 terms vanish - 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 - generalization: the page argues with x* of (5) → any x ∈ P; reason: only x* ∈ P is used, through dual feasibility; x* ∈ P, so the statement specializes to the source
- encoding: (17) bounds the minimum of (J-LP), whose third constraint defines c, for a fixed v → the bound at every point satisfying the first two constraint sets, with c written out as its sum and v dropped from
rbar,Jbar; reason: a lower bound on a minimum is a lower bound at every feasible point; c is defined by that constraint - 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_lpValue import Definitions.Def_VolunteerNotify_IsDP
Formal statement
namespace VolunteerNotify
/-- Display (17), Manshadi–Rodilitz, arXiv:2002.08474v7, p.20: for `x ∈ P`, any rewards `r̄` and
any `J̄_1, …, J̄_{T+1}` with `J̄_{T+1} = 0` satisfying the first two constraint sets of (J-LP),
Table 1, p.19, `J̄_1 ≥ (1/(2 − q)) ∑_t ∑_s λ_{s,t} r̄_{s,t} x_{v,s,t}`.
**Formalization Note.** `r̄` has no sign constraint. `J̄_{T+1} = 0` is the terminal value of p.16;
Table 1's variables are `t ∈ [T]`. The `s = 0` terms vanish because `x_{v,0,t} = 0` (fn. 18). -/
theorem display_17 {V S T : ℕ} (I : Instance V S T) (x : Decision V S T)
(hx : x ∈ feasibleSet I) (v : Fin V) (rbar : Fin S → Fin T → ℝ) (Jbar : Fin (T + 1) → ℝ)
(hlast : Jbar (Fin.last T) = 0)
(hα : ∀ t : Fin T, Jbar t.succ ≤ Jbar t.castSucc)
(hγ : ∀ t : Fin T, Jbar t.succ +
∑ s, I.lam s t * x v s t * (rbar s t - Jbar t.succ + futureValue I Jbar t) ≤
Jbar t.castSucc) :
1 / (2 - mdhr I.g) * ∑ t, ∑ s, I.lam s t * rbar s t * x v s t ≤ Jbar 0 := by sorry
end VolunteerNotify
Source
Manshadi, Rodilitz, Online Policies for Efficient Volunteer Crowdsourcing, arXiv:2002.08474v7, (17), p.20; (J-LP), Table 1, p.19
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.