FIT2013（第 12 回情報科学技術フォーラム）RF-004

地域制約の下での戦略的操作不可能なマッチングメカニズム1

橋本 直幸∗

上田 俊 ∗

岩崎 敦 ∗

安田洋祐†

横尾 真 ∗

Hashimoto Naoyuki

Suguru Ueda

Atsushi Iwasaki

Yosuke Yasuda

Makoto Yokoo限と比較して下限制約に関する研究例が少ない．残された数

序論

多くの組み合わせに関しては，未だ十分な研究が行われてい学生と学校，研修医と病院，労働者と企業のように，二種類ないのが現状である．

のエージェント間の望ましい組合せを求めるマッチング理論

そこで本論文では，表の太字で示す範囲の組合せに関してに関する研究が盛んであり，詳細なサーベイとして文献 [10]検討を行う．より詳細には，本論文ではまず，一般の場合の等が存在する (本論文では二種類のエージェントを示すために

地域制約を満たす (実行可能な) マッチングが存在するか否か

学生と学校という用語を用いる). 既存研究では，ある学校にを問う決定問題の計算量が NP 完全であることを示す．次に割り当てられる学生数に上限が課せられるといった，個別の本論文では，serial dictatorship with regional quotas (SDRQ) お

上限制約が考慮されていた．しかしながら，現実の応用問題

よび multi-stage DA with regional quotas (MSDARQ) と呼ばれを考えると上限制約のみでなく，ある学校に割り当てられる

る，階層的な地域下限制約および個別の上限制約が存在する

学生数が一定の人数以上であることを要求するといった，下場合に適用可能なメカニズムを提案する．これらが戦略的操限制約が必要となる場合が存在する．さらに，これらの上限

作不可能かつ無駄がなく，すべての学校で共通である学生の／下限制約は，個別の学校に対してではなく，学校の集合 (地ランキング (マスターリスト) の下でフェアであることを示す．

域) に対して課せられる可能性がある．

本論文では地域制約を直接扱うメカニズムを開発することこのようなモデルが必要とされる具体的な応用例として，研を目標としている．異なるアプローチとして，地域制約を個

修医と病院のマッチングがある．例えば，政策決定者は，ある別制約に変換して扱う方法が存在する．具体的には，このア

離島の複数の病院に対して一定の数以上の研修医が配属されプローチでは，個別制約が満足されれば自動的に地域制約が満ることが望ましいと考えているとする．しかしながら政策決足されるように，人為的に厳しい個別制約を設定する．この定者は，これらの研修医が具体的に離島内の複数の病院にどような変換を行えば個別制約のみが扱える既存のメカニズムのように配属されるかに関して必要以上の干渉をする意志はを用いることが可能となる．このようなアプローチを人為的なく，対象となる研修医と病院の選好／優先順位に応じて決キャップアプローチと呼ぶ．しかしながら，人為的キャップ

められるべきであると考えているとする．このような政策決アプローチでは制約を満足するマッチングの可能性を人為的定者のマッチングの結果に関する要求条件は，地域下限制約に厳しく制限しているため，得られる結果に対する学生の満を用いて自然に表現可能である．

足度や公平性が著しく損なわれる可能性がある．シミュレー

表 1 に，地域上限／下限制約に関する既存の研究 (および本ションによる評価により，本論文で新しく提案したメカニズ

論文での新しい貢献) を示す．個別の上限制約は必須として，

ムは，人為的キャップアプローチと比較して，地域制約をより

地域制約に関しては，重要な特殊例である地域制約が階層的柔軟に扱うことを可能にしており，学生の満足度および公平な構造を持つ場合と，一般の場合に分類して考えると，上限制性の観点で人為的キャップアプローチよりもはるかに優れて約に関しては，個別の上限制約のみ，階層的な地域上限制約，いることを示す．

一般的な上限制約の 3 通り，下限制約に関しては，下限制約なし，個別の下限制約のみ，階層的な地域下限制約，一般的な下限制約の 4 通りの可能性があり，合計で 3 × 4 = 12 通りの

表1

地域制約の下でのメカニズムの分類 (∗:本論文で得られた結果，KK: Kamada and Kojima, 2012, BFIM: Biro et al.,2010).

組合せが考えられる．個別の上限が存在する場合には，その場合においてフェアで無駄がなく，かつ戦略的操作不可能であるという望ましい性質を持つ deferred acceptance (DA) メカ
ニズムが広く知られている．文献 [3, 7] では階層的な上限が存在する場合のメカニズムを提案している．一方で，文献 [5]Minimum

では個別の下限制約を扱うメカニズムを提案しているが，上

quotas∗ 九州大学大学院システム情報科学府

none
individual
hierarchicalregions
generalregions

Maximum quotas
hierarchicalindividual
regionsDA
KK/BFIMMSDA
MSDARQ∗
open
SDRQ∗

generalregions

NPcomplete∗

NP-complete∗† 政策研究大学院大学

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

FIT2013（第 12 回情報科学技術フォーラム）2

定義 2. マッチング µ において，学生 s に関して以下の条件がモデル成立する場合，s は，別の学生 s′ に対して妥当な不満を持つ

地域制約が存在する場合の学生と学校の間のマッチングという: µ(s′ ) ≻s µ(s) かつ s ≻µ(s′ ) s′ . マッチング µ におい

問題は (S, C, R, p, q, ≻S , ≻C , ≻M L ) の組で定義される．S =て，妥当な不満を持つ学生が存在しない場合，マッチングは{s1 , s2 , . . . , sn } は学生の集合，C = {c1 , c2 , . . . , cm } は学校の集合であり，n = |S|，m = |C| とする．また，R = {r1 , r2 , . . .}フェアであるという．

は地域の集合であり，各地域 r は，学校の部分集合 r ∈ 2C \ ∅として与えられる．p = (pr )r∈R と q = (qr )r∈R は地域下限と上限のベクトルであり，すべての r ∈ R に関して 0 ≤ pr ≤ qrが成立する．各学生 s は学校に対して厳密な選好順序 ≻s を持つ．また，同様に各学校 c は，学生に関して個別の優先順
位 ≻c を持つ．これらの順序関係のベクトルを，学生に関して≻S = (≻s )s∈S ，学校に関して ≻C = (≻c )c∈C と表記する．各学校の学生に対する個別の優先順位は，成績等の客観的な基準に基づいて定められることが通例であり，公知となってい言葉で説明すると，学生 s は，自分が割り当てられた学校µ(s) よりも，他の学生 s′ が割り当てられた学校 µ(s′ ) を好んでおり，かつ，学校 µ(s′ ) の優先順位において s が s′ より上位の場合，s は s′ に対して妥当な不満を持つという．
これらの要求条件は自然であるが，個別の上限／下限制約のみが存在する場合においても，フェアかつ無駄のないマッ
チングが存在しない場合があることが示されている [4]. このため，ML を用いて，マッチングがフェアであるという定義を緩めた，ML の下でフェアという概念を導入する．

るとする．また，学校個別の優先順位に加えて，マスターリ

定義 3. マッチング µ において，学生 s に関して以下の条件がスト (Master List, ML) [6] と呼ばれる学生間の順位付けが存成立する場合，s は，別の学生 s′ に対して，強い意味で妥当な在することを仮定する．この仮定はマッチング理論の研究に不満を持つという: µ(s′ ) ≻s µ(s), s ≻µ(s′ ) s′ かつ s ≻M L s′ ．

おいて頻繁に用いられており [8, 9, 2]，GPA や TOEFL のスコ

マッチング µ において，強い意味で妥当な不満を持つ学生がアなどを想定している．ML と学校個別の優先順位の間には，存在しない場合，マッチングは ML-フェアであるという．

何らかの相関があると考えられるが，本論文で提案するメカ
ニズムの理論的性質は，こうした相関の有無には影響されな
い．以下，一般性を失うことなしに，マスターリストでの順位
は，s1 ≻M L s2 ≻M L · · · ≻M L sn であることを仮定する．さらに，各学校および各学生に関して，すべての学生およびすべての学校は許容可能であることを仮定する (学生／学校に対して，特定の学校／学生を許容不可能とした場合，すべての学校の下限制約を満足することは一般には不可能である).
マッチングは以下の性質を満たすマッピング µ : S ∪ C →S ∪ C である: (i) すべての s ∈ S に関して µ(s) ∈ C, (ii) す
べての c ∈ C に関して µ(c) ⊆ S, (iii) すべての s および c に関して s ∈ µ(c) の場合，かつその場合に限り µ(s) = c. また，マッチングは以下の性質を満たす場合に実行可能であるという: ∀r, pr ≤∑c∈r |µ(c)| ≤ qr が成立．

以下，マッチングが満たすべき望ましい性質として，無駄がない，およびフェアという性質を示す．ここで，学校 c を要素に持つ r の集合を regions(c) と表記する．

ここでは，強い意味で妥当な不満を持つためには，s が s′ よりも ML で上位であるという追加の条件を与えている．
メカニズムは，学生の選好順序のベクトルを入力として，マッチングを返す関数である．メカニズムが無駄がないとは，任意の学生の選好順序のベクトルに対して，必ず無駄のないマッチングを与えることをいう．同様にメカニズムが (ML-)
フェアであるとは，任意の学生の選好順序のベクトルに対して，(強い意味で) 妥当な不満を持つ学生が存在しないマッチ
ングを与えることをいう．また，メカニズムが戦略的操作不可能であるとは，どの学生も，他の学生の行動に関わらず，自身の選好順序を偽って申告する誘因を持たないことをいう．

3 実行可能なマッチングを求める計算量
3.1 一般の場合あるマッチング問題のインスタンスが与えられた場合，最初にチェックすべきこととして，すべての制約を満足する実行
可能な割当てが存在するか否かを判定することがある．通常

定義 1. マッチング µ において, 学生 s, 学校 c に関して，以下の個別の上限制約のみが存在する場合には，この判定は簡単の条件が成立する場合，学生 s は学校 c の空きシートを要求すであり，学生数 n が個別の上限の合計以下であればよい．し|µ(c′ )| <∑qr , および (iii) ∀r ∈ regions(µ(s)), c′ ∈r |µ(c′ )| > pr .

かしながら，地域上限／下限の導入により，この判定ははるかるという: (i) c ≻s µ(s), (ii) ∀r ∈ regions(c),

∑

c′ ∈r

マッチング µ において，空きシートを要求する学生が存在しない場合，マッチングは無駄がないという．

に難しくなり，以下の定理に示すように NP 完全となる．
定理 1. 与えられた S, C, R, p, および q に関して，実行可能なマッチングが存在するか否かの判定問題は NP 完全である．
これは，任意の r ∈ R に関して，|r| が 1, 2, もしくは 3 のい言葉で説明すると，学生 s は，自分が割り当てられた学校µ(s) よりも，他の学校 c を好んでおり，かつ，s の割り当てられる学校を，µ(s) から c に変更しても，c と c を含む任意の地

場合に 0 であり，|r| = 3 のときに限り qr は 3 で，その他の場

域の上限制約，および µ(s) と µ(s) を含む任意の地域の下限制

合に 1 である特殊ケースに限定しても成立する．

ずれかのみであり，|r| = 3 のときに限り pr は 1 で，その他の約が満足される場合，s は c の空きシートを要求するという．

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

FIT2013（第 12 回情報科学技術フォーラム）証明. 与えられたマッチングがすべての制約を満たすかどうか

前節で述べた変換方法により，すべての地域下限制約は地のチェックは多項式時間で可能なので，この判定問題はクラス

域上限制約に変換可能である．一般に，下限制約は上限制約

NP に属することは明らかである．以下に，任意の 3-SAT 問よりも扱い難いと考えられており既存研究も少ない．すべて

題のインスタンスが，この問題に帰着できることを示す．よ

の地域下限制約を地域上限制約に変換し，既存の地域上限制

く知られている 3-SAT 問題は，論理変数の集合 X と節の集合約を扱えるメカニズム [3, 7] を適用するといったアプローチ

L で定義される．各節 l は，例えば x1 ∨ ¬x2 ∨ x3 のような 3も考えられるが，個別の下限制約を地域上限制約に変換した

つのリテラルの選言であり．各リテラルは，論理変数 x ∈ X

場合，これらの地域上限制約は階層的にはなり得ない．よっもしくはその否定 ¬x である．

て，文献 [3, 7] に示されている階層的上限制約を扱うメカニズ

与えられた 3-SAT 問題のインスタンスに対して，それと等ムを，変換した問題に適用することは不可能である．

価なマッチング問題を以下のように構成する．各リテラル，す

本論文では以下に示す，階層的な地域下限制約が存在する

なわち論理変数 x とその否定 ¬x のそれぞれに対して，対応す場合のマッチング問題を扱う．まず，個別の学校 c に関してる学校を作る．また，x と ¬x のペアは地域を構成し，その地は，下限および上限制約を設定可能であるとする．すなわち，域の上限制約は 1 で，下限制約は 0 である．また，各節 l ∈ Lに関して，l に含まれる学校は地域を構成し，その地域の下限∀c, {c} ∈ R に関して，下限／上限制約 p{c} と q{c} が与えられる．さらに，|r| > 1 である各地域 r ∈ R に関しては，地域

制約は 1 であり，上限制約は 3 である．また，各学校は，それ下限制約 pr は与えられるが，地域上限制約 qr は存在しない，のみからなる地域を構成し，その下限制約は 0 で，上限制約

すなわち，地域に関しては下限制約のみが設定可能である場は 1 である．学生の総数 n は，論理変数の数 |X| に等しい．

合を対象とする (表 1).

ここで，ある学校に一人の学生が割当てられている場合，そ地域の集合 R が階層的である場合，R は木構造で表現可能の学校に対応するリテラルが真であると解釈し，そうでなけである．ここで，一般性を失うことなしに，すべての学校の全れば偽であると解釈すると，実行可能なマッチングと，すべ体集合である C が R に含まれることを仮定する.

ての節を充足する各変数への真偽値の割当ての間に一対一の対応が成立する．よって，実行可能なマッチングが存在すれば 3-SAT 問題は充足可能であり，実行可能なマッチングが存在しなければ，3-SAT 問題は充足不可能である．

定義 5 (木). 地域の集合 R を表現する木 TR は以下のように定義される: (i) ルートノード C はすべての学校の全体集合である, (ii) 葉ノード {c} は，個別の学校 c ∈ C のみから構成される地域である，(iii) r ̸= C である各ノード r ∈ R に関して，その親ノード r′ は，r の真上位集合であり，要素数 |r′ | が最上記の定理により，地域上限制約と地域下限制約の両方が小のものである．

存在する場合，実行可能なマッチングが存在するか否かの判

r に関して，その子ノードの集合を children(r) と表記す∪′r ′ ∈children(r) r が成立する．以下，ノー定問題は NP 完全であることが示された．一方，地域下限制

る．明らかに，r =約のみ，もしくは地域上限制約のみが存在する問題に関して

ドと地域という用語を同じ意味で用いる．

は，実行可能なマッチングを求める問題は，より簡単である

葉ノード以外のノード r ∈ R に関しては，その上限制∑

ように思われる．しかしながら地域上限制約は，地域下限制

約 qr を約に書き換えることが可能であり，逆も成立する．より詳細

限制約から内生的に決められる値であり，実行可能なマッには，地域 r に関する下限制約 pr は，r の補集合となる地域

チングには影響を与えない．この定義より明らかに，qr =r̄ = C \ r に関する上限制約 qr̄ = n − pr に置き換えることがc∈r q{c} とする．この上限制約の値は，個別の上∑r ′ ∈children(r) qr ′ が成立する．本論文では以下，地域制約にできる．よって，以下の定理が成立する．

関するいくつかの用語と定義の導入を行う．これらは次章で定理 2. 与えられた S, C, R, p, および q に関して実行可能な示すメカニズムの基礎となるものである．
まず，地域下限制約が有効となるための条件を定義する．

マッチングが存在するか否かの判定問題は NP 完全である．
これは，上限制約のみが存在する場合，もしくは下限制約のみ

定 義 6 (ノ ー ド の 無 矛 盾 性). ノ ー ド r ∈ R は ，pr ≥が存在する特殊ケースに限定しても成立する．

∑

3.2 階層的な地域制約あるという．

r ′ ∈children(r) pr

一般の場合の実行可能性のチェックは NP 完全であるため，
以下，本論文では地域制約が階層的な場合を対象とする．同様な階層的モデルは文献 [3, 7] でも扱われている．

′

もしくは |r| = 1 である場合に無矛盾で定義 7 (下限制約の修正). もしノード r が矛盾している場合，∑
r の地域下限制約 pr を r′ ∈children(r) pr′ とすることにより，ノードを無矛盾にできる．

定義 4 (階層的な地域). 地域の集合 R は以下の性質を満たす
場合に階層的であるという．r ̸= r′ である ∀r, r ′ ∈ R に関して，以下のいずれかが成立する: (i) r ∩ r′ = ∅, (ii) r ⊂ r′ , もし

この修正により，実行可能なマッチングの集合は変化しな
いことは明らかである．

くは (iii) r′ ⊂ r.

51
第 2 分冊地域制約が一般の場合とは対照的に，下限制約が階層的な

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

FIT2013（第 12 回情報科学技術フォーラム）場合には，実行可能なマッチングが存在するか否かの判定は，n′ として pC ≤ n′ ≤ qC が成立する場合，TR は学生数 n′ に下限制約の修正を行うことにより，ノード数に関する線形時

関して無矛盾であるという．

間で行うことができる．

定理 5. 学生数 n′ に関して無矛盾な木 TR に対して，k 人の定理 3. 与えられた S, C, R, p, q, および TR に関して，実行可学生に関する部分マッチング ν を適用する際，部分マッチン

能なマッチングが存在するか否かの判定問題は TR のノード

グ ν を適用する前の制約に関して，k ≤ n′ − pC が成立し，数に関する線形時間で解くことができる．

かつ，任意の学校 c に関して，|ν(c)| ≤ q{c} が成立するなら，証明. 以下にこの問題を解く手続きを示す．TR のノードに関して，下限制約の修正を深さ優先順で実行する．もしあるノー′部分マッチング ν を TR に適用した木 TR
は実行可能であり，n′ − k に関して無矛盾である．

ド r ∈ R に関して，pr > qr が成立すれば，実行可能なマッチ′′とすると，TR証明. 定理 4 より，ν を TR に適用した木を TR

ングは存在しない．そうでなければ，pC ≤ n ≤ qC が成立す′′は実行可能である．次に，TRに関する制約を p′C および qCる任意の n に関して実行可能なマッチングが存在する．

′′
として，p′C ≤ n′ − k ≤ qCが成立すること，すなわち TR

明らかに，あるノード r ∈ R に関して pr > qr となれば，は n′ − k に関して無矛盾であることを示す．仮定より TR

実行可能なマッチングは存在し得ない．また，pC ≤ n ≤ qC

は n′ に関して無矛盾であることより，pC ≤ n′ ≤ qC が成が成立するならば，ルートノードからスタートして，学生をい立する．また， k ≤ n′ − pC が成立する．さらに，定義 9

くつかのグループに分割し，再帰的に子ノードに対してそれおよび ν は k 人の学生に関する部分マッチングであること

らのグループを割り当てることにより，すべての地域上限／′から，p′C ≤ pC および qC= qC − k が成立する．よって，下限制約を満たす，個別の学校に対する割当てを求めること′
p′C ≤ pC ≤ n′ − k ≤ qC − k = qCが成立する．

ができる．この手続きは TR のノード数に関する線形時間で以下に，新たな内生的なパラメータである，要素的下限制約

終了することは明らかである．

を導入する．要素的下限制約は地域 r に含まれる学校に学生が割当て可能か否かを判定するために有用である．
本論文では，学生の部分集合に関するマッチングを決定し，

定義 11 (要素的下限制約). 地域 r に関する要素的下限制約 ar

さらに残りの学生の部分集合に関するマッチングを決定しては以下のように求められる: r が葉ノードの場合，ar = pr . そいく逐次的なメカニズムを構築する．以下に，部分マッチンの他の場合，ar = pr −グに関するいくつかの概念を導入する．

明らかに，pC =∑r ′ ∈children(r) pr .
′∑r∈R ar が成立する．直感的には要素的定義 8 (実行可能木). 木 TR は，∀r ∈ R に関して，pr ≤ qr が下限制約は，全体の下限制約の総量 pC を，各地域に重複なく成立する場合に実行可能であるという．

分割した量と考えることができる．

定義 9 (制約の更新). n 以下の k 人の学生に関する部分マッチ定理 6. n′ 人の学生に対して無矛盾な木 TR ，一人の学生 s をング ν を木 TR に適用した場合，TR の制約は以下のように修学校 c に割り当てる部分マッチング ν を考える．ν を TR に

正される．

′
適用した後の木 TR
が n′ − 1 に関して無矛盾であるのは，以∑1. 各ノード r に関して，pr ← max(0, pr − c∈r |ν(c)|)．
2. 各葉ノード {c} に関して，q{c} ← q{c} − |ν(c)|．
∑3. 葉ノード以外の各ノード r に関して，qr ← c∈r q{c} ．

下の条件のいずれかが成立する場合，かつその場合に限る．

Case 1: pC < n′ ≤ qC および q{c} > 0 が成立．
Case 2: pC = n′ ≤ qC , q{c} > 0 お よ び ∃r ∈4. さらに，TR に関する深さ優先順で下限制約の修正を行う．

regions(c), ar > 0 が成立．

定理 4. 部分マッチング ν を木 TR に適用した後に，TR が実′証明. まず，上記の条件が成立する場合に，TRが n′ − 1 に行可能であるのは，事前条件として，すべての学校 c に関し関して無矛盾であることを示す．まず，Case 1 の条件が成立て，|ν(c)| ≤ q{c} が成立する場合，かつその場合に限る．

′
する場合には，定理 5 より，TRは実行可能であり，n′ − 1

詳細な証明は割愛するが，いずれかの c で |ν(c)| > q{c} となる場合には TR が実行不可能となることは明らかである．
また，すべての c で |ν(c)| ≤ q{c} が成立する場合には，定義 7と定義 9 に基づいて更新された制約に関して，実行可能性の条件 pr ≤ qr が成立することを，葉ノードからルートノードに至るまで，再帰的に証明することができる．
次に，木が無矛盾であるということを以下に定義する．
定義 10 (無矛盾な木). 木 TR が実行可能であり，学生の数をに関して無矛盾である．また，Case 2 の条件が成立する場合′には，定理 4 より，TRは実行可能である．また，前提より，

ar > 0 が成立する地域 r ∈ regions(c) が存在する．この地域∑
r に関して，ar = pr − r′ ∈children(r) pr′ > 0 が成立すること，また，c ∈ r にのみ学生が一人割り当てられることから，
∑
∑
′
pr >
r ′ ∈children(r) pr ′ >r ′ ∈children(r) pr ′ が導かれる．
∑
さらに，pr > 0, pr > pr − 1 および pr > r′ ∈children(r) pr が∑成立すること，および p′r は max(0, pr −1, r′ ∈children(r) p′r′ )で与えられることから，pr > p′r が導かれる．さらに，ν では

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

FIT2013（第 12 回情報科学技術フォーラム）学生一人が割り当てられることから，p′r = pr − 1 が成立する．
′′

に戻る．

′′

次に，r を r の親ノードとする．この r に関して，更新された下限制約 p′r′′ は max(0, pr′′ − 1,∑′r ′ ∈children(r ′′ ) pr ′ )で与えられる．また，pr′′ ≥ pr より， pr′′ > 0 が成立する．さらに，各 r′ ∈ children(r′′ ) に関して，もし r′ = r であれば p′r′ = pr′ − 1 が成立し，r ′ ̸= r であれば p′r′ = pr′が成立する．よって，p′r′′ < pr′′ が成立する．このことは，

p′r′′ = pr′′ − 1 であることを意味する．同様な議論を，r′′ の祖先ノードに関して適用することにより，ルートノード C で′= qC − 1
p′C = pC − 1 が成立する．pC = n′ ≤ qC および qC′′′
より，pC = n − 1 ≤ qC が成立する．

k以下，q{c}= 0 となる学校 c は満員であるといい，∀r ∈regions(c), akr = 0 となる学校 c は飽和しているという．
例 1. 学 生 8 人 S = {s1 , . . . , s8 } と 学 校 4 校 C={c1 , c2 , c3 , c4 } が 存 在 す る と 仮 定 す る ．地 域 の 集 合 R は{{c1 , c2 , c3 , c4 }, {c1 , c2 }, {c3 , c4 }, {c1 }, {c2 }, {c3 }, {c4 }} で与えられる．また，各学校 c に関して, 個別の下限制約 p{c} は 1であり，c1 の個別の上限制約，すなわち q{c1 } は 1 であり，c1
以外の学校に関しては個別の上限制約は 4 とする．その他の地域に関して，p{c1 ,c2 } = 2，および p{c3 ,c4 } = 4 である. この′次に，上記の条件が成立しない場合には，TRは n′ − 1 と無状況で，要素的下限制約は a{c1 ,c2 } = 0 および a{c3 ,c4 } = 2 と矛盾にはなり得ないことを示す．q{c} ≤ 0，n′ < pC ，n′ > qC

なる．学生および学校の選好／優先順位は以下で与えられる.

′のいずれかが成立する場合には，明らかに TR
は実行不可能である．また，pC = n′ かつ ∀r ∈ regions(c), ar = 0 が成立する場合，定義 11 より，葉ノード {c} において，p{c} = p′{c} = 0が成立する．よって，制約の更新によって {c} の下限制約は減少しない．同様に，{c} の親ノードでも下限制約は減少しない．同様の議論を祖先ノードに関して繰り返すことにより，
ルートノード C において下限制約の値は減少しないことが示される．よって p′C = pC が成立する．従って p′C > n′ − 1 と′なり，TRが n′ − 1 に関して矛盾することが示される．

≻s1 , ≻s2 , ≻s3 , ≻s4 : c1≻s5 , ≻s6 , ≻s7 , ≻s8 : c2

c2
c1

c3
c4

c4 ,
c3 .

≻c1 , ≻c2 : s8
≻c3 , ≻c4 : s1
≻M L : s1

s5
s4
s4

s4
s5
s5

s3
s6
s6

s7
s2
s2

s6
s3
s3

s2
s7
s7

s1 ,
s8 ,
s8 .

SDRQ の Stage 1 では，学生 s1 の割当てを決定する．p1C = 6
かつ n − (k − 1) = 8 > 6 で，各学校は満員でないため，学生
s1 は最も選好する学校 c1 に割り当てられる．同様に，Stage
5 までは，n − (k − 1) > pkC が成立するため，s2 から s4 ま
での学生は，満員でない最も選好する学校に割当て可能であ4

階層的下限制約を扱うメカニズムり，s2 , s3 , s4 は c2 に割り当てられる．一方，Stage 5 では，

p5C = 4 および n − (k − 1) = 4 が成立するため，学生 s5 は満

4.1 地域下限制約の下での逐次的独裁者メカニズム
まず，地域下限制約の下での逐次的独裁者メカニズム (Serial

員でなく，かつ飽和していない学校のみを選択できる．ここDictatorship with Regional Quotas, SDRQ) と呼ばれるメカニで，c1 と c2 は飽和しているため，学生 s5 は c4 を選択する．

ズムを示す．このメカニズムは，定理 6 で得られた結果に基同様に，Stage 6 から 8 では, 各学生は満員でなく，かつ飽和

づいており，ML で与えられる順序に従って，一人の学生 s をしていない学校のみを選択できる．最終的に得られるマッチ

逐次的に選択し，s の割当てを決定する．

ングは以下で与えられる:

c1 : s1
c2 : s2

ここで，µk を Stage k における部分マッチングとし，µ を最終的なマッチングとする．このメカニズムでは，初期状態では

s3

s4

c3 : s8c4 : s5

s6

s7

各地域 r ∈ R に関して，p1r = pr , qr1 = qr , および a1r = ar の定理 7. pC ≤ n ≤ qC が成立している場合，SDRQ は常に実ように制約を決定し，k = 1 として以下の手続きを開始する．

行可能なマッチングを与える．

Stage k ≥ 1
Step 1: ML に従って，上位から k 番目の学生 sk を選

生数と無矛盾であることから，定理 7 が成立することは明ら

定理 6 より，各ステージでの木が実行可能であり，残りの学

択する．

かである．

Case 1: pkC < n − (k − 1) の場合，学生 sk は，まk
だ個別の上限制約に達していない (q{c}> 0 であ定理 8. SDRQ は戦略的操作不可能，パレート効率的，かつML-フェアである．

る) 学校中で，最も選好する学校 c を選択する．
Case 2: pkC = n − (k − 1) の場合，学生 sk は，
kq{c}> 0 および ∃r ∈ regions(c), akr > 0 が成立

証明. 逐次的独裁者 (Serial Dictatorship, SD) メカニズムは，一般に以下の性質を満たすメカニズムとして定義される．参加

する学校中で，最も選好する学校 c を選択する．

者は，あらかじめ決められた順序で選ばれる．最初に選ばれStep 2: 部分マッチング µk を，µk (c) = {sk }, µk (sk ) =た参加者は，すべての可能な結果から，自身が最も選好する部

c とする．
Step 3: µk を現在の木に適用し，定義 9 に従って更新された制約を pk+1
, qrk+1 , および ak+1とする．k = nrr分集合を選択する．さらに，次に選ばれた参加者が，最初の参なら終了，そうでなければ k ← k + 1 として Step 1

れた参加者が最も選好する部分集合を指定していく．任意の加者が指定した部分集合から，自身が最も選好する部分集合を選択する．以下同様に，順に残された可能性の中から，選ば

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

FIT2013（第 12 回情報科学技術フォーラム）SD メカニズムは戦略的操作不可能でパレート効率的であるこに対して適用し，更新された制約 pk+1
, qrk+1 , およびrとが知られている [1]. SDRQ は SD メカニズムの一つである

ak+1
を定義 9 に従って得る．さらに，ek+1 = pk+1
r
C

ため，SDRQ は戦略的操作不可能かつパレート効率的となる．

とする．すべての学生がマッチされていれば終了，そまた，学生 s が，c ≻s µ(s) であるにも関わらず，学校 c に割うでなければ k ← k + 1 として Step 1 に戻る．

り当てられなかった場合を考える．この場合，ML で s より下位の学生は，c に割り当てられることはない．すなわち，cに割り当てられている学生はすべて ML で s より上位である．
従って SDRQ は ML-フェアである．

MSDARQ の最後のステージは，通常は Step 1 の (b) の処
理，すなわち，保持すべき学生の数が，ルートノード C の下限制約と等しくなった場合で与えられる．他の可能性として，

C の下限制約が 0 であり，E k が ∅ となる場合，すなわちすべての下限制約が満足されている場合がある．この場合は最後

4.2 地域下限制約の下でのマルチステージ DA
本論文で提案する二番目のメカニズムは，地域下限制約ののステージで通常の DA メカニズムが適用される．

下でのマルチステージ DA (Multi-Stage Deferred Acceptance

例 2. 例 1 と同じ問題設定を考える．MSDARQ の Stage 1

with regional quotas, MSDARQ) と呼ばれる．MSDARQ は，

で は ，ル ー ト ノ ー ド の 下 限 制 約 は 6 で あ る の で ，E 1 =個別の下限を扱う MSDA [5] の拡張である．

{s3 , s4 , s5 , s6 , s7 , s8 } として，s1 と s2 に関して通常の DA

SDRQ の問題点として，各学校の個別の優先順位を完全に無視していることがある．この結果，多くの学生が (弱い意味メカニズムを適用する．Stage 1 では s1 が c2 に，s2 が c1 にで) 妥当な不満を持つことが予想される．MSDARQ は次の点Stage 2 では 6 人の学生が残っており，p2C = 4 である．よっで SDRQ を修正している．学生を一人ずつ割り当てるのはなて，E 2 = {s5 , s6 , s7 , s8 } として，s3 と s4 に関して通常の DA

割り当てられる．

く，複数の学生を同時に，通常の DA メカニズムを用いて割りメカニズムを適用する．Stage 2 では s3 と s4 は c2 に割り当

当てる．通常の DA メカニズムでは，学生は拒否されていな

てられる．

い学校のうち，最も選好する学校に申込を行う．学校は申込のあった学生と仮マッチしている学生のうち，学校の優先順

Stage 3 では 4 人の学生が残っており，p3C = 4 である．ここで，E 3 と E 2 は等しくなり，残りの学生に対して SDRQ を適位で上位の学生を上限まで仮マッチし，残りの学生は拒否す

用する．SDRQ の任意の Stage で，残りの学生数はルートノー

る．以上を全ての学生が仮マッチされるまで繰り返し，メカドの下限制約の値に等しいため，Case 2 のみが生じる．よっ

ニズムを終了する．このメカニズム終了時における仮マッチて，残りの学生は，飽和していない学校にのみ割り当て可能でをマッチングとして出力する．MSDARQ は ML を用いて，下あり，学生 s5 , s6 , s7 , s8 は，c3 もしくは c4 のみを選べる．最限制約が必ず満足されるように，学生の部分集合を保持する．

終的に得られるマッチングは以下の通りである:より正確には，MSDARQ の最初のステージでは，E 1 なる

c1 : s2c2 : s1

学生の部分集合を保持して，その他の学生，すなわち E 0 \ E 1
0(E = S) に含まれる学生を，通常の DA を用いて割り当てる．保持する学生の数 |E 1 | = e1 は，pC と等しくし，E 1 ={sn−e1 +1 , sn−e1 +2 , . . . , sn }, すなわち，E 1 はマスターリスト
で最下位から e1 人までの学生の集合である．E 0 \ E 1 に関し

s3

s4

c3 : s8c4 : s5s6

s7

定理 9. pC ≤ n ≤ qC が成立する場合，MSDARQ は常に実行可能なマッチングを得る．
証明. 以下，証明の概略のみを示す．Step 1 で (a) の条件が成1て DA を実施したのち，現在のマッチング µ を確定して，µ立している時点では，定理 5 より，MSDARQ の各ステージでを木に適用して新しい制約を得る．その後，残りのステージをの木は実行可能である．また，Step 1 で (b) の条件が成立した

1

同様な方法で適用する．より詳細には，MSDARQ は E = S,

時点で，SDRQ が適用されるため，定理 7 より，得られるマッ

e1 = pC とし，すべての r ∈ R に関して，p1r = pr および
qr1 = qr ，k = 1 として以下の手続きを開始する．

チングは実行可能となる．

Stage k ≥ 1
Step 1: E k = {sn−ek +1 , sn−ek +2 , . . . , sn } とする．すく，ML-フェアである．

0

なわち，E k は ML で最下位から ek 人目までの学生の集合である．

(a) E k−1 \ E k ̸= ∅ の場合，通常の DA メカニズムを E k−1 \ E k に含まれる学生に対して適用する(DA メカニズムの適用時には，下限制約は無視され，個別の上限制約のみが考慮される)．

(b) E k−1 \ E k = ∅ の場合，E k に関して SDRQ メ
カニズムを適用する．

Step 2: Step 1 で得た部分マッチングを µk を現在の木定理 10. MSDARQ メカニズムは戦略的操作不可能で無駄がな

証明. メカニズムが戦略的操作不可能であることは，各ステー
ジで用いられる DA メカニズムおよび SDRQ メカニズムが戦
略的操作不可能であり，各学生 s は，自分の参加するステージに影響を与えることが不可能であることから導かれる．
メカニズムに無駄がない理由は以下の通りである．ある学生が，満員でない学校に割り当てられないのは，最後のステージで SDRQ メカニズムが適用される場合のみである．この場
合，学生が割り当てられる学校はいずれも，少なくとも一つの，その学校を含む地域で下限制約がちょうど満たされてい54
第 2 分冊Copyright © 2013 by Information Processing Society of Japan and
The Institute of Electronics, Information and Communication Engineers
All rights reserved.

ratio of students
with envies

0.8

SDRQ
MSDARQ
AC-MSDA
AC-DA

0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

1

1

0.9
0.8
0.7
0.6
0.5
0.4

SDRQ
MSDARQ
AC-MSDA
AC-DA

0.3
0.2
0.1
0
0.1

ratio of minimum quotas

図 1 妥当な不満を持つ学生の比率

ratio of students

1
0.9

ratio of claiming students

FIT2013（第 12 回情報科学技術フォーラム）

0.9
0.8
0.7
0.6
0.5
0.4
0.3
SDRQ
MSDARQ
AC-MSDA
AC-DA

0.2
0.1
0

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

5

ratio of minimum quotas

10

15

20

25

rank

図 2 空きシートを要求する学生の比率

図 3 学生の満足度に関する累積分布関数

る．よって，学生は空きシートを要求することはできない．

メータ設定に関して 100 個の問題のインスタンスを生成する．

ML-フェアに関して，Stage k で割り当てられた学生 s が,提案メカニズムと，人為的キャップメカニズム，具体的に自身が割り当てられた学校よりも他の学校 c を選好すると仮は AC-DA および AC-MSDA と呼ばれるメカニズムと比較す定する．明らかに Stage k 以前に c に割り当てられた学生はる．AC-DA では，各学校の個別の上限制約を 8 として，通常

ML で s より上位にある．Stage k 以前に c が満員であれば，c に割り当てられている学生はいずれも，ML で s より上位にある．また，Stage k で c が満員でなく，s が c に割り当てらの DA メカニズムを適用する．AC-MSDA メカニズムでは，各学校の個別の下限制約を∑

r∈R ar /m, すなわち，要素的下限制約の値の総和の平均値として，文献 [5] に示されている個

れない場合，Stage k で DA メカニズムが用いられている際に別の下限を扱う MSDA メカニズムを適用する．AC-DA およは，Stage k で c に割り当てられた学生は，c の優先順位で sび AC-MSDA はすべての地域下限制約を満足するが，提案メより上位である．また，Stage k で SDRQ メカニズムが用いら

カニズムと比較すると柔軟性に乏しい．例えば，ある一つのれている際には，Stage k で c に割り当てられた学生は，ML学校に人気が集中した場合，本来は下限制約に違反することで s より上位にある．よって，いずれの場合でも，c に割り当なく，その学校に上限の 40 人の学生が割当て可能であるにもてられている学生は，ML もしくは c の優先順位で s より上位

関わらず，AC-DA メカニズムでは 8 人の学生のみが割当て可となり，得られるマッチングは ML-フェアである．

能となる．AC-MSDA メカニズムは，AC-DA メカニズムよりは割当ての自由度が大きいが，個別の下限制約に固定的に割5り当てているため，地域内での割当ての柔軟性を失っている．

評価

図 1 に，(弱い意味で) 妥当な不満を持つ学生の比率を示す．

本章では，新しく開発した SDRQ および MSDARQ の実験

ここで，x 軸は∑r∈R ar /n, すなわち，学生数に対する要素的的評価を行う．学生数 n = 512, 学校数 m = 64 とし，各学校下限制約の値の合計の比を示しており，この値が大きいほどの個別の上限制約 q{c} = 40，個別の下限制約 p{c} = 0 とす

下限制約の総量が大きくなる．AC-DA はフェアであり，不満る．地域の階層構造は二分木で与える．すなわち，木の深さを持つ学生は存在しない．MSDARQ は，常に SDRQ およびは 6 となる*1 ．また，地域の下限制約は，各地域の要素的下限

AC-MSDA よりも不満を持つ学生の数は少ない．下限制約の制約の値が概ね等しくなるように設定する．また，要素的下総量が増えるほど，学生は不満を持ちやすくなる．

∑r∈R ar の値は，64 から 448 の

図 2 は，空きシートを要求する学生の比率を示している．x

範囲で変化させる．学生の選好順序は，まず各学生に関して，軸は図 1 と同様である．MSDARQ および SDRQ は無駄がな

各学校の評価値を生成し，その評価値に基づく基数的効用をいため，空きシートを要求する学生は存在しない．図が示す

順序的効用に変換したものを用いる．学生の各学校の評価値

ように，AC-DA は非常に無駄が多い．AC-MSDA は AC-DA

は以下のように決定する．まず，すべての学生で共通のベクよりも無駄が少ないが，下限制約の総量が増えた場合に，空き

トル uc を [0, 1]m から一様分布により生成する．次に，個別シートを要求する学生の比率は 70% にも達する．

限制約の合計値，すなわちのベクトル us を，同様に [0, 1]m から一様分布により生成す

また，図 3 では学生の満足度を評価する．すなわち，各メカる．さらに，これらを用いて各学校 s の評価値を，パラメータ

ニズムにおいて学生が割り当てられた学校に関する，学生の希α ∈ [0, 1] を用いて αuc + (1 − α)us で与える．パラメータ α

望順位の累積頻度分布関数 (cumulative distribution functions,の値が大きいほど，学生の選好の相関が強くなる．以下の実
験では α は 0.6 としている．各学校の優先順位 ≻c は一様分

CDFs) を示す．例えば，MSDARQ で x 軸の値が 5 であるときに比率が 0.8 であることは，80% の学生が，第 1 希望から

布により生成し，ML は s1 ≻M L · · · ≻M L sn とする．各パラ

第 5 希望までのいずれかの学校に割り当てられていることを示している．ここでは，グラフの値が急激に上昇している方*1

他の階層構造，例えば，多くの小さい地域に分割されるもの，少数の大きな地域が存在するもの等においても実験を行い，定性的な結果は二分木の場合と非常に近いことを確認している．

が学生の満足度が高いと考えられる．MSDARQ と SDRQ は
明らかに人為的キャップメカニズムより優れている．例えば，

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

FIT2013（第 12 回情報科学技術フォーラム）rank of students
for schools

400
350
300

ト) の下でフェアである．実験的評価により，これらのメカニ

SDRQ
MSDARQ
AC-MSDA
AC-DA

ズムの人為的キャップアプローチに対する優位性を示した．
今後の研究課題として，表 1 で “open” としている，階層的

250
200

な地域上限／下限制約が混在する問題設定で適用可能なメカ

150

ニズムを開発すること，および ML が利用不可能な場合に適100用可能な，公平性を保証するメカニズムを開発することが挙50げられる．また，MSDARQ に関する，より強い理論的性質を0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

解明すること，例えば，戦略的操作不可能性かつ無駄がないメ

ratio of minimum quotas

カニズム中で，MSDARQ より厳密に優れているメカニズムが
図4

学校の優先順位における学生の評価存在しないことを示すこと等が挙げられる．

参考文献[1] A. Abdulkadiroglu and T. Sonmez. Random serial dictatorship and the core from random endowments in house al-

70% 近くの学生は，第１もしくは第 2 希望の学校に割り当てられている．人為的に上限／下限制約の値を変更するメカニ

location problems. Econometrica, Vol. 66, No. 3, pp. 689–
702, 1998.
[2] A. Abizada and S. Chen. The college admission problem

ズムでは，割当てにおける柔軟性が失われており，学生の満足度が著しく下がってしまっている．
次に，メカニズムの選択が学校に与える影響を解析する．各with entrance criterion. 2011. mimeo.
[3] P. Biro, T. Fleiner, R. W. Irving, and D. F. Manlove. The

学校は学生に関する優先順位のみを持つため，二つの学生の集合に関して，どちらがより望ましいかを定義することは困難

college admissions problem with lower and common quotas. Theoretical Computer Science, Vol. 411, No. 34-36,
pp. 3136–3153, 2010.

である．ここでは，簡単のため，割り当てられている学生の，学校の優先順位における平均順位を用いる．この評価基準は各学校に割り当てられている学生数を無視している．提案メ[4] L. Ehlers, I. E. Hafalir, M. B. Yenmez, and M. A. Yildirim.
School choice with controlled choice constraints: Hard

カニズムは学生の希望を考慮して，より柔軟に学生を割り当てるため，各学校に割り当てられる学生数に差が出やすい．こbounds versus soft bounds. 2012. mimeo.
[5] D. Fragiadakis, A. Iwasaki, P. Troyan, S. Ueda, andM. Yokoo. Strategyproof matching with minimum quo-のため，AC-DA や AC-MSDA より，MSDARQ および SDRQの方が性能が悪くなることが予想される．図 4 に x 軸は図 1および 2 と同様とした，この評価基準による結果を示す．予

tas. 2012. mimeo (An extended abstract version appearedin AAMAS, pages 1327–1328, 2012).

想通り，平均順位の高さは，AC-DA，AC-MSDA，MSDARQの順となっている．一方，SDRQ と MSDARQ を比較すると，[6] R. W. Irving, D. F. Manlove, and S. Scott. The stable marriage problem with master preference lists. Discrete Applied Mathematics, Vol. 156, pp. 2959–2977, 2008.

学校の優先順位を考慮する MSDARQ の方が平均順位は高い．
この評価では ML と各学校の優先順位は無相関であると仮定しているが，これらが相関している場合，ML を用いるメカニ[7] Y. Kamada and F. Kojima. Stability and strategy-proofness
for matching with constraints: A problem in the japanese

ズムと AC-DA との差は小さくなると予想される．
最後に，MSDARQ と SDRQ の間のトレードオフについて

medical match and its solution. American Economic Review, Vol. 102, No. 3, pp. 366–370, 2012.
[8] N. Perach, J. Polak, and U. G. Rothblum. A stable match-

考察する．学生の満足度においては，両方のメカニズムは同等である．しかしながら，SDRQ は学校の優先順位を完全に無視してるため，妥当な不満を持つ学生の比率が高く，特に要ing model with an entrance criterion applied to the assignment of students to dormitories at the technion. Inter-

素的下限制約の総数が小さい場合に，MSDARQ との差が大きい．よって，不満を持つ学生数が少ないことが望まれるのでnational Journal of Game Theory, Vol. 36, pp. 519–535,
2007.
[9] N. Perach and U. G. Rothblum. Incentive compatibility

あれば，MSDARQ を用いるべきであると考えられる．

6

結論

for the stable matching model with an entrance criterion.
International Journal of Game Theory, Vol. 39, pp. 657–

本論文では地域上限／下限制約が存在する場合に実行可能なマッチングが存在するか否かの判定問題の計算量を解析し，さらに，地域制約が階層的な場合に適用可能なメカニズムを開発した．これらのメカニズムは，個別の下限制約に対応可能な

SD および MSDA メカニズムを拡張したものであり，戦略的667, 2010.
[10] A. E. Roth and M. A. O. Sotomayor. Two-Sided Matching:
A Study in Game-Theoretic Modeling and Analysis (Econo-

操作不可能かつ無駄がないという望ましい性質を備えている．
また，すべての学校で共通の学生のランキング (マスターリス

56
第 2 分冊

metric Society Monographs). Cambridge University Press.,
1990.

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