/-
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 FormalConjecturesForMathlib.Combinatorics.StableMarriageStable matching with unequal side sizes
Complete strict preferences for firms and workers. Matchings cover all firms and may leave workers unmatched. Every partner is preferable to being unmatched.
Reference: B. Pittel, On Likely Solutions of the Stable Matching Problem with Unequal Numbers of Men and Women (2017), https://arxiv.org/abs/1701.08900.
@[expose] public sectionnamespace StableMarriage.Unbalanced
Complete strict rankings for n firms and m workers, with smaller ranks preferred.
structure Profile (n m : ℕ) whereEach firm's ranks of workers.
firmRank : Fin n → Equiv.Perm (Fin m)Each worker's ranks of firms.
workerRank : Fin m → Equiv.Perm (Fin n)
deriving Inhabitedinstance {n m : ℕ} : Fintype (Profile n m) :=
Fintype.ofEquiv
((Fin n → Equiv.Perm (Fin m)) × (Fin m → Equiv.Perm (Fin n)))
{ toFun := fun p ↦ ⟨p.1, p.2⟩
invFun := fun p ↦ (p.firmRank, p.workerRank)
left_inv := fun _ ↦ rfl
right_inv := fun _ ↦ rfl }A matching assigns every firm a distinct worker.
abbrev Matching (n m : ℕ) := Fin n ↪ Fin mA pair blocks if the firm prefers the worker, and the worker prefers the firm to its assigned firm, if any. The universal condition is vacuous for an unmatched worker.
def IsBlockingPair {n m : ℕ} (p : Profile n m) (μ : Matching n m)
(i : Fin n) (j : Fin m) : Prop :=
μ i ≠ j ∧ p.firmRank i j < p.firmRank i (μ i) ∧
∀ k, μ k = j → p.workerRank j i < p.workerRank j kA matching is stable when it has no blocking pair.
def IsStable {n m : ℕ} (p : Profile n m) (μ : Matching n m) : Prop :=
∀ i j, ¬ IsBlockingPair p μ i jThe number of stable matchings covering all firms.
noncomputable def numStableMatchings {n m : ℕ} (p : Profile n m) : ℕ := n:ℕm:ℕp:Profile n m⊢ ℕ
classical
All goals completed! 🐙instance {n m : ℕ} : MeasurableSpace (Profile n m) := ⊤The joint law of independent uniform rankings on both sides.
noncomputable def uniformProfile (n m : ℕ) : PMF (Profile n m) :=
PMF.uniformOfFintype (Profile n m)The first moment of the number of stable matchings.
noncomputable def expectedNumStableMatchings (n m : ℕ) : ℝ :=
∫ p, (numStableMatchings p : ℝ) ∂((uniformProfile n m).toMeasure)The second moment of the number of stable matchings, under the same profile law.
noncomputable def secondMomentNumStableMatchings (n m : ℕ) : ℝ :=
∫ p, (numStableMatchings p : ℝ) ^ 2 ∂((uniformProfile n m).toMeasure)A balanced profile viewed as a rectangular profile.
def ofBalancedProfile {n : ℕ} (p : StableMarriage.Profile n) : Profile n n :=
⟨p.manRank, p.womanRank⟩Blocking agrees with the balanced model when a bijection is viewed as an embedding.
theorem isBlockingPair_ofBalancedProfile {n : ℕ} (p : StableMarriage.Profile n)
(μ : StableMarriage.Matching n) (i j : Fin n) :
IsBlockingPair (ofBalancedProfile p) μ.toEmbedding i j ↔
StableMarriage.IsBlockingPair p μ i j := n:ℕp:StableMarriage.Profile nμ:StableMarriage.Matching ni:Fin nj:Fin n⊢ IsBlockingPair (ofBalancedProfile p) (Equiv.toEmbedding μ) i j ↔ StableMarriage.IsBlockingPair p μ i j
n:ℕp:StableMarriage.Profile nμ:StableMarriage.Matching ni:Fin nj:Fin n⊢ IsBlockingPair (ofBalancedProfile p) (Equiv.toEmbedding μ) i j → StableMarriage.IsBlockingPair p μ i jn:ℕp:StableMarriage.Profile nμ:StableMarriage.Matching ni:Fin nj:Fin n⊢ StableMarriage.IsBlockingPair p μ i j → IsBlockingPair (ofBalancedProfile p) (Equiv.toEmbedding μ) i j
n:ℕp:StableMarriage.Profile nμ:StableMarriage.Matching ni:Fin nj:Fin n⊢ IsBlockingPair (ofBalancedProfile p) (Equiv.toEmbedding μ) i j → StableMarriage.IsBlockingPair p μ i j n:ℕp:StableMarriage.Profile nμ:StableMarriage.Matching ni:Fin nj:Fin nhne:(Equiv.toEmbedding μ) i ≠ jhi:((ofBalancedProfile p).firmRank i) j < ((ofBalancedProfile p).firmRank i) ((Equiv.toEmbedding μ) i)hj:∀ (k : Fin n),
(Equiv.toEmbedding μ) k = j → ((ofBalancedProfile p).workerRank j) i < ((ofBalancedProfile p).workerRank j) k⊢ StableMarriage.IsBlockingPair p μ i j
All goals completed! 🐙
n:ℕp:StableMarriage.Profile nμ:StableMarriage.Matching ni:Fin nj:Fin n⊢ StableMarriage.IsBlockingPair p μ i j → IsBlockingPair (ofBalancedProfile p) (Equiv.toEmbedding μ) i j n:ℕp:StableMarriage.Profile nμ:StableMarriage.Matching ni:Fin nj:Fin nhne:μ i ≠ jhi:(p.manRank i) j < (p.manRank i) (μ i)hj:(p.womanRank j) i < (p.womanRank j) ((Equiv.symm μ) j)⊢ IsBlockingPair (ofBalancedProfile p) (Equiv.toEmbedding μ) i j
n:ℕp:StableMarriage.Profile nμ:StableMarriage.Matching ni:Fin nj:Fin nhne:μ i ≠ jhi:(p.manRank i) j < (p.manRank i) (μ i)hj:(p.womanRank j) i < (p.womanRank j) ((Equiv.symm μ) j)⊢ ∀ (k : Fin n),
(Equiv.toEmbedding μ) k = j → ((ofBalancedProfile p).workerRank j) i < ((ofBalancedProfile p).workerRank j) k
n:ℕp:StableMarriage.Profile nμ:StableMarriage.Matching ni:Fin nj:Fin nhne:μ i ≠ jhi:(p.manRank i) j < (p.manRank i) (μ i)hj:(p.womanRank j) i < (p.womanRank j) ((Equiv.symm μ) j)k:Fin nhk:(Equiv.toEmbedding μ) k = j⊢ ((ofBalancedProfile p).workerRank j) i < ((ofBalancedProfile p).workerRank j) k
n:ℕp:StableMarriage.Profile nμ:StableMarriage.Matching ni:Fin nj:Fin nhne:μ i ≠ jhi:(p.manRank i) j < (p.manRank i) (μ i)hj:(p.womanRank j) i < (p.womanRank j) ((Equiv.symm μ) j)k:Fin nhk:μ k = j⊢ ((ofBalancedProfile p).workerRank j) i < ((ofBalancedProfile p).workerRank j) k
n:ℕp:StableMarriage.Profile nμ:StableMarriage.Matching ni:Fin nj:Fin nhne:μ i ≠ jhi:(p.manRank i) j < (p.manRank i) (μ i)hj:(p.womanRank j) i < (p.womanRank j) ((Equiv.symm μ) j)k:Fin nhk:μ k = j⊢ (p.womanRank j) i < (p.womanRank j) k
All goals completed! 🐙Stability agrees with the balanced model on bijective matchings.
theorem isStable_ofBalancedProfile {n : ℕ} (p : StableMarriage.Profile n)
(μ : StableMarriage.Matching n) :
IsStable (ofBalancedProfile p) μ.toEmbedding ↔ StableMarriage.IsStable p μ := n:ℕp:StableMarriage.Profile nμ:StableMarriage.Matching n⊢ IsStable (ofBalancedProfile p) (Equiv.toEmbedding μ) ↔ StableMarriage.IsStable p μ
All goals completed! 🐙An empty firm side has a stable empty matching.
theorem isStable_zero {m : ℕ} (p : Profile 0 m) (μ : Matching 0 m) : IsStable p μ := m:ℕp:Profile 0 mμ:Matching 0 m⊢ IsStable p μ
m:ℕp:Profile 0 mμ:Matching 0 mi:Fin 0⊢ ∀ (j : Fin m), ¬IsBlockingPair p μ i j
All goals completed! 🐙With no firms there is exactly one stable matching, regardless of the workers.
theorem numStableMatchings_zero {m : ℕ} (p : Profile 0 m) : numStableMatchings p = 1 := m:ℕp:Profile 0 m⊢ numStableMatchings p = 1
classical
m:ℕp:Profile 0 m⊢ ∃ x, ∀ (y : { μ // IsStable p μ }), y = x
m:ℕp:Profile 0 m⊢ ∀ (y : { μ // IsStable p μ }), y = ⟨default, ⋯⟩
m:ℕp:Profile 0 mμ:{ μ // IsStable p μ }⊢ μ = ⟨default, ⋯⟩
All goals completed! 🐙With one firm, stability means assigning its first-choice worker.
mpr m:ℕp:Profile 1 (m + 1)μ:Matching 1 (m + 1)h:(p.firmRank 0) (μ 0) = 0j:Fin (m + 1)hb:IsBlockingPair p μ 0 jhlt:(p.firmRank 0) j < 0⊢ False
exact (not_lt_of_ge (Fin.zero_le _)) hlt All goals completed! 🐙Every nonempty one-firm market has exactly one stable matching.
theorem numStableMatchings_one {m : ℕ} (p : Profile 1 (m + 1)) :
numStableMatchings p = 1 := by m:ℕp:Profile 1 (m + 1)⊢ numStableMatchings p = 1
classical
let μ₀ : Matching 1 (m + 1) :=
⟨fun _ ↦ (p.firmRank 0).symm 0, fun _ _ _ ↦ Subsingleton.elim _ _⟩ m:ℕp:Profile 1 (m + 1)μ₀:Matching 1 (m + 1) := { toFun := fun x ↦ (Equiv.symm (p.firmRank 0)) 0, inj' := ⋯ }⊢ numStableMatchings p = 1
have hμ₀ : IsStable p μ₀ := (isStable_one_iff p μ₀).mpr (by m:ℕp:Profile 1 (m + 1)μ₀:Matching 1 (m + 1) := { toFun := fun x ↦ (Equiv.symm (p.firmRank 0)) 0, inj' := ⋯ }⊢ (p.firmRank 0) (μ₀ 0) = 0 m:ℕp:Profile 1 (m + 1)μ₀:Matching 1 (m + 1) := { toFun := fun x ↦ (Equiv.symm (p.firmRank 0)) 0, inj' := ⋯ }hμ₀:IsStable p μ₀⊢ numStableMatchings p = 1
change p.firmRank 0 ((p.firmRank 0).symm 0) = 0 m:ℕp:Profile 1 (m + 1)μ₀:Matching 1 (m + 1) := { toFun := fun x ↦ (Equiv.symm (p.firmRank 0)) 0, inj' := ⋯ }⊢ (p.firmRank 0) ((Equiv.symm (p.firmRank 0)) 0) = 0 m:ℕp:Profile 1 (m + 1)μ₀:Matching 1 (m + 1) := { toFun := fun x ↦ (Equiv.symm (p.firmRank 0)) 0, inj' := ⋯ }hμ₀:IsStable p μ₀⊢ numStableMatchings p = 1
exact (p.firmRank 0).apply_symm_apply 0 All goals completed! 🐙 m:ℕp:Profile 1 (m + 1)μ₀:Matching 1 (m + 1) := { toFun := fun x ↦ (Equiv.symm (p.firmRank 0)) 0, inj' := ⋯ }hμ₀:IsStable p μ₀⊢ numStableMatchings p = 1) m:ℕp:Profile 1 (m + 1)μ₀:Matching 1 (m + 1) := { toFun := fun x ↦ (Equiv.symm (p.firmRank 0)) 0, inj' := ⋯ }hμ₀:IsStable p μ₀⊢ numStableMatchings p = 1
apply Fintype.card_eq_one_iff.mpr m:ℕp:Profile 1 (m + 1)μ₀:Matching 1 (m + 1) := { toFun := fun x ↦ (Equiv.symm (p.firmRank 0)) 0, inj' := ⋯ }hμ₀:IsStable p μ₀⊢ ∃ x, ∀ (y : { μ // IsStable p μ }), y = x
refine ⟨⟨μ₀, hμ₀⟩, ?_⟩ m:ℕp:Profile 1 (m + 1)μ₀:Matching 1 (m + 1) := { toFun := fun x ↦ (Equiv.symm (p.firmRank 0)) 0, inj' := ⋯ }hμ₀:IsStable p μ₀⊢ ∀ (y : { μ // IsStable p μ }), y = ⟨μ₀, hμ₀⟩
rintro ⟨μ, hμ⟩ m:ℕp:Profile 1 (m + 1)μ₀:Matching 1 (m + 1) := { toFun := fun x ↦ (Equiv.symm (p.firmRank 0)) 0, inj' := ⋯ }hμ₀:IsStable p μ₀μ:Matching 1 (m + 1)hμ:IsStable p μ⊢ ⟨μ, hμ⟩ = ⟨μ₀, hμ₀⟩
apply Subtype.ext m:ℕp:Profile 1 (m + 1)μ₀:Matching 1 (m + 1) := { toFun := fun x ↦ (Equiv.symm (p.firmRank 0)) 0, inj' := ⋯ }hμ₀:IsStable p μ₀μ:Matching 1 (m + 1)hμ:IsStable p μ⊢ ↑⟨μ, hμ⟩ = ↑⟨μ₀, hμ₀⟩
apply Function.Embedding.ext m:ℕp:Profile 1 (m + 1)μ₀:Matching 1 (m + 1) := { toFun := fun x ↦ (Equiv.symm (p.firmRank 0)) 0, inj' := ⋯ }hμ₀:IsStable p μ₀μ:Matching 1 (m + 1)hμ:IsStable p μ⊢ ∀ (x : Fin 1), ↑⟨μ, hμ⟩ x = ↑⟨μ₀, hμ₀⟩ x
intro i m:ℕp:Profile 1 (m + 1)μ₀:Matching 1 (m + 1) := { toFun := fun x ↦ (Equiv.symm (p.firmRank 0)) 0, inj' := ⋯ }hμ₀:IsStable p μ₀μ:Matching 1 (m + 1)hμ:IsStable p μi:Fin 1⊢ ↑⟨μ, hμ⟩ i = ↑⟨μ₀, hμ₀⟩ i
have hi : i = 0 := Subsingleton.elim _ _ m:ℕp:Profile 1 (m + 1)μ₀:Matching 1 (m + 1) := { toFun := fun x ↦ (Equiv.symm (p.firmRank 0)) 0, inj' := ⋯ }hμ₀:IsStable p μ₀μ:Matching 1 (m + 1)hμ:IsStable p μi:Fin 1hi:i = 0⊢ ↑⟨μ, hμ⟩ i = ↑⟨μ₀, hμ₀⟩ i
subst i m:ℕp:Profile 1 (m + 1)μ₀:Matching 1 (m + 1) := { toFun := fun x ↦ (Equiv.symm (p.firmRank 0)) 0, inj' := ⋯ }hμ₀:IsStable p μ₀μ:Matching 1 (m + 1)hμ:IsStable p μ⊢ ↑⟨μ, hμ⟩ 0 = ↑⟨μ₀, hμ₀⟩ 0
apply (p.firmRank 0).injective m:ℕp:Profile 1 (m + 1)μ₀:Matching 1 (m + 1) := { toFun := fun x ↦ (Equiv.symm (p.firmRank 0)) 0, inj' := ⋯ }hμ₀:IsStable p μ₀μ:Matching 1 (m + 1)hμ:IsStable p μ⊢ (p.firmRank 0) (↑⟨μ, hμ⟩ 0) = (p.firmRank 0) (↑⟨μ₀, hμ₀⟩ 0)
change p.firmRank 0 (μ 0) = p.firmRank 0 ((p.firmRank 0).symm 0) m:ℕp:Profile 1 (m + 1)μ₀:Matching 1 (m + 1) := { toFun := fun x ↦ (Equiv.symm (p.firmRank 0)) 0, inj' := ⋯ }hμ₀:IsStable p μ₀μ:Matching 1 (m + 1)hμ:IsStable p μ⊢ (p.firmRank 0) (μ 0) = (p.firmRank 0) ((Equiv.symm (p.firmRank 0)) 0)
simpa only [Equiv.apply_symm_apply] using (isStable_one_iff p μ).mp hμ All goals completed! 🐙The profile distribution has total mass one, including when one side is empty.
theorem uniformProfile_univ (n m : ℕ) : (uniformProfile n m).toMeasure Set.univ = 1 := by n:ℕm:ℕ⊢ (uniformProfile n m).toMeasure Set.univ = 1
simp All goals completed! 🐙The first moment is one when there is one firm and a nonempty worker side.
theorem expectedNumStableMatchings_one (m : ℕ) : expectedNumStableMatchings 1 (m + 1) = 1 := by m:ℕ⊢ expectedNumStableMatchings 1 (m + 1) = 1
simp [expectedNumStableMatchings, numStableMatchings_one] All goals completed! 🐙The second moment is also one in a nonempty one-firm market.
theorem secondMomentNumStableMatchings_one (m : ℕ) :
secondMomentNumStableMatchings 1 (m + 1) = 1 := by m:ℕ⊢ secondMomentNumStableMatchings 1 (m + 1) = 1
simp [secondMomentNumStableMatchings, numStableMatchings_one] All goals completed! 🐙end StableMarriage.Unbalanced