こんにちは。機械学習やデータ分析に加えてインフラ周りでも修行中の浅野です。今年の始めにさいたま市が導入した保育所マッチングシステムがトラブルを起こしたというニュースがありました。それをきっかけに保育所マッチングではどのような技術が使われているのか興味をもったので少し調べてみました。このユニファアドベントカレンダー24日目の記事ではその技術の基礎的な部分について書いてみようと思います。
２つの方式
保護者からの申請書類に基づいて算出される保育の必要性(優先順位)と各保育所への入所希望順位から、各自治体がどの園児をどの保育所に割り当てるのがよいか調整を行います。これが保育所マッチングです。内閣府が指針を出しており、優先順位を重視するパターン1と希望順位を重視するパターン2のうち、各自治体の状況に合わせてどちらか適切な方法で調整を行うべきであることが示されています。マッチング理論においてはパターン1が受け入れ保留方式、パターン2が(通称)ボストン方式と呼ばれています。それぞれの手法について以下にまとめていきます。３人の児童と３つの保育所（定員各１名）のマッチングを考えます。各児童の入所希望順位と各保育所における優先順位は下記の表のように決まるとします。
 |
 |
ボストン方式
はじめに比較的シンプルなボストン方式についてみていきます。まず各児童の第1希望の園とマッチングを行います。はなこさんとたろうさんはひまわり保育園を希望しています。ひまわり保育園での優先順位はたろうさんの方が高いので、たろうさんがひまわり保育園に割り当てられます。じろうさんはあおぞら保育園に割り当てられます。第1希望が叶わなかったはなこさんは第2希望のあおぞら保育園もすでに定員が埋まっているので、第3希望のたんぽぽ保育園に割り当てられます。これをPythonで実装してみます。
ボストン方式の実装(クリックすると展開します)
import pandas as pd
class NurseryMatching():
def __init__(self, kids_csv, nursery_csv):
self.kids_df = pd.read_csv(kids_csv, index_col=0, header=0)
self.nursery_df = pd.read_csv(nursery_csv, index_col=0, header=0)
self.capacity = self.nursery_df['定員']
self.nursery_df = self.nursery_df.drop('定員', axis=1)
self.round = 1
self.max_round = len(self.kids_df.columns)
def matching(self):
return NotImplementedError("method matching must be implemented")
class Boston_Matching(NurseryMatching):
def __init__(self, kids_csv, nursery_csv):
super().__init__(kids_csv, nursery_csv)
self.kids_finished = []
keys = list(self.nursery_df.index)
values = [[] for _ in range(len(keys))] # empty array
self.fixed_result = dict(zip(keys, values))
def matching(self):
while self.round <= self.max_round:
#すでに確定している園児のリスト
self.kids_finished = list(flatten_list(list(self.fixed_result.values())))
#残っている園児
remaining_kids_df = self.kids_df[~self.kids_df.index.isin(self.kids_finished)]
#全員確定していたら終了
if len(remaining_kids_df) == 0:
break
#志望のあった園について園児を確定していく
unique_choices = remaining_kids_df[str(self.round)].unique()
for unique_choice in unique_choices:
# すでにその園がcapacityに達していたらskip
remaining_capacity = self.capacity[unique_choice] - len(self.fixed_result[unique_choice])
if remaining_capacity <= 0:
continue
competing_kids = remaining_kids_df[remaining_kids_df[str(self.round)] == unique_choice].index
#志望している中で優先度が高い園児をキャパシティまで選ぶ
num_kids_to_select = min(len(competing_kids), remaining_capacity)
competing_kids_flag = self.nursery_df.loc[unique_choice].isin(competing_kids)
higher_priority_kids = self.nursery_df.loc[unique_choice][competing_kids_flag][:num_kids_to_select]
self.fixed_result[unique_choice].extend(list(higher_priority_kids))
self.round += 1
このボストン方式によって得られるマッチングの結果をオレンジ色で示すと次のようになります。
 |
 |
この結果を詳しくみましょう。はなこさんの立場になると、（右側の表において）あおぞら保育園は自分の優先順位が高いのに、（左側の表において）自分はあおぞら保育園より希望順位の低いたんぽぽ保育園に割り当てられており、不満が残ります。このような状況を不安定なマッチングと呼びます。また、はなこさんが本来の希望順位を偽り、人気のあるひまわり保育園ではなくあおぞら保育園が第1希望であると申請すると、はなこさんとじろうさんの割り当てが入れ替わり、はなこさんはより希望順位が高い園に入所することができます。このように正直に希望順位を申告しないことにインセンティブが働いてしまう状況は好ましくありません（対戦略性を満たさないといいます）。このようにボストン方式は分かりやすいものの安定性と対戦略性の面で難があります。
受け入れ保留方式
もう一つの方法である受け入れ保留方式では、第1希望からマッチングを考えていく点はボストン方式と同じですが、割り当てはすぐには確定しないのが特徴です。第1希望ではたろうさんがひまわり保育園に、じろうさんはあおぞら保育園に「仮決定」します。第2希望ではなこさんがあおぞら保育園を希望しています。あおぞら保育園の優先順位は仮決定しているじろうさんよりもはなこさんの方が高いため、じろうさんに代わりはなこさんが仮決定します。仮決定先のなくなったじろうさんは第2希望のひまわり保育園はたろうさんより優先順位が低いため決まらず、第3希望のたんぽぽ保育園に仮決定します。最終的に次のように割り当てが決まります。
 |
 |
この結果を見ると、ボストン方式で問題になっていた不安定な状況は解消されていることがわかります。保育所マッチングは各児童が１つの保育所に、各保育所には複数の児童が割り当てられる1対多マッチングであり、1対多マッチングには安定なマッチングが必ず存在することと、受け入れ保留方式が常にそれを実現することが証明されています。また、受け入れ保留方式は各児童（家庭）における対戦略性を満たすことも知られており、ボストン方式よりも優れた方式であると言えます。受け入れ保留方式の実装例も示しておきます。
受け入れ保留方式の実装(クリックすると展開します)
class DA_Matching(NurseryMatching):
def __init__(self, kids_csv, nursery_csv):
super().__init__(kids_csv, nursery_csv)
self.kids_listed = [] #仮承諾された園児
keys = list(self.nursery_df.index)
values = [[] for _ in range(len(keys))]
self.temp_result = dict(zip(keys, values))
self.final_result = {}
def matching(self):
while self.round <= self.max_round:
#仮承諾されている園児のリスト
self.kids_listed = list(flatten_list(list(self.temp_result.values())))
#まだ仮承諾されていない園児
remaining_kids_df = self.kids_df[~self.kids_df.index.isin(self.kids_listed)]
#全員仮承諾していたら終了
if len(remaining_kids_df) == 0:
break
#志望のあった園について園児を優先順位に応じて仮承諾していく
unique_choices = remaining_kids_df[str(self.round)].unique()
for unique_choice in unique_choices:
#今回のラウンドで応募している園児
applying_kids = remaining_kids_df[remaining_kids_df[str(self.round)] == unique_choice].index
#仮承諾済みの園児も含めてcapacity内で優先順位の高い園児を新たに仮承諾
competing_kids = self.temp_result[unique_choice]
competing_kids.extend(list(applying_kids))
num_kids_to_select = min(len(competing_kids), self.capacity[unique_choice])
competing_kids_flag = self.nursery_df.loc[unique_choice].isin(competing_kids)
higher_priority_kids = self.nursery_df.loc[unique_choice][competing_kids_flag][:num_kids_to_select]
self.temp_result[unique_choice] = list(higher_priority_kids)
self.round += 1
self.final_result = self.temp_result
おわりに
マッチング理論で代表的な手法であるボストン方式と受け入れ保留方式について基本となるアルゴリズムを理解して実装しました。ただし実際の保育所マッチングはこれほど単純ではありません。例えば、今回は各保育所における優先順位が明確についている状況を想定していましたが、実際には保育の必要性が同じである家庭が存在します。この状況をどう解消するかによって受け入れ保留方式をベースにしていても安定性や対戦略性が失われることがあります。また、児童数の偏りを抑えるために各保育所に割り当て数の下限を設けたり、エリアごとに上限数を定めたりする場合にも、安定性、対戦略性、あるいは効率性のトレードオフを考慮しつつ慎重に方式を選択する必要があります。他にも、冒頭のさいたま市のニュースの中で示されている例のように、兄弟姉妹で一人だけ入所できることになった場合にできる限り当該家庭の希望に配慮すると対応がかなり複雑になります。このように、様々な制約や複雑な条件がある中でも効率的に最適解を導くことができるシステムをつくるというのは理論的にもエンジニアリング的にもとても興味深いテーマです。
保育園向けのプロダクトやサービスを提供しているユニファでは一緒に働く仲間を募集しています。 unifa-e.com
