/- 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.StableMarriage

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

Each 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 m

A 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 k

A 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 j

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

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 All goals completed! 🐙

Every nonempty one-firm market has exactly one stable matching.

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 μ₀⊢ ∃ x, ∀ (y : { μ // IsStable p μ }), y = x 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μ₀⟩ 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μ₀⟩ 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μ₀⟩ 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 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 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 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 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) 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) 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 := n:ℕm:ℕ⊢ (uniformProfile n m).toMeasure Set.univ = 1 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 := m:ℕ⊢ expectedNumStableMatchings 1 (m + 1) = 1 All goals completed! 🐙

The second moment is also one in a nonempty one-firm market.

theorem secondMomentNumStableMatchings_one (m : ℕ) : secondMomentNumStableMatchings 1 (m + 1) = 1 := m:ℕ⊢ secondMomentNumStableMatchings 1 (m + 1) = 1 All goals completed! 🐙end StableMarriage.Unbalanced