【結婚問題】ホールの定理 / 絶望の定理

はじめに

この記事は、NRI OpenStandia Advent Calendar 2023の24日目（シリーズ２）です。
2023年も終わりが近づき、「忘年会や年末年始で人と会う機会が増え、何か会話のネタがないかな？」と思っている方も多いのではないでしょうか。

そこで、ホールの定理と絶望の定理という、結婚問題（マッチング）に関する2つの興味深い定理について紹介したいと思います。

これらの定理は、既に詳細に解説した記事や動画がありますが、本記事では改めて紹介し、2つの定理の違いについても説明していきます。

結婚問題とは

グラフ理論における結婚問題とは、$n$人の男性と$k$人の女性がいる状況において、結婚のペアを求める問題になります。

特に、各個人が異性に対して結婚（マッチ）したい希望順位リストを持っている場合、その希望リストを満たすような結婚のペアを考えます。

希望リストがあるとき、

• 男性と女性のどちらか一方の集団のみの希望リストを考慮する場合
• 両方の集団の希望リストを考慮する場合

の2パターンに分けて考えます。
特に後者のパターンを考慮する結婚問題は、安定結婚問題と呼ばれています。

ホールの定理は、男性と女性のどちらか一方の集団のみの希望リストを考慮する場合の結婚問題に適用される定理です。
一方、絶望の定理は、両方の集団の希望リストを考慮する場合の結婚問題に適用される定理です。

ホールの定理とは

ここでは、女性の希望リストのみを考慮する場合の結婚問題を扱います。
すなわち、結婚問題を全ての女性が希望相手と結婚することが可能か、と定義します。
ただし、男女は1対1でペアになるものとします。

ホールの定理とは、
「結婚問題に解があるための必要十分条件は、どの$i$人の女性も、男性の希望リストの合計が$i$人以上であることである」
という定理です。ただし、$i$は女性の人数$k$に対して、$1 \leqq i \leqq k$ を満たすとします。

上記だけではイメージしにくいと思いますので、具体的な状況を考えてみましょう。
男女がそれぞれ4人ずついるお見合い所を例にとって説明します。
以下の図では、具体的な結婚希望リストの例と対応する矢印を表しています。

ここで、女性の集合を$W$、男性の集合を$M$と表します。
そして、集合$W$の部分集合を$W'$、集合$W'$内の女性の希望相手の集合を$N(W')$とします。

例えば、$W' = \lbrace a, d \rbrace $の場合を図示してみると以下のようになります。

このとき、$i = |W'| = 2$ 人の女性に対して、男性の希望リストの合計は$|N(W')| = 3$ 人です。

ここで先ほどの、どのi人の女性も、男性の希望リストの合計がi人以上であることという文を、集合$W'$と$N(W')$を使って定式化すると、

|W'| \leq |N(W')|   \tag{1}

であり、上記の例は式(1)を満たしていることがわかります。

このように、ホールの定理を集合記号を用いて表現すると、
「全ての部分集合$W'$の女性に対して、$|W'| \leq |N(W')|$ が成り立つ場合ことと、全ての女性が希望相手と結婚できるマッチングが存在することは同値である」
です。

ホールの定理を用いると、$|W'| \leq |N(W')|$ が成り立たない例を一つでも見つけることができれば、希望のマッチングは存在しないと言うことができます。

例えば、先程とは異なる女性の希望リストにおいて、以下の部分集合を考えてみます。

$|W'| = 2$、$|N(W')| = 3$となり、$|W'| > |N(W')|$となってしまうため、この希望リストでは、全ての女性が希望相手と結婚できないと言えます。

直感的には、特定の男性に人気が集中してしまい、全ての女性が幸せになれない状況である、と言えます。悲しいことですね。。。

安定結婚問題とは

ここでは、男女両方の希望リストを考慮する場合の結婚問題を扱います。
ただし、男女は1対1でペアになるものとします。
また、ペアができない人間の存在を許容します。

$n$人の男性と$k$人の女性がいる状況を考えます。各個人が「それほど不満はない」と思うような結婚のペアを求めることが、ゴールになります。
（今回の安定結婚問題では、全員がマッチしなくても良いケースを考えており、オリジナルの安定結婚問題とは少し異なります）

ここで、「それほど不満はない」状況とは「駆け落ちするペアが発生しない」状況であると考えます。
「駆け落ちするペア」とは、

• 男性Aは女性aと現在結婚しているが、女性bの方が好き
• 女性bは男性Bと現在結婚しているが、男性Aの方が好き

という状況の時、男性Aと女性bがそれぞれ現在のパートナーと別れ、新たに結婚してしまうペアのことを指します。ブロッキングペアとも言います。

駆け落ちするペアが存在しないようなマッチングのことを安定マッチング¹と言います。

したがって、安定結婚問題は安定マッチング問題と言い換えることができます。
安定マッチング問題は、DAアルゴリズム（受入保留アルゴリズム、別名Gale-Shapleyアルゴリズム）によって解くことができます。アルゴリズムの説明は省略します。

以下で用語の整理をします。

• マッチング：2部グラフの全てのエッジが同じ集合内に存在しないグラフ。ここでは、2部グラフは男女それぞれの集合であり、エッジは結婚ペアを指す。ここでのマッチングとは同性内でペアがないことを指す。

絶望の定理とは

ここでは、男女両方の希望リストを考慮する場合、すなわち安定結婚問題を扱います。

絶望の定理とは、
「ある安定マッチングに入れなかった人はどの安定マッチングにも入れない」
という定理です。

つまり、ある結婚ペアの決め方でペアが作れなかった人は、どのペアの組み合わせでもペアになれないという定理です。悲しい。。。

では、具体的な状況を考えてみましょう。
先程と同様に男女がそれぞれ4人ずついるお見合い所を例にとって説明します。
以下の図では、具体的な結婚希望リストの例を表しています。

この希望リストを全て満たすような結婚ペアを決めることを考えます。

以下の図では、希望リストを満たす結婚ペアを適当に決めてみました。
緑実線が今回決めた結婚ペアです。

ここで、女性cと男性Bに注目してください。
女性cは男性Dとペアになっていますが、女性cの希望リストは男性 [A > B > D] のため、男性Bの方が順位が高いです。
また、男性Bは女性dとペアになっていますが、男性Bの希望リストは女性 [c > d] のため、女性cの方が順位が高いです。
つまり、女性cと男性Bはともに現在の結婚ペアよりもお互いに対する希望順位が高いため、駆け落ちペアであることが分かります。

以下の図では、駆け落ち後の結婚ペア状態を示しています。

他の男女間では駆け落ちペアが存在しないことから、女性cと男性Bの駆け落ちによって、安定マッチングへ遷移しています。

結果として、女性dと男性Dは安定マッチングに入ることができませんでした。
よって絶望の定理より、「女性dと男性Dはいかなる安定マッチングでも希望の相手と結婚できない」ということが言えます。

このように、ある人がある安定マッチングに入れなかった場合、任意の安定マッチングに入れないという、絶望的な結果を示す定理のため、絶望の定理と呼ばれているのだと思います。（名前の由来はあくまで推測です）

ちなみに、この定理の正式名称は Rural Hospital Theorem （僻地病院の定理）です。
男性 - 女性の結婚マッチングではなく、医者 - 僻地病院の配属マッチングでモデル化しています。

ホールの定理と絶望の定理の違い

ホールの定理

女性から男性（またはその逆）への希望リストのみを考慮している結婚問題に対する定理であり、安定マッチングの概念は存在しません。言い換えると、ホールの定理はある集合$V_1$からある集合$V_2$への完全マッチングに関する定理です。

絶望の定理

女性から男性、男性から女性への両方の希望リストを考慮している安定結婚問題に対する定理であり、安定マッチングの概念が存在します。言い換えると、絶望の定理はある集合$V_1$とある集合$V_2$の安定マッチングに関する定理です。

つまり、ホールの定理と絶望の定理では、結婚問題の中でも前提とする状況がそれぞれ異なります。

応用例

ホールの定理

• トランプのカード52枚を4枚ずつ13個のグループへ任意に分けた時、各グループから1枚ずつカードをうまく選ぶと、A,2,3,4,5,6,7,8,9,10,J,Q,Kを1枚ずつ取り出せる。
  Hallの定理とその応用

• 合コン中のトイレ休憩時等に行われる作戦会議（好みが相手が被らないかの相談）

絶望の定理

絶望の定理自体というよりは、この定理が扱われる安定結婚問題の応用例について紹介します。

• 研修医の病院への配属
• 公立学校の選択制度
• 大学の研究室配属
• 資源配分問題

安定結婚問題は、2部グラフの双方向の希望リストを考慮するマッチングため、複雑なマッチング問題です。そのため、DAアルゴリズムなどの導入によるペアの改善により、マッチ率や参加者の満足度向上が示されています。

最後に

結婚問題のホールの定理、および安定結婚問題の絶望の定理について紹介しました。

この記事を通して、結婚問題などを扱うグラフ理論に興味を持たれる方が増えると良いなと思います。

最後まで読んでいただきありがとうございました。
ご質問やご指摘等ありましたらコメントまでお願いいたします。

参考文献

• 必見！？ホールの結婚定理！～結婚できるとは言っていない～
• グラフ理論⑥(ホールの結婚定理)
• 安定結婚問題「絶望の定理」の紹介
• 安定マッチングとGale-Shapleyアルゴリズム
• 1対1のマッチング問題における絶望の定理（僻地病院の定理）
• みんなHappy!? マッチングの数理と計算
• Hallの定理とその応用

1. GaleとShapleyが提案したオリジナルの安定結婚問題における安定マッチングは、駆け落ちするペアが存在しないような完全マッチングを指します。言い換えると、ブロッキングペアが存在せず、全員が個人合理性を満たすマッチングを安定マッチングと定義します。個人合理性を満たすマッチングとは、男女全員が希望リスト内の相手と結婚しているマッチングを指します。つまり、全員が必ずペアになっている状況を考えるため、絶望の定理は成り立ちません。 ↩