/-
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.Combinatorics.SimpleGraph.Basic
public import Mathlib.Data.Fin.VecNotation
public import Mathlib.Data.Fintype.Perm
public import Mathlib.Data.Nat.FindRoommates matchings and rank-improvement stability
A matching is an involution: fixed points represent single agents. Acceptability is given by an undirected graph. Rank functions are only compared on acceptable partners and the current assignment, so values on unacceptable partners are immaterial for acceptable matchings.
Reference: A. Fanelli and L. Moscardelli, Approximately Stable Matching, Section 2, https://doi.org/10.3233/FAIA251234.
@[expose] public sectionnamespace RoommatesA possibly partial matching, with fixed points representing single agents.
abbrev Matching (α : Type*) := {μ : Equiv.Perm α // Function.Involutive μ}Matchings form a finite type when the agents do.
instance {α : Type*} [Fintype α] [DecidableEq α] : Fintype (Matching α) := α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq α⊢ Fintype (Matching α)
letI : DecidablePred (fun μ : Equiv.Perm α ↦ Function.Involutive μ) := fun μ ↦ α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αμ:Equiv.Perm α⊢ Decidable ((fun μ ↦ Function.Involutive ⇑μ) μ)
α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αμ:Equiv.Perm α⊢ Decidable ((fun μ ↦ ∀ (x : α), μ (μ x) = x) μ)
All goals completed! 🐙
All goals completed! 🐙The matching in which every agent is single.
def emptyMatching (α : Type*) : Matching α := ⟨Equiv.refl α, fun _ ↦ rfl⟩Every matched pair must be an edge of the acceptability graph.
def IsAcceptable {α : Type*} (G : SimpleGraph α) (μ : Matching α) : Prop :=
∀ i, μ.val i = i ∨ G.Adj i (μ.val i)An acceptable pair blocks when both endpoints strictly prefer it to their assignments.
def IsBlockingPair {α : Type*} (G : SimpleGraph α) (rank : α → α → ℕ)
(μ : Matching α) (i j : α) : Prop :=
G.Adj i j ∧ μ.val i ≠ j ∧ rank i j < rank i (μ.val i) ∧ rank j i < rank j (μ.val j)A stable matching is acceptable and has no blocking pair.
def IsStable {α : Type*} (G : SimpleGraph α) (rank : α → α → ℕ)
(μ : Matching α) : Prop :=
IsAcceptable G μ ∧ ∀ i j, ¬ IsBlockingPair G rank μ i jAn acceptable pair $k$-blocks if both agents gain at least $k$ rank positions.
def IsKBlockingPair {α : Type*} (G : SimpleGraph α) (rank : α → α → ℕ)
(k : ℕ) (μ : Matching α) (i j : α) : Prop :=
G.Adj i j ∧ μ.val i ≠ j ∧
rank i j + k ≤ rank i (μ.val i) ∧ rank j i + k ≤ rank j (μ.val j)A $k$-stable matching is acceptable and has no $k$-blocking pair.
def IsKStable {α : Type*} (G : SimpleGraph α) (rank : α → α → ℕ)
(k : ℕ) (μ : Matching α) : Prop :=
IsAcceptable G μ ∧ ∀ i j, ¬ IsKBlockingPair G rank k μ i jThe matching with all agents single is acceptable.
theorem isAcceptable_emptyMatching {α : Type*} (G : SimpleGraph α) :
IsAcceptable G (emptyMatching α) := fun _ ↦ Or.inl rflImprovement by one position is ordinary strict improvement.
@[simp] theorem isKBlockingPair_one {α : Type*} (G : SimpleGraph α)
(rank : α → α → ℕ) (μ : Matching α) (i j : α) :
IsKBlockingPair G rank 1 μ i j ↔ IsBlockingPair G rank μ i j := α:Type u_1G:SimpleGraph αrank:α → α → ℕμ:Matching αi:αj:α⊢ IsKBlockingPair G rank 1 μ i j ↔ IsBlockingPair G rank μ i j
All goals completed! 🐙One-stability is ordinary stability.
@[simp] theorem isKStable_one {α : Type*} (G : SimpleGraph α)
(rank : α → α → ℕ) (μ : Matching α) :
IsKStable G rank 1 μ ↔ IsStable G rank μ := α:Type u_1G:SimpleGraph αrank:α → α → ℕμ:Matching α⊢ IsKStable G rank 1 μ ↔ IsStable G rank μ
All goals completed! 🐙Complete strict preferences, with the agent's own name ranked last.
structure CompleteProfile (n : ℕ) wherePermutations map candidate labels to zero-based ranks.
rank : Fin n → Equiv.Perm (Fin n)Being single is worse than every other assignment.
self_last : ∀ i, (rank i i).val + 1 = nA complete profile exists at every size, by swapping each agent's own label to last.
def CompleteProfile.canonical (n : ℕ) : CompleteProfile n where
rank i := Equiv.swap i ⟨n - 1, n:ℕi:Fin n⊢ n - 1 < n n:ℕi:Fin nthis:↑i < n⊢ n - 1 < n; All goals completed! 🐙⟩
self_last i := n:ℕi:Fin n⊢ ↑((Equiv.swap i ⟨n - 1, ⋯⟩) i) + 1 = n
n:ℕi:Fin n⊢ n - 1 + 1 = n
n:ℕi:Fin nthis:↑i < n⊢ n - 1 + 1 = n
All goals completed! 🐙One-based ranks, assigning rank $n$ to being single.
def CompleteProfile.partnerRank {n : ℕ} (p : CompleteProfile n) (i j : Fin n) : ℕ :=
(p.rank i j).val + 1Being single has rank equal to the number of agents.
@[simp] theorem CompleteProfile.partnerRank_self {n : ℕ} (p : CompleteProfile n) (i : Fin n) :
p.partnerRank i i = n := p.self_last iAll assigned ranks are at most the number of agents.
theorem CompleteProfile.partnerRank_le {n : ℕ} (p : CompleteProfile n) (i j : Fin n) :
p.partnerRank i j ≤ n := (p.rank i j).isLtA gain of $n$ positions is impossible with one-based ranks in a market of size $n$.
theorem CompleteProfile.not_isKBlockingPair_card {n : ℕ} (p : CompleteProfile n)
(μ : Matching (Fin n)) (i j : Fin n) :
¬ IsKBlockingPair ⊤ p.partnerRank n μ i j := n:ℕp:CompleteProfile nμ:Matching (Fin n)i:Fin nj:Fin n⊢ ¬IsKBlockingPair ⊤ p.partnerRank n μ i j
n:ℕp:CompleteProfile nμ:Matching (Fin n)i:Fin nj:Fin nleft✝¹:⊤.Adj i jleft✝:↑μ i ≠ jhi:p.partnerRank i j + n ≤ p.partnerRank i (↑μ i)right✝:p.partnerRank j i + n ≤ p.partnerRank j (↑μ j)⊢ False
n:ℕp:CompleteProfile nμ:Matching (Fin n)i:Fin nj:Fin nleft✝¹:⊤.Adj i jleft✝:↑μ i ≠ jhi:p.partnerRank i j + n ≤ p.partnerRank i (↑μ i)right✝:p.partnerRank j i + n ≤ p.partnerRank j (↑μ j)hbound:p.partnerRank i (↑μ i) ≤ n⊢ False
n:ℕp:CompleteProfile nμ:Matching (Fin n)i:Fin nj:Fin nleft✝¹:⊤.Adj i jleft✝:↑μ i ≠ jhi:p.partnerRank i j + n ≤ p.partnerRank i (↑μ i)right✝:p.partnerRank j i + n ≤ p.partnerRank j (↑μ j)hbound:p.partnerRank i (↑μ i) ≤ nhpositive:0 < p.partnerRank i j⊢ False
All goals completed! 🐙Every complete preference profile admits a positive stability threshold.
theorem exists_stabilityThreshold (n : ℕ) :
∃ k : ℕ, 0 < k ∧ ∀ p : CompleteProfile n,
∃ μ : Matching (Fin n), IsKStable ⊤ p.partnerRank k μ := n:ℕ⊢ ∃ k, 0 < k ∧ ∀ (p : CompleteProfile n), ∃ μ, IsKStable ⊤ p.partnerRank k μ
n:ℕp:CompleteProfile n⊢ IsKStable ⊤ p.partnerRank (n + 1) (emptyMatching (Fin n))
n:ℕp:CompleteProfile ni:Fin nj:Fin nh:IsKBlockingPair ⊤ p.partnerRank (n + 1) (emptyMatching (Fin n)) i j⊢ False
n:ℕp:CompleteProfile ni:Fin nj:Fin nh:IsKBlockingPair ⊤ p.partnerRank (n + 1) (emptyMatching (Fin n)) i jhbound:p.partnerRank i (↑(emptyMatching (Fin n)) i) ≤ n⊢ False
n:ℕp:CompleteProfile ni:Fin nj:Fin nh:IsKBlockingPair ⊤ p.partnerRank (n + 1) (emptyMatching (Fin n)) i jhbound:p.partnerRank i (↑(emptyMatching (Fin n)) i) ≤ nhpositive:0 < p.partnerRank i j⊢ False
n:ℕp:CompleteProfile ni:Fin nj:Fin nhbound:p.partnerRank i (↑(emptyMatching (Fin n)) i) ≤ nhpositive:0 < p.partnerRank i jleft✝¹:⊤.Adj i jleft✝:↑(emptyMatching (Fin n)) i ≠ jhi:p.partnerRank i j + (n + 1) ≤ p.partnerRank i (↑(emptyMatching (Fin n)) i)right✝:p.partnerRank j i + (n + 1) ≤ p.partnerRank j (↑(emptyMatching (Fin n)) j)⊢ False
All goals completed! 🐙open scoped Classical inThe least positive $k$ for which every complete profile has a $k$-stable matching.
noncomputable def stabilityThreshold (n : ℕ) : ℕ :=
Nat.find (exists_stabilityThreshold n)The threshold is positive and guarantees existence for every complete profile.
theorem stabilityThreshold_spec (n : ℕ) :
0 < stabilityThreshold n ∧ ∀ p : CompleteProfile n,
∃ μ : Matching (Fin n), IsKStable ⊤ p.partnerRank (stabilityThreshold n) μ := n:ℕ⊢ 0 < stabilityThreshold n ∧ ∀ (p : CompleteProfile n), ∃ μ, IsKStable ⊤ p.partnerRank (stabilityThreshold n) μ
classical
All goals completed! 🐙Any positive universal existence bound is at least the threshold.
theorem stabilityThreshold_le {n k : ℕ} (hk : 0 < k)
(h : ∀ p : CompleteProfile n, ∃ μ : Matching (Fin n), IsKStable ⊤ p.partnerRank k μ) :
stabilityThreshold n ≤ k := n:ℕk:ℕhk:0 < kh:∀ (p : CompleteProfile n), ∃ μ, IsKStable ⊤ p.partnerRank k μ⊢ stabilityThreshold n ≤ k
classical
All goals completed! 🐙In a nonempty market, a gain of the full market size is a universal existence bound.
theorem stabilityThreshold_le_card {n : ℕ} (hn : 0 < n) : stabilityThreshold n ≤ n := n:ℕhn:0 < n⊢ stabilityThreshold n ≤ n
n:ℕhn:0 < n⊢ ∀ (p : CompleteProfile n), ∃ μ, IsKStable ⊤ p.partnerRank n μ
n:ℕhn:0 < np:CompleteProfile n⊢ ∃ μ, IsKStable ⊤ p.partnerRank n μ
All goals completed! 🐙A single agent has no possible blocking pair.
theorem stabilityThreshold_one : stabilityThreshold 1 = 1 := ⊢ stabilityThreshold 1 = 1
⊢ stabilityThreshold 1 ≤ 1⊢ 1 ≤ stabilityThreshold 1
⊢ stabilityThreshold 1 ≤ 1 apply stabilityThreshold_le (⊢ 0 < 1 All goals completed! 🐙)
p:CompleteProfile 1⊢ ∃ μ, IsKStable ⊤ p.partnerRank 1 μ
p:CompleteProfile 1⊢ ∀ (i j : Fin 1), ¬IsKBlockingPair ⊤ p.partnerRank 1 (emptyMatching (Fin 1)) i j
p:CompleteProfile 1i:Fin 1j:Fin 1h:IsKBlockingPair ⊤ p.partnerRank 1 (emptyMatching (Fin 1)) i j⊢ False
p:CompleteProfile 1i:Fin 1j:Fin 1h:IsKBlockingPair ⊤ p.partnerRank 1 (emptyMatching (Fin 1)) i jhij:i = j⊢ False
p:CompleteProfile 1i:Fin 1h:IsKBlockingPair ⊤ p.partnerRank 1 (emptyMatching (Fin 1)) i i⊢ False
All goals completed! 🐙
⊢ 1 ≤ stabilityThreshold 1 All goals completed! 🐙Two agents can always be matched to each other.
h₁.refine_2 p:CompleteProfile 2μ:Matching (Fin 2) := ⟨Equiv.swap 0 1, ⋯⟩i:Fin 2j:Fin 2h:IsKBlockingPair ⊤ p.partnerRank 1 μ i jhswap:∀ (i j : Fin 2), i ≠ j → (Equiv.swap 0 1) i = j⊢ False
exact h.2.1 (hswap i j ((SimpleGraph.top_adj _ _).1 h.1)) All goals completed! 🐙
· h₂ ⊢ 1 ≤ stabilityThreshold 2 exact (stabilityThreshold_spec 2).1 All goals completed! 🐙Three agents whose first choices form a directed cycle.
noncomputable def CompleteProfile.cyclicThree : CompleteProfile 3 where
rank := ![Equiv.ofBijective ![2, 0, 1] (by ⊢ Function.Bijective ![2, 0, 1] decide All goals completed! 🐙),
Equiv.ofBijective ![1, 2, 0] (by ⊢ Function.Bijective ![1, 2, 0] decide All goals completed! 🐙),
Equiv.ofBijective ![0, 1, 2] (by ⊢ Function.Bijective ![0, 1, 2] decide All goals completed! 🐙)]
self_last := by ⊢ ∀ (i : Fin 3),
↑((![Equiv.ofBijective ![2, 0, 1] ⋯, Equiv.ofBijective ![1, 2, 0] ⋯, Equiv.ofBijective ![0, 1, 2] ⋯] i) i) + 1 = 3 decide All goals completed! 🐙The cyclic three-agent profile has no stable matching, even when singles are allowed.
theorem CompleteProfile.not_isStable_cyclicThree :
∀ μ : Matching (Fin 3), ¬ IsStable ⊤ CompleteProfile.cyclicThree.partnerRank μ := by ⊢ ∀ (μ : Matching (Fin 3)), ¬IsStable ⊤ cyclicThree.partnerRank μ
unfold IsStable IsAcceptable IsBlockingPair ⊢ ∀ (μ : Matching (Fin 3)),
¬((∀ (i : Fin 3), ↑μ i = i ∨ ⊤.Adj i (↑μ i)) ∧
∀ (i j : Fin 3),
¬(⊤.Adj i j ∧
↑μ i ≠ j ∧
cyclicThree.partnerRank i j < cyclicThree.partnerRank i (↑μ i) ∧
cyclicThree.partnerRank j i < cyclicThree.partnerRank j (↑μ j)))
decide All goals completed! 🐙end Roommates