安定マッチングの問題

問題の説明

適齢期の男女が何人かいる。おのおの、異性の希望リストを持っている（すみません、ここでは簡単のためこのように仮定しています。政治的により正しい問題設定については、各自考えてください）。リスト上位から順にプロポーズし、プロポーズされた側は自分の希望リストに相手が載っていれば受諾する。すでに受諾している場合は、二人のうち自分の希望リストでより上位の人を選び、下位の人への受諾は破棄する。破棄された人は、自分のリストで次点の人にプロポーズする。これを延々と続けていれば、全員が納得するマッチング（縁結びの組合せ）に到達する。

このアルゴリズムで得られるマッチングは、男女どちら側がプロポーズするかに依存して変わり得る。しかし、得られるどのマッチングも、不倫が生じ得る状態（今のパートナーより望ましい人が、その人の今のパートナーより自分を望ましいと思うこと）が存在しないという意味で、安定（stable）である。

このようなマッチングを見つける問題を「安定な結婚の問題」（「安定結婚問題」、stable marriage problem）という。

上の問題は一対一のマッチングであったが、入学・入社など一対多のマッチングを考えることもできる。入学の問題では、受験生がおのおの入学したい順に並べた学校リストを持っており、学校側もおのおの取りたい受験生の順序を持っているが、学校ごとに定員がある。こちらは「大学入学」（college admissions）あるいは「研修医配属」（resident matching）の問題などと呼ばれる。

これらの問題で安定なマッチングを求める方法は、David Gale と Lloyd S. Shapley による1962年の論文 College Admissions and the Stability of Marriage で初めて扱われたので、Gale-Shapley アルゴリズム（GSアルゴリズム）と呼ばれる。その仕組みから、受け入れ保留（Deferred Acceptance、DA）アルゴリズムとも呼ばれる。Shapley は Alvin E. Roth とともに2012年のノーベル経済学賞を受賞した。Gale は2008年に他界したのでノーベル賞を逃した。

日本語では例えば坂井豊貴『マーケットデザイン』（ちくま新書、2013年）の第2章で平易に解説されている。宮崎修一『安定マッチングの数理とアルゴリズム』（現代数学社、2018年）は力作である。拙著『［改訂新版］C言語による標準アルゴリズム事典』にもC言語のプログラムがある。

一対一のアルゴリズム

男女をそれぞれ A、B で表し、それぞれのメンバーに 1, 2, 3, … と番号を振る。Python のリストの添字は 0 から始まるので、添字の混乱を避けるために 0 番の要素はダミーの空リスト [] にして、ここでは希望リストを例えば次のように書くことにする（坂井 p.103 の例）。希望リストは左ほど好ましい。

A = [[],         # ダミー
     [1, 2, 4],  # 男1の希望リスト
     [2, 3, 1],  # 男2の希望リスト
     [1, 4]]     # 男3の希望リスト

B = [[],         # ダミー
     [3, 2, 1],  # 女1の希望リスト
     [3, 1, 2],  # 女2の希望リスト
     [3, 1],     # 女3の希望リスト
     [1, 2]]     # 女4の希望リスト

A[i] は i 番の男の希望リスト、B[j] は j 番の女の希望リストである。男1の第1〜3候補はそれぞれ女1・2・4で、女3には興味がないようだ。したがって男1はまず女1にプロポーズするが、女1の候補は男3・2・1の順なので、男1は最も優先順位が低いが、とりあえず受諾する。続いて男2は女2にプロポーズし、受諾される。さらに続いて男3は女1にプロポーズするが、女1はすでに男1を受諾している。しかし、女1の希望リストでは男3のほうが上位なので、女1は男1を捨てて男3を選ぶ。捨てられた男1は次点の女2にプロポーズし、女2は男2を捨てて男1を選ぶ。以下延々と続く。

この手順は Python で次のように表される。b[j] はその時点での女 j の受諾した男の番号であり、最初すべて 0 に初期化しておく。b[0] はダミーである。

b = [0] * len(B)
for i in range(1, len(A)):
    while A[i]:
        j = A[i].pop(0)
        if i in B[j] and (b[j] == 0 or B[j].index(i) < B[j].index(b[j])):
            b[j], i = i, b[j]
            print(b[1:])  # 途中の様子を表示

最後に表示される b[1:] が女の側の結果である。0 は相手が見つからない状態を表す。男の側を求めるには次のようにする：

a = [0] * len(A)
for j, i in enumerate(b):
    a[i] = j
print(a[1:])

このような男性プロポーズのGAアルゴリズムは、男性を並べる順序によらず、男性側に有利な（男性最適）安定マッチングを一意に与える。男性は戦略的に希望リストを偽っても得をしない。

なお、上のコードは A の要素であるリストを改変する。もし A を残しておきたいなら、浅いコピー Acopy = A.copy() では駄目で、import copy してから Acopy = copy.deepcopy(A) で深いコピーをしておく必要がある。

一対多のアルゴリズム

一対多の場合も本質的に同じである。次は宮崎 p.120 の例である。6人の研修医が3つの病院に配属する。研修医1は病院1しか希望していない。研修医2は病院1と3をこの順に希望する。などなど。逆に、病院1は研修医5, 3, 2, 6, 4をこの順に希望する。なお、病院1は2人、病院2は1人、病院3は4人しか受け入れられない。

A = [[],
     [1],
     [1, 3],
     [2, 1, 3],
     [1, 2, 3],
     [3, 2, 1],
     [1, 2, 3]]

B = [[],
     [5, 3, 2, 6, 4],
     [2, 6, 3, 5],
     [2, 1, 3, 6, 4, 5]]

quota = [0, 2, 1, 4]  # 定員 2, 1, 4

アルゴリズムは次の通り。

b = [[0] * n for n in quota] # [[], [0,0], [0], [0,0,0,0]]

for i in range(1, len(A)):
    while A[i]:
        j = A[i].pop(0)
        if i in B[j]:
            if 0 in b[j]:
                b[j][b[j].index(0)] = i
                i = 0
            else:
                k = max(range(len(b[j])), key=lambda x: B[j].index(b[j][x]))
                if B[j].index(i) < B[j].index(b[j][k]):
                    b[j][k], i = i, b[j][k]
            print(b[1:])  # 途中の状態を表示

これで b[1:] に病院の埋まり具合が表示される。各研修医の配属先 a[1:] は次のようにして求められる。いずれも 0 は空き（未配属）である。

a = [0] * len(A)
for j, i in enumerate(b):
    for k in i:
        a[k] = j
print(a[1:])

上のアルゴリズムは、研修医を並べる順序によらず、（病院側ではなく）研修医側に有利な安定マッチングを一意に与える。研修医は戦略的に希望リストを偽っても得をしない。

蛇足

「捨てる神あれば拾う神あり」をうまく利用して全員が得をするマッチングを見つけるのがGAアルゴリズムである。しかし、学生のゼミ（あるいはコース）への振り分けは、どのゼミも同じ基準（学生の成績）で判断することが多い。その場合、（学生側からプロポーズする、学生最適な）GSアルゴリズムは、単に学生を成績順に並べて、上から順に第一希望に割り振り、第1希望が定員に達したら第2希望、それも定員に達したら第3希望という具合に埋めていく通常の方式に帰着する。学生が戦略的に希望リストを偽って得をすることはできない。正直に自分の希望を並べるのがベストである。

新型コロナワクチンWeb予約抽選申込フォームについてという記事に次のような例題がある。6人の接種希望対象者がいる。元記事ではA〜Fだがここでは1〜6とした。これらにランダムに順位を付ける。横軸1〜10は元記事では会場1〜5の午前・午後であったが、ここでは時刻スロットとし、1スロット1人しか入らないとする。

これを安定結婚問題と考えれば、データは次のようになる：

A = [[],
     [1, 3, 5, 7, 9],
     [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
     [2, 4, 5, 6, 7, 8, 9],
     [1, 6],
     [3],
     [6, 8]]

B = [[]] + [[5, 6, 1, 2, 4, 3]] * 10

これを解けば、6人の接種スロット a[1:] は [1, 2, 4, 0, 3, 6] となる。図で表せば次の通りである：

対象者4は接種を受けることができない。でも、ちょっと考えれば、例えば対象者6をスロット8に移動すれば、対象者4はスロット6で接種を受けられる。しかしこれは「安定」ではない。もしこれが学生のゼミ配属の問題なら、学生6は第1希望のゼミ6に入りたいし、ゼミ6の教員は成績の高い学生6のほうを取りたいであろう。成績が低いのに希望ゼミを2つしか挙げなかった学生4が悪いのである。

でも、もともとの接種の問題では、「順位」は市が便宜上ランダムに振ったものである。どのスロットも同じ順位にする理由はない。順位をスロットごとにランダムにしたらどうだろう？

B = [[]]
for i in range(10):
    B.append(random.sample(range(1, len(A)), len(A) - 1))

やってみると、全員が接種を受けられることもあれば、そうでないこともある。乱数で何回かやってみて、できるだけ多くの人が接種を受けられるようなマッチングを選べばどうだろう。もっとも、これは単なる説明のための例題で、実際にはこのようなことは生じないのかもしれない。

奥村 晴彦

Last modified: 2022-06-04 20:21:00 JST