安定結婚問題アルゴリズムの概要と実装例及び適用例

life tips & 雑記 旅と歴史 禅とライフティップ 経済とビジネス 本ブログのナビ 人工知能技術 デジタルトランスフォーメーション 深層学習技術 機械学習技術

安定結婚問題アルゴリズムについて

安定結婚問題（Stable Marriage Problem, SMP）アルゴリズムは、2つのグループ間での「安定したマッチング」を実現するための問題と解法の一種となる。この問題の最も有名な解法として「ゲイル＝シャプレー・アルゴリズム（Gale–Shapley Algorithm）」があり、安定した組み合わせを効率よく見つけることが可能で、このアルゴリズムは特に、医学生と病院のマッチング、求職者と企業のマッチングなど、現実の多くのマッチング問題に応用されるものとなる。

安定結婚問題は、以下の条件を満たすマッチングを見つけることを目的としている。

1. 2つのグループ（男女や2種類の候補者）があり、各メンバーは異性のメンバーに対する好みの順序を持っている。
2. マッチングは「安定」でなければならない。ここで「安定」とは、ある2人のペアが、現在のペアリングよりもお互いを好むことがない状態（このようなペアが存在すると「不安定なマッチング」となる）を指す。

ゲイル＝シャプレー・アルゴリズムは、以下のような手順で安定したマッチングを求めるものとなる。アルゴリズムは「求婚側」と「選択側」に分かれ、求婚側がアクティブにプロポーズ（申請）を行い、選択側がそれを受け入れるかどうかを決定する。

1. 初期設定： 各メンバーは、異性のメンバーに対する好みのリストを持ち、すべてのペアリングは未確定。

2. 求婚と暫定マッチングの構築： 求婚側のメンバー（例：男性）が、好みのリストの一番上にいる選択側（例：女性）にプロポーズをして、選択側は、プロポーズを受けた場合に次のルールで行動する。

• もしまだペアリングがない場合、そのプロポーズを一時的に受け入れる（暫定的なマッチング）。
• 既に他の人と暫定的なペアリングをしている場合、現在の暫定ペアと新しいプロポーズを比較し、好みが高い方を残す。好みが低い方は拒否される。

3. リジェクトされた場合のリトライ： 求婚側のメンバーがプロポーズを拒否された場合、そのメンバーはリストの次の選択肢へ進み、再度プロポーズを行い、この手順を繰り返すことで、最終的に安定したペアリングができるまで続ける。

4. 安定マッチングの完成： すべてのメンバーがペアリングされ、もはや新たに生じるペアがない場合、安定マッチングが成立する。

このようなアルゴリズムは以下のようなケースに適用される。

男性の好みリスト：
– 男性A: 女性X > 女性Y > 女性Z
– 男性B: 女性Y > 女性X > 女性Z
– 男性C: 女性X > 女性Z > 女性Y

女性の好みリスト：
– 女性X: 男性B > 男性A > 男性C
– 女性Y: 男性A > 男性B > 男性C
– 女性Z: 男性A > 男性B > 男性C

上記の場合、アルゴリズムが進むにつれて、最終的にすべてのメンバーが安定したペアを形成するようになる。

ゲイル＝シャプレー・アルゴリズムの特徴と特性としては以下が挙げられる。

• 安定性の保証：ゲイル＝シャプレー・アルゴリズムは常に安定なマッチングを提供し、これにより不安定な組み合わせが生じることはない。
• 求婚側に有利な結果：このアルゴリズムは、プロポーズを行う側（求婚側）に有利な安定マッチングを生成することが知られている。
• 効率性：計算効率も高く、求婚・選択の手順を繰り返していくことで、比較的短時間で安定したマッチングが得られる。

このアルゴリズムにより、双方が納得しやすいマッチングを効率的に実現できるため、社会全体の効用を高める効果が期待できる。

実装例

以下にゲイル＝シャプレー・アルゴリズム（安定結婚問題アルゴリズム）のPythonによる実装例を示す。このコードでは、男性が求婚側で、女性が選択側として設定されており、男性の好みリストと女性の好みリストを使って、安定したペアを作成している。

def stable_marriage(men_preferences, women_preferences):
    # 男性・女性の数
    num_men = len(men_preferences)
    
    # 全員がマッチングされるまで続ける
    free_men = list(range(num_men))  # マッチングが確定していない男性のリスト
    engaged_to = [None] * num_men     # 女性が誰と婚約しているかを保持するリスト
    proposals = [[False] * num_men for _ in range(num_men)]  # 提案済みかどうか
    
    # 女性の好みを辞書形式にして高速にアクセスできるようにする
    women_rank = [
        {man: rank for rank, man in enumerate(preferences)}
        for preferences in women_preferences
    ]
    
    # マッチングの過程
    while free_men:
        man = free_men[0]  # フリーの男性を一人選ぶ
        man_pref = men_preferences[man]
        
        # 提案可能な女性に順番にプロポーズ
        for woman in man_pref:
            if not proposals[man][woman]:  # まだプロポーズしていない女性に対して
                proposals[man][woman] = True  # プロポーズ済みと記録
                
                if engaged_to[woman] is None:
                    # 女性がフリーなら婚約
                    engaged_to[woman] = man
                    free_men.pop(0)  # フリーの男性リストから外す
                    break
                else:
                    # 婚約済みの場合、より好みの男性かを比較
                    current_partner = engaged_to[woman]
                    if women_rank[woman][man] < women_rank[woman][current_partner]: # 女性が新しい男性を好むなら婚約を更新 
                    engaged_to[woman] = man free_men.pop(0) free_men.append(current_partner) # 元の婚約者をフリーに 
                    break # 最終的なマッチング結果 
                    matches = [(man, woman) for woman, man in enumerate(engaged_to)] return matches # 好みのリスト（例） 
                    men_preferences = [ [0, 1, 2], # 男性0の好み（女性0 > 女性1 > 女性2）
                    [1, 0, 2],  # 男性1の好み
                    [1, 2, 0]   # 男性2の好み
]

women_preferences = [
    [2, 0, 1],  # 女性0の好み（男性2 > 男性0 > 男性1）
    [0, 1, 2],  # 女性1の好み
    [1, 2, 0]   # 女性2の好み
]

# 実行
result = stable_marriage(men_preferences, women_preferences)
for man, woman in result:
    print(f"Man {man} is matched with Woman {woman}")

コードの解説:

1. 初期設定：
   • free_men：フリーな男性のリストです。男性がマッチングされるまで保持される。
   • engaged_to：女性が誰と婚約しているかを記録する。Noneの場合、その女性はまだ婚約していないことを示す。
   • proposals：男性が既に提案した女性を追跡するためのリストとなる。
2. メインループ：
   • すべての男性が婚約するまで、フリーの男性を選び、好みの順に女性にプロポーズする。
   • 女性がフリーの場合、プロポーズした男性と婚約する。
   • すでに婚約中の場合は、現在の婚約者と新たにプロポーズしてきた男性の好みを比較し、より好みの男性を選びます。元の婚約者は再びフリーになる。
3. 最終的なマッチング結果の表示：
   • すべてのペアが安定なマッチングに達したとき、matchesリストに結果が保存される。

実行結果例: 上記のコードを実行すると、以下が出力される。

Man 0 is matched with Woman 0
Man 1 is matched with Woman 1
Man 2 is matched with Woman 2

適用事例

安定結婚問題とゲイル＝シャプレー・アルゴリズムは、複数の意思決定主体が存在する現実のさまざまな分野で活用されている。代表的な適用事例を以下に示す。

1. 医学生と病院のマッチング（レジデントマッチング）:
– 概要：医学生が卒業後にレジデント（研修医）として働く病院を選ぶ際、医学生の希望と病院の受け入れ希望を安定的にマッチングさせる問題。
– 使用されている国：アメリカ合衆国、カナダ、日本などでは、毎年このアルゴリズムを利用したマッチングシステムが運用されている。
– 効果：医学生と病院の双方の希望を踏まえた最適な配置が実現し、病院の質の向上や医学生の満足度向上に寄与している。

2. 求職者と企業のマッチング:
– 概要：企業が求めるスキルや適性を持った求職者と、求職者の希望条件を安定してマッチングさせる問題。
– 使用例：新卒採用、インターンシップなどで候補者と企業のマッチングに用いられる。
– 効果：求職者と企業のマッチングを安定化させ、離職率の低下や人材の最適配置を促進できる。

3. スクール・チョイス・プログラム（学校選択制度）:
– 概要：保護者と学生の希望に基づいて学校に割り当てる問題。都市部などで、希望者が集中する学校に対して、すべての生徒が希望に沿うように配置されるのは難しい。
– 使用されている都市：ボストン、ニューヨーク、デンバーなどの都市で、学校選択制度に導入されている。
– 効果：親と学生の希望に基づき、学校への安定した配属を実現し、満足度の向上に貢献している。

4. 臓器移植ネットワーク:
– 概要：臓器移植では、患者の待機リストと臓器提供者のリストを安定的にマッチングさせる必要がある。特に腎臓などのペアドネーション（親族間などでの移植希望）が関連する場合に、安定したマッチングが求められている。
– 効果：臓器提供者と患者のマッチングが効率化され、より多くの患者がタイムリーに適合する臓器を受けられるようになる。

5. シェアハウス・ルームメイトのマッチング:
– 概要：学生や若年層を中心に、ルームメイトの選択にゲイル＝シャプレー・アルゴリズムを使う例もある。好みやライフスタイルに基づき安定したマッチングが可能となる。
– 効果：互いに好ましいと思う人と住むことで、長期的なルームシェアが可能になる。

6. オンラインデーティングとマッチングアプリ:
– 概要：デーティングアプリなどで、ユーザーの好みや関心を考慮して、マッチングの安定化が試みられている。
– 効果：ユーザー同士の好みを考慮した「安定」した組み合わせが可能になり、相性の良いカップルの成立が促進される。

7. ペアプログラミングやチームビルディング:
– 概要：企業や学校などで、プロジェクトやペアプログラミングに適したパートナーを選ぶ際に、このアルゴリズムが活用されている。
– 効果：互いに相性が良いと判断されるペアができることで、チームのパフォーマンスが向上し、協働作業の効率も上がる。

8. 婚活・マッチングサービス:
– 概要：マッチングサービスの分野でも、ユーザーの好みを反映させてマッチングの安定性を実現するために、安定結婚問題アルゴリズムが活用されている。
– 効果：お互いに好感を持てる安定したマッチングが可能になり、成婚率の向上が期待できる。

ゲイル＝シャプレー・アルゴリズムを用いると、互いの好みを尊重した安定したマッチングが可能になるため、マッチング結果に対する当事者の満足度が向上する。また、各主体がリソースの最適利用を実現でき、全体として社会的効率が高まることが期待される。

参考図書

安定結婚問題アルゴリズムやマッチング理論に関連する参考図書について述べる。

1. Best Matching Theory & Applications

2. Algorithm Design Manual

3. Introduction to Algorithms

4. Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis

Chinoba

Chinoba

Intelligence as Relationship

Research Platform

founded by

Masao Watanabe

AI Systems Architecture
Decision Trace
Human–AI Coordination
Algorithmic Governance