こんにちは。CyberAgent AI Labの冨田（@miiitomi）です。
今回は CyberAgent Developers Advent Calendar 2021 9日目の記事として、東京大学マーケットデザインセンター（UTMD）との共同研究の1つとして取り組んでいる「保育所マッチングプロジェクト」についてお話ししたいと思います。
ご興味のある方は共同研究の概要についてはこちらを、私たちのプロジェクトに対しての思いについてはこちらをよかったらご覧ください。
目次
待機児童問題と保育所利用調整
「保育園落ちた日本死ね！！！」という題の匿名ブログが大きな話題となってから5年が経ちました。厚生労働省令和2年10月時点の保育所等の待機児童数の状況についてによると、令和2年10月1日時点の待機児童数は27,814人となっており、減少傾向にはあるもののまだ待機児童問題はなくなっていません。また、保護者が求職活動を休止している、特定の施設のみを希望している、自治体が独自で財政支援する保育サービスを利用している、といった理由で、認可保育所に入れなかったのに待機児童としてカウントされていない「隠れ待機児童（潜在的待機児童）」がいることも指摘されています。
待機児童をなくすためには保育施設を拡充し定員を増やすことが第一です。しかし保育施設の制約は一定の下でも、保護者の申し込みを受けて利用調整を行う際の調整方法を変更することで、待機児童問題を緩和できる可能性があるという議論が経済学のマーケットデザインと呼ばれる分野でされています(Kamada and Kojima 2020, Okumura 2019)。
保育所利用調整の流れ
まず保育所利用調整の流れについて説明します。ご存知の方も多いと思いますが、保育所の利用調整は大まかに以下のような流れで行われます。
- 各保育所各年齢別の募集定員の決定・募集要項公開
- 保護者が希望する保育所のリストを記入した申込書を提出
- 例：第1希望 A保育園 第2希望 B保育園 第3希望 C保育園 …
- 各申込児童について調整指数を計算
- 募集定員・各申込児童の希望保育園・調整指数をもとに利用調整を行い、入園先を決定
- 結果通知
- 2次募集など
以下では、1における年齢別募集定員の決定と、4の利用調整方式について注目します。
年齢別定員と保育士数・児童数比率制約
1において各保育所では、保育士数や施設の制約から事前に決められた入所定員と在籍児童数から、0歳から5歳まで6クラス毎に募集定員を決定します。
一方、保育士数や設備面積といった保育園のリソースと児童数について、国により満たすべき比率が定められており、例えば保育士数に関しては、保育士1人あたり0歳から5歳までそれぞれ3人、6人、6人、20人、30人、30人とされています。
このような状況では、例として以下のような状況が発生することがあります。
A園が0歳に非常に人気があり、B園が1歳に非常に人気があったとします。すると0歳、1歳それぞれ定員を満たすまで指数の高い順にA園、B園に入園していきます。続いて児童5と児童11はそれぞれ第2希望であるB園、A園に入園となり、最後に児童6と児童12は第2希望を記入してないためいずれも入園先なしとなります。
しかし、本来国によって定められている保育士数と園児数の比率に注目すると、保育士2人に対し0歳児6人、あるいは1歳児6人というのは制約を満たすはずです。したがって、本来の制約では児童1から12まで全員がそれぞれ第1希望に入園できるはずです。
よってこの例は、年齢別定員を調整前に固定的に決定していることにより、希望にそぐわない保育所に入所することになる児童（児童5,11）や保育所未入所となってしまう児童（児童6,12）が生じている例と考えられます。
年齢別定員を柔軟に調整するアルゴリズム
上記の例のような状況を起こさないために、事前に固定的に年齢別定員を決定してから調整するのではなく、利用調整を行いながら年齢別定員を柔軟に調整するようなアルゴリズムを考えたいとします。
では、アルゴリズムが返すマッチング結果に満たして欲しい性質には、どのようなものがあるでしょうか。
公平性
例えば、指数の高い児童が未入所となっているのに、指数の低い児童が入所できているとすれば、公平でないとして望ましいマッチング結果になっているとは言えないでしょう。マッチング理論では、公平性を次のように定義します。
定義1（公平マッチング）
- ある児童 a と別の児童 b について, 児童 b はある保育所 s にマッチしており, 児童 a は自分の結果より保育所 s への入所を望んでおり, 児童 a の方が児童 b より指数が高い場合, 児童 a は児童 b に対して正当な羨望（justified envy）を持っているという。
- マッチング結果 μ において、正当な羨望を持つ児童がいない場合、μ は公平マッチングであるという。
つまり、不公平感を抱く（正当な羨望をもつ）児童のいないマッチング結果が公平マッチングです。利用調整を行うアルゴリズムは、常に公平マッチングを返してくれるものが望ましいでしょう。
児童側最適公平マッチング
しかし、公平マッチングであるだけでは望ましいマッチングであるとは言えません。極端な例では、全児童を未入所とするようなマッチング結果も定義上公平マッチングとなってしまいます。
公平マッチングの中で、全ての児童が最も望むようなマッチング結果を得るような公平マッチングが存在すれば、それが好ましいと言えるでしょう。それは次のように定義されます。
定義2（児童側最適公平マッチング）
- ある公平マッチング μ について、別の任意の公平マッチング μ’ をとってきたときに、全ての児童が μ’ における結果より μ における結果の方を（少なくとも同等以上に）望むのであれば、μ を児童側最適公平マッチング（student-optimal-fair-matching）という。
児童側最適公平マッチングは、存在するのであれば非常に望ましいマッチングであると言えるでしょう。また、定義より児童側最適公平マッチング μ は存在するのであれば一意に決まります。しかし、全ての児童が μ における結果を公平マッチングの中で最も望むというのは強い要請に思われます。児童側最適公平マッチングは常に存在すると言えるのでしょうか。またその場合、児童側公平マッチングを見つけてくれる効率的なアルゴリズムはあるのでしょうか。
SOFMアルゴリズム
Kamada and Kojima (2020) は、本稿で考えている保育所マッチング問題を含む広い範囲の制約付きマッチング問題において、上記の問題が肯定的に解決できることを示しました。主結果は次のようなものになります。
命題1 [Kamada and Kojima (2020)]
- 保育所マッチング問題において、児童側最適公平マッチングは常に存在する。
- 保育所マッチング問題において、児童側最適公平マッチングはアルゴリズム1（SOFMアルゴリズム）によって求めることができる。
SOFMアルゴリズムは以下のものです。
アルゴリズム1（SOFMアルゴリズム）
- 全児童を調整指数の高い方から1列に並べる。
- 各保育所 s について、カットオフ p(s) を「全児童数」で初期化する。
- 各児童は、自分が前から p(s) 番目までにいるような保育所 s のうち最も望ましいと思う保育所に応募する（そのような保育所 s がない場合、どの保育所にも応募しない）。
- 応募された全ての児童を制約上受け入れることができないような保育所がある限り、以下を繰り返す。
-
- 応募された全ての児童を制約上受け入れることができないような保育所それぞれについて, p(s) ← p(s) – 1 とする。
- 新たなカットオフのもとで、全児童は自分が前から p(s) 番目までにいるような保育所 s のうち最も望ましいと思う保育所に応募する（前のステップと同じ保育所に応募し直すこともありうる）。
-
- この時点で各児童は応募している保育所に入所決定する（応募している保育所がない場合、未入所とする）。
SOFMアルゴリズムは保育所マッチング問題において常に制約をきちんと満たすマッチング μ を返し、それは児童側最適公平マッチングとなっています。
シミュレーション
SOFMアルゴリズムが保育所マッチング問題の制約のもとで柔軟に定員を調整しながら利用調整を行い、望ましいマッチング（児童側最適公平マッチング）を見つけてくれることが理論的にわかりました。このアルゴリズムは、待機児童問題に対してどのくらい有効なのでしょうか。保育所マッチング問題を模した人工的なデータを作ってみてシミュレーション分析してみましょう。シミュレーション時の設定は以下のようにしました。
- 保育所数：50園
- 各保育所の固定的年齢別定員：0歳から5歳まで順に、6人、6人、4人、4人、2人、2人。
- 各保育所の保育士数：上記定員が比率規定を満たせるようになる最小人数（4人）
- 年齢別児童数：0歳から5歳まで順に、300人、300人、150人、150人、50人、50人（合計1000人）。
- 各児童の提出する希望保育所リストの長さ：5園。
- 各児童の調整指数・希望保育所リストはランダムに発生させる。
全年齢とも、各児童がどの保育所でも良いというのであれば固定的年齢別定員のもとで全児童が入所できるように定員を設定しています。また、本プロジェクトにご協力いただいている自治体のデータをもとに、以下のような特徴をもたせています。
- 児童数・年齢別定員ともに、年齢が上がることに少なくなるが、その下がり方は児童数の方が大きい。
- 各児童は希望する保育所リストに全ての保育所を記入するわけではない（ここでは1割の5園を書くとする）。
この設定においてシミュレーションを行ったところ、結果は以下のようになりました。
| 未内定者数 | 第1希望に入所した児童数 | 正当な羨望を持つ児童数 | |
|---|---|---|---|
| SOFM | 7 | 892 | 0 |
| 逐次独裁方式 | 23 | 818 | 147 |
| 受入即決方式 | 31 | 860 | 121 |
逐次独裁（Serial Dictatorship）方式および受入即決（Boston）方式は多くの自治体で使われているもので、固定的年齢別定員を利用する一般的なマッチングアルゴリズムです。いずれのアルゴリズムでも未内定者は発生していますがSOFMが最も少なく、また第一希望に入所できた児童数もSOFMで最も多くなっています。
また正当な羨望を持つ児童数は、SOFMでは理論通り0人ですが、逐次独裁・受入即決方式では1割程度発生しています。
まとめ
本稿では保育所マッチングプロジェクトに関連して、Kamada and Kojima (2020) で提案されたSOFMアルゴリズムについて紹介しました。また実際の保育所マッチング問題の状況を模した設定においてシミュレーションを行い、SOFMが他の一般的なアルゴリズムより未内定者数を減らし、第1希望に入所できる児童数を増やすことを確認しました。
ただし本稿の分析は簡単化のため多くの仮定を置いています。例えば、ここでは年齢別定員を柔軟に調整可能であるとしましたが、実際には多くの保育所でクラス運営や施設上の問題等で、過度に年齢別定員を調整することは不可能であると考えられるでしょう。また実際の保育所利用調整では、きょうだいの応募があった場合に両者が同じ保育所に入園できるように対応していることが多いですが、今回はその問題には触れていません。
私たちの保育所マッチングプロジェクトでは、こうした現実のより複雑な制約の下で、SOFMを含む各種のマッチングアルゴリズムをシミュレーション分析し、より良いアルゴリズムの開発・実装を行っています。待機児童問題のマーケットデザインによる解消を目指し、今後も頑張っていきたいと思います。
参考文献
Kamada, Yuichiro, and Fuhito Kojima (2020), “Fair Matching under Constraints:Theory and Applications,” The Review of Economic Studies, forthcoming.
Okumura, Yasunori (2019), “School Choice with General Constraints: A Market Design Approach for the Nursery School Waiting List Problem in Japan,” The Japanese Economic Review, 70(4), 497-516.