Rounding with exact marginals (4): every fractional first-stage matching is a mixture of matchings
ProvedTwoStageMatch.rounding_existscompetitive-ratioonline-matchingp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1ride-hailingtwo-stage-stochastic-matching
For every instance and every feasible point of (a fractional matching of ), there is a probability distribution on matchings of such that
This is the step "because of the integrality of the bipartite matching polytope, the fractional matching can be written down as a convex combination of integral bipartite matchings in " (p.12), which makes step 4 of Algorithm 1 possible.
Differences from the source:
- generalization: the optimal solution {x_ij} of 𝒫^g → every feasible point x of 𝒫^g; reason: the decomposition does not use optimality; the paper's case is x = x
- encoding: a convex combination of integral bipartite matchings → a nonnegative weight ρ on Finsets of edges, summing to 1 and supported on first-stage matchings, with the edge marginals (4); reason: same objects
Preamble
import Mathlib import Definitions.Def_TwoStageMatch_Algorithm1
Formal statement
namespace TwoStageMatch
/-- **Sampling rule (4)** (Feng, Niazadeh & Saberi, arXiv:2210.11648v1, p.12: "because of the
integrality of the bipartite matching polytope (Schrijver 2003), the fractional matching {x*_ij}
can be written down as a convex combination of integral bipartite matchings in G[D₁, S]").
Every feasible point `x` of `𝒫^g` is the edge-marginal vector of a probability distribution on
first-stage matchings: there is a probability weight `ρ` on matchings of `G[D₁, S]` with
`Pr[(i, j) ∈ M₁] = x_{ij}` for every first-stage edge `(i, j)`.
With `balanced_program_has_optimum` this shows that a run of Algorithm 1 exists on every
instance. -/
theorem rounding_exists {D₁ D₂ S : Type*} [Fintype D₁] [Fintype D₂] [Fintype S]
[DecidableEq D₁] [DecidableEq D₂] [DecidableEq S]
(I : Instance D₁ D₂ S) (x : D₁ → S → ℝ) (hx : IsFeasible I x) :
∃ ρ : Finset ((D₁ ⊕ D₂) × S) → ℝ, IsRounding I x ρ := by sorry
end TwoStageMatch
Source
Y. Feng, R. Niazadeh, A. Saberi, Two-stage Stochastic Matching and Pricing with Applications to Ride Hailing, arXiv:2210.11648v1 [cs.DS] (preprint, 21 Oct 2022), https://arxiv.org/abs/2210.11648v1, §3.1.1, p.12, eq. (4) and the sentence after it
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.