§3.3, p.20 — a run of Algorithm 1 is a feasible primal assignment
ProvedMultiStageAlloc.run_feasiblebatchingcompetitive-analysisconvex-programmingonline-matchingp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1primal-dual
Let be a run of PR-MWM. The sum of the stage allocations is feasible for the offline primal LP, its objective value is , and each level vector , , lies in .
This is the "feasible primal assignment" of the primal-dual argument: it shows that the algorithm's output competes in the offline LP and keeps every later stage program well posed.
Differences from the source:
- generalization: capacities n_j = 1 "without the loss of generality" (p.12), and Algorithm 1 printed only for n_j = 1 → every real n_j > 0, with normalized levels y_j + Σ_i x_ij / n_j and the coefficient n_j in the regularizer and in the dual objective; reason: at n_j = 1 this is the printed text character for character, so the statement specializes to the source
- generalization: |U_k| ≥ 1 (p.12) → a batch may be empty, and U, V may be empty; reason: instances with nonempty batches are a subclass, and nothing in the proof uses nonemptiness
- reading: no cardinality assumption on U and V is printed → U and V are finite (Fintype); reason: the program and the LP are finite sums on the page, and footnote 8 and "no further assumptions" concern batch sizes
- encoding: x_k ∈ ℝ^{E_k} → x : U → V → ℝ vanishing off E_k; reason: sums over U and V are then the printed sums over E_k; same instances
- reading: feasibility is asserted in passing ("the feasible primal assignment") → a statement with the value identity and the range of the levels; reason: these are what the certificate and later stages use
Preamble
import Mathlib import Definitions.Def_MultiStageAlloc_OfflineLP import Definitions.Def_MultiStageAlloc_Run
Formal statement
namespace MultiStageAlloc
/-- **A run is a feasible primal assignment.** Feng & Niazadeh, arXiv:2211.16581v1, §3.3, p.20: "the
feasible primal assignment `{x*_k}_{k∈[K]}` produced by Algorithm 1". The sum of the stage allocations
is feasible for the offline LP with value `ALG`, and the levels `y^(k)`, `k ≤ K`, stay in `[0, 1]`. -/
theorem run_feasible {U V : Type*} [Fintype U] [Fintype V] {K : ℕ} (I : Instance U V K)
(x : ℕ → U → V → ℝ) (y : ℕ → V → ℝ) (hrun : IsRun I x y) :
OfflineFeasible I (fun i j => ∑ k ∈ Finset.Icc 1 K, x k i j) ∧
offlineValue I (fun i j => ∑ k ∈ Finset.Icc 1 K, x k i j) = ALG I x ∧
∀ k, k ≤ K → ∀ j, y k j ∈ Set.Icc (0 : ℝ) 1 := by sorry
end MultiStageAlloc
Source
Feng & Niazadeh, Batching and Optimal Multi-stage Bipartite Allocations, arXiv:2211.16581v1, §3.3, p.20, "the feasible primal assignment"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.