Python上でのGale-Shapleyアルゴリズムの実行 #アルゴリズム

この記事を理解すると嬉しいこと

我々の日常生活ではたびたびマッチング問題で扱われるようなシチュエーションが実際に起きる。様々なマッチング問題に対しては、過去にも（ Kleinberg, Jon, and Eva Tardos. Algorithm design. Pearson Education India, 2006.）であるように、詳細な議論が為されてきている。GSアルゴリズムは、そんなアルゴリズムの中でも代表格である。我々が日常生活で直面する結婚や大学の選択などの具体的なシチュエーションにおいて、互いに選好順序が存在する場合でも、効率的かつ公平なマッチングを実現するアルゴリズムである。このアルゴリズムを理解することで、社会で活用されているマッチングの実情を垣間見ることができ、マッチングそのものに対しても深い洞察を得ることができる。結婚や大学の選択などの重要な決定を下すときを考えてみよう。このとき、意思決定者には異なる選択肢が存在し、その各選択には異なる重みがある。GSアルゴリズムは、意思決定者の選好順序を考慮しながら、最適な状態に収束するようなマッチングを実現する。

例えば、上で挙げたような結婚マッチングや研究室ゼミ配属などのシチュエーションにおいて、意思決定者は応募者側と受け入れ側に二分できることが分かる。両者はお互いの構成員を好みの順に並べた選好順序を持っているが、GSアルゴリズムはこれら2つの選好順序を含む選好行列を受け取り、両側にとって最適なマッチング結果を導き出す。これにより、GSアルゴリズムに基づいたマッチング結果は応募者側と受け入れ側の両者、つまり参加者全員にとって満足度の高い結果をもたらすことができる。このアルゴリズムを理解することで、個人の選好がどのように考慮され、最終的に最適なマッチングが生まれるかを明確に理解することが可能になる。

Pythonのアルゴリズム実例コードの解説

結婚マッチングや研究室ゼミ配属など、応募者側と受け入れ側が互いに対する選好順序を有しているシチュエーションに対して、最適なペアを計算するために、このアルゴリズムを実行することは有効である。ここでは独身男女による結婚マッチングを例にとって、コードでの実装を考えてみたい。注意しておく点としては、このコードでは異性と結婚しないという選択を許し、最終的な結果において独身者が存在することを認めているという点である。しかし、プログラムの仕様上、全ての夫は妻を持ち、全ての妻は夫を持つという構造を崩したくはない。そこで、未婚を選択した男もしくは女は、それぞれを妻・夫と紐づけるものの、それは幻の妻・幻の夫とするというアイデアを採用したい。言葉上では、夫・妻と言っているが、実際は実体がない幻としてそれらを扱うということだ。この「幻の夫・幻の妻」を以下、ダミーと呼ぶことがある。また以下、簡単のために「告白する者 / applicant」を「男」・「告白される側 / host」を「女」とすることに注意してもらいたい。
今回の実例コードの出典は以下のリンクである。
https://github.com/13tsuyoshi/DA_algorithms/blob/master/DA_Algorithms.ipynb

def gale_shapley(applicant_prefers_input, host_prefers_input, **kwargs):
    unmatch = kwargs.get('unmatch', True)

    # 選好表の型チェック。listならnumpyへ変換
    applicant_preferences = np.asarray(applicant_prefers_input, dtype=int)
    host_preferences = np.asarray(host_prefers_input, dtype=int)

    # 選好表の行列数をチェック
    app_row, app_col = applicant_preferences.shape
    host_row, host_col = host_preferences.shape

applicant_prefers_input と host_prefers_inputは、それぞれ、男性側が作った選好行列と⼥性側が作った選好⾏列を示し、その選好行列は○⾏×列の形をしている。ここで選好⾏列がPythonのリスト形式で提供されている場合、これらをNumPyの配列に変換する。

Numpyは高速計算に長けており、アルゴリズムの実行にかかる時間を短縮することができる。この時点において、男性側と女性側のいずれの選好行列もNumPy配列への変換を経て名前が変わっていることに注意したい。applicant_prefers_inputはapplicant_preferencesになり、host_prefers_inputは host_preferencesに名前が変換された。次に、先ほど変換した選好行列の行数・列数を確認し、計4つの情報を記録しておく。具体的には、男性の選好行列の行数及び列数・女性の選好行列の行数及び列数のことである。

#unmatchマークが入力されていない時は、選好表の列の最後にunmatch列をつくる
    if not unmatch:
         dummy_host = np.repeat(app_col+1, app_row)
         dummy_applicant = np.repeat(host_col+1, host_row)
         applicant_preferences = np.c_[applicant_preferences, dummy_host]
         host_preferences = np.c_[host_preferences, dummy_applicant]
         app_col += 1
         host_col += 1

この部分では、ダミーの男性と女性を追加している。前述の通り、このアルゴリズムでは、最終的なマッチング結果として未婚状態が認められているため、そのためのセクションと言える。男性の既婚を認める時、仕様上は妻を用意しなければならないため、ダミーの妻を用意し未婚男性とマッチさせておく。以下では男性目線で操作の説明をしていくが、同様の操作が女性の選好行列に対しても行われる。

男性の選好⾏列には、独身の男性のためのダミーの妻を新たに⽤意することが必要であり、ダミーの女性を男性の選好行列に追加しなければならない。さて、選好⾏列のどこに追加するのがよいか？今回は、男性の選好⾏列の「最後列」にダミー⼥性のリストを追加することとする。ここで、選好行列の行数は男性の人数、列数は女性の人数に対応しているため、ダミーの女性を追加した分、男性の選好行列の列数を１だけ増やす必要がある。実際のコードでは、男性の選好行列に、列数に１足した値が行数分並んだリストを付け足している。

    if (app_row != host_col-1) or (host_row != app_col-1):
         raise CustomConditionError("選好表の行列数が不正です")
    
    applicant_unmatched_mark = app_col-1
    host_unmatched_mark = host_col-1

この部分では、先ほど作った未婚考慮済み選好行列が適正にできているかを確認している。この時点では男性及び女性の選好行列の列数がダミーの追加によって1列増えていることに注意しよう。オリジナルエラー「選好表の⾏列数が不正です」が起きないときは、app_row = host_col-1 かつ host_row = app_col-1 となっている時である。この時点における、host_col-1 と app_col-1 はダミー考慮前の選好⾏列の列数にそのまま等しいため、当時の男性の選好⾏列の⾏数（男性の人数）は、⼥性の選好⾏列の列数（男性の人数）に等しい。逆も同じであるため、上述の2つの当式は成り⽴つ。つまり、ここではエラーが出ないはずである。その後、ダミー考慮前の男性の選好⾏列の列数（⼥性の人数）をapplicant_unmatched_mark として、ダミー考慮前の⼥性の選好⾏列の列数（男性の人数）をhost_unmatched_mark として保存しておく。

　   # ソート
    host_preferences = np.argsort(host_preferences, axis=-1)
    
    # 未マッチング者のリスト
    stack = list(range(app_row))

    # マッチングを入れる（初期値は未マッチングflag）
    applicant_matchings = np.repeat(applicant_unmatched_mark, app_row)
    host_matchings = np.repeat(host_unmatched_mark, host_row)

次に、#ソート、#未マッチング者のリスト、#マッチングを入れる、の説明をする。np.argsortはNumPyの関数であり、指定した配列の要素のインデックスを昇順（⼩さい値から⼤きい値）に並び替える。ソートの操作では、 host_preferences の各⾏に対してソートを⾏い、各⼥性（⼥性の選好リスト）ごとに、その⼥性が好む男性の順番を⽰すように、選好の順序をソートしている。ソートする際は、実際の要素の値（各男性の固体識別番号）をソートするのではなく、要素のインデックス（各男性にあてがわれた順位）をソートすることになることに留意しよう。’stack’ リストには男性数（男性の選好⾏列の⾏数）に等しい枠が⽤意されており、中⾝は番号は0から始まり、app_row - 1 までの、合計 app_row（個）の整数（男性の個体識別番号）で構成されている。男性が女性とマッチングした場合、このリストから取り除かれる。そのため、アルゴリズムの終了時にはstackリストは空になっている。#マッチングを⼊れるの部分では、先ほど保存したダミー考慮前の⼥性数の値を男性数分繰り返して格納したリストとダミー考慮前の男性数の値を⼥性数分繰り返して格納したリストを作成している。

以下、Gale-Shapleyアルゴリズムの実行に先立ち、初期状態として、男女全員独身状態から始める。

#メインループ
     next_start = np.zeros(app_row, dtype=int)
     while len(stack) > 0:
          # スタックから1人応募者を取り出す
          applicant = stack.pop()

          # 取り出した応募者の選好表
          applicant_preference = applicant_preferences[applicant]

この部分のコードは、男性が選好表に基づいて女性にプロポーズする段階を実装している。next_start という配列には、0が男性数分格納されており、全ての男性が最初に誰にプロポーズするかを指⽰する。続く、while文は’stack’が空になるまでループ内の操作を実⾏し続けるという処理を書いたものだ。 ‘stack’は未マッチングの男性たちを格納しているため、このwhile文は未マッチングの男性が居なくなるまで処理を続けることになる。ここで読者が疑問に思われるかもしれない点は、独身者を認めるのだから、未婚男性が'stack'に残り続けて、永遠にループが終わらないのではないかという点である。しかし、未婚を望んでいる男性でも今回はダミー妻と結婚した扱いにするため、’stack’は最終的には空になり、ループが永遠に終わらないという事態は起こりえないため、この疑問点は杞憂である。続いて、気になるループの中身を見てみよう。applicantは’stack’から1⼈の未マッチングの男性を末尾から取り出したものである。ここで取り出された男性が次に女性にプロポーズする告⽩者となる。applicantと等号で結ばれているstack.pop()は男性人数分の整数が格納されたstack から番号を取り出していく操作を示すので、 applicantの正体はある男性の個体識別番号を表している。

さて、一人の男性を取り出したのち、applicant_preferences[applicant] はその男性の選好表、つまりその男性がどの女性をどの順番で好むかを示す一行の選好リストを取得する。

#選好表の上から順番にプロポーズ
for index,host in enumerate(applicant_preference[next_start[applicant]:]):
# unmatched_markまでapplicantがマッチングできなければ、アンマッチ
    if host == applicant_unmatched_mark:
       break

#プロポーズする相手の選好表
    host_preference = host_preferences[host]

#相手の選好表で応募者と現在のマッチング相手のどちらが順位が高いのか比較する
    　rank_applicant = host_preference[applicant]
      matched = host_matchings[host]
      rank_matched = host_preference[matched]

この部分のコードは、男性が女性に対して順番にプロポーズし、女性がマッチングの妥当性を評価する段階実装している。ここにおいて、女性は告白者の男性と現在のマッチング相手の男性を比較し、選好順位が高い方とマッチングし直す。# 選好表の上から順番にプロポーズで示されているに該当する箇所は、選好表を使って男性が順番にプロポーズする部分である。このコード内のnext_start[applicant] は、告⽩者が次にプロポーズする⼥性を⽰す。

for文の中身はhostがapplicant_unmatched_markにあてがわれる条件の下での操作を考慮することから始まる。これはもし告⽩者が未マッチングを⽰すダミー妻に到達した場合、これ以上⼥性に対してプロポーズすることを中⽌し、次のステップに進むことを意味する。無事にプロポーズが終了した後、host_preference = host_preferences[host] においてプロポーズされた⼥性が告白者の男性をどのような順番で好んでいるかを格納する選好表を取得する。続いて、告白された女性はマッチングの男性を選択し直す段階に入るのだが、その前準備として比較される値を用意する必要がある。

rank_applicantで告白された女性から見た新規告白者の順位番号を表し、rank_matchedは告白された女性から見た現在マッチング中の男性の順位番号を表している。これらの数値を前もって取得しておくことにより女性は新規告⽩者と現在のマッチング相⼿とのランキングを⽐較することが可能となる。⼥性はこの2⼈の順位を⾃⾝の選好リストを参照して、順位が⾼い⽅とマッチングを結び直す。さて、この時、もし女性が現マッチング男性よりも新規告白者の方を好むなら、どのような操作が行われるだろう。この条件はその下のif文で表された通りである。この条件が満たされる場合、以下の処理が続けて⾏われる。

# もし受け入れ側が新しい応募者の方を好むなら
       if rank_matched > rank_applicant:
           applicant_matchings[applicant] = host
           host_matchings[host] = applicant

ここで思い出してほしいことがある。applicant_matchings 、host_matchings は、先ほどの「マッチングを⼊れる」のセクションで作ったリストたちである。前者は、ダミー考慮前の⼥性数の値（未マッチングを⽰す値として利⽤し、ダミー妻の識別番号ともなっている）を男性数分繰り返して格納したリストだ。後者は、ダミー考慮前の男性数の値（未マッチングを⽰す値として利⽤し、これはダミー夫の識別番号ともなる）を⼥性数分繰り返して格納したリストだ。全部、同じ値が格納されているのは、ただの初期化のためであり、⼤きな意味はない。これから、このリストたちには、異性の個体識別番号が更新され、⼊れ替わりながら格納されていく。この異性の個体識別番号が⽬まぐるしく⼊れ替わるこのリストは、現在男⼥が誰とマッチングしているかという情報を逐⼀保存していく役割を持つことを念頭に入れておきたい。

applicant_matchings[applicant] = host は、新規告⽩者に対応するダミー妻の枠に、彼の告⽩を受けた⼥性の識別番号をあてがうことを意味する。つまり、告⽩された⼥性が新しい告⽩者の⽅を選択し、その男性とのマッチングが新しく成⽴したことを⽰す
host_matchings[host] = applicant は、彼の告⽩を受けた⼥性に対応するダミー夫の枠に、彼の識別番号をあてがうことを意味する。男性側からもマッチングを更新していく。これにより、男性と⼥性の間で双⽅向のマッチングが更新‧ 確⽴される。この後、もう一つの条件分岐が登場する。

#既にマッチしていた相手がダミーでなければ、マッチングを解除する
                 if matched != host_unmatched_mark:
                   applicant_matchings[matched]=applicant_unmatched_mark
                   stack.append(matched)

                   next_start[applicant] = index
                   break

    return applicant_matchings, host_matchings

ここでのif文は、その⼥性が先ほど振った彼が未婚者⽤のダミー夫でない場合の条件式である。もし、振った彼がダミーでなかったとき、彼はもう独身に舞い戻ったため、その彼に対応するダミー妻の枠に正式に新しくダミー妻の識別番号をあてがう必要がある。この操作を表したのがapplicant_matchings[matched] = applicant_unmatched_markである。
そしてそのまま、stack.append(matched) で先ほどフラれてしまった彼をstackに戻す。結局、新しい告⽩者に敗北したことでその⼥性とマッチングしていた男性は未マッチング状態に戻った。

最後に next_start は、0が男性数分格納されている配列だったことを思い出すと、next_start[applicant] = index は、次に男性がプロポーズする⼥性のインデックスを設定し、その次のループで正しいインデックスからプロポーズを再開できるようにするためのものである。

GSアルゴリズムの実装

def gale_shapley(applicant_prefers_input, host_prefers_input, **kwargs): 
    unmatch = kwargs.get('unmatch', True)

GSアルゴリズムを実行するためのgale_shapley関数を定義する。
・コードの例

辞書内に’unmatch’が存在すれば、対応する値を返す
kwargs = {'key1’ : 1. ‘key2’ : 2, ‘unmatch’ : 3}
kwargs.get(‘unmatch’,True)
出力
3

存在しなければ、Trueを返す
kwargs = {'key1’ : 1. ‘key2’ : 2, ‘key3’ : 3}
kwargs.get(‘unmatch’,True)
出力
True

#ソート
    host_preferences = np.argsort(host_preferences, axis=-1)

女性ごとに、選好順序をソートしている。

・np.sortの例

コード
arr = [3,1,2]
idx = np.argsort(arr)
print(idx)
出力
[1 2 0]

      # 選好表の上から順番にプロポーズ
      for index, host in enumerate(applicant_preference[next_start[applicant]:]):
           # unmatched_markまでapplicantがマッチングできなければ、アンマッチ
           if host == applicant_unmatched_mark:
                break

この部分では、男性が選好表に従ってプロポーズしていく。next_start[applicant]は次にプロポーズする女性を表す。もしunmatched_mark(ダミーの妻)まで到達すれば、それ以上プロポーズせず次の男性に進む。

・enumerateの例

コード
applicant_preference = [‘a’, ’b’, ’c’]
for index, host in enumarate(applicant_preference):
  print(index, host)
出力
0  a
1  b
2  c

・不等号の向きについての追加説明
rank_matched > rank_applicantは、現在のマッチング相手よりも新しい告白者を好む状況を表す。不等号の向きが一見逆に見えるのは、好き度ではなく選好順序における順位を比較しているからである。例えば、Cちゃんが、A君とB君のどちらが好きかを不等号で表すことを考えてみよう。Cちゃんにとってはクラスメイトの中で、A君は1番目に好きで、B君は5番目に好きだとする。このとき、CちゃんはB君よりA君の方が好きであることは明白だから、好き度と言う指標に基づいて不等式を立てようとすると「A ＞ B」と書きたくなる。しかし、今回の例のように「値」番目という順位の値そのものに焦点を当てるｔおき、「A ＜ B（= 1 < 5）」となり、一見不等号の向きが逆転しているように見えるのだ。

・ランダムに選好表を作る方法①
unmatchのTrueとFalseは、独身を認めるかを判断する。(Trueなら認める)
numpyがTrueなら、Pythonの拡張モジュールであるNumpyに含まれる関数を使用して選好表を作る。Falseなら、標準モジュールに含まれるrandom関数を使用する。
　　
　numpyがTrueの場合

#選好表をランダムに作る
def random_preference_table(row, col, **kwargs):
    unmatch = kwargs.get('unmatch', True)
    numpy = kwargs.get('numpy', False)
   
    if numpy:
         li = np.tile(np.arange(col+1, dtype=int), (row, 1))
         stop = None if unmatch else -1
         for i in li:
              np.random.shuffle(i[:stop])
         
         return li

np.arangeとnp.tileを使い、row行col列のリストを作り、np.random.shuffleで行ごとにシャッフルするrandom_preference_table関数を定義している。以下に例を挙げる。

コード
list01 = np.arange(10)
print(list01)
出力
[0 1 2 3 4 5 6 7 8 9]

コード
list02 = np.tile(np.arange(11),(3,1))
print(list02)
出力
[[0 1 2 3 4 5 6 7 8 9 10]
[0 1 2 3 4 5 6 7 8 9 10]
[0 1 2 3 4 5 6 7 8 9 10]]

コード
for i in list02:
  no.random.shuffle(i)
print(list02)
出力
[[3 4 0 7 1 2 6 5 10 8 9]
[2 3 10 9 1 6 7 0 4 8 5]
[8 7 5 6 10 1 3 0 9 4 2]]

　numpyがfalseの場合

   else:     
        def __sshuffle(li):
             shuffle(li)
             return li

        if unmatch:
             return [__sshuffle(list(range(col+1))) for i in range(row)]
        else:
             return [__sshuffle(list(range(col))) + [col+1] for i in range(row)]

sshuffle関数を定義する。sshufle関数は、unmatchがTrueの場合はシャッフルされたrow行col列のリストli を返し、unmatchがFalseの場合はシャフルされたrow行col-1列のリストを作り、各行の末尾にcolの値を追加したリストliを返す。

・ランダムに選好表を作る方法②

#巨大な選好表をきちんとランダムに作るのは大変時間がかかる
#そこで、選好のパターンをn個用意し、その中から選ぶようにする
def pseudo_random_preference_table(row, col, n=1000, **kwargs):
   unmatch = kwargs.get('unmatch', True)

   if n > row:
        n = row

   size = col+1 if unmatch else col
   sample = np.tile(np.arange(size, dtype=int), (n, 1))
   for i in sample:
        np.random.shuffle(i)

   index = np.random.randint(0, n, row)
   li = np.empty((row, size))
   li += sample[index]

   return li

疑似的にランダムな選好表を作るpseudo_random_preference_table関数を定義する。
シャッフルされた選好表のパターンをn個作り、np.random.randintを使いその中からランダムに選出した選好表を並べたリストliを返す。

・np.random.randintの例

コード
n=10
index = np.random.randint(0,n,5)
print(index)
出力
[6 5 5 5 8]
0からnの中から、5回ランダムな整数を取り出している。

GSアルゴリズムのシミュレーション

ここでは実際にGSアルゴリズムを用いたコードを実行してみる。

app_table = [[0, 2, 1, 3], [2, 1, 3, 0], [3, 1, 0, 2]]
hos_table = [[3, 0, 2, 1], [2, 0, 1, 3], [2, 0, 3, 1]]

print("DAアルゴリズム スタート!")
start = time.time()
matching = gale_shapley(app_table, hos_table)
stop = time.time() - start
print("ストップ！")
print("実行時間は " + str(stop) + " 秒でした\n")

print("申し込み側からみたマッチングは")
print(matching[0])
print("受け入れ側からみたマッチングは")
print(matching[1])

上記のコードは、男性３人、女性３人のマッチングを実行するものである。今回は手動で選考リストを作成している。ちなみに、選考リストが４人分あるように見えるのはダミーが入っているからである。 time.time（）は現在の時刻を秒単位で取得する関数で、GSアルゴリズムの実行時間を記録するために用いている。 strはstop変数を文字列(string型)に変換、\n は改行するという意味である。

得られた実行結果は以下の通りである。

DAアルゴリズム スタート!
ストップ！ 
実行時間は 0.0 秒でした 
申し込み側からみたマッチングは 
[2 1 3]
受け入れ側からみたマッチングは 
[3 1 0]

申し込み側（男性）からみたマッチングは
男性０と女性２、男性１と女性１、男性２と女性３　がマッチングしたことを表している。

受け入れ側（女性）からみたマッチングは
女性０と男性３、女性１と男性１、女性２と男性０　がマッチングしたことを表している。

上記のように申し込み側からみたマッチングと受け入れ側からみたマッチングは対応しているのである。ここで注意をしたいのが、男性３と女性３のダミーという存在である。男性３と女性３はダミーであり、この2人とペアになっている人は結婚しないという選択をしていることに気を付ける。

次は random_preference_table を用いて選考リストを自動で作成してみる。
先ほどのコードの先頭に下記のコードを加える。

start = time.time()
app_table = random_preference_table(1000, 1000)
hos_table = random_preference_table(1000, 1000)
stop = time.time() - start
print("選好表生成は " + str(stop) + " 秒でした\n")

得られた実行結果は以下の通りである。

選好表生成は 1.0190796852111816 秒でした 

DAアルゴリズム スタート!
ストップ！ 

実行時間は 0.18959403038024902 秒でした

申し込み側からみたマッチングは 
[ 942 236 690 1000 991 896 156 459 144 601 544 868 95 683 516 798 829 648 496 94 642 918 609 252 593 695 108 837 104 827 442 268 919 37 780 300 566 323 881 723 850 1000 208 506 561 509 368 572 870 203 836 643 93 952 162 502 960 992 396 0 879 121 852 200 413 343 869 75 795 417 481 715 258 605 1000 409 711 211 907 718 303 88 534 403 569 65 633 205 565 20 84 328 778 493 867 334 933 832 381 326 154 16 215 891 167 486 347 428 1000 480 1000 1000 1000 503 511 731 990 437 263 623 743 129 451 292 625 385 172 119 950 532 241 744 400 332 789 936 859 630 216 552 420 12 1000 826 686 48 640 611 315 374 114 251 928 464 51 209 599 963 161 371 498 805 195 762 469 55 964 255 98 759 993 874 651 785 913 929 740 951 585 287 378 769 273 21 959 632 1000 547 2 665 987 277 1000 528 1000 131 294 624 541 450 284 201 357 589 56 1000 530 218 855 457 120 259 983 595 416 887 912 45 976 816 1000 336 123 546 783 1000 801 800 46 821 660 656 692 508 604 706 906 835 100 250 751 247 714 264 52 819 424 834 796 367 47 741
...
53 855 823 976 769 308 352 184 56 551 698 157 166 882 707 489 925 683 929 353 483 644 708 896 218 749 622 994 474 374 479 212 600 919 334 190 721 499 116 4 57 170 629 581 931 493 725 621] 
Output is truncated. View as a scrollable element or open in a text editor. Adjust cell output settings...

途中で省略されているが、1000人であってもGSアルゴリズムは0.1秒で実行することができ、選考リストを自動で定めることができるということもわかる。下の2行は表示しきれないということを表している。

現実の例

GSアルゴリズムは、実際の社会生活のなかでどのように利用することができるのか考えてみよう。

例１）待機児童問題

　　・各家庭は希望する保育園に希望順位をつけて提出（申し込む側）
　　・各保育園は優先して入園させたい子供の順位付けを行う（申し込まれる側）
　（親の就労状況、片親かどうか、祖父母が周りに住んでいるか、保育園との距離など）
　　・この条件でマッチングを行う
　メリット…一度に多数の待機児童に対応できるため効率がよい　
　デメリット…兄弟などへの対応が難しい

東京都多摩市では保育園の入園希望者の選定にマッチング理論を導入している

例２）ワクチン配布

　　・ワクチン接種希望者は日時、場所の希望を提出（申し込む側）
　　・各自治体や医療機関が優先的ワクチンを接種してほしい人の条件や受け入れ人数をきめる（申し込まれる側）
　　・この条件でマッチングを行う
　メリット…早い者勝ちという状況やワクチン在庫の偏りをなくせる

アメリカでは各州へのワクチンの割り当てを決める際にアルゴリズムを導入していた

応用及び今後の課題

最後に、GSアルゴリズムの応用と課題について説明する。応用として、男性と女性の人数が異なる場合でもアルゴリズムは適応できる。これにより研修医と病院や、子供と保育園といった応募側と募集側の数に差がある場合でもマッチングを作り出すことができる。課題として、告白側が有利になるという不公平性がある。男性が告白する場合、男性から見た最高の最適なマッチングが返されるが、女性から見ると最悪な最適マッチが返される。以下に例を挙げる。

男女二人ずつの状況を考える。それぞれの選好表は
$M1：W1 ＞ W2$（女性２より女性１が好き）　$W1：M2 ＞ M1$
$M2：W2 ＞ W1$　　　　　　　　　　　　　　$W2：M1 ＞ M2$
男性から告白する場合、返されるマッチングは（$M1, W1$）（$M2, W2$）
女性から告白する場合、返されるマッチングは（$M2, W1$）（$M1, W2$）
どちらも安定マッチングであるが、告白する側が有利になっていることがわかる。

他の課題として、GSアルゴリズムが返すマッチングは相対的な値を基準に作られたものであり、絶対的な値を考慮に入れられないことがある。絶対的な値とは、兄弟を考慮した保育園の選定や、研修医の配属先までの通勤時間などが当てはまる。それら絶対的な値を加味したうえで全国の保育園や研修病院をランキングにするのは労力がかかり、GSアルゴリズムの長所である効率性を失ってしまう。