AI Lab EconSIチームの孫と竹浪です。この記事では、人工知能分野のトップカンファレンスであるAAAI-24に採択されたSun et al. ”Stable Matchings in Practice: A Constraint Programming Approach” [1]について紹介します。本研究は孫を中心とし、山田、竹浪、森脇および九州大学の横尾真教授により実施されました。本論文のarXivリンクはこちらです。

はじめに

本論文では、保育所の入所選考にマッチング理論を適用することで、入所選考の実務にて利用可能なマッチングについて提案しています。

日本の保育所入所選考を取り扱ったこれまでの論文では、きょうだいや転園を考慮できていない、または同一世帯から同時に申し込むきょうだいの数に制限がある、という課題がありました。

そこで、本論文ではこれらの課題に対処し、以下のような貢献をしました。

• 以下の性質を満たすマッチング結果を導いた
  • 個人合理性、安定性と呼ばれる望ましい性質を満たす
  • きょうだいの数に制限を設けない
  • 転園に対応する
  • 異年齢間で定員を共有できる
• 制約プログラミング（Constraint Programming：CP）による高速な計算

このモデルを実際のデータに適用したところ、実際のマッチング結果よりも少なくとも同等以上に望ましいマッチング結果を得ることができました。また、一部の制約を緩和することで待機児童を更に減少できることを確認しました。

また、本論文はSun et al. [2]を発展させた論文です。保育所入所選考の問題意識や難しさについては、Sun et al. [2]を解説したブログに詳しく記載していますので、あわせてご覧ください。

これまでの保育所入所選考に関する研究

日本の保育所入所選考における待機児童問題は、社会的な問題として注目されており、国や自治体において待機児童対策が進められています。この問題の解決策のひとつとして、資源の最適な配分を考える学問であるマッチング理論を適用することが考えられます。実際に、マッチング理論を用いた保育所入所選考について、いくつかの研究があります。

Okumura[3]とKamada and Kojima[4]は、待機児童を最大限削減するため、異年齢間で定員を融通することを提案しました。例えば、保育所では、1歳や2歳について募集人数の余裕がなく、多くの待機児童が存在している一方、4歳や5歳については募集人数に余裕がある場合が存在します。これらの研究では、ある年齢にて余剰となっている保育士や面積といった資源を、募集人数に余裕のない年齢に振り分けることで、全体の待機児童を減少させるアルゴリズムが提案されています。しかし、これらの研究では、

• きょうだい同時申し込みに対応していない
• 転園を希望する場合に対応していない

という問題があり、これらのアルゴリズムを保育所入所選考の実務にそのまま適用することはできませんでした。

Sun et al. [2]では、線形計画法の一種である整数計画法を用いて、以下のようなマッチングを導く方法を提案しました。

• 3人までのきょうだい同時申し込みに対応
• 転園にも対応
• 以下の性質を満たす
  • 個人合理性：希望していない保育所に割り当てない
  • 公平性：優先順位が高い人を優先して割り当てる
  • 非浪費性：「その保育所を希望する応募者がいるにもかかわらず受け入れ枠に空きがある状況」（浪費的な状況）をつくらない

しかし、この研究には、以下のような問題がありました。

• 4人以上のきょうだい同時申し込みに対応していない
• 異年齢間の定員共有に対応していない

異年齢間の定員共有を行っている保育所では、例えば4歳と5歳で合計5名まで受け入れ可能、という具合に、異年齢間で定員を共有しています。このような保育所がある自治体では、4歳と5歳の児童を年齢に関係なく優先順位が高い順にその保育所へとマッチングさせる必要があります。また、こういった保育所が複数存在している自治体では、入所選考が複雑になります。

この論文の貢献

そこで、本論文ではSun et al. [2]の制約をクリアする新たなアルゴリズムを提案しました。本論文による貢献は次の通りです。

• 以下の性質を満たすマッチング方法（この記事では「CPモデル」と呼ぶことにします）の提案
  • 個人合理性、安定性（公平性と非浪費性）を満たす
  • きょうだい同時申し込みの人数制限がない
  • 異年齢間の定員共有ができる
• CPモデルによるシミュレーション
  • CPモデルによるマッチング結果と実際のマッチング結果とを比較すると、実際の割り当てよりも少なくとも同等以上に望ましいマッチング結果が得られる
  • 制約を緩和することによってマッチングできる児童が増える
• 制約プログラミング（CP）によるモデリングおよび高速化
  • NP困難である保育所マッチング問題に対して、CPを使うことで高速化を実現
• 計算複雑性に関する問題
  • 初期配分と異なる、実現可能で個人合理的なマッチングが存在するかどうかチェックすることが、NP完全であることを示した

以下では、CPモデルによるマッチング結果、および制約を緩和することで達成できるマッチング結果について解説します。

CPモデルによるマッチング結果

本論文で提案しているCPモデルによるマッチング結果と、自治体における実際のマッチング結果とを比較します。

ここでは、東京都渋谷区と多摩市（それぞれ2021 年度と 2022 年度の一斉入所）、および福島県郡山市から提供された 2022 年度の一斉入所のデータ（匿名加工処理済み）を利用しています。マッチした児童数は保育所に内定した児童の数です。また、ブロッキング連合の数についてもカウントしています。ブロッキング連合があると、ある児童にとってより望ましい保育所に入所できた可能性があることを示しており、これがゼロであれば公平なマッチングが実現できていると言えます。

	多摩市2021		多摩市2022		渋谷区2021		渋谷区2022		郡山市2022
	実際	CP	実際	CP	実際	CP	実際	CP	実際	CP
マッチした児童数	558	560	464	470	1307	1307	1087	1087	979	1200
ブロッキング連合の数	26	0	2	0	0	0	0	0	1059	0

表1 実際のマッチング結果（実際）とCPモデルによるマッチング結果（CP）との比較

 

表1は、各自治体における実際のマッチング結果とCPモデルのマッチング結果を比較したものです。この表から、CPモデルについて次のことが言えます。

• 各自治体で実際のマッチング結果と少なくとも同等以上に望ましいマッチングを達成できた
  • 渋谷区においては、実際のマッチングと同一の結果が得られた
  • それ以外の多摩市と郡山市においては、CPモデルを用いることで実際の結果よりも多く児童をマッチングできた。
• 公平なマッチングが実現できている
  • CPモデルではブロッキング連合が存在しないため、公平なマッチングが実現できていると言える

待機児童をさらに減少させるために

本論文では、CPモデルを用いてさらに待機児童を減少させるために、3つの案を示しています。

1. 同点解消をせず、無差別に取り扱う
2. ブロッキング連合を許容する
3. 異年齢間の定員共有をさらに許容する

1については、後述します。

2については、ブロッキング連合を許容することで、待機児童数を減少できることがシミュレーションでわかりました。しかし、公平なマッチングが実現できなくなる、計算時間が増えるという欠点があります。

3については、異年齢間の定員共有を許容することで、待機児童数が減ると期待されます。しかし、我々が保有するデータのうち、定員共有を許容しているデータではサイズが小さく、シミュレーションでは明確なことが言えませんでした。

同点を解消せず、同点者を無差別に取り扱うと、待機児童数は減少する

多くの自治体では、就労状況や世帯状況を指数化し、指数が高い児童から順に割り当てています。この際、指数が同点になることもあります。例えば、郡山市[5]では1月140時間以上の就労で200点加算され、育児休業明けだとさらに30点加算されます。つまり、両親ともにフルタイム勤務で育児休業明けの場合、合計430点となります。しかし、同様の世帯状況である申込者は多く、同じ点数の申込者が多数存在することが予想されます。

自治体はこのような事態を想定し、同点者に対してタイブレークするルールを設けています。郡山市では、「満3歳に達する日以後の最初の3月31日までを対象年齢とする保育施設等を満了する入所児童が連携施設を希望している場合」、「現に認定こども園を1号認定で利用している入所児童が、同施設で2号認定での利用を希望している場合」、「類型間の優先順位」、「養育している小学生以下の子どもの人数が多い世帯」、「経済的状況」…の順に優先することとなっています。

ここで、実際のルールを一旦無視して、タイブレークを行わず、同点者を無差別に取り扱った場合のシミュレーションを実施します。このCPモデルには、同点者に差をつけず、無差別に取り扱うことができる機能があるため、これを利用してシミュレーションを実施しました。このとき、個人合理性と安定性は保持されています。

表2では、各自治体データを用いて、CPモデルによるマッチング結果と、タイブレークせず同点者を無差別に取り扱ったCPモデルによるマッチング結果とを比較しています。

	多摩市2021		多摩市2022		渋谷区2021		渋谷区2022		郡山市2022
	CP	CP無差別	CP	CP無差別	CP	CP無差別	CP	CP無差別	CP	CP無差別
マッチした児童数	560	571	470	478	1307	1335	1087	1135	1200	1217
計算時間	9.6秒	12.5秒	1.7秒	3.0秒	18.1秒	1000秒	11.6秒	803秒	18.5秒	24.1秒

表2 CPモデルによるマッチング結果（CP）と、タイブレークせず同点者を無差別に取り扱ったCPモデルによるマッチング結果（CP無差別）の比較

表2では、同点者を無差別に扱うCP無差別において、いずれのデータでもマッチした児童の数が増加しています。CPモデルは最大限に待機児童を減らすという目的のもとでマッチングしています。同点者を無差別に扱うことにより、マッチングの自由度が増し、その結果マッチした児童の数が増えています。ただし、渋谷区2021の例のように、計算時間が大きく増加する可能性もあります。

社会実装に向けて

AI LabとGovTech開発センターは、本論文で示されたアルゴリズムを用いた自治体向け保育所入所選考システムを開発しており、自治体に提供することができます。

研究に基づいた保育所入所選考システムや、待機児童減少に向けた取り組みにご興味のある自治体の方はこちらからご連絡をください。

 

参考文献

[1] Sun, Z., Yamada, N., Takenami, Y., Moriwaki, D., & Yokoo, M. (in press) ”Stable Matchings in Practice: A Constraint Programming Approach”, AAAI, Thirty-Eighth AAAI Conference on Artificial Intelligence.

[2] Sun, Z., Takenami, Y., Moriwaki, D., Tomita, Y., & Yokoo, M. 2023. Daycare Matching in Japan: Transfers and Siblings. Proceedings of the AAAI Conference on Artificial Intelligence, 37(12), 14487-14495.

[3] Okumura, Y. 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.

[4] Kamada, Y.; and Kojima, F. 2023. Fair matching under constraints: Theory and applications. The Review of Economic Studies.

[5] 福島県郡山市. 2023. 郡山市保育施設等の利用調整及び保育の必要性の認定に関する事務取扱要領 https://www.city.koriyama.lg.jp/uploaded/attachment/69154.pdf