日本ソフトウェア科学会第 30 回大会 (2013 年度) 講演論文集

制約付きマッチングのメカニズムデザイン
横尾 真

マッチングは，生徒と学校をマッチする学校選択制，研修医と病院をマッチする研修医配属問題等の様々な応用問題を表現できる一般的な枠組みである．望ましい性質を持つマッチングを求める著名なメカニズムとしてゲールとシャプレイによる受入保留 (DA) メカニズムがあるが，下限制約や地域の上限制約等，マッチングの結果に対して様々な制約が課せられる場合には，DA メカニズムをそのまま適用することができない．本稿では，このような制約付きマッチングでのメカニズム設計について概説する．

マを自分で研究することは考えていなかった．実際，

1 はじめにゲールとシャプレイの論文が出版されたのは 1962 年

マッチングは，生徒と学校，労働者と企業のようなとずいぶん前 (ちなみに筆者が生まれた年) である．

二種類のエージェント間の望ましい組合せを求める問

さぞかし，重要な研究テーマのほとんどは研究が進ん題であり，生徒と学校をマッチする学校選択制，研修でおり，大事な研究テーマは残っていないだろうとい医と病院をマッチする研修医配属問題，また，大学関う漠然とした印象を持っていた．

係者に非常に身近な問題として，学生を卒業研究のところが，2011 年度の九州大学電気情報工学科で研究室にマッチする研究室配属問題，さらに生体腎移の卒業研究配属の担当となったため，実際に研究室配植において，患者とドナーをマッチする腎臓交換メカ属のメカニズム設計を手がけることとなった．それまニズムなどの広範な応用を持つ．ロイド・シャプレイ

でに用いられていた方式は第一希望優先方式（ボストとアルビン・ロスはマッチングメカニズムの理論とそン方式）と呼ばれるもので，学生側は自身の希望するの実践に関する業績で 2012 年のノーベル経済学賞を研究室を第 1 希望から第 n 希望まで申告する．メカ受賞している．特に，デイビット・ゲールとロイド・ニズムはまず，全学生の第 1 希望において定員を満シャプレイによる，受入保留 (deferred acceptance,たすまで成績順に配属し，配属されていない学生とDA) メカニズム [1] がよく知られている．

定員の残る研究室で次の希望順位について同様に繰

本稿では，マッチングの結果に対して様々な制約がり返すというものである．この方式の問題点として，課せられる制約付きマッチングにおけるメカニズム設学生同士の読みあいが必要であるという点がある．こ計について概説する．最初に，筆者がこの研究テーマの方式では，各学生は，自分より成績の良い学生の希に興味を持ったきっかけについて述べる．ごく最近ま望順位に応じて、自分の希望順位を適切に決める必で，筆者はメカニズムデザインの一分野として，DA要があるが，この読みを間違えると望ましくない結メカニズム等の一応の知識はあったものの，このテー果になる．例えば，学生 1 の希望は A 研究室であるが，自分の成績だと第 1 希望で通る自信がもてず，BMechanism Design for Constrained Matching
Makoto Yokoo, 九 州 大 学 大 学 院 シ ス テ ム 情 報 科 学 研究院, Faculty of Information Science and ElectricalEngineering, Kyushu University.

研究室を第 1 希望にしたとする．しかし，蓋を開けてみると難関の A 研究室は多くの学生が敬遠し，自分より成績が低い学生 2 が配属されたとする．この

結果は学生 1 にとっても，A 研究室にとっても望ま

この学生は上限制約を満たす範囲で，もっとも好きなしくない (後述するフェアでない結果となっている).

研究室に配属される．そうでない場合は，下限制約をせっかくなので，理論的に優れた DA メカニズム

未だ満たしていない研究室の中から，もっとも好きなを利用したいと教授会で提案して合意が得られた．通研究室に配属される．この方式を用いた場合，各学生

常，このような制度の変更は，様々な立場からの意見は自分の選好順を偽って申告する誘因を持たない．さが出て，なかなか合意が得られないものであるが，こらに，この方式を工夫することにより，研究室が個別の年度では各研究室の定員枠を固定できないというの優先順位を持つ場合にも対応可能となることが分事情により，従来方式では対応が難しいということかかった．

ら，制度の変更の必要性に関して容易に合意が得るこ以上，やや長文となってしまったが，この経験で分とができた．具体的には，この年度は留年等により卒かったこととして，DA メカニズムを実際の問題に適論に着手できない学生が多く，従来の定員枠を満たす用しようとした場合，マッチングに対して，なんらか十分な学生が確保できないため，各研究室には最低のの制約が課せられることが通例であり，そのような制配属人数を保証し，学生の希望に応じて，追加でさら約付きのマッチングに関しては，様々な研究課題がに一名の学生が配属可能とした．このように状況に残っているということがある．前述の例では，各研よって定員が変わってしまうと，従来方式での学生同究室の配属人数の下限に対して制約が課せられたが，士の読みあいが格段に難しくなってしまい，従来方式例えば学科がいくつかのコースに分かれている場合，では破綻することが容易に想像できたのである．

あるコースに学生が集中するのは望ましくないといっ

当初は単に DA メカニズムを使えば良いと思っていたのだが，各研究室の最低配属人数を保証するたた，コース毎の上限制約が課せられることも考えられる．

めには，DA メカニズムの修整が必要である．これぐ以下，マッチング理論の基礎となる，一対一のマッらいは既存研究で当然やられているだろうと思って，チングを扱う安定結婚問題と DA メカニズムについたまたま知り合いだった日本と米国のマッチング研究て説明し，続いて多対一のマッチングに関して，問題のプロフェッショナルに相談したところ，この問題はのフォーマルな定義，望ましい性質，および DA メ

難しくて良い方法が知られていないと言われて愕然

カニズムについて概説する．さらに，地域上限，およとした次第である．すでに教授会で，既存方式の問題び個別下限を扱う DA メカニズムの拡張について紹点は，DA メカニズムですべて解決できると大見得を介する．

切ってしまっていた．
さすがにいまさら従来方式に戻すとも言えず，何と2 一対一のマッチング (安定結婚問題)かする方法がないかと考えたところ，この配属におけマッチングの理論的な基礎となる問題として，安定る特殊な性質を使えば，最低配属人数（後述する下限結婚問題というものがある．これは男女がそれぞれ制約）を満たすメカニズムがなんとか設計できるこn 人いるとして，ある望ましい性質を満たす n 組のとに分かった．具体的には，通常のマッチングでは，男女のペア（マッチング）を作るというものである．

学生，研究室といった両方のエージェントが，個別の望ましい性質として，ここでは安定性を考える．例え選好ないしは優先順位を持つことが通例であるのにば Alice, Becky, Carol, Daisy の 4 名の女性，John,対して，九州大学での研究室配属では，各研究室毎のKen, Lee, Mike の 4 名の男性がいるとする．各男学生に対する優先順位は存在せず，学科で共通の成績性は 4 人の女性に対して，各女性は 4 人男性に対し順を用いることが要求されている．この性質を使ってて，好みの順番が決まっている．当然，好みの順番以下のようなメカニズムが構築可能である．成績が上は（たまたま同じとなるかも知れないが）人によっ位の学生から順に配属先を決定する．配属先の決定て異なる．Alice にとって，より望ましい男性の順がにあたって，残りの学生で下限制約が満たせるなら，J A K A L A M であるとし, John にとって，より望ましい女性の順が A J B J C J D である

でにプロポーズして断られている．また，男性に関しとする．ここで，もし Alice のペアが Ken で，Johnては，今まで自分にプロポーズしてきた女性の中で，のペアが Becky だと，Alice と John は今のペアと別最も望ましい女性と婚約している（すなわち，自分にれてペアとなった方が二人とも今より幸福になることとってより好ましい女性は，自分以外の男性にプロになる．このようなペアを不安定なペアと呼び，不安ポーズしている）．このことから，全員が婚約してい定なペアを含まないマッチングを安定なマッチングとる終了時のマッチングが安定であることが導かれる．

呼ぶ．

さらに，女性にとっては，まだプロポーズしていなさて，どうしたら安定なマッチングを求めることがい中で最も好みの男性にプロポーズするのが最適であできるだろうか? 最も単純な方法として，男性の順序る，すなわち，正直が最良の策であることが示さる．

を，J, K, L, M で固定し，女性 A, B, C, D の並び替要は，この方式ではプロポーズして断られても，そのえをすべて生成し，J, K, L, M と組み合わせて，安定後に不利な扱いを受けることはないので，玉砕覚悟でかどうかをチェックするという総当り法が考えられる

最も好みの相手にプロポーズするのが最適となる．

が，これは，最悪，n! の組合せをチェックすることに一方，男性にとっては，現在自分にプロポーズしてなり，人数が増えると絶望的となる．もっと効率的にいる女性の中で，最も好みの女性を選ぶのが最適と安定マッチングを見つける方法として提案されているは限らない．あえて好みでない女性を選ぶことで，結のが，前述のロイド・シャプレイと，デイビッド・ゲ果としてより望ましい女性と結ばれるという，恋愛ドイルによる受入保留 (deferred acceptance, DA) メカ

ラマで出てくるような複雑な状況が存在し得る．興ニズムである．この方式では，男性／女性は，独身，味のある読者は，ぜひ例を考えてみて頂きたい．これ

婚約中のどちらかであり，初期状態では全員独身であは DA メカニズム固有の問題点ではなく，文献 [3] でる．独身の女性が残っていれば，以下の処理を繰り返は，男性と女性の両方にとって正直が最良となるメカし適用する．

ニズムは理論的に存在し得ないことが示されている．

• 独身の女性は，これまでにまだプロポーズをしていない男性のうちで，最も好みの男性にプロ3 多対一のマッチングポーズする（男性が婚約中でも気にしない）．

3. 1 モデル• その際，一人の男性には一回しかプロポーズで

本稿では以下，二種類のエージェントを示す際に，きない（一度断られた男性には二度とプロポーズ

学生と学校という用語を用いるが，学生と研究室，できない）．

研修医と病院と読みかえれば対応する問題に対応で• 男性は，自分にプロポーズしている女性の中で，最も好みの女性と婚約し，他の女性のプロポーズを断る (現在婚約中の女性がいても，より良い相きる．
多対一のマッチング問題は hS, C, q, S , C i の組で定義される．

手がプロポーズしてきたら，現在の婚約を解消し• S = {s1 , s2 , . . . , sn }: 学生の集合て，最も好みの女性と改めて婚約する).

• C = {c1 , c2 , . . . , cm }: 学校の集合

独身の女性がいなくなれば，現在婚約中のペアでマッ• q = (qc )c∈C : 学校の個別の上限のベクトルチングを決定する．

• S = (s )s∈S : 学生の学校に対する厳密な (同この方式を用いた場合，各女性は，一人の男性に一回しかプロポーズできないので，繰り返しは高々4 回点のない) 選好順序のベクトル．c1 s c2 は，学生 s が c2 より c1 を好むことを示す．

(n 人なら n 回) で終了する．次に，この方式で安定な• C = (c )c∈C : 学校の学生に対する厳密な (同マッチングが得られることを示そう．任意の時点で，点のない) 優先順序のベクトル．s1 c s2 は，学婚約中の男女に関して以下の性質が成立する．女性に校 c に関して，学生 s1 の方が s2 より優先順位が関しては，婚約中の相手よりも望ましい男性には，す高いことを意味する．

以下の議論では，簡単のため，各学校および各学生にいう．

関して，すべての学生およびすべての学校は許容可能言葉で説明すると，学生 s は，自分が割り当てられたである (どうしても行きたくない学校，絶対に入学を学校 µ(s) よりも，他の学生 s0 が割り当てられた学校許可できない学生は存在しない) ことを仮定する.

c の方が望ましいと考えており，かつ，学校 c の優先

定義 1 (マッチング) マッチングは以下の性質を満たすマッピング µ : S ∪ C → 2S∪C である†1

順位において s が s0 より上位の場合，s は s0 に対して妥当な不満を持つ．

1. すべての s ∈ S に関して µ(s) ∈ C,

前章で述べた安定なマッチングは，フェアかつ無駄

2. すべての c ∈ C に関して µ(c) ⊆ S,がないマッチングに対応する．ある学生 s が，ある学

3. すべての s および c に関して s ∈ µ(c) の場合，校 c に割り当てられている学生に妥当な不満を持つ

かつその場合に限り µ(s) = c.

場合，もしくは c の空きシートを要求する場合，s と定義 2 (実行可能性) マッチングは以下の性質を満たc が不安定なペアとなる．

す場合に実行可能であるという: ∀c ∈ C, |µ(c)| ≤ qc

定義 5 (戦略的操作不可能性) あるメカニズムにおいが成立．て，s 以外の学生の申告を固定し，s が真実の選好を以下，マッチングメカニズムが満たすべき望ましいした場合に得られるマッチングを µ，真実と異なる申性質を示す．まず，マッチングにおいて無駄がないと告をした場合に得られるマッチングを µ0 として，常いう，良く知られたパレート効率性を弱めた性質を定に µ(c) s µ0 (c), もしくは µ(c) = µ0 (c) が成立する

義する．

場合，このマッチングメカニズムは戦略的操作不可能

定義 3 (無駄のないマッチング) マッチング µ におであるという．

いて, 学生 s，学校 c に関して，c s µ(s) および

すなわち，戦略的操作不可能なメカニズムでは，学生|µ(c)| < qc が成立する際，学生 s は学校 c の空きシーは自身の選好順序を偽って申告する誘因を持たない．

トを要求するという. マッチング µ において，空き以下，DA メカニズムの概要を示す．

シートを要求する学生が存在しない場合，マッチングは無駄がないという．また，あるメカニズムが，任意

3. 2 DA メカニズムの入力に対して無駄のないマッチングを出力する場

第 1 ステップ： 各学生を，それぞれ希望順位 1 位合，このメカニズムは無駄がないという．の学校に割り振る．定員枠を超えなかった場合

すなわち，学生 s にとって，割り当てられた学校 µ(s)は，希望学生をその学校に仮にマッチさせる．定よりも好ましい学校 c の上限が満たされていない場

員枠を上回った場合は，希望学生を各学校の優先合，学校 c の空きシートを要求することができる．

順位の高い方から定員枠まで仮にマッチさせる

次に，学生間の公平性に関する概念を導入する．

（あくまでこの段階では仮マッチであり，後のス定義 4 (フェアなマッチング) マッチング µ におい

テップで定員枠からもれる可能性があることに注て，学生 s に関して以下の条件が成立する場合，s は，意）．その他の学生はリジェクトする．

0

学校 c に配属されている別の学生 s に対して妥当な
0

第 2 ステップ： 第 1 ステップでリジェクトされた

不満を持つという: c s µ(s) かつ s c s . マッチン

学生をそれぞれの第 2 希望の学校に割り振る．

グ µ において，妥当な不満を持つ学生が存在しない

個々の学校において，第 2 ステップで移動した学

場合，マッチングはフェアであるという．また，ある生と，既に仮にマッチしている学生を合わせて，メカニズムが，任意の入力に対してフェアなマッチン

第 1 ステップと同様にマッチングを行う．すなわ

グを出力する場合，このメカニズムはフェアであるとち，定員枠以内であれば全員を仮にマッチとし，†1 この定義では，厳密には µ(s) は {c} のように要素が一つの集合として記述すべきであるが，µ(s) = c と略記するのが慣例となっている.

定員枠を超えた場合は，各学校の優先順位の高い方から定員枠まで仮にマッチとし，残りの学生はリジェクトされる．
」

...の配属人数が 20 名以下となることを要求するのが地

第 k ステップ： 第 k − 1 ステップでリジェクトさ域上限である．

れた学生を，それぞれの第 k 希望の学校に割り地域上限を扱う最も簡単な方法として，地域上限を振る．以下，リジェクトされた学生が一人もいな満たすように，人為的に個別の学校の上限を厳しくくなるまで同様の手順を続ける. 最終的に，それする方法がある．例えば，合計で 20 名以下という上ぞれの学校と仮にマッチしていた学生を正式配属

記の制約を満たすためには，個別の研究室の上限を 2とする．とすればよい．この場合，個別の上限を満たせば自動学生を女性，学校を男性と考えれば，前章で示したメ的に地域の上限を満たすことができるため，得られたカニズムと本質的に同じ処理が行われていることは個別の上限のみの問題を，通常の DA メカニズムを明らかである．

用いて解けば良い．この方法を人為的キャップ DA と定理 1 (DA メカニズムの性質)

呼ぶ [2]. しかしながら，人為的キャップ DA の問題

DA メカニズムは戦略的操作不可能であり，無駄がな点として，柔軟性に欠ける点がある．情報科学コース

くフェアである．

内の研究室で人気に差がある場合，ある研究室には 3

ここでの戦略的操作不可能性の定義は，学生のみを対名の学生を割り当て，人気のない研究室には 1 名の象としており，学校側が選好を偽る可能性は考慮して学生を割り当てることによっても，合計人数の制約はいないことに注意されたい．DA メカニズムでは，あ満足できるが，人為的キャップ DA では，各研究室のる学生 s がある学校 c からリジェクトされている場

配属人数は 2 名以下に制限されてしまう．

合，c は上限まで学生をアクセプトしており，c にア

この問題点を解決するために考案されたメカニズ

クセプトされた学生は，c の優先順位で s より上位にムが，文献 [2] に示されている Flexible DA メカニズ

なっていることから，無駄がなくフェアであることがムである．このメカニズムでは，学校の集合 C に関導かれる．

して，学校の選択順リストと呼ばれる，学生を選択する順序が与えられる．Flexible DA メカニズムでは，

4 地域上限の導入

DA の各ステップ内で，すべての学生が仮マッチもし研究室配属において，ある学科の研究室が，情報科

くはリジェクトになるまで以下を実行する．すなわ

学，電子システム等の複数のコースに分かれている状

ち，学校の選択順リストの順番に従って，個別の上限況を考えよう．学科のポリシーとして，あるコースにおよび地域の上限に違反しない限り，各学校は希望し過度に学生が集中することは望ましくないすることている学生から，自分の優先順位で最も上位の学生をは自然である．また，研修医の配属において，大都市一人，仮マッチにできる．そうでなければ希望してい圏に過度に研修医が集中することも望ましくないとる学生をすべてリジェクトする．選択順リストの最後考えられる．地域上限の導入は，このようなポリシーの学校に関する処理が終われば，選択順リストの先頭の実現を可能とする．に戻って (ラウンドロビン式で) 処理を続行する．

前章で示した基本のモデルに，地域の集合 R =地域上限がある場合，空きシートを要求することの{r1 , r2 , . . .} を加える．各地域 r は C の部分集合で互定義の修整が必要となる．

いに素である．また，各地域の地域上限である qr が定義 6 (無駄のないマッチング (地域上限)) マッチン与えられる．マッチング µ が feasible となるためにPは，通常の上限制約に加えて, | c∈r µ(c)| ≤ qr といグ µ において, 学生 s，学校 c, 学校 c が属する地域

う，地域上限に関する制約が加えられる．例えば，情r に関して，c s µ(s) および |µ(c)| < qc ，およびP| c0 ∈r µ(c0 )| < qr が成立する際，学生 s は学校 c

報科学コースに 10 の研究室が所属し，各研究室の個の空きシートを要求するという. マッチング µ にお別の上限が 3 であるとする．ここで，情報科学コーいて，空きシートを要求する学生が存在しない場合，

ス全体としての配属人数に制約を与える，例えば合計マッチングは無駄がないという．また，あるメカニズ

ムが，任意の入力に対して無駄のないマッチングを出力する場合，このメカニズムは無駄がないという．

えられる．
また，無駄のないマッチングの定義を以下のようにすなわち，空きシートを要求するためには，行きたい修整する．

学校 c に空きがあるだけでは不十分で，c の属する地

定義 8 (無駄のないマッチング (下限制約)) マッチン

域にも空きがある必要がある．

グ µ において, 学生 s，学校 c, および c0 = µ(s) に関

しかしながら上記の定義は，c と µ(s) が同じ地域

して，c s c0 ，|µ(c)| < qc ，および |µ(c0 )| > pc0 がに属している場合を考慮していないため不十分であ成立する際，学生 s は学校 c の空きシートを要求する．すなわち，c と µ(s) が同じ地域に属するなら，地るという. マッチング µ において，空きシートを要求域上限に違反することなく，s を µ(s) から c に移動する学生が存在しない場合，マッチングは無駄がないできる．以下，このような場合に対応する追加の条件という．また，あるメカニズムが，任意の入力に対しを示す．て無駄のないマッチングを出力する場合，このメカニ

定義 7 (強い意味での無駄のないマッチング) マッチズムは無駄がないという．

ング µ において, 学生 s，学校 c, 学校 c が属する地域

すなわち，学生 s が学校 c の空きシートを要求する

r に関して，µ(s) が r に属し，c s µ(s)，|µ(c)| < qc ，P
および | c0 ∈r µ(c0 )| = qr が成立する際，学生 s はためには，行きたい学校 c に空きがあるだけでなく，学校 c の空きシートを地域的に要求するという．マッ

おり，s が c に移動しても，すべての上限／下限制約

チング µ において，空きシートを要求する学生，おが満足される必要がある．

現在割り当てられている学校 c0 が下限制約を超えてよび空きシートを地域的に要求する学生が存在しな

下限制約がある場合には，地域上限制約の場合と同い場合，強い意味でマッチングは無駄がないという．

様に，マッチングがフェアであることと無駄がないこ

また，あるメカニズムが，任意の入力に対して強い意とは両立不可能であることが示されている．筆者ら

味で無駄のないマッチングを出力する場合，このメカは文献 [4] で，下限制約に対応する DA ベースの戦略

ニズムは強い意味で無駄がないという．

的操作不可能性を満たす二つのメカニズムを示して定理 2 (Flexible DA メカニズムの性質)いる．一つは Extended-seat DA メカニズムと呼ばFlexible DA メカニズムは，戦略的操作不可能，フェれるもので，フェアであるが無駄がある．もう片方はア，かつ無駄がないが，強い意味で無駄がないことはMulti-stage DA メカニズムと呼ばれ，無駄がないが保証されない．一方，人為的キャップ DA では，戦略フェアではない．以下，それぞれのメカニズムのアイ的操作不可能かつフェアであることは保証されるが，デアを示す．

人為的に制限される前の本来の上限の元では，通常のExtended-seat DA メカニズムの基本的なアイデア意味で無駄がないことも保証されない．

は，各学校を二つの学校に分割することにより，個別

実際，ある状況では，フェアかつ強い意味で無駄のなの上限／下限が存在する問題を，個別の上限と，地いマッチングは存在し得ないことが示されているた域の上限が存在する (下限が存在しない) 問題に変換

め，一般にマッチングがフェアであることと，強い意し，地域の上限が扱える Flexible DA メカニズムを味で無駄がないことは原理的に両立不可能である．

用いるというものである．具体的には，各学校 c を通常枠と呼ばれる学校 c0 と，拡張枠と呼ばれる学校 c00

5 下限制約に分割する．ここで，通常枠の学校 c0 の個別の上限

学校個別の下限制約が存在する場合のモデルは，は，本来の下限である pc として，拡張枠の学校 c00 の3. 1 章で示した基本のモデルに，各学校の個別の下限

個別の上限は，本来の個別の上限と下限の差分であるのベクトル p = (pc )c∈C を加える．また，マッチングµ が実行可能となるためには，通常の上限制約に加えqc − pc とする．さらに，拡張枠の学校全体で一つの地P
域 r を構成し，この地域 r の上限 qr を，n − c∈C pcて, pc ≤ |µ(c)| という，個別の下限に関する制約が加とする．全体で n 人の学生が存在し，拡張枠には合計で n −Pc∈C pc 人の学生のみが配属可能であるため，通常枠には合計でP

定理 4 (Multi-stage DA メカニズムの性質)c∈C pc 人の学生が配属されMulti-stage DA メカニズムは下限制約を満たし，戦る．ここで，通常枠の学校 c0 の個別の上限は pc であ

略的操作不可能で無駄がないが，フェアであることはるため，すべての通常枠の学校は上限まで埋まる，す保証されない．

なわち元の問題で下限制約が満たされることが保証

各学生にとって，自分がどのグループに含まれるかはされる．

マスターリストで決められるため，戦略的な操作を行定理 3 (Extended-seat DA メカニズムの性質)う余地が存在しない．また，学生 s が上限を満たして

Extended-seat DA メカニズムは下限制約を満たし，いない学校から reject されるのは，上の 2 の処理が戦略的操作不可能かつフェアであるが，メカニズムに生じた場合のみであり，この場合, s が配属される学無駄がないことは保証されない．

校は必ず下限ぎりぎりの人数のみが配属されており，Extended-seat DA メカニズムがフェアであること空きシートを要求する学生は存在せず，Multi-stageは，ある学生 s が c からリジェクトされた場合，c にDA メカニズムは無駄がない．しかしながら，マスアクセプトされている学生は，全員 s よりも優先順

ターリストの順位は，各学校の優先順位とは一般には位が高いことから導かれる．

異なるため，マッチングがフェアであることは保証でMulti-stage DA メカニズムでは，各学校の個別のきない．すなわち，学生 s が学校 c の優先順位でトッ優先順位に加えて，すべての学校で共有される，共通プであっても，マスターリストでの順位が低ければ，の学生に対する順位付け（マスターリスト）が存在すc に配属されない可能性がある．

ることを仮定する．最初に述べた九州大学での研究室配属では，共通の成績順というマスターリストの6 おわりにみが存在していた．Multi-stage DA メカニズムでは，本稿では，マッチングの結果に，個別の下限や地域マスターリストを用いて学生を上位グループと下位の上限等の制約が課せられる制約付きマッチングにグループに分ける．その際，下位グループの人数を，Pc∈C pc , すなわち下限制約の合計と等しくなるよう関して概説した．このようなメカニズムに関する研に選んでおく．次に，上位グループの学生を，学校個界領域の研究分野であり，歴史のある研究分野ではあ別の上限のみを考慮する通常の DA メカニズムを用るが未解決な問題が山積しており，計算機科学の側かいて割り当てる．上位グループの学生を割り当てた状らの貢献が期待される．マッチング理論に関して，文況で，各研究室の上限／下限を再計算する．ここで生

献 [5] は，日米にまたがる学校選択制の実際と理論にじ得る状況は以下の三通りである.

詳しい良書である．また，解説記事として文献 [6] が1. すべての下限制約が満足されている場合：下位

究は，ミクロ経済学，ゲーム理論と計算機科学の境ある．

グループの学生を，通常の DA メカニズムを用いて割り当てる．

2. すべての下限制約の合計が，下位グループの学生の数と等しい場合：各研究室の上限制約を下限制約に置き換えて，下位グループの学生を，通常の DA メカニズムを用いて割り当てる．

3. 下限制約の合計が，下位グループの学生数より少ない場合：最初の処理と同様，下位グループを，さらに上位と下位の二つに分割し，再帰的に同様の処理を行う．その際に，下位グループの人数を，下限制約の合計と等しく選ぶ．

参 考 文 献[1] Gale, D. and Shapley, L. S.: College Admissions
and the Stability of Marriage, American Mathematical Monthly, Vol. 69(1962), pp. 9–15.
[2] Kamada, Y. and Kojima, F.: Stability andStrategy-Proofness for Matching with Constraints:
A Problem in the Japanese Medical Match andIts Solution, American Economic Review, Vol. 102,No. 3(2012), pp. 366–70.
[3] Roth, A. E.: The Economics of Matching: Stability and Incentives, Mathematics of Operations Research, Vol. 7(1982), pp. 617–628.
[4] Ueda, S., Fragiadakis, D., Iwasaki, A., Troyan,

P., and Yokoo, M.: Strategy-proof mechanisms for
two-sided matching with minimum and maximum
quotas, Proceedings of International Conference
on Autonomous Agents and Multiagent Systems(AAMAS-2012), 2012, pp. 1327–1328. An extended
version is available at: https://sites.google.com/

site/petetroyan/files/Fragiadakis_et_al_RES.pdf.
[5] 安田洋祐 (編): 学校選択制のデザイン: ゲーム理論ア
プローチ, NTT 出版, 2010.
[6] 小島武仁, 安田洋祐: マッチング・マーケットデザイ
ン, 経済セミナー, No. 647(2009), pp. 135–145.