第 5 章 結びの議論 27
A.2 命題 4.1 の証明
まず,マッチングµが安定であるならば,µに対する選択関数Cについて条件(4.1.2)が満たされるこ とを示す.
miを任意の男性とする.
(1) µにおいて,miにパートナーの女性wi=µ(mi)が存在するとき;
C(mi)= wiとする.µは安定であるから,定義2.2の性質(S)により,mj wi miなる任意の男性 mj ∈Mに対して,µ(mj) mj wiが成立する.故に,集合{m∈M : wim µ(m)}に属するすべての
男性mに対して,mi =µ(wi)mである.すると,選択関数Cは,
C(wi)=max
wi {m∈M : wim µ(m)} ∪ {wi}
=max
wi {µ(wi)∪wi}
と変形できる.さらに,安定マッチングµは個人合理性(IR)を満たすので,µ(wi)wi wiである から,
C(wi)=max
wi {µ(wi)∪wi}
=µ(wi)
=mi.
従って,C(mi)=wiならばC(wi)=miである.即ち,C◦C(mi)=C(wi)=mi. (2) µにおいて,miが独身であるとき;
µの安定性(S)から,wjmi mi なる任意の女性wj ∈Wに対して,µ(wj)wj miが成立する.この とき,集合{w∈W : mi wµ(w)}に属するすべての女性w∈Wに対して,mi mi wj である.従っ
て,Cの性質(4.1.1)の男性の場合に注目すると,
C(mi)=max
mi {w∈W : mi wµ(w)} ∪ {mi}
=mi.
故に,C◦C(mi)=C(mi)=miがいえる.
また,男性と女性の立場を入れ替えることで同様に,任意の女性wi ∈Wに対してC◦C(wi)=wiが導 出される.
次に,マッチングµに対する選択関数Cについて条件(4.1.2)が満たされるならば,µは安定であるこ とを示す.任意のマッチングµが与えられたとする.条件(4.1.2)は以下の4つの場合として書き下すこ とができる:
(1) 男性mi ∈Mに対して,パートナーの女性wi=µ(mi)∈Wが存在し,C(mi)=wiかつC(wi)=mi; (2) 男性mi ∈Mが独身(mi=µ(mi))であり,C(mi)=mi;
(3) 女性wk ∈Wに対して,パートナーの男性mk =µ(wk)∈Mが存在し,C(wk)=mkかつC(mk)=wk; (4) 女性wk ∈Wが独身(wk=µ(wk))であり,C(wk)=wk.
しかし,ケース(3)はケース(1)と同値であり,ケース(4)はケース(2)の男性を女性に置き換えたもので ある.従って,男性miがケース(1)に当てはまる場合とケース(2)に当てはまる場合に分けて,ケース (1)と(2),(4)からマッチングµの安定性を導くことを示す.
ケース(1):C(mi) = wi であることは,選択関数C の性質(4.1.1) の男性の場合から,女性wi が集合
{w∈W : mi wµ(w)} ∪ {mi}の選好順序mi に関する最大元であることを意味する.従って,
mi wj µ(wj)なる任意の女性wjに対して,wi =µ(mi)mi wj;かつ (A.2.1)
wi=µ(mi)mi mi (A.2.2)
である.また,C(wi)=miであることは,性質(4.1.1)の女性の場合から,男性miが集合{m∈ M : wi m
µ(m)} ∪ {wi}の選好順序wi に関する最大元であることを意味する.故に,
wi mj µ(mj)なる任意の男性mjに対して,mi=µ(wi)wi mj;かつ (A.2.3)
mi=µ(wi)wi wi (A.2.4)
である.
ケース(2):C(mi)=miであることは,性質(4.1.1)の男性の場合から,その男性miは集合{w∈W : mi w
µ(w)} ∪ {mi}の選好順序mi に関する最大元であることを意味する.即ち,
mi wj µ(wj)なる任意の女性wjに対して,mi =µ(mi)mi wj (A.2.5) である.
ケース(4):ケース(2)に関して男女を入れ替えての同様の議論から,条件C(wk)=wkは,
wkml µ(ml)なる任意の男性mlに対して,wk=µ(wk)wk ml (A.2.6) である.
以上で得た性質(A.2.2) と (A.2.4) からマッチング µの安定性の定義2.2 の (IR)が構成され,性質 (A.2.1)と(A.2.3),(A.2.5),(A.2.6)から(S)が構成される.
Acknowledgements
本論文を纏めるにあたって,直接・間接的に多くの御指導や御助言を頂きました.特に,石川竜一郎先 生には,日々多くの時間を割いて熱心な御指導を頂きました.心から御礼を申し上げます.
また,金子守先生・秋山英三先生には,研究が萌芽の段階から有益な御助言を多数頂きました.心から 御礼を申し上げます.石川研究室の皆様には,多くの発表の機会と御助言を頂きましたことを感謝申し上 げます.
縁あって,集合・位相論をともに勉強することとなった中村研究室・金子研究室の皆様からは,お互い が意識している以上に素晴らしい刺激を頂いていたと信じています.
最後に,本論文の執筆を含め大学院生活を支えてくれた両親に感謝します.
2011年3月 つくばにて(修士(社会経済))
References
Adachi, H. (2000): “On a Characterization of Stable Matchings,” Economics Letters, 68, 43–49.
Alkan, A. (2001): “On Preferences over Subsets and the Lattice Structure of Stable Matchings,” Review of Economic Design, 6, 99–111.
Alkan, A., Gale, D. (2002): “A Class of Multipartner Matching Markets with a Strong Lattice Structure,”
Economic Theory, 19, 737–746.
Alkan, A. (2003): “Stable Schedule Matching under Revealed Preference,” Journal of Economic Theory, 112, 289–306.
Blair, C. (1988): “The Lattice Structure of the Set of Stable Matchings with Multiple Partners,” Mathematics of Operations Research, 13, 619–628.
Dubins, L. E., Freedman, D. A. (1981): “Machiavelli and the Gale-Shapley Algorithm,” The American Math-ematical Monthly, 88, 485–494.
Fishburn, P. C. (1978): “Non-cooperative Stochastic Dominance Games,” International Journal of Game Theory, 7, 51–61.
Gale, D., Shapley, L. (1962): “College Admissions and the Stability of Marriage,” The American Mathemat-ical Monthly, 69, 9–15.
Gale, D., Sotomayor, M. A. O. (1985): “Ms. Machiavelli and the Stable Matching Problem,” The American Mathematical Monthly, 92, 261–268.
Knuth, D. E. (1976): Mariages Stables, Montreal, Les Presses de l’Universite de Montreal.
Perea, A., Peters, H. Schulteis, T. Vermeulen, D. (2006): “Stochastic Dominance Equilibria in Two-person Noncooperative Games,” International Journal of Game Theory, 34, 457–473.
Roth, A. E. (1982): “The Economics of Matching Stability and Incentives,” Mathematics of Operations Research, 7, 617–628.
Roth, A. E. (1984): “Misrepresentation and Stability in the Marriage Problem,” Journal of Economic Theory, 34, 383–387.
Roth, A. E. (1989): “Two-Sided Matching with Incomplete Information about Others’ Preferences,” Games and Economic Behavior, 1, 191–209.
Roth, A. E. (1991): “Incentives in Two-Sided Matching with Random Stable Mechanithms,” Economic The-ory, 1, 31–44.