FIT2019（第 18 回情報科学技術フォーラム）F-028

部分的選好下における学校選択メカニズム
School Choice Mechanism with Partial Preferences
和田 凌司∗

八尋 健太郎∗

東藤 大樹∗

横尾 真∗

Ryoji Wada

Kentaro Yahiro

Taiki Todo

Makoto Yokoo

場合，Gale-Shapley アルゴリズム (GS) [6] により，学生最1 序論

適性を満たす割当を求めることができる．学生最適性を満た学生と学校，研修医と病院のような 2 種類のエージェント

す割当は，安定性を満たす割当の中で，すべての学生が最も間のお互いの好み (選好) に基づく適切な割当を求めるマッ好む割当である．部分的な選好の下での一対一マッチング問

チング問題は，経済学や人工知能，マルチエージェントシス

題においては，必要最小限のインタビューを行うことで，GSテムの分野において盛んに研究されている [1, 2, 3]．マッチと等価な割当，すなわち学生最適性を満たす割当を求めるメング問題の代表的な問題の一つとして，学校選択問題がある．

カニズムが存在する [7]．しかしながら，このメカニズムはす

学校選択問題は，複数の学生を学校に割り当てる問題であり，べての学校に対して，共通な部分的選好を仮定している．そ学校の割当人数に対して，上限や下限などの制約が課される

こで本論文では，より一般的な仮定の下における多対一マッことが一般的である [4]．本論文では，その中でも個々の学校

チング問題を考察する．

の割当人数に上限値が存在する，個別上限制約を扱う．

本論文の貢献は主に 3 つである．1 つ目は，任意の部分的

学校選択問題に関する既存研究の多くは，各エージェント

な選好の下における学校選択問題に対して，学生最適な割当の持つ選好が厳密に順序付けられており，学生や学校が自らを出力する Lazy Gale-Shapley アルゴリズム (LGS) のの選好を完全に把握している問題を前提としている．しかし提案である．LGS においては，既存のメカニズムが動作するながら，学生や学校が数多く存在する現実的な仮定の下では，ために要求した仮定を必要とせず，多対一マッチング問題を学生がすべての学校の情報を正確に得ることは困難であり，扱うことができる．その上で，LGS が出力する割当が満たす

同様に学校がすべての学生の差異を明確にすることも容易で性質は，既存研究と等価であることを証明した．2 つ目は，部はない．そこで本論文では，各エージェントの選好の一部が分的な選好に対する既存の仮定を緩和した，整合性の提案で明確に順序付けられていない，部分的な選好の下での学校選ある．学校側の部分的な選好に整合性を仮定することにより，択問題を考察する．

LGS は必要最低限のインタビューのみを行う．また，整合性

各エージェントが潜在的に持つ選好の厳密な順序付けを解を満たす学校側の部分選好においては，各学校の持つ選好が明する方法として，様々な手法が考察されている．例えば，それぞれ異なる場合も存在する．これにより，既存研究を一

学生に質問を行うことにより，その学生が厳密に順序付けを般化したモデルにおいて，LGS が既存研究と同等の性質を満行っていない学校の順序付けを明らかにするクエリが存在すたすことを明らかにした．3 つ目は，LGS が必要とするインる [5]．本論文ではそのような手法の中でも，学生が学校に行

タビュー回数の定量的な評価である．部分的な選好の下で既うインタビューにより，各エージェントが厳密な順序付けを

存の GS が動作するために必要なインタビュー回数との比較行うモデルを扱う．個々の学生や学校に対して行うクエリににより，LGS が削減できるインタビューの割合を示した．ま対して，インタビューでは学生と学校が相互に情報を得る．

た，実験結果より，各エージェントの持つ選好がより詳細で学生は順序付けが明確でない複数の学校にインタビューを行あるほど，より少ないインタビューの回数で割当を出力できうことにより，それらの学校間の厳密な順序付けを行うことることが明らかとなった．

ができる．学校側も同様に，複数の学生からインタビューを受けることにより，それらの学生間の順序付けが可能となる．
すなわち，インタビューによって，双方のエージェントが潜2 モデル
部分的選好下における学校選択問題は，(S, C, pS , pC , qC )の組で定義される．S = {s1 , . . . , sn } は学生の集合である．

在的に持つ厳密な選好を明らかにすることができる．
インタビューのような情報を収集する行為には，時間的・金C = {c1 , . . . , cm } は学校の集合である．X = S × C は契銭的なコストが生じると仮定するのが一般的である．そこで，約の集合であり，契約 (s, c) ∈ X は，学生 s が学校 c に

必要最小限のインタビューを用いて，各エージェントが潜在割り当てられていることを意味する．X ′ ⊆ X において，的に持つ厳密な順序付けを解明しつつ，望ましい性質を満た

Xs′ = {c ∈ C | (s, c) ∈ X ′ } は学生 s が割り当てられている

す割当を求めることが望まれる．

学校の集合を，Xc′ = {s ∈ S | (s, c) ∈ X ′ } は学校 c に割り当

各エージェントの選好がすべて厳密に順序付けられている

てられている学生の集合を表す．≻S = (≻s1 , . . . , ≻sn ) は，学生側が持つ潜在選好の組である．学生 s が持つ潜在選好 ≻s∗ 九州大学大学院システム情報科学府 Graduate School of Informa-は，∅ を含むすべての学校 C ∪ {∅} を厳密に順序付ける．学

tion Science and Electrical Engineering, Kyushu University319
第 2 分冊Copyright © 2019 by Information Processing Society of Japan and
The Institute of Electronics, Information and Communication Engineers
All rights reserved.

FIT2019（第 18 回情報科学技術フォーラム）校 c が s にとって受け入れ可能であるとは，c ≻s ∅ が成り

定義 4 (安定性). マッチング X ′ が安定性を満たすとは，X ′立つことである．≻C = (≻c1 , . . . , ≻cm ) は，学校側が持つ潜が非浪費性を満たし，かつ，公平性を満たすことである．

在選好の組である．学校 c が持つ潜在選好 ≻c は，∅ を含む
すべての学生 S ∪ {∅} を厳密に順序付ける．学校 s が c にとって受け入れ可能であるとは，s ≻c ∅ が成り立つことである．pS = (ps1 , . . . , psn ) は，学生側が持つ部分選好の組である．学生 s が持つ部分選好 ps は，s に関するすべての同格
クラスを厳密に順序付ける．同格クラス pis は C ∪ {∅} の部
分集合であり，s が潜在選好を把握できない初期の段階で厳

定義 5 (学生最適性). マッチング X ′ が学生最適であるとは，

X ′ が安定性を満たし，かつ，他の任意の安定性を満たすマッチングと比較して，どの学生もより低い選好順位の学校に割り当てられていないことである．任意の入力に対して学生最適なマッチングを出力するとき，そのメカニズムは学生最適であるという．

密に順序付けできない学校との契約の集合のうち，s が i 番

学生最適なマッチングは，安定性を満たすマッチングの中目に好むものである．同格クラスの順序付けにおいて，i < j

ですべての学生が最も好むマッチングである．各エージェン

ならば，任意の学校 c ∈ pis と c′ ∈ pjs に対して，c ≻s c′ がトが自分の潜在選好を把握している場合，学生最適なマッチ成り立つ．また，∪|ps |ii=1 ps = C ∪ {∅} かつ，i ̸= j に対してングは常に一意に求まる [6]．

pis ∩ pjs = ∅ である．pC = (pc1 , . . . , pcm ) は，学校側が持つ部分選好から学生最適なマッチングを求めるために，学生

部分選好の組である．学生 c が持つ部分選好 pc は，c に関すが学校にインタビューを行うことで追加の情報を得る必要がるすべての同格クラスを厳密に順序付ける．同格クラス pic はある．学生 s が学校 c に対してインタビューを行うことをS ∪ {∅} の部分集合であり，c が潜在選好を把握できない初期(s : c) と表す．インタビュー (s : c) を行うことにより，学生の段階で厳密に順序付けできない学生との契約の集合のうち，s は既にインタビューを行った学校と c を厳密に順序付ける

c が i 番目に好むものである．同格クラスの順序付けにおいことができる．同様に，学校 c は既にインタビューを行ったて，i < j ならば，任意の学生 s ∈ pic と s′ ∈ pjc に対して，

学生と s を厳密に順序付けることができる．

′

s ≻c s が成り立つ．また，∪|pc |ii=1 pc = S ∪ {∅} かつ，i ̸= jに対して pic ∩ pjc = ∅ である．qC = (qc1 , . . . , qcm ) は，学校の定員のベクトルである．
各学生・学校が互いの詳細な情報を持たない初期の段階においては，各エージェントは自分の潜在選好を把握していな
いと考える．したがって，部分選好のみが入力として与えられ，その部分選好に矛盾しない厳密な順序付けのいずれか 1
つが真の潜在選好となる．

インタビューを行うことで明らかになった順序付けを以下のように定義する．
定義 6 (インタビュー状態). 学生 s のインタビュー状態 Isとは，s がインタビューを行った学校間の，s の潜在選好に基づく厳密な順序付けである．同様に，学校 c のインタビュー状態 Ic とは，c とインタビューを行った学生間の，c の潜在選好に基づく厳密な順序付けである．また，IS = (Is1 , · · · , Isn )，IC = (Ic1 , · · · , Icm ) とする．

′

定義 1 (実現可能性). X が 学校側実現可能であるとは，任意の学校 c ∈ C について |Xc′ | ≤ qc が成り立つことである．

X ′ が 学生側実現可能であるとは，任意の学生 s ∈ S について，s の受け入れ可能な学校 c に対して Xs′ = {c} を満たす，
あるいは，Xs′ = ∅ を満たすことである．X ′ が実現可能であるとは，X ′ が学校側実現可能かつ学生側実現可能であることである．また，実現可能な契約の集合をマッチングという．
マッチングに望まれる性質として，以下のいくつかの性質

任意の学生 s ∈ S と任意の学校 c, c′ ∈ C に対して，ps において s が c を c′ より厳密に高く順序付けているとき，Is においても c を c′ より厳密に高く順序付けているならば，インタ
ビュー状態 IS が部分選好 pS を詳細化するといい，IS ◁ pSと表す．同様に，任意の学校 c と任意の学生 s, s′ ∈ S に対して上記が成り立つならば，インタビュー状態 IC が部分選
好 pC を詳細化するといい，IC ◁ pC と表す．また，潜在選
好 ≻S や ≻C が，部分選好 pS , pC を詳細化するとき，それを定義する．

ぞれ ≻S ◁pS , ≻C ◁pC と表す．

定義 2 (非浪費性). マッチング X ′ において，学生 s が学校

定義 7 (ポリシー). インタビュー状態 IS ◁ pS , IC ◁ pC かc に空きシートを要求するとは，(s, c) ∈ X\X ′ , (s, c′ ) ∈ X ′らインタビューの実行，あるいはマッチングの出力を行う写

′

′

′

に対して c ≻s c を満たし，かつ，(X \{(s, c )}) ∪ {(s, c)}が実現可能であることである．マッチング X ′ が非浪費性を満たすとは，空きシートを要求する学生が存在しないことである．

像を，ポリシーという．
ポリシーは，I = (S, C, pS , pC , qC ) を入力として一連のインタビューを行った後，マッチングを出力する．ここでは簡単のために，入力 I は所与のものであるとしている．ポリ定義 3 (公平性). マッチング X ′ における (s, c) ∈ X ′ に対′

シーは直前までのインタビューの結果に基づいて，次に行う

して，学生 s が他の学生 s (̸= s) に妥当な不満を持つとは，

インタビューを決定する．ポリシーに望まれる性質として，(s, c′ ) ∈ X\X ′ , (s′ , c′ ) ∈ X ′ について，c′ ≻s c かつ s ≻c′ s′以下を定義する．

が成り立つことである．マッチング X ′ が公平性を満たすとは，妥当な不満を持つ学生が存在しないことである．

定義 8 (健全性). あるポリシーが健全であるとは，そのポリ

320
第 2 分冊Copyright © 2019 by Information Processing Society of Japan and
The Institute of Electronics, Information and Communication Engineers
All rights reserved.

FIT2019（第 18 回情報科学技術フォーラム）シーが任意の潜在選好 ≻S ◁pS , ≻C ◁pC に対して，学生最

この順序付け O は，部分選好と同様に学生の部分集合に対す適なマッチングを出力することである．

る順序付けであり，k 番目に順序付けられる学生の部分集合

健全なポリシーにおいて，学生はインタビューを行っていない学校に割り当てられうる．しかしながら，現実的な状況
では，最終的に割り当てられる学生と学校の間では，必ずインタビューが行われていることが望ましい．よって，以下の性質を導入する．

だし，

∪|O|

k=1 O

k

= S であり，Ok ∈ O は ∅ を含まない．また，アルゴリズムを実行する前の処理として，各学校 c の部
|p |−1

分選好内のある同格クラス ptc ∈ {p1c , . . . , pc c

} が ∅ を含

|pc |む場合，pt+1
内の学生 s は c にとって受け入れ可c , . . . , pc

能でないため，そのような各学生 s について，c を ps 内の同

定義 9 (慎重性). あるポリシーが慎重であるとは，そのポリシーが健全であり，かつ，任意の契約 (s, c) ∈ X ′ に対し，∗を O k とするとき，O = (O 1 , · · · , O k , · · · , O |O| ) である．た格クラスから削除する．
以上の定義を以て，LGS を定義する．

′s ∈ Ic , c ∈ Is となる場合に限り，IS , IC から X を出力することである．
すなわち，慎重なポリシーにおいて，学生はインタビューを行った学校のみに割り当てられる．

メカニズム 1 (Lazy Gale-Shapley アルゴリズム (LGS)).
′′
初期値 X ′ = ∅, ls∈S = 0, Is∈S= ∅, Ic∈C= ∅, k = 1

ステージ k健全なポリシーを構成すること自体は困難ではない．例えば，すべての学生がすべての学校にインタビューを行うポリステップ 1 Is′ = ∅ である間，以下を繰り返す．

1. ls ← ls + 1 とする．

シーにより，すべてのエージェントの潜在選好が明らかにな

2. plss 内のすべての学校 c について，インタビュー(s : c) を行う．Is′ に c を，Ic′ に s を加え，順序付

るため，既存のメカニズムを用いることが可能である．しかしながら，このポリシーは必ずしも必要でないインタビューをける．

行うことがある．また，現実的な仮定において，インタビュー

3. Ic′ に ∅ が含まれておらず，かつ pc において s と ∅にはコストがかかると考えるのが自然である．したがって，が同じ同格クラスに含まれる場合，Ic′ に ∅ を加え，インタビューを行う回数を必要最小限にする健全なポリシー

順序付ける．

を求めたい．そこで，ポリシーに以下の性質を定義する．こ4. Ic′ において ∅ が s より厳密に上位である場合，Is′

こで，潜在選好が ≻S ◁pS , ≻C ◁pC である場合に，ポリシー

から c を削除する．

f が実行するインタビューの回数を，θ(f, ≻S , ≻C , pS , pC ) と表す．

Ok 内の各学生 s ∈ Ok に対して，以下を行う† ．

5. ∅ ∈ plss である場合，Is′ に ∅ を加え，順序付ける．
ステップ 2 Is′ において ∅ が最も上位である場合，s をどの

定義 10 (インタビュー数の最小性). ポリシー f が健全なポリ学校にも割り当てずに s の割当を終了する．そうでなけ

シー g を弱支配するとは，任意の潜在選好 ≻S ◁pS , ≻C ◁pC

れば，s は Is′ において最も上位の学校 ctop に申し込み，

に対し，θ(f, ≻S , ≻C , pS , pC ) ≤ θ(g, ≻S , ≻C , pS , pC ) が成り

X ′ ← X ′ ∪ {(s, ctop )} とする．

立つことである．ポリシー f が健全であり，かつ，他の任意ステップ 3 qctop < |Xc′ top | である場合，ctop は Xc′ top の中の健全なポリシー g を弱支配するとき，ポリシー f はインタ

で Ic′ top において最も順位の低い学生 sw を拒否する．

ビュー数が最小であるという．

すなわち，X ′ ← X ′ \{(sw , ctop )} とする．

本論文ではインタビュー数を最小にするポリシーの発見をステップ 4 |Xc′ top | = qctop である場合，Xc′ top の中で Ic′ top
において最も順位の低い学生を sw とする．さらに，pctop

目的として，第 3 章で新たなメカニズムを提案する．

あるいは Ic′ top の少なくとも一方において sw より厳密に下位である各学生 s′w に対して，ps′w 内の同格クラスと3 Lazy Gale-Shapley アルゴリズム

Is′ ′w から ctop を削除する．

Gale と Shapley による既存の Gale-Shapley アルゴリズ
ム (GS) [6] は，すべてのエージェントの厳密に順序付けらステップ 3 において ctop から拒否された学生 s′ が存在す

れた選好の下で，学生最適性を満たす．本章では GS に基づる場合，s ← s′ として再度上記のステップを繰り返す．すべき，部分的選好下における多対一マッチング問題において，学ての学生の割当が決定した場合，X ′ を出力して動作を終了す

生最適性を満たす Lazy Deferred Acceptance アルゴリズム

る．O 1 , · · · , O k に含まれるすべての学生に割当が決定した場(LGS) を提案する．

合，ステージ k + 1 を行う．

部分的選好の下で GS の動作を実現するために，学生が学校に逐次的にインタビューを行うことにより，潜在選好を明らかにする．学生はある定められた順序付け O に基づいて順番にインタビューを行った後，GS に従って学校に申し込む．

定理 1. LGS は学生最適であり多項式時間で動作する，
証明は紙幅の都合上割愛するが，LGS の出力が GS の出力と等価になることを利用して証明を行う．

∗ i がある順序付け P の要素の一つであるとき， i ∈ P と表すことに

する．

321
第 2 分冊† O k 内の学生の順序は，アルゴリズムの出力に影響しない．

Copyright © 2019 by Information Processing Society of Japan and
The Institute of Electronics, Information and Communication Engineers
All rights reserved.

FIT2019（第 18 回情報科学技術フォーラム）と，Sc に限定した GC が表す部分選好がそれぞれ一致する．

4 整合性を満たす部分選好

整合性を満たす学校側の部分選好 pC における部分選好グラ

既存研究 [7] では，任意の部分選好の下ではインタビュー

フ GC を考える．入次数が 0 である頂点の集合を O 1 = {s ∈数を最小にするポリシーは必ずしも存在しないが，学校側の

1
S | deg−
GC (s) = 0} とする． GC から頂点 s ∈ O を除いた誘部分選好がすべて等しいという仮定をおくことにより，一対導部分グラフを G1C とし, O 2 = {s ∈ S | deg−(s) = 0} とす
G1

一マッチングにおいて，提案メカニズムがインタビュー数をる．同様の操作を頂点がなくなるまで繰り返し， O 3 , O 4 , · · ·最小にするポリシーを実行することを示した．本章では，よとしていく．以上により得られる順序付け O = (O 1 , O 2 , · · · )C

り一般的な仮定である整合性を学校側の部分選好に仮定するを整合的順序 O という．学校側の部分選好が整合性を満たす

ことにより，LGS がインタビュー数が最小であるポリシーを場合，整合的順序 O が一意に決定する．

実行することを示す．
学校 c ∈ C の ∅ ∈ pic となる i に対して，Sc =学校側の部分選好が整合性を満たす仮定の下で，LGS のイ∪ijj=1 pc \{∅}

ンタビュー数を議論する．LGS において，整合的順序 O がとする．また，qc < |Sc | を満たす学校の集合を C+ とする．

インタビュー数に与える影響を，以下の補題により示す．こpc∈C+ において， qc 番目に順序付けられた学生が存在するのとき，LGS の入力において，O = O である．

i
同格クラス phc に対し，Ŝc = {s ∈ S | s ∈ pc , 1 ≤ i ≤ h} とする．
有向グ ラフ G は，頂点集合 V と頂点の順序対の集合

E ⊂ {(i, j) | i, j ∈ V } の組 (V, E) である．順序対 (i, j)

補題 1. 整合的順序 O に従って LGS を行う場合，O k+l (l >0) 内の任意の学生の割当によって，Ok 内の学生が現在の割当から拒否されることはない．

を，i から j への有向エッジと呼ぶ．また，頂点 i に対して，証明. O において，s ∈ O k , s′ ∈ O k+l (l > 0) となる任意

deg−
G (i) = |{(j, i) ∈ E | i, j ∈ V, i ̸= j}| を i の入次数との学生 s, s′ を考える．このとき，整合的順序の定義より，いう．

s′ ∈ Sc \Ŝc となる s′ に対して，pc において s ≻ s′ とする学

定義 11 (部分選好グラフ). 学校 c ∈ C+ に対して，頂点集

校 c が，少なくとも 1 校以上存在する．
上記以外の学校 c′ を考える．

合 V = S であり，かつ，有向エッジの集合 Ec が， pc において s ∈ Sc を s′ ∈ Sc \Ŝc より厳密に高く順序付けるよう′• s∈/ Sc′ または s′ ∈/ Sc′ を満たす場合，部分選好グラフ′

な s から s への有向エッジ (s, s ) をすべて含む有向グラフの誘導部分グラフ Gc′ [Sc′ ], GC [Sc′ ] において，s, s′ 間のGc = (V, Ec ) を，(学校 c の) 部分選好グラフという．すべて

有向エッジを持たないため，pc′ における s, s′ の順序はの c ∈ C+ について Gc が部分選好グラフであるとき，V = S
かつ EC =∪

O に影響しない．
• s, s′ ∈ Ŝc′ を満たす場合，c′ は申し込んできた s, s′ の両c∈C+ Ec とした有向グラフ GC = (V, EC ) を考者を必ず受け入れるため，pc′ における s, s′ の順序は O

える．GC が有向非巡回グラフであるとき，GC を部分選好
グラフという．

に影響しない．

• s, s′ ∈ Sc′ かつ，s ∈/ Ŝc′ または s′ ∈/ Ŝc′ を満たす場合，

すなわち，部分選好グラフは各学生を頂点とし，その中でc′ が pc′ において s′ ≻ s とするとき，GC において閉も Sc に含まれる学生について，部分選好における上位の学路が存在するため，整合性の定義に反する．また，c′ が生から厳密に下位の学生への有向エッジを持つ．したがって，s, s′ ∈ pdc′ とする場合，部分選好グラフ Gc′ は s, s′ 間の学校 c の部分選好グラフ Gc は，Sc に限定した c の部分選好

有向エッジを持たないが，GC は (s, s′ ) を持つため，整pc を表す．

合性の定義に反する．

部分選好グラフを用いて，以下の性質を定義する．
定義 12 (整合性). 学校 c ∈ C+ に対して， Gc の頂点 Sc
に関する誘導部分グラフ Gc [Sc ] と，GC の頂点 Sc に関する誘導部分グラフ GC [Sc ] を考える．GC [Sc ] において，s, s′ ∈ Ŝc を満たす学生間の有向エッジ (s, s′ ) をすべて除いた有向非巡回グラフを ĜC [Sc ] とする．学校側の部分選好

pC が整合性を満たすとは，任意の学校 c ∈ C+ について，
Gc [Sc ] と ĜC [Sc ] が一致することである．ただし，有向グラ′

フ G = (V, E) の頂点の任意の部分集合 V ⊂ V に関する誘導部分グラフ G[V ′ ] は，頂点集合を V ′ とし，有向エッジの集合を E[V ′ ] = {(i, j) ∈ E | i, j ∈ V ′ } とする有向グラフである．
すなわち，学校側の部分選好が整合性を満たすとき，各学校

c の部分選好グラフ Gc が表す，Sc に限定した c の部分選好したがって，s, s′ の順序が O に影響を与えるすべての学校′

c は，pc′ において s ≻ s′ を満たす．以上より，O において
Ok 内のすべての学生がインタビューを行い，割当が仮に決定したとき，任意の s′ ∈ O k+l の割当によって，O k 内の学生が現在の割当先から拒否されることはない．

□
補題 1 により，LGS のインタビュー数に関する以下の定義が示される．
定理 2. 整合性を満たす学校側の部分選好の下で，LGS は慎重かつインタビュー数が最小であるポリシーを実行する．
証明. 学校 c は，pc において ∅ より厳密に優先順位の低い学
生 s を受け入れないため，Sc に含まれる学生についてのみ，インタビューを行う順序を考える．また，|Sc | ≤ qc を満たす

322
第 2 分冊Copyright © 2019 by Information Processing Society of Japan and
The Institute of Electronics, Information and Communication Engineers
All rights reserved.

FIT2019（第 18 回情報科学技術フォーラム）学校 c は，Sc 内のすべての学生を受け入れられるため，インタビューを行う学生の順序を考慮しない．一方，qc < |Sc |を満たす各学校 c について考える．pC が整合性を満たすこ

5 実験
本章では，計算機実験により LGS が必要とするインタとから，インタビューを行う学生の順序 O は整合的順序であビュー数を評価する．学生数 n = 400，学校数 m = 20 とし，る．したがって，補題 1 より，plc 内の学生の割当によって plc

各学校の定員は qc = 20 とする．また，各学生は全学校を受より高い同格クラス内の学生が拒否されることはない．また，け入れ可能であり，同様に各学校は全学生を受け入れ可能で

plc 内の学生がインタビューを行うとき， plc より高い同格クラあるとする．学生，学校の選好順序は以下のように設定する．

ス内のすべての学生は割当が仮に決定している．さらに LGSにおいて，仮の割当が決定した学生は，現在割り当てられてい学生の選好て潜在選好 ≻s を生成する．Mallows モデルはパラメーる学校から拒否されない限り他の学校に申し込むことはないタ θ(≥ 0) を持ち，θ が大きいほど学生同士の潜在選好のため，現在の割当が最終的なマッチングとなる．定理 1 より，相関は強くなる．θ = 0 のとき，学生の潜在選好は一様

そのマッチングは学生最適である．したがって，qc < |Sc | を分布に従う．次に，全学生で共通の分割数 d を定め，≻s満たす各学校 c において，plc より上位の同格クラス内のすべをランダムに d 分割して部分選好 ps を生成する．このての学生が，学生最適なマッチングにおける割当先に割り当とき，各学生の ps 内の同格クラスに含まれる学校数の平てられたとき，plc 内の学生のみがインタビューを行う．
学生 s にとって学校 c が達成可能であるとは，s が c にとって受け入れ可能であり，|Xc′ | < qc ，あるいは，|Xc′ | = qc

均を σS = m/d とする．
学校の選好

全学生の順序をランダムに生成する．次に，分割数 e を定め，生成した順序を e 等分したものを，各学

かつ，pc において Xc′ 内の最も好まない学生より厳密に下位校の部分選好として与える．すなわち，すべての学校はでないことである．各学生 s ∈ S の ps において，最終的な共通の部分選好を持つため，pC は整合性を満たす．各マッチング X ′ における s の割当先 c より厳密に下位でない，学校は，与えられた pc 内の同格クラスに含まれる学生

s にとって達成可能な学校の集合を Ωs とする．

をランダムに順序付けて潜在選好 ≻c とする．このとき，

s が c′ ∈ Ωs にインタビューを行っていないと仮定する．c′

各学校の pc 内の同格クラスに含まれる学生数の平均をは c 以上の同格クラスに含まれるため，c′ ≻′s c となる ≻′s がσC = n/e とする．

存在しうる．これは LGS により出力されたマッチングが学生最適であることに矛盾するため，s は Ωs 内のすべての学校

各学生 s に対して，Mallows モデル [8] を用い

上記の設定の下で，全学生が全学校にインタビューを行う
場合，すなわち n · m(= 8000) 回のインタビューを行う場合とインタビューを行う．
次に，s にとって達成可能でない学校 ċ を考える．ċ にとっと比較して，LGS が行うインタビュー数の割合を求める．たて s が受け入れ可能でない場合，ps から ċ を削除する．まだし，LGS は慎重なポリシーを実行するため，各学生は少な

た，s が wċ より厳密に下位である場合，O に基づいて s がイ

くとも 1 回のインタビューを行う．したがって，割合の最小ンタビューを行う時点で wċ は既にインタビューを行い，ċ に

値は 0.05 となる．各パラメータ設定に対して 100 個の問題

割り当てられている．また，wċ ∈ O j は ċ が X ′ 内で最も好のインスタンスを生成し，インタビュー数の割合の平均を求

まない学生であるため，LGS のステージ j において，ċ の定める．

員は満たされる．このとき，ステージ j 内のステップ 4 の操図 1 に，横軸を σS ，縦軸をインタビュー数の割合とした作により，ps 内の同格クラスから ċ が削除される．したがっ結果を示す．図 1 (a) は，θ = 0.5 とし，σS による影響を比て，s がインタビューを行うとき，ċ は ps 内のどの同格クラ較している．いかなる σC の値に対しても，σS が増加するとスにも存在しないため，s は達成可能でない学校 ċ にインタインタビュー数の割合も増加する．したがって，選好に関す

ビューを行わない．

る情報を学生が多く持たない場合，LGS がより多くのインタ

また，ps において c より厳密に低く順序付けられた学校 c̈

ビューを要求することが分かる．図 1 (b) は，σC = 50 とし，を考える．s が c にインタビューを行うとき，インタビュー

θ による影響を比較している．θ による有意な差はないため，(s : c̈) は行われない．また，s の最終的な割当は c となるた

学生の選好の相関がインタビュー数に与える影響は少ないとめ，インタビュー (s : c̈) が行われることはない．したがって，考えられる．

s は Ωs 以外の学校とはインタビューを行わない．

次に，図 2 に，横軸を σC ，縦軸をインタビュー数の割合と以上より，LGS において，s は Ωs 内のすべての学校とイした結果を示す．図 2 (a) は，θ = 0.5 とし，σC による影響

ンタビューを行い，かつ，Ωs 以外の学校とはインタビューをを比較している．図 1 (a) と同様に，学校が持つ，選好に関行わない．また，学生はインタビューを行った学校にのみ申する情報が少ないほど，多くのインタビューが要求されるこし込むため，LGS は慎重かつインタビュー数が最小であるポとが分かる．図 1 (b) は，σS = 5 とし，θ による影響を比較□している．σC が小さいとき，θ による有意な差は見られない

リシーを実行する．

が，σC が増加すると θ が大きいほど多くのインタビューを要求することが分かる．これは，学校が多くの情報を持たず，学生同士の順序付けが困難な状況では，学生同士の選好が類

323
第 2 分冊Copyright © 2019 by Information Processing Society of Japan and
The Institute of Electronics, Information and Communication Engineers
All rights reserved.

FIT2019（第 18 回情報科学技術フォーラム）0.8

σC = 1σC = 50σC = 200σC = 400

0.8

θ = 0.2
θ = 0.5
θ = 0.8

0.7

Ratio of the numberof Interviews

Ratio of the numberof interviews

1

0.6
0.4
0.2

0.6
0.5
0.4
0.3
0.2
0.1

0
2

4

6

8

10

12

14

16

18

20

2

4

6

8

10

12

14

16

18

20

σS

σS

(a) σC による影響 (θ = 0.5)(b) θ による影響 (σC = 50)

図 1: σS の変化に伴うインタビュー数の割合の変化
0.45

σS = 1σS = 5σS = 10σS = 20

0.8

Ratio of the numberof Interviews

Ratio of the numberof Interviews

1

0.6
0.4
0.2
0

0.4

θ = 0.2
θ = 0.5
θ = 0.8

0.35
0.3
0.25
0.2
0.15

20

40

60

80 100 120 140 160 180 200

20

40

60

80 100 120 140 160 180 200σCσC(a) σS による影響 (θ = 0.5)(b) θ による影響 (σS = 5)

図 2: σC の変化に伴うインタビュー数の割合の変化

似すると特定の学校に申し込みが集中し，結果として拒否する学生数も増加するためであると考えられる．

[2] Fuhito Kojima, Akihisa Tamura, and Makoto Yokoo.
Designing matching mechanisms under constraints: An
approach from discrete convex analysis. Journal of Eco-

6 結論

nomic Theory, Vol. 176, pp. 803–833, 2018.

本論文では，部分的な選好下での多対一マッチング問題を[3] Masahiro Goto, Fuhiko Kojima, Ryoji Kurata, Akihisa

考察し，各エージェントが潜在的に持つ選好をインタビュー

Tamura, and Makoto Yokoo. Designing matching mecha-

により明らかにすることで．学生最適なマッチングを求める

nisms under general distributional constraints. American

LGS を新たに提案した．また，インタビューを行う回数を必Economic Journal: Microeconomics, 9(2):226–62, 2017.

要最小限にするために，学校側の部分選好に関する既存の仮[4] Ryoji Kurata, Naoto Hamada, Atsushi Iwasaki, and定を一般化した整合性を提案し，その下でインタビュー回数

Makoto Yokoo. Controlled school choice with soft boundsを最小にすることを示した．

and overlapping types. Journal of Artiﬁcial Intelligence

今後の課題としては，インタビュー数の最小化に関する整

Research, 58:153–184, 2017.

合性の特徴付けや，より現実に即した形式のインタビューの[5] Joanna Drummond and Craig Boutilier. Preference elic-モデル化と，その下でインタビュー数を最小化するメカニズ

itation and interview minimization in stable matchings.

ムの考察などが挙げられる．

In Proc. AAAI-2014, pp. 645–653, 2014.
[6] David Gale and Lloyd Stowell Shapley. College admis-

謝辞

sions and the stability of marriage. The American Math-

本研究は JSPS 科研費 JP17H00761 および 17H04695 の助成を受けたものです．深く感謝いたします．

ematical Monthly, 69(1):9–15, 1962.
[7] Baharak Rastegari, Anne Condon, Nicole Immorlica,
and Kevin Leyton-Brown. Two-sided matching with par-

参考文献

tial information. In Proc. EC-2013, pages 733–750, 2013.

[1] Haris Aziz, Péter Biró, Tamás Fleiner, Serge Gaspers,[8] JD Tubbs. Distance based binary matching. In Com-

Ronald de Haan, Nicholas Mattei, and Baharak Raste-

puting Science and Statistics, pages 548–550, 1992.

gari. Stable matching with uncertain pairwise preferences. In Proc. AAMAS-2017, pages 344–352, 2017.

324
第 2 分冊Copyright © 2019 by Information Processing Society of Japan and
The Institute of Electronics, Information and Communication Engineers
All rights reserved.