/- 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 section

Stable 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 : ℕ) where

The 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 Inhabited

Preference 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 w

The 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) → Bool

The 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 : ℕ) where

The 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 wn:ℕ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) 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 μ := n:ℕp:Profile nμ:Matching n⊢ IsPartialStable p (Admissibility.all n) μ.toPartialMatching ↔ IsStable p μ 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 All goals completed! 🐙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μ:Fin n ≃ Fin n := Equiv.ofBijective 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μ:Fin n ≃ Fin n := Equiv.ofBijective wife ⋯⊢ Matching.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μ:Fin n ≃ Fin n := Equiv.ofBijective wife ⋯⊢ (Matching.toPartialMatching μ).pairs = M.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⊢ (m, w) ∈ (Matching.toPartialMatching μ).pairs ↔ (m, w) ∈ M.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 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.pairsn:ℕ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 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 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 All goals completed! 🐙 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 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 All goals completed! 🐙

With every pair admissible, stable partial matchings are exactly the pair sets of unique stable complete matchings.

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 All goals completed! 🐙 n:ℕp:Profile nM:PartialMatching n⊢ (∃! μ, μ.toPartialMatching = M ∧ IsStable p μ) → IsPartialStable p (Admissibility.all n) M 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 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).card

The 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.2

The 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.2n:ℕr:Equiv.Perm (Fin n)x:Fin n⊢ (Finset.filter ((fun y ↦ r y < r x) ∘ ⇑(Equiv.symm r)) Finset.univ).card = ↑(r x) All goals completed! 🐙

With every pair admissible, the total wife rank is the sum of the one-based preference ranks.

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⊢ ∑ m, wifeRank p (Admissibility.all n) m (μ m) = ∑ m, (1 + ↑((p.manRank m) (μ m))) All goals completed! 🐙

With every pair admissible, the total husband rank is the sum of the one-based preference ranks.

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⊢ ∑ m, husbandRank p (Admissibility.all n) m (μ m) = ∑ w, (1 + ↑((p.womanRank w) ((Equiv.symm μ) w))) All goals completed! 🐙end StableMarriage