ルームメイト問題における安定性とパレート効率性 Stability and Pareto

ルームメイト問題における安定性とパレート効率性
Stability and Pareto Efficiency in Roommate Problems
制度設計理論 (経済学) プログラム
マッチング ν がマッチング µ をパレート支配するとは

 ν(i) ≿ µ(i) ∀i ∈ N
i
 ν(i) ≻ µ(i) ∃i ∈ N
i
12 01976 上田敬人 Norihito Ueda が成り立つことをいい、ν ≻N µ と表す。ν が他のいかなる
指導教員 武藤滋夫 Adviser Shigeo Muto マッチングによってもパレート支配されないとき、ν はパ
1. はじめに
ルームメイト問題は複数のプレイヤーで 2 人 1 組のペア
レート効率的であるという。強選好の問題の場合には、パ
レート効率的であることは安定であるための必要条件であ
る。しかし、無差別を含む選好の下では、安定なマッチン
を作る問題で、男性女性のペアを作る結婚問題から派生し
グがパレート効率的でないことがある。
た問題である。マッチングのペアの相手よりもお互いのこ
定理 1 (Erdil and Ergin, 2015). とを好む 2 人のペアが存在しない状態を安定であるといい、
もしある安定なマッチング µ に対して、ν ≿N µ が成立
Gale and Shapley (1962) は強選好を持つ結婚問題において すれば、ν も安定である。
安定なマッチングが常に存在することを示し、それを求め
Erdil and Ergin (2015) が上の定理から、安定で且つパ
るアルゴリズムを与えている。彼らは強選好のみのルーム
メイト問題において常に安定なマッチングが存在するとは レート効率的なマッチングは存在することを主張しており、
限らないことを明らかにしており、Irving (1985) は安定な 安定で且つパレート効率的なマッチングを次のようなサイ
マッチングが存在すればそれを導き、存在しなければ存在 クルから、求めている。
しないと与えるアルゴリズムを導いた。
強選好の下では安定なマッチングはパレート効率的であ
るが、無差別を許した選好の下では安定なマッチングがパ
定義 1. Pareto Improvement (PI) サイクル
女性 w1 , ..., wm がいて (ただし、wm ≡ w0 )、
レート効率的であるとは限らない。Erdil and Ergin (2015)
1. 各女性 w1 , ..., wm がある男性とマッチしている
は無差別を許す選好を持つ多対一のマッチング問題におい
2. µ(wt+1 )
て、安定でパレート効率的なマッチングを求めることに成
功した。その際に用いたのが PI サイクルや PI チェーンで
ある。本研究ではそれをルームメイト問題に応用して、安
定でパレート効率的なマッチングを求められるかどうか考
察することを目的としている。
2．先行研究
この後の議論は多対一のマッチング問題で述べられてい
ることであるが、簡単化のため、結婚問題で考える。結婚
問題では各主体 i は異性に選好 ≿i をもっていて、男性の集
合 M ＝ {m1 ，m2 ，m3 ，
...，mp } と女性の集合 W ＝ {w1 ，w2
，w3 ，
...，wp } から 1 人ずつ組み合わせてペアを作る。この
とき、誰もが独身にならないことにする。そのペアの作り
方をマッチングといい、µ で表す。µ(x) はマッチング µ に
おける x のペアの相手を表す。j ≻i k で「i は k より j を
≿wt
µ(wt ) and wt
≿µ(wt+1 )
wt+1 , ∀t = 0, ...m − 1
3. µ(wt+1 ) ≻wt µ(wt ) or wt ≻µ(wt+1 ) wt+1 , ∃t =
0, ...m − 1
が成立しているとき、σ = (w1 , ..., wm ) を PI サイクルと
いう。
次で定義される ν は µ をパレート支配する。

µ(w ) if w = w (t = 0, ..., m − 1)
t+1
t
ν(w) =
µ(w)
otherwise
定理 2 (Erdil and Ergin, 2015). ある安定なマッチングが PI サイクルを許さないことは、
それがパレート効率的であるための必要十分条件である。
ある安定なマッチングに対して PI サイクルでパレート改
好む」、j ≿i k で「i は k より j を好む、または i は k と同
善を行い、それらが、見つからなくなったとき、安定でパ
程度に j を好む」ことを表す。
レート効率的なマッチングを得る。
あるマッチング µ において男性 m と女性 w は結婚して
いないが、µ における配偶者よりもお互いのことを好むと
き、すなわち w ≻m µ(m) 且つ m ≻w µ(w) のとき、(m，w)
はマッチング µ をブロックするという。そしてマッチング
µ がいかなるペアによってもブロックされないとき、µ は
安定であるという。Gale and Shapley (1962) は安定なマッ
チングが常に存在することを示している。
3．無差別を許したルームメイト問題
ルームメイト問題ではある主体 i が自分以外の人に選好
≿i を持っていて、人数が偶数である人々(N ＝ {1，2，3，
...
，n}) を 2 人 1 組のペアに分ける。そのペアの作り方をマッ
チングといい、µ で表す。µ(x) はマッチング µ における x
のペアの相手を表す。マッチング µ において i と j はペア
を組んでいないが、µ におけるペアの相手よりもお互いの
ことを好むとき、すなわち j ≻i µ(i) 且つ i ≻j µ(j) が成り
立つとき、(i，j) はマッチング µ をブロックするという。そ
してマッチング µ がいかなるペアによってもブロックされ
ないとき、µ は安定であるという。ルームメイト問題にお
2. µ(it+1 ) ≻it µ(it ) or it ≻µ(it+1 ) it+1 , ∃t =
0, ..., m − 1
3. {i1 , ..., im , µ(i1 ), ..., µ(im )} は重複せず、すべて異なる
人である
いてもパレート支配やパレート効率性の定義を同様に行う。 が成立しているとき、σ = (i1 , ..., im ) を制限された PI サイ
Gale and Shapley (1962) は安定なマッチングが存在しない クルという。
例を与えている。
3.1 ルームメイト問題における安定でパレート効率的な
マッチング
ある主体の選好の無差別を解消して強選好にしてしまう
ことをタイ・ブレイクといい、次のように定義される。
定義 2. ルームメイト問題 (N ，≿′ ) がルームメイト問題 (N ，≿)
のタイ・ブレイクであるとは
次で定義されるマッチング ν は µ をパレート支配する。



µ(i ) if i = it (t = 0, ..., m − 1)

 t+1
ν(i) = it
if i = µ(it+1 ) (t = 0, ..., m − 1)



µ(i)
otherwise
結婚問題では定理 2 が成立したが、ルームメイト問題で
は次が成立する。
命題 2. ある安定なマッチングが制限された PI サイクルを許さな
1. j ∼i k ⇒ j ≻′i k or k ≻′i j
いことは、それがパレート効率的であるための必要十分条
2. j ≻i k ⇒ j ≻′i k
件である。
がともに成り立つことをいう。
タイ・ブレイクした問題の安定性と元の問題の安定性と
パレート効率性について以下が成り立つ。
命題 1. あるマッチング µ がタイ・ブレイクしたすべての問題に
おいて安定であるならば、µ は元の問題において安定でパ
レート効率的なマッチングである。
4．まとめ
本研究では命題 1，2 を新たに得た。今後の課題としては
奇数人数の場合のパレート効率性と PI チェーンや一般的な
PI サイクルの存在性との関係を考える必要がある。また、
タイ・ブレイクした問題各々について Irving (1985) のアル
ゴリズムを用いて安定なマッチングを求めることは多くの
時間を要するため、元の問題から直接安定なマッチングを
得られるようなアルゴリズムを考えること、そして安定性
しかしながら，命題 1 の逆は偽であることを示す反例が
存在する。
3.2 ルームメイト問題における PI サイクル
ルームメイト問題においても強選好の問題の場合には、
パレート効率的であることは安定であるための必要条件で
の定義を拡張した強安定や超安定と呼ばれるものを適用し
て、タイ・ブレイクした問題と元の問題との関係について
考察することも今後の課題である。
5．参考文献
D.Gale and L.S.Shapley (1962), “ College Admissions
ある。しかし、無差別を含む選好の下では、安定なマッチ
and the Stability of Marriage ”, The American Matheングがパレート効率的でないことがある。
matical Monthly Vol. 69, No. 1, pp. 9-15.
ルームメイト問題においても定理 1 が成立する。そして、
Robert W. Irving (1985), “ An Eficient Algorithm for
安定なマッチングが存在すれば、安定で且つパレート効率 the‘ Stable Roommates ’Problem ”, Journal of Algorithms
的なマッチングが存在する。定義 1 の PI サイクルによって
Volume 6, Issue 4, pp. 577-595.
安定なマッチング µ をパレート改善したいが、ν がマッチ
Aytek Erdil and Haluk Ergin (2015), “ Two-sided
Matching with Indifferences ” Harvard Business School
Working paper.
ングにならないことがある。そのため、ルームメイト問題
のためのサイクルを考える。
定義 3. 制限された Pareto Improvement(PI) サイクル
主体 i1 , ..., im がいて (ただし、im ≡ i0 )、
1. µ(it+1 ) ≿it µ(it ) and it ≿µ(it+1 ) it+1 , ∀t =
0, ..., m − 1