DEIM Forum 2023 5a-6-3

二部グラフにおける選好の拡張手法について
田邉 優斗†

鈴木 伸崇††† 筑波大学情報学群知識情報・図書館学類 〒 305–8550 茨城県つくば市春日 1-2†† 筑波大学図書館情報メディア系 〒 305–8550 茨城県つくば市春日 1–2
E-mail: †s1911504@s.tsukuba.ac.jp, ††nsuzuki@slis.tsukuba.ac.jp
あらまし

本研究では，不完全な選好を許す学校選択問題について着目する．不完全な選好では，生徒は一部の学校を選好に選ばなくても良く，生徒の選好の選択の負担を軽減することができる．しかし，選好に含まれていない学校には割り当てられないため，マッチングのサイズが減少する可能性がある．そのため本稿では，現実の学校選択制を運営する組織における生徒と学校のマッチングを調査し，不完全な選好による影響を調査した．また，ランダムに生成された選好によるマッチングを行うことで，選好のサイズによってどの程度割り当てられなかった生徒が生じるか実験を行った．その結果から，公平性を維持しながら学校選択制を運営する組織の負担を軽減するために，割り当てられなかった生徒を割り当てる選好の拡張手法を提案した．
キーワード マッチング理論，マーケットデザイン，学校選択問題
つに，ニューヨーク市やボストン市における公立学校の学校選

1 はじめに
世の中の多くの問題は「マッチング問題」として捉えることができる．例えば，就職活動は就活生と企業のマッチング，入試は学生と学校のマッチング，結婚や保活などもマッチング問
題として捉えることができる．
「マッチング理論」とは，マッチング問題において，適材適所の組み合わせを考える学問のことを指す．マッチング理論を利用してマッチング問題を解決するには，大きく分けて二つの作業が必要になる．一つ目は，参加者にマッチ相手に関する選好（第一希望，第二希望，…）を聞
いてデータを得ること．二つ目は，適したアルゴリズムを用いて「良い」マッチングを見つけることである [1]．
特に「良い」マッチングの基準として重要視されているのが「安定性」である．安定性を考慮したマッチング問題として代表的なものに「安定結婚問題」がある．この問題は，1962 年にDavid Gale 氏と Lloyd Shapley 氏によって提案された [2]．安定結婚問題では，かけおちするようなペアが存在しない「安定マッチング」を求める．かけおちするペアは，マッチしていな
い男性と女性で，お互いに今のマッチ相手よりも希望順位が高いペアのことである．安定マッチングを効率よく見つけることができるアルゴリズムとして，Gale-Shapley アルゴリズムが知られている [2]．アルゴリズムの動作内容から受け入れ保留ア
ルゴリズムとも呼ばれている（以降は受け入れ保留アルゴリズ
ムと記すことにする）．
アメリカでは「マーケットデザイン」という分野の研究が行われており，これはマッチング理論を応用して現実の社会制度をどのように設計すると上手くいくのかを研究するものである．

2012 年のノーベル経済学賞は，マッチング理論とマーケットデ
ザインにおける功績で，ハーバード大学の Alvin Roth 教授とカルフォルニア大学ロサンゼルス校の Lloyd Shapley 名誉教授に贈られた．そのうちの一人である Alvin Roth 氏の実績の一択制を学校と生徒のマッチングと捉え，受け入れ保留アルゴリ
ズムを応用した制度設計を行ったものがある．現在ではアメリカの多くの都市で Alvin Roth 氏と共同研究者たちによって提案された方式が採用されている [8]．学校選択制とは，生徒が進学する公立小学校や中学校を，従来の通学区域に縛られることなく，選択肢の中から保護者が選択できるようにした制度のことである [4]．日本でも 1998 年に三重県南牟婁郡紀宝町が学校選択制を導入したのをきっかけに，全国での導入が進んでいった．[7]．
本研究では，不完全な選好を許す学校選択問題における問題について考える．学校選択問題とは，既存の学校選択制を制度設計問題として捉えたもので，有名なものに Atila Abdulkadiroğlu
氏と Tayfun Sönmez 氏によって定式化された学校選択モデルがある [9]．安定結婚問題では参加者は一対一でのみマッチングができたが，学校選択問題では各学校は複数の生徒とマッチすることができるため，安定結婚問題のような一対一マッチングに対して，多対一マッチングと呼ばれる．学校選択問題でも安定結婚問題で使用される，受け入れ保留アルゴリズムを用いることで，安定マッチングを得ることができる．実際に，アメリカのニューヨーク市やボストン市における学校選択制の制度は，受け入れ保留アルゴリズムを用いたものに変更された [4]．実際の学校選択制では「不完全な選好」を許すことがある．不完全な選好では，生徒は一部の学校を選好に選ばなくても良く，生徒の選好を選ぶ負担を軽減することができる．しかし，選好に上げていない学校には割り当てられないため，マッチングのサイズ（成立しているペアの数）が減少してしまう可能性がある．
そこで，実際の学校選択制を運営する組織における生徒と学校のマッチングを調査し，不完全な選好による影響を調査した．
具体的には，学校選択制において，受け入れ保留アルゴリズムと同様のアルゴリズムを用いていおり，生徒に不完全な選好を許している SFUSD（San Francisco Uniﬁed School District）

における生徒の割り当てを調査した．また，学校選択モデルを，生徒に不完全な選好を許すよう拡張したアルゴリズムを実装し，

表2
男性

マッチング M1

選好

女性

選好

1

",

$,

%,

&,

'

%

4,

1,

3,

2,

5

2

%,

',

",

&,

$

'

5,

1,

2,

3,

4

3

%,

&,

",

$,

'

"

2,

3,

1,

5,

4

り当てられなかった生徒が生じるか実験を行った．その結果，

4

',

$,

&,

%,

"

&

3,

4,

2,

5,

1

条件によっては生徒に十分な選好を用意させることが困難であ

5

&,

%,

$,

',

"

$

3,

1,

5,

2,

4

SFUSD と同様の条件において，ランダムに生成した選好によるマッチングを行うことで，選好のサイズによってどの程度割ることが分かった．そこで，公平性を保ちながら，学校選択制[3] を参考に作成

を運営する組織の負担を軽減するために，割り当てられなかった生徒を割り当てる選好の拡張手法を提案した．

あるマッチング M において，男性 m と女性 w がペアになっていることを M (m) = w や M (w) = m として表せる．マッ2 諸 定 義チング M において，男性 m と女性 w がペアになっておらず，本章では，マッチング，学校選択問題について述べる．

男性 m が今のペアである M (m) よりも女性 w を好んでおり，
女性 w も今のペアである M (w) よりも男性 m を好むとき，男

2. 1 マッチングとは性 m と女性 w がかけおちする可能性がある．男性 m と女性 w

世の中の多くの問題は「マッチング問題」として捉えることのようなペアのことを「ブロッキングペア」と呼ぶ．ブロッキができる．例えば，就職活動は就活生と企業のマッチング，入ングペアはマッチングを壊してしまう可能性を持っており，ブ

試は学生と学校のマッチング，結婚や保活などもマッチング問

ロッキングペアが存在しないマッチングを「安定マッチング」

題として捉えることができる．
「マッチング理論」とは，マッチと呼ぶ．表 2 では，男性 1 は今のペアである女性 a よりも女性ング問題において，適材適所の組み合わせを考える学問のこと

e を好んでおり，女性 e も今のペアである男性 5 よりも男性 1を指す．マッチング理論を利用してマッチング問題を解決するを好んでいるため，男性 1 と女性 e はマッチング M1 におけるには，大きく分けて二つの作業が必要になる．一つ目は，参加

ブロッキングペアであり，マッチング M1 は安定マッチングで者にマッチ相手に関する選好（第一希望，第二希望，…）を聞はないことが分かる．

いてデータを得ること．二つ目は，適したアルゴリズムを用いて「良い」マッチングを見つけることである [1]．

安定結婚問題において，どのような入力に対しても安定マッ
チングが存在することが分かっている．しかし，同数（n 人）

特に「良い」マッチングの基準として重要視されているのがの男性と女性のマッチングの場合はマッチングが n! 通り存在し「安定性」である．安定性を考慮したマッチング問題として代ており，一つずつ確認して安定マッチングを見つけるためには表的なものに「安定結婚問題」がある．この問題は，1962 年に非常に時間がかかってしまう．そこで，安定マッチングを効率David Gale 氏と Lloyd Shapley 氏によって提案された [2]．以

よく見つけることができるアルゴリズムとして，Gale-Shapley

下に，安定結婚問題の最も基本的な定義を述べる [3]．

アルゴリズムが知られている [2]．アルゴリズムの動作内容から

表1
男性

受け入れ保留アルゴリズムとも呼ばれている（以降は受け入れ

入力例 I1 （左から好みの順）
選好

女性

保留アルゴリズムと記すことにする）．以下では，受け入れ保

選好

1

",

$,

%,

&,

'

%

4,

1,

3,

2,

5

2

%,

',

",

&,

$

'

5,

1,

2,

3,

4

3

%,

&,

",

$,

'

"

2,

3,

1,

5,

4

4

',

$,

&,

%,

"

&

3,

4,

2,

5,

1

5

&,

%,

$,

',

"

$

3,

1,

5,

2,

4

留アルゴリズムの動作を簡単に説明する [3]．
まず，全ての男性と女性が誰ともペアになっていない状態とする．次に，誰ともペアになっていない男性が存在する限り，次の操作を繰り返し行う．誰ともペアになっていない男性を一人選ぶ．その男性が一番好んでいる女性に対してプロポーズす[3] を参考に作成

る（既にプロポーズした女性を除く）．このとき，プロポーズした女性が誰ともペアになっていない場合は，その女性とペアに安定結婚問題の入力例は，同数（以降は n 人とする）の男性と女性と，各参加者の選好からなる．ここで言う選好とは，各参加者が異性を好みの順に並べたリストのことである．表 1 の
入力例 I1 では，n = 5 の男性と女性がおり，男性を 1〜5，女
性を a〜g としている．ここで，各参加者の選好は左から好みの順で並んでいる．例えば，男性 1 は，女性 c を一番好んでおり，その次に女性 e, a, d, b の順で好んでいる．安定結婚問題におけるマッチングは n 組の男性と女性のペアからなる集合であり，各参加者は一人の相手としかペアになることができない．
例えば，M1 = (1, a), (2, b), (3, c), (4, d), (5, e) はマッチングである．表 2 では，各参加者の選好の中でペアになった相手を丸で囲っている．

なる（この時点ではペアを確定させない）．プロポーズした女
性が既に誰かとペアになっている場合，女性は今ペアになっている男性と新たにプロポーズしてきた男性を比較する．このとき，女性が今ペアになっている男性より，新たにプロポーズしてきた男性を好む場合，今のペアを解消し新たにプロポーズしてきた男性とペアになる．逆に，女性が新たにプロポーズしてきた男性より，今ペアとなっている男性を好む場合，今のペアを維持する．最後に，誰ともペアになっていない男性がいなくなった時点でペアを確定させ，最終的なペアの集合を安定マッ
チングとして出力する．
表 1 の入力例 I1 に対して受け入れ保留アルゴリズムを行っ表3
男性

品川区と豊島区が，2001 年に長野県松本市と東京都日野市が，安定マッチング M2

選好女性

2002 年に東京都足立区と江東区，広島県安芸郡熊野町が学校

選好

1

",

$,

%,

&,

'

%

4,

1,

3,

2,

5

2

%,

',

",

&,

$

'

5,

1,

2,

3,

4

3

%,

&,

",

$,

'

"

2,

3,

1,

5,

4

4

',

$,

&,

%,

"

&

3,

4,

2,

5,

1

われており，これはマッチング理論を応用して現実の社会制度

5

&,

%,

$,

',

"

$

3,

1,

5,

2,

4

をどのように設計すると上手くいくのかを研究するものであ[3] を参考に作成

選択制の導入に踏み切った [7]．
アメリカでは「マーケットデザイン」という分野の研究が行る．2012 年のノーベル経済学賞は，マッチング理論とその応用分野であるマーケットデザインにおける功績で，ハーバード大てみる．まず，全ての男性と女性が誰ともペアになっていない状態とする．次に，誰ともペアになっていない男性の中から男性 1 を選び，男性 1 が一番好んでいる女性 c にプロポーズする．
女性 c は誰ともペアになっていないため，男性 1 と女性 c がペアになる（この時点ではペアを確定させない）．次に，男性 2が女性 a にプロポーズする．女性 a は誰ともペアになっていな
いため，男性 2 が女性 a とのペアになる．以下同様に行っていくと，表 3 に示す安定マッチング M2 が得られる．各参加者の選好の中でペアになった相手を丸で囲っている．
受け入れ保留アルゴリズムを利用することで安定マッチングを得られることが分かった．しかし，得られた安定マッチング
は一つの入力例に対して複数存在する安定マッチングのうちの一つであり，必ずしも全ての参加者にとって最適なものではな
いことに注意する必要がある．例えば，表 3 の安定マッチング

M2 は男性からプロポーズして得られる安定マッチングであり，男性の選好が優先されているため必ずしも女性にとって良いマッチングであるとは言えない．このような安定マッチングは「男性最適安定マッチング」と呼ばれている（女性からプロポー
ズする女性最適安定マッチングも存在する）．安定結婚問題のように 2 つのグループを対等に扱わなければならない場合，片方が優遇されるようなアルゴリズムを現実の社会制度に応用す
ると倫理的に問題が生じてしまう．学校選択問題の場合，学校よりも生徒を優遇するようなケースが多く，生徒からプロポー
ズする「生徒最適安定マッチング」を採用していることが多い．

2. 2 学校選択問題とは学の Alvin Roth 教授とカルフォルニア大学ロサンゼルス校のLloyd Shapley 名誉教授に贈られた．Alvin Roth 氏の主な功績は，マッチング理論の経済学的な価値に気づき，その理論を社会問題解決のために応用・展開させたことにある．その実績の一つに，ニューヨーク市やボストン市における公立学校の学
校選択制を学校と生徒のマッチングと捉え，受け入れ保留アル
ゴリズムを応用した制度設計を行ったものがある．現在ではアメリカの多くの都市で Alvin Roth 氏と共同研究者たちの方式が採用されている [8]．
学校選択問題とは，既存の学校選択制を制度設計問題として捉えたもので，有名なものに学校選択モデルがある．Atila

Abdulkadiroğlu 氏と Tayfun Sönmez 氏によって定式化された
学校選択モデルでは，『学校選択問題では，生徒がおり，各生徒
は学校のうちの 1 校に座席を割り当てる必要がある．各学校には定員があるが，全体の定員数に不足はない．各生徒はすべての学校に対して厳密な選好を持っており，各学校はすべての生徒に対して厳密な優先順位を持つ．ここで，優先順位は学校の好みではなく，州や地域の法律で決められている．例えば，いくつかの州では，ある学校にすでに通っている兄弟がいる生徒
は，教育法によってその学校に優先的に入学できることになっている．同様に，学校から歩いて行ける距離に住んでいる生徒が優先される．各学校では，通常，各関連項目が同じ生徒同士の優先順位は，抽選で決定される．
』（訳は引用者による）とされている [9]．以上からマッチング理論を利用するために必要となる要素を抜き出すと以下の 5 つとなる．
（ 1 ） 生徒の集合

学校選択制とは，生徒が進学する公立小学校や中学校を，従（ 2 ） 学校の集合

来の通学区域に縛られることなく，選択肢の中から保護者が選（ 3 ） 各学校の定員択できるようにした制度のことである．1980 年代後半から様々（ 4 ） 各生徒のすべての学校に対する厳密な選好な国で導入されるようになり，多くの国で学校選択制に関する（ 5 ） 各学校のすべての生徒に対する厳密な選好議論が為されてきた [4]．

安定結婚問題が男性と女性のマッチングで，各参加者は一人と日本では，学校教育法施行令第 5 条第 2 項によって，それぞしかマッチできなかったのに対して，学校選択問題は各学校はれの学校には通学区域が設定され，これに基づき各生徒は就学複数の生徒とマッチすることができるため，安定結婚問題のよすべき学校を指定されていた [5]．しかし，1997 年に文部省初

うな一対一マッチングに対して，多対一マッチングと呼ばれる．

等中等教育局から各都道府県の教育委員会に対して「通学区域安定結婚問題では，受け入れ保留アルゴリズムを用いることで制度の弾力的運用について（通知）」が出されたことにより，地安定マッチングを得ることができた．学校選択問題でも，受け理的な理由や身体的な理由，いじめへの対応を理由とする場合

入れ保留アルゴリズムを用いることで安定マッチングを得るこ以外にも，生徒の個人的な事情にも配慮して学校を選択できるとができるが，安定結婚問題で使用されるものを少し拡張する

ように変化していった [6]．

必要がある．安定結婚問題では，ある男性がプロポーズした女1998 年に三重県南牟婁郡紀宝町が学校選択制を導入したの性が既に他の男性とペアになっている場合，その女性は新たにをきっかけに，全国での導入が進んでいった．2000 年に東京都

プロポーズしてきた男性と今ペアになっている男性を比較していたが，学校選択問題では，各学校に定員があり，定員を上回らない限りプロポーズしてきた生徒とペアを組む．定員を上

表4

入力例 I2 （左から好みの順）回った場合は，学校は今ペアを組んでいる生徒の中で，一番優生徒先度が低い生徒と新たにプロポーズしてきた生徒を比較するよ

1

%,

",

'

2

',

",

3

",

4

の制度は，2000 年代に入ってから経済学者による助言に基づき受け入れ保留アルゴリズムを用いたものに変更された [4]．それ

うにする．
アメリカのニューヨーク市やボストン市における学校選択制

選好

学校

選好

%(")

1,

2,

3,

4,

5,

6

%

'(")

6,

5,

4,

3,

2,

1

%,

'

"(")

6,

5,

4,

3,

2,

1

",

%,

'

5

",

',

%

6

",

',

%

までボストン市で使われていた「ボストンアルゴリズム」と呼ばれるアルゴリズムは，受け入れ保留アルゴリズムより単純なものであった．受け入れ保留アルゴリズムでは，今ペアとなっている相手がいても，より好む相手がプロポーズしてきた場合ペアを変更していたが，ボストンアルゴリズムでは，一度ペアになったらその時点でペアを確定させてしまう．ボストンアル
ゴリズムでは安定性を満たさない上に，「対戦略性」がなかった．
そのため，参加者が選好を偽ることで自身がより良い学校に割り当てられるようになる可能性があった．例えば，一番行きたい学校が人気である場合，正直な選好を提出してしまうと高い

前に決められた基準に基づいて優先度順で並べたリストのことである．表 4 の入力例 I2 では，6 人の生徒と，定員が 2 人の学校が 3 校あり，生徒を 1〜6，学校を a〜c としている．ここで，それぞれの選好は左から好みの順で並んでいる．また，それぞれの学校の定員数を学校名の右下に示す．例えば，生徒 1
は，学校 a を一番好んでおり，その次に学校 c, b の順で好んでいる．
表5

安定マッチング M3 （生徒側が完全な選好の場合）

確率でその学校に割り当てられず，そのステップで第二希望の生徒

学校も定員が埋まってしまう可能性がある．そこで選好を偽り，

1

%,

",

'

%(")

1,

2,

3,

4,

5,

6

二番目に行きたい学校を選好の一番目にすることでその学校に

2

',

",

%

'(")

6,

5,

4,

3,

2,

1

3

",

%,

'

"(")

6,

5,

4,

3,

2,

1

4

",

%,

'

5

",

',

%

6

",

',

%

割り当てられることができ，正直な選好を提出するよりも良い学校に割り当てられる可能性が生まれる．ボストンアルゴリズ
ムから受け入れ保留アルゴリズムへの変更により，生徒は選好

選好

学校

選好

を偽る必要がなくなった．

3 不完全な選好を許す学校選択問題

表 4 の入力例 I2 に対して受け入れ保留アルゴリズム（学校選択問題のために拡張したもの）を行ってみる．まず，すべて本章では, 不完全な選好を許す学校選択問題において，選好の生徒と学校がペアとなっていない状態とする．次に，どの学のサイズを変化させた場合に，割り当てられなかった生徒の人

校ともペアになっていない生徒の中から生徒 1 を選び，生徒 1

数にどのような影響があるか調べる．

が一番好んでいる学校 a にプロポーズする．学校 a は誰とも3. 1 問 題 提 起
実際の学校選択制では，Atila Abdulkadiroğlu 氏と Tayfun

Sönmez 氏によって定式化された学校選択モデルにおける「各生徒はすべての学校に対して厳密な選好を持つ．
」という定義を完全に満たすことが困難である．学校選択モデルでは，各生徒
はすべての学校に順位付けを行う必要があるが，学校の数に比ペアになっていないため，生徒 1 と学校 a がペアとなる（この時点ではペアを確定させない）．次に，生徒 2 が学校 b にプロポーズする．学校 b は誰ともペアになっていないため，生徒 2と学校 b がペアとなる．以下同様に行っていくと，表 5 に示す
安定マッチング M3 が得られる．それぞれの選好の中でペアになった相手を丸で囲っている．

例して生徒の選好を用意する負担が大きくなってしまう．そこ

表6

入力例 I3 （左から好みの順）

で実際の学校選択制では「不完全な選好」を許すことで，生徒生徒の負担を軽減している場合がある．不完全な選好では，各生徒

1

%,

"

%(")

1,

2,

3,

4,

5,

6

2

',

"

'(")

6,

5,

4,

3,

2,

1

3

",

%

"(")

6,

5,

4,

3,

2,

1

4

",

%

5

",

'

6

",

'

は一部の学校を選好に書かなくても良い．しかし，選好に上げていない学校には割り当てられないため，マッチングのサイズ（成立しているペアの数）が減少してしまう可能性がある．
「各
学校はすべての生徒に対して厳密な優先順位を持つ．
」という

選好

学校

選好

定義もあるが，学校は事前に決められた基準に基づいてすべての生徒に対する優先順位が決まるため，選好を用意する負担はない．
学校選択問題の入力例は，生徒の集合と，学校の集合と，それぞれの選好からなる．ここで言う選好とは，生徒側では学校を好みの順で並べたリストのことであり，学校側では生徒を事

表 4 の入力例 I2 では，各生徒はすべての学校に順位付けを行っていたため，すべての生徒が選好にある学校に割り当てられた．ここで，各生徒に対して不完全な選好を許した場合を考えてみる．表 6 の入力例 I3 では，6 人の生徒と，定員が 2 人の学校が 3 校あり，生徒を 1〜6，学校を a〜c としている．生徒は不完全な選好を許されており，3 校の中から 2 校に順位付に Transitional Kindergarten を加えたもの）において，学校けを行い選好として提出するだけでよい．それぞれの選好は左選択制を利用した 13, 708 人の生徒の中で，57 ％の生徒が第 1から好みの順で並んでいる．また，それぞれの学校の定員数を希望の学校に合格しており，約 80 ％の人が第 1 希望から第 3

学校名の右下に示す．例えば，生徒 1 は，学校 a を一番好んで希望の学校に合格している．しかし，12 ％の生徒が選好の中のおり，その次に学校 c を好んでいる．

どの学校にも割り当てられず，定員の余っている学校のうち一

表7

安定マッチング M4 （生徒側が不完全な選好の場合）

生徒

選好

学校

番近い学校に割り当てられたことが分かる [12]．

3. 2 実 験 方 法

選好

1

%,

"

%(")

1,

2,

3,

4,

5,

6

2

',

"

'(")

6,

5,

4,

3,

2,

1

3

",

%

"(")

6,

5,

4,

3,

2,

1

4

",

%

で，生徒側の選択肢が多い ES の K grade に注目する．Main

5

",

'

Round 2022 Program Requests by Seat によると，2022-23 年

6

",

'

TK-12 の中でも grade によって生徒の割り当ては分かれているため，今回は SFUSD の行っている生徒の割り当ての中度に新たに ES の K grade に割り当てられた生徒は 4, 023 人であった．K grade の生徒を募集している ES は 71 校あり，プ

表 6 の入力例 I3 に対して受け入れ保留アルゴリズム（学校選択問題のために拡張したもの）を行ってみる．表 7 に示す
安定マッチング M4 が得られる．それぞれの選好の中でペアになった相手を丸で囲っている．生徒 4 は学校 c と学校 a にプロポーズしているが，どちらとも生徒 4 よりも優先順位の高い生徒で定員が埋まっており割り当てらなかった．その結果，生徒

4 はどの学校ともペアになっておらず，学校 b は定員が 2 人であるが 1 人としかペアになっておらず定員を余らせてしまった．
不完全な選好を許した場合は，生徒の選好を用意する負担を減

ログラムによって定員が分かれているため，生徒には 154 の選択肢があることになる．それぞれの選択肢には平均で 27.9 人の定員があり，合計 4, 304 人の定員があった．Main Round 2022

Choice Results by Rank によると，285 人（全体の 7.1 ％）の生徒が選好の中のどの学校にも割り当てられず，定員の余っている学校のうち一番近い学校に割り当てられたことが分かる [12]．
ここで，可能な限り SFUSD におけるマッチングと同様の条件を用意した上でマッチングを行い，不完全な選好によって生じらすことができるが，選好の中のどの学校ともペアになれない

る問題について調査を行うことを考える．Student Assignment

生徒が生じてしまう可能性が生じ，生徒余っているにも関わらPolicy や Annual Enrollment Highlights などの公開されていず定員を余らせる学校が生じる可能性があることが分かる．
学校選択制の制度に受け入れ保留アルゴリズムと同様のアルゴリズムを用いており，不完全な選好を許している具体例として，SFUSD（San Francisco Uniﬁed School District）における生徒の割り当てを取り上げる．SFUSD は，カリフォルニア
州で 7 番目に大きな学区で，毎年 57, 000 人以上の生徒を教育している [10]．日本の義務教育制度では，小学校 6 年間と中学校 3 年の合計 9 年間となっているが，アメリカでは，K-12 と呼ばれる義務教育制度が行われている．K-12 とは Kindergartenの K とその後の 12 年間の義務教育期間を表ている．まず ES（Elementary School）へ，5 歳ごろに K grade として入学することができ，その後，1st grade から 5th grade まで毎年上
がっていき，10 歳ごろに卒業する．次に MS（Middle School）
へ，11 歳ごろに 6th grade として入学することができ，8th

grade まで毎年上がっていき，13 歳ごろに卒業する．HS（High
School）へ，14 歳ごろに 9th grade として入学することがで
き，12th grade まで毎年上がっていき，18 歳ごろに卒業する．

SFUSD のような組織では，主に ES，MS，HS への入学時に生徒を学校に割り当てる業務を行っている．

SFUSD では生徒に対して不完全な選好を許しており，最低でも 5 校以上の学校を選好として提出するように求めている．
また，割り当てられなかった生徒は，定員の余っている学校のう
ち一番近い学校に割り当てることになっている [11]．SFUSD は
毎年 Annual Enrollment Highlights を公開しており，2022-23

Main Round Assignment Highlights によると TK-12（K-12

る情報から，マッチングに必要となる要素を抜き出すと以下の5 つとなる [11], [12]．
（ 1 ） 生徒の合計数は 4, 023 人（ 2 ） 学校の合計数は 150 校（定員が 0 人だった 4 つの選択肢を除いた数）（ 3 ） 各学校の定員は Main Round 2022 Program Requests

by Seat と同様のもの（ 4 ） 各生徒の選好は 1〜10 校（最低でも 5 校以上の学校を選好として提出するように推奨されている）（ 5 ） 各学校はすべての生徒に対する厳密な選好を持っている
一つ目の要素については，Main Round 2022 Program Re-

quests by Seat から ES の K grade において割り当てられた生徒の合計数を利用する．二つ目の要素については，Main Round2022 Program Requests by Seat から ES で K grade の生徒を募集している学校は 71 校であるが，プログラムによって定員が分かれているため 154 の選択肢があることになる．さらに，SFUSD では同じ学校でも違うプログラムであれば選好に含むことができるため，本実験では，定員が 0 人であった 4 つの選択肢を除いた 150 の選択肢を学校として扱う．三つ目の要素については，Main Round 2022 Program Requests by Seat
から ES で K grade の生徒を募集している学校の定員を利用する．四つ目の要素については，Student Assignment Policy
で SFUSD は生徒に対して不完全な選好を許しており，最低でも 5 校以上の学校を選好として提出するように推奨されていることから，選好のサイズ（選好に含める学校の数）による影響表8を調査するため，各生徒の選好を 1〜10 校とする．以上の条件

選好のサイズ

第1希望

12946 73.22%

22519 62.60%

945 23.48%

32303 57.25%

987 24.54%

422 10.48%

42167 53.87%

1002 24.90%

462 11.49%

213 5.29%

52080 51.71%

1007 25.03%

486 12.08%

234 5.82%

112 2.79%

103 2.56%

62025 50.35%1008 25.05%

500 12.44%

248 6.16%

123 3.05%

58 1.45%7

1994 49.56%

1007 25.04%

509

12.64%

256 6.36%

129 3.20%

32 0.79%

81975 49.08%

1007 25.04%

513 12.75%

261 6.49%

132 3.29%

17 0.43%91965 48.84%

1007 25.04%

515 12.81%

263 6.54%

134 3.34%

9 0.22%

101959 48.69%

1007 25.04%

517 12.85%

265 6.58%

135 3.36%

5 0.12%のもと，各生徒の選好と各学校の選好をランダムに生成し，学校選択問題と不完全な選好に対応させた，受け入れ保留アルゴ
リズムを用いてマッチングを行う．

SFUSD では，学校からプロポーズする受け入れ保留アルゴ
リズムに近いものを採用しているが，本実験では，生徒から学校からプロポーズする受け入れ保留アルゴリズムを用いる．

SFUSD で用いられているアルゴリズムと違い生徒の選好が優ランダムに生成した選好による生徒の割り当て結果
第2希望

第3希望

第4希望

第5希望

選好外
1077 26.78%
560 13.92%
311 7.72%
179 4.45%

先されるため，より生徒の希望が通りやすくなると考えられるが， 「Rural Hospitals Theorem」という有名な定理によって，

表 9 2022-23 Main Round における生徒の割り当て結果

生徒の集合 S は，すべての安定マッチングでいずれかの学校に割り当てられる集合 S1 と，すべての安定マッチングにおいてどの学校にも割り当てられない集合 S2 に分けられることが分かっている．また，どの学校も割り当てられる生徒数がすべて

Grade

総学校数

総生徒数

第1希望

第2希望

第3希望

第4希望

第5希望

選好外

K

72

4008

2574 64.2%

425 10.6%

226 5.6%

157 3.9%120 3.0%285 7.1%

6

14

3538

2293 64.8%

409 11.6%

169 4.8%

96 2.7%65 1.8%480 13.6%

9

19

4477

2089 46.7%

730 16.3%

528 11.8%

289 6.5%

169 3.8%

637 14.2%の安定マッチングで同じであり，割り当てられる生徒が定員を下回っている学校には，すべての安定マッチングで同じ生徒が

出典: Main Round 2022 Choice Results by Rank [12]割り当てられることが分かっている [13]．そのため，生徒からプロポーズする場合でも，不完全な選好によって生じる問題にた．ただし，本研究ではランダムな選好を用意し生徒と学校のついての調査に大きな影響はない．

選好としているため，実際の学校選択制にあるような，人気の3. 3 結果以下に SFUSD が公開している Student Assignment Policy
や Annual Enrollment をもとに，K grade における生徒の割
り当てと，可能な限り同様の条件を用意した上でマッチングを行った結果を示す [11], [?]．すべての安定マッチングを求めるには非常に時間がかかってしまうため，本実験では各生徒と各学校の選好はランダムに生成したものを用いて 16641 回マッチ
ングを行った．表 8 には，16641 回行ったマッチングの平均値を示している．また，この表では生徒が提出する選好のサイズ
が 1〜10 の場合に，どのくらいの生徒が第何希望の学校に割り当てられ，どのくらいの生徒が割り当てられなかったのかを表している．例えば，表 8 から各生徒の選好のサイズが 5 の場合には，マッチングに参加している 4, 023 人の生徒のうち，2080
人（51.71 ％）の生徒が選好の中で第 1 希望の学校に割り当てある学校に選好が偏ることや，似たような学校が一緒に選ばれるなど，生徒の嗜好が反映されておらず，割り当てられなかった生徒の割合は増えると考えられる．実際に SFUSD は生徒に対して，最低でも 5 校以上の学校を選好として提出するように推奨しているが，表 8 において選好のサイズが 5 の場合を見ると 103 人（2.56 ％）の生徒が割り当てられておらず，実際のマッチング結果より少ないことが分かる．

SFUSD は，K grade における生徒の割り当てにおいて，可能であれば 10 校以上の学校を選好として提出することを求めている．表 8 において選好のサイズが 10 の場合を見ると 5 人（0.12 ％）の生徒が割り当てられておらず，実際には少し増えるとしても割り当てられなかった生徒の数をかなり減らすことができると考えられる．しかし，生徒の選好を用意する負担が非常に大きくなるため，10 校以上の学校を選好として提出する
ように強制することは困難であると考察される．

られ，103 人（2.56 ％）の生徒が選好の中のどの学校にも割り当てられなかったことが分かる．
表 9 には，2022-23 Main Round における生徒の割り当て結果から，各 grade において，どのくらいの生徒が第何希望の学校に割り当てられ，どのくらいの生徒が割り当てられなかったのかを表している．例えば，表 9 から K grade におけるマッチングでは，マッチングに参加している 4008 人の生徒のうち，2574 人（64.2 ％）の生徒が選好の中で第 1 希望の学校に割り当てられ，285 人（7.1 ％）の生徒が選好の中のどの学校にも割り当てられなかったことが分かる．

3. 4 考察

前節で示した結果を見ると，割り当てられなかった生徒の割

4 選好の拡張手法
本章では, 不完全な選好を許す学校選択問題における，選好の拡張手法の利用について述べる.

4. 1 問 題 提 起
SFUSD では生徒に対して不完全な選好を許しており，最低でも 5 校以上の学校を選好として提出するように求めている．
特に K grade における生徒の割り当てでは 10 校以上の学校を選好として提出することが望ましいとされている．また，割り当てられなかった生徒は定員の余っている学校のうち一番近い学校に割り当てることになっている [11]．

合が，2022-23 Main Round の K grade における生徒の割り

表 8 から，2022-23 Main Round の K grade における生徒

当て結果に一番近かったのが，選好のサイズが 3 の場合であっの割り当てでは，4, 023 人の生徒がマッチングに参加しており，

285 人（7.1 ％）の生徒が選好の中のどの学校にも割り当てられに応じて他のルールを使用することも可能である．

なかったことが分かる．6 grade における生徒の割り当てでは，

これらの要素の中で，選好の拡張手法を用いて，割り当てら

3, 538 人の生徒がマッチングに参加しており，480 人（13.6 ％）れなかった生徒の割り当てを行うためには，以下の 5 つの要素の生徒が選好の中のどの学校にも割り当てられなかったことがが必要になる．

分かる．9 grade における生徒の割り当てでは，4, 477 人の生（ 1 ） 割り当てられなかった生徒の集合

徒がマッチングに参加しており，637 人（14.2 ％）の生徒が選（ 2 ） 定員が余っている学校の集合

好の中のどの学校にも割り当てられなかったことが分かる．

（ 3 ） 各学校の余っている定員

前章で示した結果から生徒に 10 校以上の学校を選好として提出するように強制することが可能であれば，割り当てられな（ 4 ） 割り当てられなかった生徒の割り当てに関するルール（ 5 ） 各学校のすべての生徒に対する厳密な選好かった生徒の数を非常に少なくできるが，これは生徒の負担がまずは，生徒の選好を拡張する方法について説明する．生徒

大きすぎて現実的ではないことが明らかである．そこで，割りの選好を拡張するために，以下の 3 ステップを行う必要がある．

当てられなかった生徒の割り当てにおける問題点を考える．

ステップ 1.

割り当てられなかった生徒を一人選ぶ
その生徒の選好に定員が余っている学校を近い

まず考えられるのは，SFUSD のような学校選択制を運営すステップ 2.

る組織の負担である．割り当てられなかった生徒の数が少なけ順に追加する

れば，定員の余っている学校のうち一番近い学校を探して割りステップ 3.

当てることは難しくない．しかし，2022-23 Main Round の K

2 を繰り返す

すべての生徒の選好を拡張するまで ステップ 1,

grade における生徒の割り当てでは，285 人（7.1 ％）の生徒がステップ 1 では，割り当てられなかった生徒の集合から生徒

選好の中のどの学校にも割り当てられておらず，SFUSD のよを一人選ぶ．ステップ 2 では，割り当てられなかった生徒の割

うな組織の負担になっていると言える．

り当てに関するルールに基づいて，生徒の選好に定員が余って次に考えられるのは，割り当てられなかった生徒の割り当ている学校を追加することで，選好を拡張していく．ここでは，における公平性である．SFUSD では，割り当てられなかった

その生徒の選好に定員が余っている学校を近い順に追加してい生徒の割り当てに関してのルールが決められているが，学校選る．ステップ 3 では，すべての割り当てられなかった生徒の選択制を運営する組織によっては特に明記されておらず不明なと

好を拡張するまで ステップ 1, 2 を繰り返す．この結果，各生ころもある．また，割り当てられなかった生徒同士で，各学校徒のすべての（定員が余っている）学校に対する厳密な選好をのすべての生徒に対する厳密な選好が考慮された，公平な結果得ることができる．

が得られるとは限らない．

マッチング理論を利用するために必要な要素がすべて揃った

本論文では，公平性を保ちながら，学校選択制を運営する組

ため，受け入れ保留アルゴリズムによって，割り当てられな織の負担を軽減するために，割り当てられなかった生徒を割りかった生徒と定員が余っている学校の，安定マッチングを得る

当てる選好の拡張手法を提案する．

ことができる．各生徒の不完全な選好を用いた場合と違い，各4. 2 提 案 手 法
不完全な選好を許す学校選択問題においてマッチング理論を生徒のすべての（定員が余っている）学校に対する厳密な選好を用いているため，このマッチングでは割り当てられなかった生徒は生じない．

利用するためには，以下の 5 つの要素が必要であった．
（ 1 ） 生徒の集合

4. 3 提案手法の説明（ 2 ） 学校の集合

一度目の安定マッチングは固定するため，選好の中のいずれ（ 3 ） 各学校の定員かの学校に割り当てられた生徒には影響がなく公平性が保たれ（ 4 ） 各生徒の不完全な選好る．割り当てられなかった生徒同士でも受け入れ保留アルゴリ（ 5 ） 各学校のすべての生徒に対する厳密な選好ズムによって安定性が確保されている．学校選択制を運営する

これら 5 つの要素と，受け入れ保留アルゴリズムを使うこと組織もアルゴリズムによって割り当て先を決定されるので負担で安定マッチングが得られる．特に，割り当てられなかった生が少ない．また，割り当てられなかった生徒は，一番近い学校

徒が発生した場合，以下の 4 つの要素が得られる．

からプロポーズしていき，受け入れ保留アルゴリズムによって，（ 1 ） 安定マッチング

いずれかの定員が余っている学校とペアになることができる．

（ 2 ） 割り当てられなかった生徒の集合

ここで，具体的な入力例でアルゴリズムの動作を確認してみ（ 3 ） 定員が余っている学校の集合

る．ある学校選択問題の入力例があり，受け入れ保留アルゴリ（ 4 ） 各学校の余っている定員

ズムを用いてマッチングを行った結果，割り当てられなかった提案手法を用いるためには，割り当てられなかった生徒の割

生徒が 10 人，定員が余っている学校が 5 校となったとする．まり当てに関するルールが決まっている必要がある．そのため，た，各学校は 2 人の定員が余ったとする．ここで，生徒を 1〜

今回は SFUSD が採用している，定員の余っている学校のうち10，学校を a〜e とする．また，割り当てられなかった生徒の一番近い学校に割り当てるルールを用いて説明する．また，今割り当てルールでは，定員の余っている学校のうち一番近い学

回は説明のために SFUSD のルールを用いているが，適用対象校に割り当てることになっているとする．この条件で，提案手

法を用いて割り当てられなかった生徒の割り当てを行ってみる．
まず，割り当てられなかった生徒の選好の拡張を行うため，
割り当てられなかった生徒の中から生徒 1 を選択する．生徒 1と定員の余っている学校の位置関係は 図 1 のようになっているとする．このとき，割り当てられなかった生徒の割り当てルー
ルでは，定員の余っている学校のうち一番近い学校に割り当てることになっているため，定員の余っている学校を近い順に並べると 表 10 になる．他の割り当てられなかった生徒についても，定員の余っている学校を近い順に並べることで，各生徒のすべての（定員が余っている）学校に対する厳密な選好を得る

表 11
生徒

入力例 I4 （左から好みの順）

選好

学校

選好

1

%,

',

(,

),

*

*(")

7,

6,

3,

9,

1,

4,

8,

2,

10,

5

2

',

(,

%,

),

*

'(")

1,

10,

8,

3,

6,

4,

5,

9,

7,

2

3

*,

),

',

%,

(

%(")

9,

6,

8,

4,

5,

3,

10,

2,

1,

7

4

',

*,

%,

),

(

)(")

5,

1,

3,

9,

10,

7,

6,

2,

4,

8

5

(,

*,

%,

),

'

((")

8,

4,

3,

10,

6,

2,

9,

1,

7,

5

6

),

*,

(,

',

%

7

*,

(,

%,

),

'

8

),

(,

%,

*,

'

9

(,

%,

),

',

*

10

',

*,

%,

(,

)

ことができる．
表 12
生徒

学校 "

学校 &
学校 e

選好

学校

学校 #

図1

生徒 1 と各学校の距離

表 10

生徒 1 と各学校の距離

生徒
1

$,

&,

',

(,

)

)(")

7,

6,

3,

9,

1,

4,

8,

2,

10,

5

2

&,

',

$,

(,

)

&(")

1,

10,

8,

3,

6,

4,

5,

9,

7,

2

3

),

(,

&,

$,

'

$(")

9,

6,

8,

4,

5,

3,

10,

2,

1,

7

4

&,

),

$,

(,

'

((")

5,

1,

3,

9,

10,

7,

6,

2,

4,

8

5

',

),

$,

(,

&

'(")

8,

4,

3,

10,

6,

2,

9,

1,

7,

5

6

(,

),

',

&,

$

7

),

',

$,

(,

&

8

(,

',

$,

),

&

9

',

$,

(,

&,

)

10

&,

),

$,

',

(

#,

$,

%,

こで，学校を定員数だけコピーして，安定結婚問題と同じ形に変換することを考える．このとき，学校選択問題においても安距離が近い順
!,

選好

1

生徒 1
学校 %

安定マッチング M5&

定マッチングが存在することが分かる．
割り当てられなかった生徒は，選好の中の全ての学校にプロ

この時点で，各生徒のすべての（定員が余っている）学校にポーズしており，プロポーズした学校はその生徒よりも優先順

対する厳密な選好と，各学校のすべての（割り当てられなかっ位の高い生徒で定員が埋まっている．また，割り当てられなかった）生徒に対する厳密な選好が揃ったため，表 11 に入力例 I4た生徒は，いずれの定員が余っている学校も選に選んでいない．

としてまとめた．ここで，生徒の選好は左から近い順，学校の選好は左から優先度の高い順で並んでいる．

「Rural Hospitals Theorem」より，割り当てられなかった
生徒は，全ての安定マッチングで同じであり，余っている定員

マッチング理論を利用するために必要な要素がすべて揃ったの数も，全ての安定マッチングで同じであることが知られていため，受け入れ保留アルゴリズムによって，表 12 に示す安定る．ここで，提案手法により割り当てられなかった生徒の選好マッチング M5 が得られる．それぞれの選好の中でペアになっに，定員が余っている学校を追加して，定員が余っている学校

た相手を丸で囲っている．生徒側が不完全な選好であった場合と受け入れ保留アルゴリズムによるマッチング行った場合は，と違い，各生徒のすべての（定員が余っている）学校に対する全ての生徒がいずれかの学校に割り当てられることになる．

厳密な選好であるため，このマッチングで割り当てられなかっ

よって，不完全な選好を許す学校選択問題において，学校にた生徒は生じない．実際に 表 12 に示す安定マッチング M5 で割り当てられなかった生徒が存在する場合でも，学校の定員のもすべての生徒が選好の中のいずれかの学校とペアになって合計が生徒数以上である場合，提案手法によりすべての生徒をいる．

割り当てることができる．□

提案手法に関して以下の定理が成り立つ．
定理：不完全な選好を許す学校選択問題において，受け入れ保
留アルゴリズムによって学校に割り当てられなかった生徒が生じたとする．学校の定員の合計が生徒数以上である場合，提案手法によりすべての生徒を割り当てることができる．
証明：不完全な選好を許す安定結婚問題において，受け入れ保
留アルゴリズムよって安定マッチングを得ることができる．こ4. 4 評 価 実 験
提案手法を用いて選好の拡張を行い，ボストンアルゴリズムと受け入れ保留アルゴリズムを用いて割り当てられなかった
生徒を割り当てを行い，マッチング結果を比較した．具体的には，一度目のマッチングでは生徒の選好のサイズを 5 とし，受け入れ保留アルゴリズムを用いてマッチングを行う．その後，選好の拡張を行い，ボストンアルゴリズムと受け入れ保留アル表 13

評価実験の結果（選好のサイズ=5, 実行数=16641）

学校選択制を運営する組織の負担を軽減するために，割り当て

受け入れ保留アルゴリズム

ボストンアルゴリズム

生徒の不満度

1.08861.0882

今後の課題として，提案手法を実際の学校選択制に導入でき学校の不満度50.6375

52.0935

るのか調査することが挙げられる．本研究では，ランダムな選られなかった生徒を割り当てる選好の拡張手法を提案した．

好を用意し生徒と学校の選好としているが，実際の学校選択制
ゴリズムで再度マッチングを行う．この作業を 16, 641 回行いでは，人気のある学校に選好が偏ることや，似たような学校が平均値を求めた．結果を 表 13 に示した．その結果，受け入れ一緒に選ばれることなど生徒の嗜好が反映されるため，ランダ

保留アルゴリズムを用いた場合において，学校の不満度がボス

ムな選好を用いた場合とは異なる結果になると考えられる．そトンアルゴリズムよりも低い値となった．これは，学校選択制のため，学校選択制を運営する組織と協力し，より詳細な選好で決められた生徒の優先度がより順守されたマッチングを得る

データなどを用いて提案手法を検証する必要がある．しかしなことができたため，公平性が向上したと考えられる．この結果

がら，学校選択制を導入をしていて，かつ受け入れ保留アルゴ

は，学校選択問題において選好の中のどの学校にも割り当てら

リズムを導入しているところとなると，非常に限られるため対れなかった生徒を割り当てる際に選好の拡張手法を用いること象となる組織を探す必要がある．また，生徒の割り当てに関すで．より公平なマッチング結果を得ることができることを示しる条件が課されている場合，マッチングアルゴリズムが複雑にている．

なり実行時間が非常に大きくなってしまうことや，実装が不可

4. 5 考察

前節で示したように，割り当てられなかった生徒がいる場合，能なこともあるため，出来るだけ今回行ったのような条件に近い組織を見つける必要がある．

割り当てられなかった生徒の割り当てルールがあれば，提案手法を用いてその選好を拡張することができる．各生徒のすべての（定員が余っている）学校に対する厳密な選好を得ることができ，受け入れ保留アルゴリズムによって，すべての生徒をいずれかの学校に割り当てることができる．また，SFUSD のよ
うに定員の余っている学校のうち一番近い学校に割り当てるというルールであれば，生徒の住所と学校の住所がわかっている
ため，生徒の自宅と学校の間の距離を計算するプログラムを用意するだけで済み，新たな選好を提出させる必要がなく負担も少ない．
提案手法では，一度目の安定マッチングは固定するため，選好の中のいずれかの学校に割り当てられた生徒には影響がなく公平性が保たれる．また，割り当てられなかった生徒同士でも，受け入れ保留アルゴリズムによって安定性が確保されている．
例えば，表 12 に示す安定マッチング M5 では，生徒 2, 4, 10が学校 b を選好の第 1 希望にしているが，学校 b の優先度が高い生徒 4, 10 が割り当てられていることが分かる．

5 む す び
本論文では，不完全な選好を許す学校選択問題において，選
好の中のどの学校にも割り当てられなかった生徒が生じる問題について調査し，割り当てられなかった生徒の選好を拡張する
ことで，マッチングを改善する方法を提案した．具体的には，

SFUSD（San Francisco Uniﬁed School District）における生徒の割り当てを取り上げ，実際の学校選択問題における，不完
全な選好による影響を調査した．また，Atila Abdulkadiroğlu
氏と Tayfun Sönmez 氏によって定式化された学校選択モデル
を，生徒に不完全な選好を許すよう拡張したアルゴリズムを実装し，実際にマッチングを行うことで，選好のサイズによってどの程度割り当てられなかった生徒が生じるか実験を行った．
その結果，条件によっては生徒に十分な選好を用意させることが困難であることが分かった．そこで，公平性を保ちながら，

文

献[1] 小島武仁, “マッチング理論とマーケットデザインの実践,” 財
務総合政策研究所, https://www.mof.go.jp/pri/research/seminar/fy2021/lm20220316.pdf, Dec. 7, 2022.
[2] D. Gale, L.S. Shapley, “College admissions and the stabilityof marriage,” The American Math ematical Monthly, vol.69,
no.1, pp.9-15, Jan. 1962.
[3] 宮崎修一, “安定マッチング問題,” 情報処理, vol.54, no.10,
pp.1064-1071, Sep. 2013.
[4] 安田洋祐, “学校選択問題のマッチング理論分析,” 現代経済学の潮流 2014, pp.95-122, Jun. 2014.
[5] デジタル庁, “学校教育法施行令,” イーガブ法令検索, https://
elaws.e-gov.go.jp/document?lawid=328CO0000000340_20210401_
501CO0000000128, Dec. 7, 2022.
[6] 文 部 省 初 等 中 等 教 育 局 長, “通 学 区 域 制 度 の 弾 力 的 運 用 について（通知）,” 文部科学省, https://www.mext.go.jp/a_menu/shotou/gakko-sentaku/06041014/008/003.htm, Dec.
7, 2022.
[7] 曽我雅比児, “公立義務教育学校通学区域制度の弾力化に関す
るー考察,” 岡山理科大学紀要, no.39, pp.49-63, Mar. 2004.
[8] 小島武仁, “ノーベル経済学賞にロス氏とシャプレー氏,” 日本経済新聞, 朝刊, pp.25, Oct. 19, 2012.
[9] A. Abdulkadiroğlu, T. Sönme, “School Choice: A Mechanism Design Approach,” American Economic Review,
vol.93, no.3, pp.729-747, Jun. 2003.
[10] SFUSD, “About SFUSD,” SFUSD, https://www.sfusd.
edu/about-sfusd, Dec. 16, 2022.
[11] SFUSD, “Student Assignment Policy,” SFUSD, https://www.sfusd.edu/schools/enroll/student-assignment-policy,
Dec. 16, 2022.
[12] SFUSD, “Annual Enrollment Highlights,” SFUSD, https://www.sfusd.edu/schools/enroll/student-assignment-policy/
annual-enrollment-highlights, Dec. 16, 2022.
[13] D. Gale, M. Sotomayor, “Some remarks on the stablematching problem,” Discrete Applied Mathematics, vol.11,
no.3, pp.223-232, Jul. 1985.