Gale-Shapleyアルゴリズム

　最近、安定結婚問題に基づいてパートナーを決める出会い系アプリに関する記事を読みました。安定結婚問題を解くGale-Shapleyアルゴリズムが面白そうだったので勉強してみました。

安定結婚問題とは?

N人の男とN人の女がいる。N組のカップルを作りたい。
ただし、駆け落ちする人が現れないようにカップルを作りたい。

「駆け落ち」が起こりえる条件は、

1. 自分のパートナーよりも、好きな人（A）が別にいる
2. Aさんも、Aさん自身のパートナーより自分のことを好きでいてくれる

である。

Gale-Shapleyアルゴリズムとは?

安定結婚問題を解くためのアルゴリズムで、以下のような手続きをパートナーのいない男がいなくなるまで繰り返します。

1. パートナーがいない男（X）は、まだプロポーズをしたことのない相手の中で一番好きな人にプロポーズをする。
2. プロポーズされた女は、
1. フリーの場合、そのプロポーズを受け入れる。
2. すでに婚約中の場合、
1. 今の婚約相手よりもXの方が魅力的であれば、今の婚約相手を振って、Xのプロポーズを受け入れる。
2. Xよりも今の婚約相手の方が魅力的であれば、Xのプロポーズを断る。

このアルゴリズムが本当に正しく動作するのか考えてみました。

ーまず、このアルゴリズムは停止するのか？

アルゴリズムは、パートナーがいない男が存在する間は停止しない。パートナーという関係は男集合から女集合へのbijectiveな写像なので、「パートナーがいない男が存在する」と「パートナーがいない女が存在する」は同値。

女は、一度でもプロポーズされると、それ以降はうまく男をキープすることで常にパートナーのいる状態を継続できる。よって、すべての女が一度でもプロポーズをされたことがある状態になるとこのアルゴリズムは停止する。

男はN人いて、それぞれの男には１位からN位まで女をランク付けしたリストがあり、それにしたがってプロポーズしていくので、プロポーズという行為が全体でN * N回行われた時点でアルゴリズムは停止する。

よって計算量はO(N²)。

ーアルゴリズムが停止したときのマッチングには、ブロッキングペア（駆け落ちが発生するようなペア）が存在しないか？

m1はf1よりf2の方が好き、かつ、f2はm2よりm1の方が好きであるにも関わらず、アルゴリズムが停止したとき、(m1, f1)、(m2, f2)というペアがえられたと仮定する。

しかしこの場合、m1はf1にプロポーズする前にf2にプロポーズしているはずで、f2はそのプロポーズを受け入れているはずである。よってそのようなペアは存在しない。

ソースコード

C++で書いたソースコードを貼りつけておきます。Gale-Shapleyアルゴリズムの処理は関数process()で行なっています。

#include <iostream>
#include <vector>
#include <queue>
#include <cassert>

using namespace std;

const int N = 100;

int male[N][N];    // j-th favorite of i-th male is male[i][j]
int female[N][N];  // j-th favorite of i-th female is female[i][j]

int rmale[N][N];   // for i-th male, j-th female is rmale[i][j]-th place
int rfemale[N][N]; // for i-th female, j-th male is rfemale[i][j]-th place

int match[N];      // i-th female is engaged to match[i]-th male

void read() {

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> male[i][j];
            rmale[i][male[i][j]] = j;
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> female[i][j];
            rfemale[i][female[i][j]] = j;
        }
    }

}

void process() {

    fill(match, match + N, -1);

    queue<pair<int, int> > q;
    
    for (int i = 0; i < N; i++) {
        // i-th male is trying to propose his first favorite
        q.push(make_pair(i, 0));
    }
    
    while (!q.empty()) {
        int m = q.front().first;
        int order = q.front().second;
        q.pop();

        int f = male[m][order];

        // The proposed female is free.
        if (match[f] == -1) {
            match[f] = m;
        } 
        // The proposed female is engaged but switches over to him.
        else if (rfemale[f][m] < rfemale[f][match[f]]) {
            int dumped = match[f];
            match[f] = m;
            q.push(make_pair(dumped, rmale[dumped][f] + 1));
        } 
        // The proposed female is engaged and rejects him.
        else {
            q.push(make_pair(m, order + 1));
        }
    }

}

void write() {

    for (int i = 0; i < N; i++) {
        cout << i << " th female is engaged to " << match[i] << " th male." << endl;
    }

}

void check() {

    for (int f1 = 0; f1 < N; f1++) {

        int m1 = match[f1];

        for (int f2 = 0; f2 < N; f2++) {

            if (f1 == f2)
                continue;

            int m2 = match[f2];

            // m1 won't elope with another female.
            assert(rmale[m1][f1] < rmale[m1][f2] || rfemale[f2][m2] < rfemale[f2][m1]);

            // f1 won't elope with another male.
            assert(rfemale[f1][m1] < rfemale[f1][m2] || rmale[m2][f2] < rmale[m2][f1]);
            
        }
    }

}

int main(int argc, char **argv) {

    read();

    process();

    write();
    
    check();
    
    return 0;
}