Lemma 2 — refusing arrivals cannot cover more girls
ProvedKVVMatching.Ranking.lemma_2bipartite-matchingonline-algorithmsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix a graph, an arrival order of boys, and a priority order of girls. A refusal algorithm may, at each arrival, either take its highest-ranked eligible girl or decline the boy even when an eligible girl exists. The refusal rule may depend on the time and that algorithm's current matching. Every girl matched by the refusal algorithm is also matched by RANKING under the same orders.
The comparison concerns the set of covered girls, not necessarily identical edges. It supports the comparison with EARLY and the triangular reduction.
Preamble
import Definitions.Def_KVVMatching_Ranking_GreedyRun
Formal statement
namespace KVVMatching.Ranking
/-- Lemma 2, p. 354: an arbitrary refusal rule cannot cover more girls. -/
theorem lemma_2 {n : ℕ} (adj : Fin n → Fin n → Prop)
(boyOrder girlRank : Equiv.Perm (Fin n))
(refuse : ℕ → Finset (Fin n × Fin n) → Fin n → Bool) :
((greedyRun adj boyOrder girlRank refuse).image Prod.snd) ⊆
((greedyRun adj boyOrder girlRank (fun _ _ _ => false)).image Prod.snd) := by sorry
end KVVMatching.Ranking
Source
Karp, Vazirani, Vazirani, An Optimal Algorithm for On-line Bipartite Matching, STOC 1990, p. 354, refusal-algorithm paragraph and Lemma 2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.