/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/
module
public import Mathlib.Data.Fintype.Perm
public import Mathlib.Data.Fintype.Pi
public import Mathlib.Data.Fintype.Prod
public import Mathlib.MeasureTheory.Constructions.Pi
public import Mathlib.Probability.Distributions.Uniform
public import Mathlib.Probability.ProbabilityMassFunction.Integrals@[expose] public sectionStable marriage
A minimal finite model of the stable marriage problem with complete strict preferences.
For admissibility constraints, see Pittel, On Constrained Matchings.
namespace StableMarriage
A preference profile for n men and n women. Each permutation maps a candidate to their
rank, with lower ranks preferred.
structure Profile (n : ℕ) whereThe rank that each man assigns to each woman.
manRank : Fin n → Equiv.Perm (Fin n)The rank that each woman assigns to each man.
womanRank : Fin n → Equiv.Perm (Fin n)
deriving InhabitedPreference profiles form a finite type.
instance {n : ℕ} : Fintype (Profile n) :=
Fintype.ofEquiv
((Fin n → Equiv.Perm (Fin n)) × (Fin n → Equiv.Perm (Fin n)))
{ toFun := fun p => ⟨p.1, p.2⟩
invFun := fun p => (p.manRank, p.womanRank)
left_inv := fun _ => rfl
right_inv := fun _ => rfl }
A complete matching of n men to n women.
abbrev Matching (n : ℕ) := Equiv.Perm (Fin n)A man and woman form a blocking pair when they are not matched to each other and each ranks the other above their current partner.
def IsBlockingPair {n : ℕ} (p : Profile n) (μ : Matching n) (m w : Fin n) : Prop :=
μ m ≠ w ∧
p.manRank m w < p.manRank m (μ m) ∧
p.womanRank w m < p.womanRank w (μ.symm w)A matching is stable when it has no blocking pair.
def IsStable {n : ℕ} (p : Profile n) (μ : Matching n) : Prop :=
∀ m w, ¬ IsBlockingPair p μ m wThe number of stable complete matchings for a preference profile.
noncomputable def numStableMatchings {n : ℕ} (p : Profile n) : ℕ := n:ℕp:Profile n⊢ ℕ
classical
All goals completed! 🐙The discrete measurable structure on preference profiles.
instance {n : ℕ} : MeasurableSpace (Profile n) := ⊤The uniform probability mass function on preference profiles.
noncomputable def uniformProfile (n : ℕ) : PMF (Profile n) :=
PMF.uniformOfFintype (Profile n)The expected number of stable matchings under the uniform profile distribution.
noncomputable def expectedNumStableMatchings (n : ℕ) : ℝ :=
∫ p, (numStableMatchings p : ℝ) ∂((uniformProfile n).toMeasure)A mask indicating which pairs may be matched.
abbrev Admissibility (n : ℕ) := (Fin n × Fin n) → BoolThe mask that admits every pair.
def Admissibility.all (n : ℕ) : Admissibility n := fun _ ↦ true
Each pair is admitted independently with probability p.
noncomputable def Admissibility.law (n : ℕ) (p : Set.Icc (0 : ℝ) 1) :
MeasureTheory.Measure (Admissibility n) :=
MeasureTheory.Measure.pi fun _ ↦ ProbabilityTheory.bernoulliMeasure true false pinstance (n : ℕ) (p : Set.Icc (0 : ℝ) 1) :
MeasureTheory.IsProbabilityMeasure (Admissibility.law n p) := n:ℕp:↑(Set.Icc 0 1)⊢ MeasureTheory.IsProbabilityMeasure (Admissibility.law n p)
n:ℕp:↑(Set.Icc 0 1)⊢ MeasureTheory.IsProbabilityMeasure (MeasureTheory.Measure.pi fun x ↦ ProbabilityTheory.bernoulliMeasure true false p)
All goals completed! 🐙At probability one, every pair is admissible almost surely.
@[simp]
theorem Admissibility.law_one (n : ℕ) :
law n 1 = MeasureTheory.Measure.dirac (all n) := n:ℕ⊢ law n 1 = MeasureTheory.Measure.dirac (all n)
classical
n:ℕ⊢ (MeasureTheory.Measure.pi fun x ↦ ProbabilityTheory.bernoulliMeasure true false 1) = MeasureTheory.Measure.dirac (all n)
n:ℕs:Fin n × Fin n → Set Boolx✝:∀ (i : Fin n × Fin n), MeasurableSet (s i)⊢ (MeasureTheory.Measure.dirac (all n)) (Set.univ.pi s) = ∏ i, (ProbabilityTheory.bernoulliMeasure true false 1) (s i)
All goals completed! 🐙A partial matching is a set of pairs in which each participant appears at most once.
@[ext]
structure PartialMatching (n : ℕ) whereThe pairs in the matching.
pairs : Finset (Fin n × Fin n)Each man has at most one partner.
left_inj : Set.InjOn Prod.fst (pairs : Set (Fin n × Fin n))Each woman has at most one partner.
right_inj : Set.InjOn Prod.snd (pairs : Set (Fin n × Fin n))The partial matching consisting of the pairs of a complete matching.
def Matching.toPartialMatching {n : ℕ} (μ : Matching n) : PartialMatching n where
pairs := Finset.univ.map ⟨fun m ↦ (m, μ m), fun _ _ h ↦ congrArg Prod.fst h⟩
left_inj := n:ℕμ:Matching n⊢ Set.InjOn Prod.fst ↑(Finset.map { toFun := fun m ↦ (m, μ m), inj' := ⋯ } Finset.univ)
n:ℕμ:Matching na:Fin n × Fin nha:a ∈ ↑(Finset.map { toFun := fun m ↦ (m, μ m), inj' := ⋯ } Finset.univ)b:Fin n × Fin nhb:b ∈ ↑(Finset.map { toFun := fun m ↦ (m, μ m), inj' := ⋯ } Finset.univ)h:a.1 = b.1⊢ a = b
n:ℕμ:Matching nb:Fin n × Fin nhb:b ∈ ↑(Finset.map { toFun := fun m ↦ (m, μ m), inj' := ⋯ } Finset.univ)m:Fin nha:{ toFun := fun m ↦ (m, μ m), inj' := ⋯ } m ∈ ↑(Finset.map { toFun := fun m ↦ (m, μ m), inj' := ⋯ } Finset.univ)h:({ toFun := fun m ↦ (m, μ m), inj' := ⋯ } m).1 = b.1⊢ { toFun := fun m ↦ (m, μ m), inj' := ⋯ } m = b
n:ℕμ:Matching nm:Fin nha:{ toFun := fun m ↦ (m, μ m), inj' := ⋯ } m ∈ ↑(Finset.map { toFun := fun m ↦ (m, μ m), inj' := ⋯ } Finset.univ)m':Fin nhb:{ toFun := fun m ↦ (m, μ m), inj' := ⋯ } m' ∈ ↑(Finset.map { toFun := fun m ↦ (m, μ m), inj' := ⋯ } Finset.univ)h:({ toFun := fun m ↦ (m, μ m), inj' := ⋯ } m).1 = ({ toFun := fun m ↦ (m, μ m), inj' := ⋯ } m').1⊢ { toFun := fun m ↦ (m, μ m), inj' := ⋯ } m = { toFun := fun m ↦ (m, μ m), inj' := ⋯ } m'
All goals completed! 🐙
right_inj := n:ℕμ:Matching n⊢ Set.InjOn Prod.snd ↑(Finset.map { toFun := fun m ↦ (m, μ m), inj' := ⋯ } Finset.univ)
n:ℕμ:Matching na:Fin n × Fin nha:a ∈ ↑(Finset.map { toFun := fun m ↦ (m, μ m), inj' := ⋯ } Finset.univ)b:Fin n × Fin nhb:b ∈ ↑(Finset.map { toFun := fun m ↦ (m, μ m), inj' := ⋯ } Finset.univ)h:a.2 = b.2⊢ a = b
n:ℕμ:Matching nb:Fin n × Fin nhb:b ∈ ↑(Finset.map { toFun := fun m ↦ (m, μ m), inj' := ⋯ } Finset.univ)m:Fin nha:{ toFun := fun m ↦ (m, μ m), inj' := ⋯ } m ∈ ↑(Finset.map { toFun := fun m ↦ (m, μ m), inj' := ⋯ } Finset.univ)h:({ toFun := fun m ↦ (m, μ m), inj' := ⋯ } m).2 = b.2⊢ { toFun := fun m ↦ (m, μ m), inj' := ⋯ } m = b
n:ℕμ:Matching nm:Fin nha:{ toFun := fun m ↦ (m, μ m), inj' := ⋯ } m ∈ ↑(Finset.map { toFun := fun m ↦ (m, μ m), inj' := ⋯ } Finset.univ)m':Fin nhb:{ toFun := fun m ↦ (m, μ m), inj' := ⋯ } m' ∈ ↑(Finset.map { toFun := fun m ↦ (m, μ m), inj' := ⋯ } Finset.univ)h:({ toFun := fun m ↦ (m, μ m), inj' := ⋯ } m).2 = ({ toFun := fun m ↦ (m, μ m), inj' := ⋯ } m').2⊢ { toFun := fun m ↦ (m, μ m), inj' := ⋯ } m = { toFun := fun m ↦ (m, μ m), inj' := ⋯ } m'
All goals completed! 🐙@[simp]
theorem mem_toPartialMatching_pairs {n : ℕ} (μ : Matching n) (m w : Fin n) :
(m, w) ∈ μ.toPartialMatching.pairs ↔ μ m = w := n:ℕμ:Matching nm:Fin nw:Fin n⊢ (m, w) ∈ μ.toPartialMatching.pairs ↔ μ m = w
n:ℕμ:Matching nm:Fin nw:Fin n⊢ (∃ a, { toFun := fun m ↦ (m, μ m), inj' := ⋯ } a = (m, w)) ↔ μ m = w
n:ℕμ:Matching nm:Fin nw:Fin n⊢ (∃ i, (i, μ i) = (m, w)) ↔ μ m = w
All goals completed! 🐙An admissible pair blocks a partial matching if each participant is unmatched or prefers the other to their current partner.
def IsPartialBlockingPair {n : ℕ} (p : Profile n) (A : Admissibility n)
(M : PartialMatching n) (m w : Fin n) : Prop :=
A (m, w) ∧
(∀ w', (m, w') ∈ M.pairs → p.manRank m w < p.manRank m w') ∧
(∀ m', (m', w) ∈ M.pairs → p.womanRank w m < p.womanRank w m')A partial matching is stable if its pairs are admissible and no admissible pair blocks it.
def IsPartialStable {n : ℕ} (p : Profile n) (A : Admissibility n)
(M : PartialMatching n) : Prop :=
(∀ e ∈ M.pairs, A e) ∧ ∀ m w, ¬ IsPartialBlockingPair p A M m wmpr n:ℕp:Profile nμ:Matching nm:Fin nw:Fin nleft✝:μ m ≠ whm:(p.manRank m) w < (p.manRank m) (μ m)hw:(p.womanRank w) m < (p.womanRank w) ((Equiv.symm μ) w)m':Fin nh:μ m' = w⊢ (p.womanRank w) m < (p.womanRank w) ((Equiv.symm μ) w)
exact hw All goals completed! 🐙With every pair admissible, the two definitions of stability agree on complete matchings.
theorem isPartialStable_toPartialMatching_iff {n : ℕ} (p : Profile n) (μ : Matching n) :
IsPartialStable p (Admissibility.all n) μ.toPartialMatching ↔ IsStable p μ := by n:ℕp:Profile nμ:Matching n⊢ IsPartialStable p (Admissibility.all n) μ.toPartialMatching ↔ IsStable p μ
simp only [IsPartialStable, IsStable, isPartialBlockingPair_all_iff] n:ℕp:Profile nμ:Matching n⊢ ((∀ e ∈ μ.toPartialMatching.pairs, Admissibility.all n e = true) ∧ ∀ (m w : Fin n), ¬IsBlockingPair p μ m w) ↔
∀ (m w : Fin n), ¬IsBlockingPair p μ m w
simp [Admissibility.all] All goals completed! 🐙
private theorem exists_matching_of_isPartialStable_all {n : ℕ} {p : Profile n}
{M : PartialMatching n} (hStable : IsPartialStable p (Admissibility.all n) M) :
∃ μ : Matching n, μ.toPartialMatching = M := by n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) M⊢ ∃ μ, μ.toPartialMatching = M
classical
have hmatch : ∀ m, ∃ w, (m, w) ∈ M.pairs := by n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) M⊢ ∃ μ, μ.toPartialMatching = M n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mhmatch:∀ (m : Fin n), ∃ w, (m, w) ∈ M.pairs⊢ ∃ μ, μ.toPartialMatching = M
intro m n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mm:Fin n⊢ ∃ w, (m, w) ∈ M.pairs n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mhmatch:∀ (m : Fin n), ∃ w, (m, w) ∈ M.pairs⊢ ∃ μ, μ.toPartialMatching = M
by_contra! hm n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mm:Fin nhm:∀ (w : Fin n), (m, w) ∉ M.pairs⊢ False n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mhmatch:∀ (m : Fin n), ∃ w, (m, w) ∈ M.pairs⊢ ∃ μ, μ.toPartialMatching = M
have hw : ∀ w, ∃ m', (m', w) ∈ M.pairs := by n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) M⊢ ∃ μ, μ.toPartialMatching = M n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mm:Fin nhm:∀ (w : Fin n), (m, w) ∉ M.pairshw:∀ (w : Fin n), ∃ m', (m', w) ∈ M.pairs⊢ False n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mhmatch:∀ (m : Fin n), ∃ w, (m, w) ∈ M.pairs⊢ ∃ μ, μ.toPartialMatching = M
intro w n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mm:Fin nhm:∀ (w : Fin n), (m, w) ∉ M.pairsw:Fin n⊢ ∃ m', (m', w) ∈ M.pairs n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mm:Fin nhm:∀ (w : Fin n), (m, w) ∉ M.pairshw:∀ (w : Fin n), ∃ m', (m', w) ∈ M.pairs⊢ False n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mhmatch:∀ (m : Fin n), ∃ w, (m, w) ∈ M.pairs⊢ ∃ μ, μ.toPartialMatching = M
by_contra! h n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mm:Fin nhm:∀ (w : Fin n), (m, w) ∉ M.pairsw:Fin nh:∀ (m' : Fin n), (m', w) ∉ M.pairs⊢ False n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mm:Fin nhm:∀ (w : Fin n), (m, w) ∉ M.pairshw:∀ (w : Fin n), ∃ m', (m', w) ∈ M.pairs⊢ False n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mhmatch:∀ (m : Fin n), ∃ w, (m, w) ∈ M.pairs⊢ ∃ μ, μ.toPartialMatching = M
exact hStable.2 m w ⟨rfl, fun w' hw' ↦ (hm w' hw').elim, fun m' hm' ↦ (h m' hm').elim⟩ n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mm:Fin nhm:∀ (w : Fin n), (m, w) ∉ M.pairshw:∀ (w : Fin n), ∃ m', (m', w) ∈ M.pairs⊢ False n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mhmatch:∀ (m : Fin n), ∃ w, (m, w) ∈ M.pairs⊢ ∃ μ, μ.toPartialMatching = M n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mm:Fin nhm:∀ (w : Fin n), (m, w) ∉ M.pairshw:∀ (w : Fin n), ∃ m', (m', w) ∈ M.pairs⊢ False n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mhmatch:∀ (m : Fin n), ∃ w, (m, w) ∈ M.pairs⊢ ∃ μ, μ.toPartialMatching = M
choose husband hHusband using hw n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mm:Fin nhm:∀ (w : Fin n), (m, w) ∉ M.pairshusband:Fin n → Fin nhHusband:∀ (w : Fin n), (husband w, w) ∈ M.pairs⊢ False n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mhmatch:∀ (m : Fin n), ∃ w, (m, w) ∈ M.pairs⊢ ∃ μ, μ.toPartialMatching = M
have hHusbandInj : Function.Injective husband := by n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) M⊢ ∃ μ, μ.toPartialMatching = M n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mm:Fin nhm:∀ (w : Fin n), (m, w) ∉ M.pairshusband:Fin n → Fin nhHusband:∀ (w : Fin n), (husband w, w) ∈ M.pairshHusbandInj:Function.Injective husband⊢ False n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mhmatch:∀ (m : Fin n), ∃ w, (m, w) ∈ M.pairs⊢ ∃ μ, μ.toPartialMatching = M
intro w w' h n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mm:Fin nhm:∀ (w : Fin n), (m, w) ∉ M.pairshusband:Fin n → Fin nhHusband:∀ (w : Fin n), (husband w, w) ∈ M.pairsw:Fin nw':Fin nh:husband w = husband w'⊢ w = w' n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mm:Fin nhm:∀ (w : Fin n), (m, w) ∉ M.pairshusband:Fin n → Fin nhHusband:∀ (w : Fin n), (husband w, w) ∈ M.pairshHusbandInj:Function.Injective husband⊢ False n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mhmatch:∀ (m : Fin n), ∃ w, (m, w) ∈ M.pairs⊢ ∃ μ, μ.toPartialMatching = M
exact congrArg Prod.snd (M.left_inj (hHusband w) (hHusband w') h) n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mm:Fin nhm:∀ (w : Fin n), (m, w) ∉ M.pairshusband:Fin n → Fin nhHusband:∀ (w : Fin n), (husband w, w) ∈ M.pairshHusbandInj:Function.Injective husband⊢ False n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mhmatch:∀ (m : Fin n), ∃ w, (m, w) ∈ M.pairs⊢ ∃ μ, μ.toPartialMatching = M n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mm:Fin nhm:∀ (w : Fin n), (m, w) ∉ M.pairshusband:Fin n → Fin nhHusband:∀ (w : Fin n), (husband w, w) ∈ M.pairshHusbandInj:Function.Injective husband⊢ False n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mhmatch:∀ (m : Fin n), ∃ w, (m, w) ∈ M.pairs⊢ ∃ μ, μ.toPartialMatching = M
obtain ⟨w, rfl⟩ := Finite.surjective_of_injective hHusbandInj m n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mhusband:Fin n → Fin nhHusband:∀ (w : Fin n), (husband w, w) ∈ M.pairshHusbandInj:Function.Injective husbandw:Fin nhm:∀ (w_1 : Fin n), (husband w, w_1) ∉ M.pairs⊢ False n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mhmatch:∀ (m : Fin n), ∃ w, (m, w) ∈ M.pairs⊢ ∃ μ, μ.toPartialMatching = M
exact hm w (hHusband w) n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mhmatch:∀ (m : Fin n), ∃ w, (m, w) ∈ M.pairs⊢ ∃ μ, μ.toPartialMatching = M n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mhmatch:∀ (m : Fin n), ∃ w, (m, w) ∈ M.pairs⊢ ∃ μ, μ.toPartialMatching = M
choose wife hWife using hmatch n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mwife:Fin n → Fin nhWife:∀ (m : Fin n), (m, wife m) ∈ M.pairs⊢ ∃ μ, μ.toPartialMatching = M
have hWifeInj : Function.Injective wife := by n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) M⊢ ∃ μ, μ.toPartialMatching = M n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mwife:Fin n → Fin nhWife:∀ (m : Fin n), (m, wife m) ∈ M.pairshWifeInj:Function.Injective wife⊢ ∃ μ, μ.toPartialMatching = M
intro m m' h n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mwife:Fin n → Fin nhWife:∀ (m : Fin n), (m, wife m) ∈ M.pairsm:Fin nm':Fin nh:wife m = wife m'⊢ m = m' n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mwife:Fin n → Fin nhWife:∀ (m : Fin n), (m, wife m) ∈ M.pairshWifeInj:Function.Injective wife⊢ ∃ μ, μ.toPartialMatching = M
exact congrArg Prod.fst (M.right_inj (hWife m) (hWife m') h) n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mwife:Fin n → Fin nhWife:∀ (m : Fin n), (m, wife m) ∈ M.pairshWifeInj:Function.Injective wife⊢ ∃ μ, μ.toPartialMatching = M n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mwife:Fin n → Fin nhWife:∀ (m : Fin n), (m, wife m) ∈ M.pairshWifeInj:Function.Injective wife⊢ ∃ μ, μ.toPartialMatching = M
let μ := Equiv.ofBijective wife hWifeInj.bijective_of_finite n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mwife:Fin n → Fin nhWife:∀ (m : Fin n), (m, wife m) ∈ M.pairshWifeInj:Function.Injective wifeμ:Fin n ≃ Fin n := Equiv.ofBijective wife ⋯⊢ ∃ μ, μ.toPartialMatching = M
refine ⟨μ, ?_⟩ n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mwife:Fin n → Fin nhWife:∀ (m : Fin n), (m, wife m) ∈ M.pairshWifeInj:Function.Injective wifeμ:Fin n ≃ Fin n := Equiv.ofBijective wife ⋯⊢ Matching.toPartialMatching μ = M
ext : 1 n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mwife:Fin n → Fin nhWife:∀ (m : Fin n), (m, wife m) ∈ M.pairshWifeInj:Function.Injective wifeμ:Fin n ≃ Fin n := Equiv.ofBijective wife ⋯⊢ (Matching.toPartialMatching μ).pairs = M.pairs
ext ⟨m, w⟩ n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mwife:Fin n → Fin nhWife:∀ (m : Fin n), (m, wife m) ∈ M.pairshWifeInj:Function.Injective wifeμ:Fin n ≃ Fin n := Equiv.ofBijective wife ⋯m:Fin nw:Fin n⊢ (m, w) ∈ (Matching.toPartialMatching μ).pairs ↔ (m, w) ∈ M.pairs
simp only [mem_toPartialMatching_pairs, μ] n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mwife:Fin n → Fin nhWife:∀ (m : Fin n), (m, wife m) ∈ M.pairshWifeInj:Function.Injective wifeμ:Fin n ≃ Fin n := Equiv.ofBijective wife ⋯m:Fin nw:Fin n⊢ (Equiv.ofBijective wife ⋯) m = w ↔ (m, w) ∈ M.pairs
constructor mp n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mwife:Fin n → Fin nhWife:∀ (m : Fin n), (m, wife m) ∈ M.pairshWifeInj:Function.Injective wifeμ:Fin n ≃ Fin n := Equiv.ofBijective wife ⋯m:Fin nw:Fin n⊢ (Equiv.ofBijective wife ⋯) m = w → (m, w) ∈ M.pairsmpr n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mwife:Fin n → Fin nhWife:∀ (m : Fin n), (m, wife m) ∈ M.pairshWifeInj:Function.Injective wifeμ:Fin n ≃ Fin n := Equiv.ofBijective wife ⋯m:Fin nw:Fin n⊢ (m, w) ∈ M.pairs → (Equiv.ofBijective wife ⋯) m = w
· mp n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mwife:Fin n → Fin nhWife:∀ (m : Fin n), (m, wife m) ∈ M.pairshWifeInj:Function.Injective wifeμ:Fin n ≃ Fin n := Equiv.ofBijective wife ⋯m:Fin nw:Fin n⊢ (Equiv.ofBijective wife ⋯) m = w → (m, w) ∈ M.pairs rintro rfl mp n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mwife:Fin n → Fin nhWife:∀ (m : Fin n), (m, wife m) ∈ M.pairshWifeInj:Function.Injective wifeμ:Fin n ≃ Fin n := Equiv.ofBijective wife ⋯m:Fin n⊢ (m, (Equiv.ofBijective wife ⋯) m) ∈ M.pairs
exact hWife m All goals completed! 🐙
· mpr n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mwife:Fin n → Fin nhWife:∀ (m : Fin n), (m, wife m) ∈ M.pairshWifeInj:Function.Injective wifeμ:Fin n ≃ Fin n := Equiv.ofBijective wife ⋯m:Fin nw:Fin n⊢ (m, w) ∈ M.pairs → (Equiv.ofBijective wife ⋯) m = w intro h mpr n:ℕp:Profile nM:PartialMatching nhStable:IsPartialStable p (Admissibility.all n) Mwife:Fin n → Fin nhWife:∀ (m : Fin n), (m, wife m) ∈ M.pairshWifeInj:Function.Injective wifeμ:Fin n ≃ Fin n := Equiv.ofBijective wife ⋯m:Fin nw:Fin nh:(m, w) ∈ M.pairs⊢ (Equiv.ofBijective wife ⋯) m = w
exact congrArg Prod.snd (M.left_inj (hWife m) h rfl) All goals completed! 🐙With every pair admissible, stable partial matchings are exactly the pair sets of unique stable complete matchings.
theorem isPartialStable_all_iff {n : ℕ} (p : Profile n) (M : PartialMatching n) :
IsPartialStable p (Admissibility.all n) M ↔
∃! μ : Matching n, μ.toPartialMatching = M ∧ IsStable p μ := by n:ℕp:Profile nM:PartialMatching n⊢ IsPartialStable p (Admissibility.all n) M ↔ ∃! μ, μ.toPartialMatching = M ∧ IsStable p μ
constructor mp n:ℕp:Profile nM:PartialMatching n⊢ IsPartialStable p (Admissibility.all n) M → ∃! μ, μ.toPartialMatching = M ∧ IsStable p μmpr n:ℕp:Profile nM:PartialMatching n⊢ (∃! μ, μ.toPartialMatching = M ∧ IsStable p μ) → IsPartialStable p (Admissibility.all n) M
· mp n:ℕp:Profile nM:PartialMatching n⊢ IsPartialStable p (Admissibility.all n) M → ∃! μ, μ.toPartialMatching = M ∧ IsStable p μ intro h mp n:ℕp:Profile nM:PartialMatching nh:IsPartialStable p (Admissibility.all n) M⊢ ∃! μ, μ.toPartialMatching = M ∧ IsStable p μ
obtain ⟨μ, rfl⟩ := exists_matching_of_isPartialStable_all h mp n:ℕp:Profile nμ:Matching nh:IsPartialStable p (Admissibility.all n) μ.toPartialMatching⊢ ∃! μ_1, μ_1.toPartialMatching = μ.toPartialMatching ∧ IsStable p μ_1
refine ⟨μ, ⟨rfl, (isPartialStable_toPartialMatching_iff p μ).mp h⟩, ?_⟩ mp n:ℕp:Profile nμ:Matching nh:IsPartialStable p (Admissibility.all n) μ.toPartialMatching⊢ ∀ (y : Matching n), (fun μ_1 ↦ μ_1.toPartialMatching = μ.toPartialMatching ∧ IsStable p μ_1) y → y = μ
intro ν hν mp n:ℕp:Profile nμ:Matching nh:IsPartialStable p (Admissibility.all n) μ.toPartialMatchingν:Matching nhν:ν.toPartialMatching = μ.toPartialMatching ∧ IsStable p ν⊢ ν = μ
apply Equiv.ext mp n:ℕp:Profile nμ:Matching nh:IsPartialStable p (Admissibility.all n) μ.toPartialMatchingν:Matching nhν:ν.toPartialMatching = μ.toPartialMatching ∧ IsStable p ν⊢ ∀ (x : Fin n), ν x = μ x
intro m mp n:ℕp:Profile nμ:Matching nh:IsPartialStable p (Admissibility.all n) μ.toPartialMatchingν:Matching nhν:ν.toPartialMatching = μ.toPartialMatching ∧ IsStable p νm:Fin n⊢ ν m = μ m
apply (mem_toPartialMatching_pairs ν m (μ m)).mp mp n:ℕp:Profile nμ:Matching nh:IsPartialStable p (Admissibility.all n) μ.toPartialMatchingν:Matching nhν:ν.toPartialMatching = μ.toPartialMatching ∧ IsStable p νm:Fin n⊢ (m, μ m) ∈ ν.toPartialMatching.pairs
rw [hν.1 mp n:ℕp:Profile nμ:Matching nh:IsPartialStable p (Admissibility.all n) μ.toPartialMatchingν:Matching nhν:ν.toPartialMatching = μ.toPartialMatching ∧ IsStable p νm:Fin n⊢ (m, μ m) ∈ μ.toPartialMatching.pairs mp n:ℕp:Profile nμ:Matching nh:IsPartialStable p (Admissibility.all n) μ.toPartialMatchingν:Matching nhν:ν.toPartialMatching = μ.toPartialMatching ∧ IsStable p νm:Fin n⊢ (m, μ m) ∈ μ.toPartialMatching.pairs] mp n:ℕp:Profile nμ:Matching nh:IsPartialStable p (Admissibility.all n) μ.toPartialMatchingν:Matching nhν:ν.toPartialMatching = μ.toPartialMatching ∧ IsStable p νm:Fin n⊢ (m, μ m) ∈ μ.toPartialMatching.pairs
simp All goals completed! 🐙
· mpr n:ℕp:Profile nM:PartialMatching n⊢ (∃! μ, μ.toPartialMatching = M ∧ IsStable p μ) → IsPartialStable p (Admissibility.all n) M rintro ⟨μ, ⟨rfl, h⟩, _⟩ mpr n:ℕp:Profile nμ:Matching nh:IsStable p μright✝:∀ (y : Matching n), (fun μ_1 ↦ μ_1.toPartialMatching = μ.toPartialMatching ∧ IsStable p μ_1) y → y = μ⊢ IsPartialStable p (Admissibility.all n) μ.toPartialMatching
exact (isPartialStable_toPartialMatching_iff p μ).mpr h All goals completed! 🐙
One plus the number of admissible women whom m ranks ahead of w.
def wifeRank {n : ℕ} (p : Profile n) (A : Admissibility n) (m w : Fin n) : ℕ :=
1 + (Finset.univ.filter fun v ↦ A (m, v) ∧ p.manRank m v < p.manRank m w).card
One plus the number of admissible men whom w ranks ahead of m.
def husbandRank {n : ℕ} (p : Profile n) (A : Admissibility n) (m w : Fin n) : ℕ :=
1 + (Finset.univ.filter fun u ↦ A (u, w) ∧ p.womanRank w u < p.womanRank w m).cardThe sum of the one-based ranks that matched men assign to their partners.
def totalWifeRank {n : ℕ} (p : Profile n) (A : Admissibility n) (M : PartialMatching n) : ℕ :=
∑ e ∈ M.pairs, wifeRank p A e.1 e.2The sum of the one-based ranks that matched women assign to their partners.
def totalHusbandRank {n : ℕ} (p : Profile n) (A : Admissibility n)
(M : PartialMatching n) : ℕ :=
∑ e ∈ M.pairs, husbandRank p A e.1 e.2
private theorem card_filter_rank_lt {n : ℕ} (r : Equiv.Perm (Fin n)) (x : Fin n) :
(Finset.univ.filter fun y ↦ r y < r x).card = (r x).val := by n:ℕr:Equiv.Perm (Fin n)x:Fin n⊢ {y | r y < r x}.card = ↑(r x)
rw [← Finset.card_map r.toEmbedding, n:ℕr:Equiv.Perm (Fin n)x:Fin n⊢ (Finset.map (Equiv.toEmbedding r) {y | r y < r x}).card = ↑(r x) n:ℕr:Equiv.Perm (Fin n)x:Fin n⊢ (Finset.filter ((fun y ↦ r y < r x) ∘ ⇑(Equiv.symm r)) Finset.univ).card = ↑(r x) Finset.map_filter, n:ℕr:Equiv.Perm (Fin n)x:Fin n⊢ (Finset.filter ((fun y ↦ r y < r x) ∘ ⇑(Equiv.symm r)) (Finset.map (Equiv.toEmbedding r) Finset.univ)).card = ↑(r x) n:ℕr:Equiv.Perm (Fin n)x:Fin n⊢ (Finset.filter ((fun y ↦ r y < r x) ∘ ⇑(Equiv.symm r)) Finset.univ).card = ↑(r x) Finset.map_univ_equiv n:ℕr:Equiv.Perm (Fin n)x:Fin n⊢ (Finset.filter ((fun y ↦ r y < r x) ∘ ⇑(Equiv.symm r)) Finset.univ).card = ↑(r x) n:ℕr:Equiv.Perm (Fin n)x:Fin n⊢ (Finset.filter ((fun y ↦ r y < r x) ∘ ⇑(Equiv.symm r)) Finset.univ).card = ↑(r x)] n:ℕr:Equiv.Perm (Fin n)x:Fin n⊢ (Finset.filter ((fun y ↦ r y < r x) ∘ ⇑(Equiv.symm r)) Finset.univ).card = ↑(r x)
simp [Finset.filter_gt_eq_Iio] All goals completed! 🐙With every pair admissible, the total wife rank is the sum of the one-based preference ranks.
theorem totalWifeRank_toPartialMatching {n : ℕ} (p : Profile n) (μ : Matching n) :
totalWifeRank p (Admissibility.all n) μ.toPartialMatching =
∑ m, (1 + (p.manRank m (μ m)).val) := by n:ℕp:Profile nμ:Matching n⊢ totalWifeRank p (Admissibility.all n) μ.toPartialMatching = ∑ m, (1 + ↑((p.manRank m) (μ m)))
rw [totalWifeRank, n:ℕp:Profile nμ:Matching n⊢ ∑ e ∈ μ.toPartialMatching.pairs, wifeRank p (Admissibility.all n) e.1 e.2 = ∑ m, (1 + ↑((p.manRank m) (μ m))) n:ℕp:Profile nμ:Matching n⊢ ∑ x,
wifeRank p (Admissibility.all n) ({ toFun := fun m ↦ (m, μ m), inj' := ⋯ } x).1
({ toFun := fun m ↦ (m, μ m), inj' := ⋯ } x).2 =
∑ m, (1 + ↑((p.manRank m) (μ m))) Matching.toPartialMatching, n:ℕp:Profile nμ:Matching n⊢ ∑ e ∈ { pairs := Finset.map { toFun := fun m ↦ (m, μ m), inj' := ⋯ } Finset.univ, left_inj := ⋯, right_inj := ⋯ }.pairs,
wifeRank p (Admissibility.all n) e.1 e.2 =
∑ m, (1 + ↑((p.manRank m) (μ m))) n:ℕp:Profile nμ:Matching n⊢ ∑ x,
wifeRank p (Admissibility.all n) ({ toFun := fun m ↦ (m, μ m), inj' := ⋯ } x).1
({ toFun := fun m ↦ (m, μ m), inj' := ⋯ } x).2 =
∑ m, (1 + ↑((p.manRank m) (μ m))) Finset.sum_map n:ℕp:Profile nμ:Matching n⊢ ∑ x,
wifeRank p (Admissibility.all n) ({ toFun := fun m ↦ (m, μ m), inj' := ⋯ } x).1
({ toFun := fun m ↦ (m, μ m), inj' := ⋯ } x).2 =
∑ m, (1 + ↑((p.manRank m) (μ m))) n:ℕp:Profile nμ:Matching n⊢ ∑ x,
wifeRank p (Admissibility.all n) ({ toFun := fun m ↦ (m, μ m), inj' := ⋯ } x).1
({ toFun := fun m ↦ (m, μ m), inj' := ⋯ } x).2 =
∑ m, (1 + ↑((p.manRank m) (μ m)))] n:ℕp:Profile nμ:Matching n⊢ ∑ x,
wifeRank p (Admissibility.all n) ({ toFun := fun m ↦ (m, μ m), inj' := ⋯ } x).1
({ toFun := fun m ↦ (m, μ m), inj' := ⋯ } x).2 =
∑ m, (1 + ↑((p.manRank m) (μ m)))
change (∑ m, wifeRank p (Admissibility.all n) m (μ m)) = _ n:ℕp:Profile nμ:Matching n⊢ ∑ m, wifeRank p (Admissibility.all n) m (μ m) = ∑ m, (1 + ↑((p.manRank m) (μ m)))
simp [wifeRank, Admissibility.all, card_filter_rank_lt] All goals completed! 🐙With every pair admissible, the total husband rank is the sum of the one-based preference ranks.
theorem totalHusbandRank_toPartialMatching {n : ℕ} (p : Profile n) (μ : Matching n) :
totalHusbandRank p (Admissibility.all n) μ.toPartialMatching =
∑ w, (1 + (p.womanRank w (μ.symm w)).val) := by n:ℕp:Profile nμ:Matching n⊢ totalHusbandRank p (Admissibility.all n) μ.toPartialMatching = ∑ w, (1 + ↑((p.womanRank w) ((Equiv.symm μ) w)))
rw [totalHusbandRank, n:ℕp:Profile nμ:Matching n⊢ ∑ e ∈ μ.toPartialMatching.pairs, husbandRank p (Admissibility.all n) e.1 e.2 =
∑ w, (1 + ↑((p.womanRank w) ((Equiv.symm μ) w))) n:ℕp:Profile nμ:Matching n⊢ ∑ x,
husbandRank p (Admissibility.all n) ({ toFun := fun m ↦ (m, μ m), inj' := ⋯ } x).1
({ toFun := fun m ↦ (m, μ m), inj' := ⋯ } x).2 =
∑ w, (1 + ↑((p.womanRank w) ((Equiv.symm μ) w))) Matching.toPartialMatching, n:ℕp:Profile nμ:Matching n⊢ ∑ e ∈ { pairs := Finset.map { toFun := fun m ↦ (m, μ m), inj' := ⋯ } Finset.univ, left_inj := ⋯, right_inj := ⋯ }.pairs,
husbandRank p (Admissibility.all n) e.1 e.2 =
∑ w, (1 + ↑((p.womanRank w) ((Equiv.symm μ) w))) n:ℕp:Profile nμ:Matching n⊢ ∑ x,
husbandRank p (Admissibility.all n) ({ toFun := fun m ↦ (m, μ m), inj' := ⋯ } x).1
({ toFun := fun m ↦ (m, μ m), inj' := ⋯ } x).2 =
∑ w, (1 + ↑((p.womanRank w) ((Equiv.symm μ) w))) Finset.sum_map n:ℕp:Profile nμ:Matching n⊢ ∑ x,
husbandRank p (Admissibility.all n) ({ toFun := fun m ↦ (m, μ m), inj' := ⋯ } x).1
({ toFun := fun m ↦ (m, μ m), inj' := ⋯ } x).2 =
∑ w, (1 + ↑((p.womanRank w) ((Equiv.symm μ) w))) n:ℕp:Profile nμ:Matching n⊢ ∑ x,
husbandRank p (Admissibility.all n) ({ toFun := fun m ↦ (m, μ m), inj' := ⋯ } x).1
({ toFun := fun m ↦ (m, μ m), inj' := ⋯ } x).2 =
∑ w, (1 + ↑((p.womanRank w) ((Equiv.symm μ) w)))] n:ℕp:Profile nμ:Matching n⊢ ∑ x,
husbandRank p (Admissibility.all n) ({ toFun := fun m ↦ (m, μ m), inj' := ⋯ } x).1
({ toFun := fun m ↦ (m, μ m), inj' := ⋯ } x).2 =
∑ w, (1 + ↑((p.womanRank w) ((Equiv.symm μ) w)))
change (∑ m, husbandRank p (Admissibility.all n) m (μ m)) = _ n:ℕp:Profile nμ:Matching n⊢ ∑ m, husbandRank p (Admissibility.all n) m (μ m) = ∑ w, (1 + ↑((p.womanRank w) ((Equiv.symm μ) w)))
simpa [husbandRank, Admissibility.all, card_filter_rank_lt] using
(Equiv.sum_comp μ fun w ↦ 1 + (p.womanRank w (μ.symm w)).val) All goals completed! 🐙end StableMarriage