筑波大学大学院博士課程
システム情報工学研究科修士論文
安定マッチングへの分権的プロセスと知識の役割
上圷 宏史
(
社会システム工学専攻
)
指導教員 金子 守
2011
年
3
月
Abstract 本論文は，Gale-Shapley結婚問題における安定マッチングへの分権的プロセスに，各個人がもつ自分や他 人の選好に関する知識が果たす役割を考察する．主結果は以下の2つである： (1) マッチングを形成する事前に，2サイド間で異性の選好に関する知識に優劣がある状況を仮定す る．そして，知識優位な側とする女性達が各安定マッチングの生起する確率を推論し，自分の選好 を顕示するか否かを選択するゲームを構築する．このとき，均衡として女性達の一部が選好を顕示 せず，安定マッチングの確率分布を自分達が好ましいように操作できる可能性があることを示す． この結果は，“各個人が異性全員の選好を知っている”という仮定は確率的な分権的プロセスに及 ぼす影響が大きいことを含意する； (2) (1)と異なり事前の知識の優劣の存在は仮定せず，各個人がどのようにペア候補を選択するかの意 思決定基準を定式化する．この定式化を通して，不安定マッチング内でのサイクルから脱却して安 定マッチングに到達するためには，意思決定の評価基準である自分の選好に関する知識に加えて， 最小限必要となる異性の選好が存在することが明らかとなる．
目次
第1章 序論 1 1.1 目的と背景. . . 1 1.2 本論文の構成 . . . 2 第2章 マッチングと知識 4 2.1 集権化マッチングと知識 . . . 4 2.1.1 Gale-Shapleyアルゴリズムと知識 . . . 4 2.1.2 不完備情報としての他人の選好 . . . 6 2.2 分権化マッチングと知識 . . . 9 2.2.1 萌芽的研究と知識の必要性 . . . 9 2.2.2 プレマッチングと意思決定 . . . 10 2.2.3 マッチングと顕示選好 . . . 12 第3章 戦略的な選好の顕示 14 3.1 他人の選好に関する知識と安定性 . . . 14 3.2 選好顕示ゲーム . . . 17 第4章 分権的プロセスにおける意思決定 20 4.1 意思決定基準の定式化 . . . 20 4.2 意思決定と知識 . . . 23 4.2.1 Knuth (1976)の未解決問題 . . . 23 4.2.2 選択関数と必要最小限の知識 . . . 24 第5章 結びの議論 27 付録A 証明 28 A.1 命題3.2の証明 . . . 28 A.2 命題4.1の証明 . . . 29 Acknowledgements 32第
1
章
序論
1.1
目的と背景
社会には，各個人がパートナーを見つけてある目的を達成しようとする状況がある．その状況をモデル 化したものがマッチング理論である．各個人が互いに満足できるパートナーを見つけることは，そのマッ チングを長期にわたって安定的に維持することを可能にする．しかし，その満足感には，自分や他人が潜 在的なパートナー達に関してもつ好ましさの順序―――選好の知識が必要なはずである．本論文は，マッチ ング理論のなかでも特に分権化された環境に注目し，各個人がもつ自分や他人の選好に関する知識がマッ チングの形成に与える影響を理論的に考察することが目的である． 様々な社会・経済のようすが2サイド・マッチング（two-sided matching）としてモデル化できる．病 院側と研修医側との間のインターンシップがその例である．各病院は研修医達に関する選好をもち，逆 に，各研修医は病院側に関する選好をもつ．そして，その選好の情報をもとに長期にわたって安定的な パートナーシップである安定マッチングを目指す．このとき，安定マッチングを出力することが期待され る特定のアルゴリズムを制度として導入しようと試みるのがマッチング研究における集権化マッチング研究の立場である．こうしたアルゴリズムの設計は，Gale and Shapley (1962)による“deferred acceptance”
アルゴリズムに始まるが，現在のマッチング研究においても理論的・制度的に重要な位置にある． 一方，現実社会でのマッチング環境は必ずしも集権化されている（もしくは，され得る）とは限らな い．結婚相手や共同研究のパートナーを見つけるときが，多くある例のなかの一部として挙げられる．し かし，アルゴリズムの与えられていないマッチング環境においても，安定マッチングが形成されているの
ではないかという予想は自然であろう*1．この集権化されていない，即ち，分権化されたマッチングを研
究の対象とするのがもうひとつのマッチング研究の立場である．特に，Roth and Vande Vate (1990)は，
任意のGale-Shapley結婚問題には，参加個人達が自発的にペアを組み替えることを繰り返すことで安定 マッチングに到達するパスが必ず存在することを理論的に示した．この研究は，その後の分権化マッチン グ研究の発展における基礎となっている． 一般に，ゲーム理論・経済学において，直面するゲームや経済に関して個人達が如何なる知識をもつ *1 Roth (1991)も，アルゴリズムによって制度化されていない場合でも，マッチングに参加する個人達による自発的なペアの組 み替え（再契約）を繰り返すことで安定マッチングに達し得ることを示唆している．
かは重要な要素である．そして，マッチング理論においてもこのことは例外でない．本論文は2サイド・ マッチングを対象とするが，以下Gale-Shapley結婚問題に従って，2サイドを男性集合と女性集合とす る．このとき，参加個人の視点から参加者達の選好に関する知識に注目すると，その種類を以下の3つに 関する知識に分類することができる： (1) 自分の選好； (2) 同性達の選好； (3) 異性達の選好 である． 安定マッチングを出力できるアルゴリズムを設計する集権的立場の研究なかでも，Gale-Shapleyアル ゴリズムを基礎としてその拡張を試みる学校選択などの制度研究においては，各個人にとっての(1)自分 の選好と(2)同性達の選好に関する知識について重要視しているといえる．それは，アルゴリズムが安定 マッチングを出力することと同時に，耐戦略的（strategy-proof）であることがその評価基準の1つとなっ ていることからわかる．アルゴリズムを運営するときには，まず，各個人に自分の選好を申告してもらう ことから始まる．その際，同性達の選好と彼らの申告に対して自分の選好の申告の仕方を戦略的に考慮す る必要がないことが望ましいとされるのである． また，同じ集権化マッチング研究においても，より一般のメカニズム・デザイン理論の立場では，(1) 自分の選好と(2)同性達の選好に加えて，各個人にとっての(3)異性達の選好の知識を考慮することがあ る．Roth (1989)は，各個人が自分の選好（タイプ）は知っているが，異性達の選好は必ずしも完全には 知らないという状況の集権化マッチングに対して，男女双方からの自分の選好の申告を戦略とする不完備 情報ゲームとして定式化した． このように，集権化マッチングでは選好に関する個人達の知識量に様々なバリエーションをつけた研究 がされている．一方，分権化マッチングの文脈では，知識の役割に焦点を絞った研究はされていない．し かし，集権化環境では制度設計者が最終的な安定マッチングを形成するのに対して，分権化環境では参加 者達自身が自発的にマッチングを形成しなくてはならない．つまり，参加者達が安定マッチングを形成す るためにおこなう一連の意思決定は直接的に相互に依存しており，その相互依存関係を結ぶ媒介となるの が他人の選好に関する知識であると考える．とりわけ本論文は，安定マッチングへの分権的プロセスとし て，不安定マッチングのなかでのサイクルから脱して安定へと収束するために必要となる最低限の知識を 検証することが目的である．
1.2
本論文の構成
第2章では，まず，本論文が対象とするGale-Shapley結婚問題を概説する．次に，Gale-Shapleyアル ゴリズムに注目し，集権化マッチングと各個人の選好に関する知識との関係を考察する．続いて，分権化 マッチングにおいては，Gale-Shapleyアルゴリズムと異なり，異性達の選好に関する知識が必要であるこ とを指摘する．そして同時に，集権化・分権化マッチングそれぞれの他研究のなかで，他人の知識に関す る知識について如何に対処されてきたか，そして，本論文とどのように関連しているかを順に纏める．第3章では，異性達の選好に関する知識量が事前にサイド間で異なることを想定し，その情報の非対称 性が分権化マッチングに与える影響を考察する．そして，情報優位な側が自分の選好を戦略的に顕示でき るというゲーム的状況を構築することによって，分権化環境における安定マッチングへの確率的な到達プ ロセスへの影響を明らかにする．
第4章では，分権化マッチング研究の代表的論文であるRoth and Vande Vate (1990)に代わる分権化プ
ロセスを提示する．これは各個人の意思決定基準を定式化することに始まる．そして，分権化マッチング と各個人の選好に関する知識との関係を明らかにする．
第5章では，結びの議論として本論文を総括的に纏めるとともに，残された課題を提示する．付録は，
第
2
章
マッチングと知識
本章は，集権化マッチングと分権化マッチングのそれぞれについて，過去の研究では選好に関する知識 をどのように扱ってきたかを纏めたものである． 集権的アプローチの萌芽であるGale-Shapleyアルゴリズムは，各個人が自分の選好を知っていること のみで安定マッチングを出力する．しかし，アルゴリズムを安定マッチングを出力する一般のメカニズム へと拡張すると，議論は複雑さを増す．他人の選好に関する知識の欠落をゲームにおける不完備情報とし て導入した場合，確実に安定マッチングを出力するメカニズムは存在しないことが知られている．何れに しても，集権化マッチングは不完備情報を扱う手法が確立しているといえる．続いて，分権化マッチングの萌芽であるRoth and Vande Vate (1990)を概説する．Roth and Vande Vate
(1990)は，マッチングの安定性の定義に最も忠実な自発的なペアの組み替えという概念をもとに，安定 マッチングへの分権化プロセスを記述した．しかし，マッチング形成に参加する各個人が如何なる意思決 定をしているかが明確でない．それに比べて，Adachi (2000)は安定マッチングを達成するために各個人 がおこなう意思決定を明確にしている．但し，各個人は，異性達の選好を熟知した上でその意思決定の結 果を互いに推論することが要請されており，Adachi (2000)を安定マッチングへの分権的プロセスと解釈 することは難しい．最後に，マッチングに顕示選好という概念を導入した研究を紹介する．この研究は， 事前には知らなかった他人の選好が徐々に顕示されることでその知識を順に獲得していくマッチング・モ デルの構築へとつながる方向性をもつのではないかと予想する．
2.1
集権化マッチングと知識
2.1.1
Gale-Shapley
アルゴリズムと知識
本小節では，初めに，本論文が対象とする1対1の2サイド・マッチング―――Gale-Shapley結婚問題 を概説する．続いて，集権化マッチングとしてのGale-Shapleyアルゴリズムと各個人が必要とする選好 に関する知識との関係について纏める． Gale-Shapley結婚問題は，組(M, W; P)で与えられ，モデルを構成する各要素は以下のように定義され る：2つの集合MとWは互いに素な有限集合であり，M= {m1, m2, . . . , mp}を p人の男性全員の集合，W= {w1, w2, . . . , wq}をq人の女性全員の集合とする．各男性m∈ Mは，女性全員と自分とを元とする集 合W∪ {m}上に選好関係%mをもち，各女性w∈ Wは，集合M∪ {w}上に選好関係%wをもつ．また，各 男性，各女性のもつ選好関係は合理的（rational）であると仮定する．即ち，完備性*1（completeness；比 較可能性）と推移性*2（transitivity）を満たすとする．男性全員の選好関係の集合を{{%m}m∈M}，女性全員 の選好関係の集合を{{%w}w∈W}と書き，それぞれ男性選好プロファイル，女性選好プロファイルと呼ぶ． そして，2つのプロファイルを纏めた集合{{%m}m∈M, {%w}w∈W}をPと書き，選好プロファイルと呼ぶ． Gale-Shapley結婚問題の1つの解（outcome）概念は，以下の結ばれたペア（結婚）全体の集合である． Definition 2.1 マッチング（matching）µは，µ ◦ µ(x) = xを満たすM∪ Wから M∪ Wへの全単射であ り，µ(m) , mならばµ(m) ∈ W，かつ，µ(w) , wならばµ(w) ∈ Mとする． Definition 2.2 あるマッチングµが安定（stable）であるとは，µが個人合理的であり，かつ，いかなる男 女のペアによってもブロックされないことである．即ち，マッチングµが以下の(IR)と(S)を同時に満 たすことである：
(IR) µ(m) %m m for all m∈ M and µ(w) %ww for all w∈ W; and
(S) @(m, w) ∈ M × W such that w m µ(m) and m wµ(w).
また，定義2.2の性質(S)における男女のペア(m, w)を一般にブロッキング・ペア（blocking pair）と
呼ぶ．
Gale and Shapley (1962)は，任意の結婚問題に対して安定マッチングが常に存在することを証明した．
この証明は，いかなる選好プロファイルの結婚問題に適用しても安定なマッチングを出力するアルゴリズ ムを提案するという構成的方法によるものである*3． 次に，集権化マッチングにおける安定性と各個人の選好に関する知識の役割を確認するため，このアル ゴリズム自体に注目する．Gale-Shapleyアルゴリズムは，各個人が(1)自分の選好に関する知識のみを完 全にもっていれば運営上一切問題が生じない．その理由は，Gale-Shapleyアルゴリズムが耐戦略的*4 で あることによる．耐戦略的なアルゴリズムが与えられれば，各個人は同性達による戦略的な選好の申告の 可能性を考慮する必要がない．即ち，互いが真の選好が申告された上でアルゴリズムが運営されることを 期待しているが故に，(2)同性達の選好を各個人が互いに知る必要はない．同様に，(3)異性達の選好に関 *1 ある男性mに関する選好関係の完備性は以下のように記述される：Wの任意の元x，yに対して，x%myまたはy%mxで ある． *2 ある男性mに関する選好関係の推移性は以下のように記述される：Wの任意の元x，y，zに対して，x%myかつy%mzな らばx%mzである． *3 証明は無差別関係を許容しない厳密な選好関係のもとでおこなわれたが，無差別関係を許容する場合の証明も，その自然な 拡張により得られることが知られている *4 メカニズムが耐戦略的（strategy-proof）であるとは，そのアルゴリズムにおいて，他人が如何なる申告をしていたとしても， どの個人も自分の真の選好を申告することが決して損にならないことをいう．つまり，Gale-Shapleyアルゴリズムにおいて は，他人の異性達に対するプロポーズの順番にかかわらず，自分は真の選好に従って好ましい順にプロポーズをすることで 損をしない．
しても知る必要はない．従って，集権的プロセスとしてのGale-Shapleyアルゴリズムが(1)自分の選好 に関する知識のみを必要とすることに比べて，分権化プロセスにおいては如何なる知識を各個人が最低限 必要とするかを考察することを，第2.2節以降では展開する． 一方，Gale-Shapleyアルゴリズムに限らず，より一般に安定マッチングを出力する集権的メカニズムに 議論を拡張すると，他人の選好に関する知識が不完備であるとき，安定マッチングを出力するメカニズム が存在しないという結果を得る．次小節で紹介する複数の研究は，集権化マッチングにおいて知識が完備 であることが如何に重要かを示す結果である．
2.1.2
不完備情報としての他人の選好
Roth (1989)は，自分の選好の情報は完全に知っているが他人の選好の情報は必ずしも完全には知らな い状況の集権化マッチングを分析した萌芽的研究である．そのために，不完備情報ゲームの文脈としての 集権化マッチングを定式化した．そこでは，参加者達が制度設計者に対して戦略的に選好を顕示して，設 計者はその申告された選好をもとにマッチングを形成する． 不完備情報ゲームの定式化を紹介するにあたり，まず，完備情報ゲームとしてのマッチング・モデルを 概説する．引き続き，Gale-Shapley結婚問題(M, W; P)において，集権的に，即ち，制度設計者が設計す るメカニズムによってマッチングを決定することを考える．メカニズムは，先程のGale-Shapleyアルゴ リズムとは異なり，各個人が申告する選好のプロファイルによって運営される．本小節のみ，選好プロ ファイルをP= {P(m1), . . . , P(mp), P(w1), . . . , P(wq)}と記述する*5．このとき，選好P(m)をもつ各男性 mは自分の選好としてどのような選好Q(m)を申告するかという戦略的状況に直面し，同様に，各女性w もP(w)をもつが，選好Q(w)を戦略的に申告できる状況にある．この申告された選好のプロファイルを 纏めてQ= {Q(m1), . . . , Q(mp), Q(w1), . . . , Q(wq)}とする*6．そして，hは任意の申告されたプロファイル Qに対してマッチングµを出力する関数であり，メカニズムと呼ばれる．プロファイルQに対して出力 するマッチングµ = h(Q)がQに関して安定であるとき，メカニズムhを安定メカニズムという．また， マッチングh(Q)がQに関する男性最適な安定マッチング*7 であるとき，メカニズムhを男性最適安定 メカニズムという．以上を纏めると，マッチングにおける情報完備ゲームは組(N= M ∪ W, Q, h, P)で表 現できる．通常のゲーム理論と同様に，完備情報ゲームでは，すべての個人がもつ真の選好は共通認識で あることが仮定されている． 個人i∈ M ∪ Wの戦略Q∗(i)が他の個人達の戦略の組Q−i に対する最適反応であるとは，マッチング µ = h(Q∗(i), Q−i)におけるペアµ(i)が他のいかなるマッチングν = h(Q(i), Q−i)におけるペアν(i)より少
なくとも同程度に好ましいときをいう．続いて，個人i∈ M ∪ Wの戦略Q∗(i)が支配戦略であるとは，戦 *5 Pはすべての個人に対して無差別関係を許さない強選好のみからなるプロファイルとする． *6 強選好プロファイルPに応じて，Qも強選好の申告のみ扱うことにする． *7 2つのマッチングµとνを考える．マッチングµにおいて，どの男性もマッチングνにおけるパートナーより好ましくな い女性とパートナーになることなく，少なくとも1人の男性がマッチングνにおけるパートナーより厳密に好ましい女性と パートナーになるとき，マッチングµはマッチングνを男性側の立場から（パレート）支配するという．そして，あるマッ チングが男性最適であるとは，それを男性側の立場から支配するマッチングが存在しないことをいう．女性側の立場からの 支配関係，最適性も同様に定義される．
略Q∗(i)が他の個人のあらゆる戦略の組Q−i に対する最適反応であるときをいう．
次の定理はこのマッチング・モデルにおける不可能性定理にあたり，不完備情報下においても再考察さ れる結果である．
Theorem 2.1 (Roth (1982)) Gale-Shapley結婚問題の各サイドに少なくとも2人ずつ存在するとき，すべ
ての個人に対して真の選好を申告することが常に支配戦略となる安定メカニズムは存在しない．
しかし，安定メカニズムを男性（女性）最適安定メカニズムへと限定すると，以下の定理が示される．
Theorem 2.2 (Dubins and Freedman (1981)) 男性最適安定メカニズムにおいては，すべての男性にとっ
て真の選好を申告することが支配戦略となる（同様に，女性最適安定メカニズムにおいては，すべての女 性にとって真の選好を申告することが支配戦略となる．）． 情報完備ゲーム(N= M ∪ W, Q, h, P)において，戦略の組Q= (Q(m1), . . . , Q(mp), Q(w1), . . . , Q(wq))が 均衡であるとは，すべての個人i∈ M ∪ W に対してQ(i)が他の個人の戦略の組Q−i に対する最適反応で あるときをいう． 定理2.1は，すべての個人に対して，他の個人達が真の選好を申告しているときに真の選好を申告する ことが常に最適反応となる安定メカニズムは存在しないということを含意しているため，以下の系が導か れる．
Corollary 2.1 (Roth and Sotomayor(1990)) すべての個人が真の選好を申告することが常に均衡となる
安定メカニズムは存在しない． 定理2.2は，男性最適安定メカニズムが設計者によって運営される場合，女性達によって虚偽の申告が されたとしても，男性達は真の選好を申告するという均衡の存在を示唆していた*8．また，すべての個人 の選好が強選好ならば，男性最適な安定マッチングは女性最悪なマッチングであることが知られている． つまり，男性最適安定メカニズムが運営されるときという女性達にとって選好の虚偽の申告をするインセ ンティブがある状況において，そのメカニズムが出力するマッチングが真の選好に関して安定であり得る かが，不可能性定理2.1に対するメカニズム・デザインの立場としての興味となる．その結果は，次の定 理に集約されている． Theorem 2.3 (Roth (1984)) メカニズムhを男性最適安定メカニズムとする．すべての男性が支配戦略を 選択して真の選好を申告していると仮定する．また，女性達は情報完備ゲーム(N = M ∪ W, Q, h, P)にお ける均衡となる任意の戦略の組P0 = (P0(w))w∈Wを選択すると仮定する．このとき，出力される男性最適 安定マッチングは真の選好Pにおける安定マッチングの1つである．
続いて，他人の選好に関する不完備性を導入したマッチング・ゲームとその主要な結果を概説する．各 個人は他人の選好を知らないが，それらがどのような確率分布から生起するかを知っていることを想定 する． 不完備情報ゲームとしてのマッチングは以下の組によって定義される*9： Γ = (N = M ∪ W, Q, h, U =∏ i∈N Ui, F). h : Q→ L[M]は，申告された各個人の選好から，すべてのマッチングの集合M上の確率分布族L[M] への関数であり，メカニズムと呼ばれる．Uiは，潜在的なパートナー達と自分との集合に実数値を対応 させる効用関数の集合である．即ち，各個人が如何なる効用関数をもつかが不完備情報ゲームにおける各 個人の“タイプ”であり，それらは確率的に実現する．その個人達の効用関数の各組u= {ui}i∈N ∈ U に対 する確率を纏めた確率分布がF である．確率分布Fは個人達の共通認識であり，各個人は自分のタイプ のみを知ってこのFをもとに申告を選択する．この“戦略”をσiで表現し，個人の効用関数の集合Uiか らあらゆる申告の集合への関数とする．σ = {σ}i∈N と定義するとき，個人達の申告Q= σ(u)に対して， マッチング全体の確率分布h(σ(u))が決定し，結果としてあるマッチングが実現する． タイプがuiである個人iの期待効用は以下のように記述できる： ui(σ) = ∑
u−i∈U−i
pi(u−i|ui)ui[h(σ(u−i, ui))].
但し，pi(u−i|ui)は個人iが確率分布Fを用いてベイズ・ルールによって計算する条件付き確率である． 不完備情報のマッチング・ゲームΓにおいて，戦略の組σ∗が均衡であるとは，すべての個人i∈ Nと その個人のすべての効用関数ui ∈ Uiに対して，以下の性質が成り立つことである：個人iのすべての戦 略σiに対して，ui(σ∗)≥ ui(σi, σ∗−i)． メカニズムhが安定であるとは，申告された選好Qに対してその出力h(Q)が確率1で安定マッチン グであることをいう．次の定理は，完備情報のマッチング・ゲームの定理2.3を否定する不可能性定理で ある．
Theorem 2.4 (Roth (1989)) Gale-Shapley結婚問題の各サイドに少なくとも2人ずつ存在するとする．こ
のとき，不完備情報ゲームΓの均衡のうち，実現するマッチングh(σ∗(u))が確率1で常に安定となる均 衡σ∗が少なくとも1つ存在するようなメカニズムhは存在しない． 以上が，他人の選好を知らない状況での集権化マッチングを不完備情報ゲームとして定式化した先行研 究の主結果である．前述のように，この結果は，集権化マッチングに参加する個人達にとって，そのタイ プに関するすべての個人間で共通の確率分布が利用可能であるとされる．このように共通の確率分布を信 念として形成すると仮定することは，各個人が十分に理性的であるという想定のもとでのアプローチとし *9 Roth (1989)は，各個人iの戦略を自分の選好の申告Q(i)に限らず，より一般の戦略を許した集合Diとして定義した．しか し本論文では，特殊ケースとして選好の申告のみが戦略である場合の結果を概説する．
て意味がある．一方，第3章においては，知らなかった他人の選好の情報を事前に獲得できる可能性があ る個人達を分析の対象としたいため，その個人達が事前に共通の信念を形成していると仮定する積極的な 理由はない．従って，第3章では不完備情報ゲームとは異なるアプローチをとる．
2.2
分権化マッチングと知識
2.2.1
萌芽的研究と知識の必要性
本小節は，安定マッチングへの分権的プロセスの萌芽的研究の結果を紹介するとともに，そのプロセス のなかで参加個人達が必要とする選好に関する知識について纏める．Roth and Vande Vate (1990)は，Gale-Shapley結婚問題には，参加個人達が自発的にペアを組み替える
ことを繰り返すことで安定マッチングに到達するパスが必ず存在することを示した．
Theorem 2.5 (Roth and Vande Vate (1990)) µを (M, W; P)における任意のマッチングとする．このと き，µ = µ1，かつ，µk が安定となるマッチングの有限列µ1, . . . , µk が存在する．但し，各i= 1, . . . , k − 1 に対して，µiにはブロッキング・ペア(mi, wi)が存在し，µi+1はµiからブロッキング・ペア(mi, wi)を満 足させることにより構成される． この定理は，Knuth (1976)が当時未解決とした“任意の選好プロファイルに対して，任意のマッチング から安定マッチングに到達するパスは存在するか”という問題を解決したとされている．そして，一見す れば安定性の定義2.2の性質(S)に沿った納得のいく結果でもある．しかし，集権化マッチングと比較し て，各個人の選好に関する知識の側面からこの定理を再考すると，この性質(S)に基づくブロッキング・ ペアの分権的な組み替えは，当然の結果として起こり得るものではないといえる．それは，マッチングが 与えられて，そこにある男女のブロッキング・ペアが存在していたとしても，その男女が互いの選好を知 らなければ，性質(S)の意味するそこに成立している両想いの事実に気付かず，そのマッチングが不安定 なまま維持されることが考えられるからである*10． 前節でも述べたように，Gale-Shapleyアルゴリズムには，各個人が(1)自分の選好に関する知識のみを 完全にもっていれば十分であった．一方，制度設計者のいない分権的状況のなかで安定マッチングに到達 するためには，ブロッキング・ペアが各個人の意思決定に基づき自発的に組み替えられていく必要があ る．そのために，各個人にとって(1)自分の選好に関する知識は完全であっても(3)異性達の選好に関す る知識が欠如していることは，前述の意味において安定マッチングに到達することを妨げる明らかな要因 となるのである．そこで，次章では，Gale-Shapleyアルゴリズムと分権化マッチングに共通して必要な (1)自分の選好に関する知識が完全であったとき，(3)異性達の選好に関する知識が分権化マッチングの安 定へのプロセスに与える影響に焦点を絞って考察する．
加えて，Roth and Vande Vate (1990)は，各個人が如何なる意思決定をおこなった結果として安定マッ
チングに到達するはずなのかについて一切記述していない．このことは，ある不安定マッチングに対して
複数のブロッキング・ペアが同時に存在する場合に問題を含む．定理2.5から，あらゆるブロッキング・ ペアが正の確率で生起すると仮定したとき，以下の系を導いている．
Corollary 2.2 (Roth and Vande Vate (1990)) 任意のマッチングµは確率1で安定マッチングに収束する．
しかしこの結果は，ブロッキング・ペアが複数存在するときには，そのなかの1組しかマッチすること が許されないばかりか，その1組は確率的に決定されることを意味している．この性質は，参加個人達の 自由な意思決定のもとで安定マッチングを目指そうとする分権的プロセスのなかでは外生的な要因であ り，そのプロセスの説明として相応しくないと考える．また，ブロッキング・ペアの組み替えの回数が限 られている状況を想定した場合，確率的に安定マッチングに必ず収束するとしても，その有限回内におい て安定マッチングに到達できるかは定かではない．つまり，Knuth (1976)の提示した未解決問題に厳密な 解決策を与えたことにはなっていないと考える． 故に，第4章では，分権化マッチングに参加する個人達が，直面したマッチングに対してどのような意 思決定をするか，即ち，どのような評価基準に基づいてペアの組み換えを希望してそれが達成されていく かを定式化する．Adachi (2000)は，その定式化に有用な概念を与えており，それが次小節で紹介するプ レマッチングである．そしてこの定式化は，分権的プロセスにおいて異性の選好に関して最低限必要とな る知識が何かを明らかにする．また同時に，この意思決定基準によって先程の確率的構造を回避すること ができる．
2.2.2
プレマッチングと意思決定
Adachi (2000)*11が定義したプレマッチングを概説するため，マッチングの定義2.1を書き直す．マッ チングµは，M∪ Wから M∪ Wへの全単射であり，次の3条件を満たすものである： (1) 任意の x∈ M ∪ W に対して，µ ◦ µ(x) = x； (2) µ(m) , mならばµ(m) ∈ W； (3) µ(w) , wならばµ(w) ∈ M． (1)の条件は，独身である以外は男性1人と女性1人とが対になっていることを要請する．(2)の条件は， 男性が独身でないならば相手は女性であることを要請する．(3)は，女性が独身でないならば相手は男性 であることを要請する． プレマッチングは，マッチングの3条件から条件(1)を除いたものである．正確には，以下のように定 義している． Definition 2.3 写像vM: M → M ∪ WとvW : W → M ∪ Wが以下の条件を満たすとき，2つの写像のペ*11 Gale and Shapley (1962)の構成的証明に代わる安定マッチングの存在証明を，Tarskiの不動点定理を用いておこなったこと
アv= (vM, vW)をプレマッチングという： vM(m), mならばvM(m)∈ W; vW(w), wならばvW(w)∈ M. (2.2.1) つまり，独身でない男性は女性と対応して，独身でない女性は男性と対応していれば，男性1人と女性 1人とが対になっていなくてもよい状態である．これは，各男性が各々どの女性とマッチしているかの予 想をしていて，各女性も各々どの男性とマッチしているかの予想をしていると解釈できる．そしてその予 想は必ずしも正しい訳ではなく，すべての男女の予想が正しいときに限ってプレマッチングはマッチング になっているといえる． 以下では，各個人は無差別を許さない強選好関係のみをもつとする．この仮定に応じて，新たな表記を 1つ導入している．ある男性mにとって女性wが女性w0より厳密に好ましい，または，wがw0と同じ 女性であるとき，wmw0と書く．女性側の立場についても同様の表記を用いる． マッチングの定義とプレマッチングの定義2.3により，マッチングが1つ与えられると，プレマッチン グは一意に定まる．そこで，“安定”マッチングが与えられたとき，一意に定まるプレマッチングが如何 なる性質をもつかが焦点となる．Adachi (2000)は，その性質が以下の方程式系であることを導いた： vM(m)= max m {w ∈ W : m wvW(w)} ∪ {m} for all m ∈ M; vW(w)= max w {m ∈ M : w m vM(m)} ∪ {w} for all w ∈ W. (2.2.2) また逆に，(2.2.2)をもつプレマッチングが与えられたとき，マッチングが一意に定まり，かつ，安定で あることを示している．このようにして，安定マッチングの存在を証明することを，(2.2.2)を満たすプレ マッチングの存在を証明することに帰着させた．方程式系(2.2.2)の含意するところは，マッチングの安 定性の条件は，各男女が自分を受け入れてくれる（と予想する）異性達と自分自身のなかで最も好ましい 1人を選ぶことと同値であるということである．先程から“予想”と表現しているのは，(2.2.2)が非協力 ゲームにおけるナッシュ均衡に近い特徴をもっているからである．つまり，各男性の最適な選択vMは女 性達の最適な選択vW に関する予想に依存していて，逆に，各女性の最適な選択vWは男性達の最適な選 択vMに関する予想に依存しているのである．男女の推論の連鎖が停止するのはお互いの予想と最適な異 性の選択とが一致するときであり，このとき，その男女は互いに他から逸脱したいインセンティブをもた ない．つまり，すべての男女に対してその一致がみられれば，もはやプレマッチングは誰も逸脱のインセ ンティブをもたない男女のペアの集合を構成しており，それが到達する安定マッチングなのである．この ように，プレマッチングという概念は安定マッチングを達成させるための各参加者の意思決定を表現する ものであるといえる． しかし，この推論の連鎖とその停止は，各参加者が十分に合理的・理性的であるときの予想と選択の結 果であるといえ，かつ，それらには異性達がもつ選好の情報が必要不可欠である．また，プレマッチング が安定マッチングを一意に定めるにあたって，実際になんらかのペアの組み替えがおこなわれている訳で はなく，強いて言えば，それは各個人の頭のなかでおこなわれていることになる．一方，本論文が対象と しているのは，マッチングが与えられたときに各個人がどのような意思決定をすることで分権的プロセス
が構成されていくかである．故に，Adachi (2000)は本論文が意思決定基準を定式化するのに優れた結果 をもたらしてくれるが，集権化されてはいないにしても，分権化マッチングの要素は薄い．さらに本論文 は，その分権化プロセスのなかで他人の選好に関する知識の必要性を見出すことを目的としているが，知 識が不完備であることを分析対象とはしていない．
2.2.3
マッチングと顕示選好
マッチングの参加者達が高度な推論能力のなかで，安定マッチングに到達することを期待するのではな く，与えられたマッチングやそのときに起こるであろうペアの組み替えを観察して，安定マッチングを目 指すことが分権化の焦点である．そこで予想することが，“あるマッチングに対して起こったペアの組み替えは，参加者達の選好の情報を顕示しているのではないか”ということである．実際，Roth and Vande
Vate (1990)におけるペアの組み替えは，互いが両想いであることが事実であるブロッキング・ペアが順 にマッチングを変化させていく．そして，ここで予想する選好の情報の顕示は，本論文が注目した他人の 選好に関する知識について，参加者達にその知識の獲得の可能性をもたらすのではないかと考えた． 経済学においては，財の価格や需要などの観察可能なデータから消費者のもつ選好関係を近似的に導出 することの可否を検証するのが顕示選好理論である．2サイド・マッチングにおける観察可能なデータと は，そのとき選択可能であった異性達や自分自身のなかからパートナーとして誰を選択したかということ になる． 顕示選好としての二項関係をマッチング理論に初めて導入したのはBlair (1988)であり，その後，Alkan
(2001, 2002)によって研究が続けられた．また，Alkan and Gale (2003)は，Alkan (2001, 2002)における
成果をスケジュール・マッチングに拡張している．スケジュール・マッチングとは，通常のマッチング理 論が考察の対象とする各個人が“誰とパートナーシップを組むか”に加えて，“どのくらいの時間その人と パートナーであり続けるか”という追加的な意思決定要素をもつマッチングである．しかし，何れの研究 も，安定マッチングの集合の数学的構造を議論する束論のオペレーションのために顕示選好を用いている だけであり，前述の期待のように，マッチングにおいて個人が形成していったパートナーシップの履歴を 観察することによってその個人の選好が顕示されるか否かを直接議論したものではない．但し，このよう な議論がされていないことはそれ程不思議なことではない．あるマッチングからペアの組み替えが起こっ たとき，自分にとってより好ましい異性とのペアが実現できるが故に新たなペアを形成したのならば，当 然，新しいパートナーは以前のパートナーより好ましい．一方，相手側からペアを解消された立場で新た なペアを形成したのならば，以前のパートナーが新しいパートナーより好ましかった可能性がある．しか もこの2つの組み替えは見分けがつかない．従って，経済学における顕示選好理論のように，観察可能な データから一貫性のある選好を導出することは困難である．そこで，個人達がマッチングを形成する以前 に選好を自ら直接顕示することを想定する．これが，第3としての選好顕示の有無を戦略と考えるゲー ム的状況の構築へとつながる．このゲームは，第2.1.2小節において概説した不完備情報ゲームとしての マッチング・モデルとも関連する．集権化マッチングにおいては，制度設計者が存在し，最も単純な場合 であれば選好を戦略的に申告する．一方，本論文は分権化マッチングを対象としているため，制度設計者 は存在しない．しかし，ブロッキング・ペアとしての自発的なペアの組み替えにとって，異性達の選好に
関する知識が必要であることは前述のとおりであり，戦略的に選好を申告する相手を，同じく参加者であ る異性達と想定することも可能であろう． 但し，個人が選好を顕示する，もしくは，他人から選好が顕示されることに意味がある，即ち，顕示さ れた選好を“知る”ということを議論する際には，分権化マッチングやその安定性の概念を選好に関する 知識の不完備性を扱うことができるものへと拡張する必要がある．他人の選好を必ずしも完全には知らな い状況において，ペアの組み替えが如何にして起こるのか，そして，長期的に維持され得るという意味で 安定であると解釈できるマッチングとは如何なるものかを定義しなければならない． 以上の流れに沿って，第4章のアプローチをとる前に，本論文に関わる一連の研究のなかで提案を考え
た別のアプローチを纏めたものが次章である．このアプローチは，Roth and Vande Vate (1990)を知識の
制約を導入することを通じて拡張し，分権化プロセスに対する異性達の選好に関する知識の影響を炙り出 そうとしたものである．但し，既に問題点が多く明らかになっているため，どこが問題であるかを自ら指
第
3
章
戦略的な選好の顕示
系2.2のように，Roth and Vande Vate (1990)は分権化マッチングにおける安定へのプロセスに確率構
造を導入した．前述のように，これは各個人の意思決定としては説明できない外生的構造である．しかし 本章では，その確率構造を積極的に援用することによって，個人達がもつ異性達の選好に関する知識が果 たす役割を考察する．2サイド間でその知識に優劣があるとき，知識優位な側の個人達の一部が戦略的に 自分の選好を顕示せず，生起する安定マッチングの確率分布を変化させる可能性があることを示す．以下 では，女性達は男性達がもつ選好を知っているが男性達は女性達がもつ選好を知らないという，もっとも 基礎的な事前情報の優劣が2サイド間で存在する状況を想定する．
3.1
他人の選好に関する知識と安定性
まず，Gale-Shapley結婚問題を知識の要素を含むかたちに拡張する．続いて，その拡張モデルにおける安定性やRoth and Vande Vate (1990)との関係を纏める．
女性集合W のべき集合をP(W)，そして，集合P(W)の任意の元をKW と書く．このとき，集合KW の元である任意の女性に対して，その女性の選好は“男性全員が事前に知っている選好である”ことを あらわし，KW の元でない女性達の選好は“男性全員が事前には知らない選好である”ことをあらわす． また，女性達は各男性の選好を事前に知っていることを想定する．即ち，知識優位な側が女性サイド， 知識劣位な側が男性サイドといえる．そして，異性全員に事前に選好が知られている個人達をあらわす 集合K = M ∪ KW を知識プロファイルと呼ぶ．知識プロファイルK を新たな要素として構成した組 (M, W; P, K)をK-安定結婚モデルと呼ぶ． 次に，定義2.2に知識の要素を明示した安定マッチングを定義する．本章では，選好関係に以下の2つ の性質を仮定する： Assumption 3.1 すべての個人は無差別関係を許さない強選好関係をもつ． Assumption 3.2 すべての個人にとって，任意の異性とペアになることは独身でいることより好ましい．
仮定3.1に応じて，選好プロファイルと知識プロファイルの各元の記述に対しても強選好関係 を用い る．仮定3.2は安定マッチングの定義2.2における個人合理性(IR)が任意のマッチングに対して成り立 つことを意味する．しかし，これは簡単化のためのみの仮定ではない．本論文で扱う知識の優劣は異性達 の選好に関するものであり，自分の選好に関する知識の優劣は存在しない．そこで，知識の優劣に焦点を 絞るためにこのような仮定をする． 仮定3.2のもとでは，あるマッチングが安定であるとは，そのマッチングによるパートナーより好まし い相手だと互いが思う男女がペアになっていないことが存在しないことである．しかし前述のように，自 発的なペアの組み替えを可能にするには，男女がその両想いの事実に気付くことが本質的である．そして 本論文では，それは男女が互いの選好を知っていることと同義である． そこで，あるマッチングが安定であることを，互いの選好を知っている男女の場合のみブロッキング・ ペアとなり，そのような男女のペアが存在しないことであると定義する*1． Definition 3.1 K-GS結婚問題において，あるマッチングµがK-安定（K-stable）であるとは，µが以下 の(KS)を満たすことである：
(KS) @(m, w) ∈ M × KWsuch that w m µ(m) and m wµ(w).
次の例で，K-安定とK-不安定なマッチングを確認する． Example 3.1 M= {m1, m2, m3}，W= {w1, w2, w3}とする．選好プロファイルを以下のものとする*2： m1: w1, w2, w3, m1, w1: m1, m2, m3, w1; m2: w1, w2, w3, m2, w2: m1, m3, m2, w2; m3: w1, w3, w2, m3, w3: m1, m2, m3, w3. 知識プロファイルをK = {m1, m2, m3, w2, w3}とする．つまり，情報優位な女性達は男性全員の選好を 知っているが，情報劣位な男性達は女性w2と女性w3 の選好のみを知っていて，女性w1の選好は知ら ないとする．このとき，以下のマッチングµ1はK-安定であり，マッチングµ2にはブロッキング・ペア *1 K-安定性の概念は，それ自体に未だ問題を抱えている．定義3.1は，互いに他の真の選好を知っている男女のみが現在の マッチングから逸脱するインセンティブをもつことを含意しているが，それ以外の男女がまったく逸脱のインセンティブを もたないとするのは議論が単純過ぎている．各個人が与えられたマッチングから逸脱するとき，もしくは，逸脱したいと思 うとき，選好に関する如何なる知識を用いているかを明らかにする必要がある． また，あるマッチングが達成されているときにその事実と一貫性のある知識が何であるかということも考察されていない． 例3.1ではK-安定・K-不安定なマッチングを確認する．そのなかで，K-安定マッチングµ1に注目する．情報劣位な男性達 は女性w2と女性w3の選好のみを知っていて，女性w1の選好は知らない．マッチングµ1が達成され，男性m2は女性w1 とマッチしている．しかし，パートナーシップが形成されたその瞬間にも，男性m2は女性w1の選好を知らないことになっ てしまう．このように，パートナーに自分が如何に評価されているかを知らないままでいるということは違和感があり，あ るマッチングが達成されたということと矛盾しない知識のあり方を再考察する必要がある． *2 各個人に対して，左から順に好ましい異性を並べている．
(m1, w2)が存在してK-不安定である*3： µ1= ( m1 m2 m3 w2 w1 w3 ) , µ2 = ( m1 m2 m3 w3 w1 w2 ) . 次の補題は，K-GS結婚問題において，知識プロファイルKの変化によるK-安定マッチングの集合の 変化を明らかにする． Lemma 3.1 K-GS 結 婚 問 題 (M, W; P, K = M ∪ KW) が 知 識 プ ロ フ ァ イ ル K0 = M ∪ KW0 に よ っ て (M, W; P, K0)へと変化したとする．このとき，K-安定マッチングの集合をそれぞれM，M0 とすると， KW0 ⊇ KWならばM0⊆ Mである． 証明：KW0 ⊇ KW を仮定する．µを集合M0 に属する任意の元とする．定義により，このK-安定マッチ ングµにはw m µ(m)かつm wµ(w)を満たす M× KW0 の元(m, w)が存在しない．KW0 = KW ならば， マッチングµは知識プロファイルKのもとで自明にK-安定である．故に，KW0 ⊃ KW とする． まず，w0をw0 ∈ KW0 かつw0∈ KWを満たす集合Wの元とする．マッチングµは知識プロファイルK0 のもとでK-安定であるから，w0 mµ(m)かつm w0 µ(w0)を満たすM× KWの元(m, w0)は存在しない． 一方，w00をw00 ∈ KW0 かつw00< KW を満たすWの任意の元とする．このとき，(m, w00) < M × KWで ある．しかしこれは，w00 m µ(m)かつm w00 µ(w00)を満たすM× KWの元(m, w00)が存在しないことを 含意する．故に，KW0 ⊂ KW ならばマッチングµは知識プロファイルKのもとでもK-安定である． 従って，KW0 ⊆ KWならば，任意のµ ∈ M0に対してµ ∈ Mである． 補題3.1によって，次の命題が得られる． Proposition 3.1 K-GS結婚問題にはK-安定マッチングが常に存在する．
証明：Gale and Shapley (1962)により，補題3.1においてK0 = M ∪ WのときM0は非空である．故に，
Wに含まれる任意のKWに対して，Mは非空である．
続いて，Roth and Vande Vate (1990)の安定マッチングへの収束パスが，K-GS結婚問題にも存在する
か否かが興味となる．次の命題は，その収束パスの存在を保証する． Proposition 3.2 集合K を任意の知識プロファイルとし，K-GS結婚問題(M, W; P, K)を考える．µを (M, W; P, K)における任意のマッチングとする．このとき，µ = µ1，かつ，µkがK-安定となるマッチング の有限列µ1, . . . , µk が存在する．但し，各i= 1, . . . , k − 1に対して，µiにはブロッキング・ペア(mi, wi) が存在し，µi+1はµiからブロッキング・ペア(mi, wi)を満足させることにより構成される． *3 同じ列の男性と女性がペアであることをあらわす．
証明：K-GS結婚問題に対して，Roth and Vande Vate (1990)の証明を適用すればよい（付録A.1）．
3.2
選好顕示ゲーム
本節は，情報劣位な側の男性達に対して，情報優位な側の女性達が自分の選好を顕示するか否かを事前 に意思決定することを考える．ある女性がどの男性とペアになるかは，自分がどのような選好をもってい るか，そして他の女性達がいかなる選好をもっているかに依存する．即ち，各女性のパートナーの決定 は，自分が選好を顕示するか否かだけでなく他の女性達が選好を顕示するか否かにも相互依存するといえ る．本章は，この相互依存関係を表現する戦略形ゲーム“選好顕示ゲーム”を定義することから始める*4 ．そして，この選好顕示ゲームにおいて，女性達の一部もしくは全員が戦略的に自分の選好の情報を顕示 しないという戦略をとり，かつ，ランダムメカニズムによって生起するK-安定マッチングの確率分布に変化をもたらすことを示す．この結果は，Roth and Vande Vate (1990)の安定マッチングへの収束パスに
他人の選好に関する知識が影響を及ぼすことを含意する． (M, W; P)を男性 p人と女性q人の任意のGale-Shapley結婚問題とする．そして，与えられた Gale-Shapley結婚問題に対して，知識プロファイルKを決定してK-GS結婚問題(M, W; P, K)を構成するの が選好顕示ゲームである．KW = ∅，即ち，K= M ∪ ∅ = M のときの有限個のK-安定マッチング全体の 集合をM = {µ1, . . . , µn}と書く．定義3.1により，Mは与えられたGale-Shapley結婚問題において仮定 3.2を満たすマッチング全体の集合と一致する．また補題3.1により，選好顕示ゲームによって決定され る任意の知識プロファイルK ⊇ M ∪ Wに対して，K-GS結婚問題はMに属するマッチング以外のK-安 定マッチングをもたない． 選好顕示ゲームは，戦略形ゲームとして次の要素の組によって定義される： G= (W, { w}w∈W, {Sw}w∈W; M, { m}m∈M), 但し， (1) W = {w1, . . . , wq}は情報優位な側の女性集合； (2) w∈W は女性wの選好； (3) Sw= {rw, nw}は女性wの純粋戦略の集合（rwは自分の選好を男性達に顕示する（reveal）という戦 略，nwは顕示しないという戦略*5）； (4) M= {m1, . . . , mp}は情報劣位な側の男性集合； (5) m∈M は男性mの選好 *4 このゲームは確率支配関係をもとにプレイヤー達の意思決定基準を構築している．このように，確率支配とその均衡概念を
非協力ゲームにおいて構築したものにFishburn (1978)やPerea et al. (2006)がある．これらをマッチング理論の文脈に沿う ように再構築したものが選好顕示ゲームである．
*5 選好顕示ゲームでは，真の選好を顕示するか否かの2つのみを戦略とみなし，虚偽の顕示を許していない．しかし，集権化
マッチングの文脈での既存研究のように，プレイヤー達が選好を顕示（申告）する際には，虚偽の申告の可能性を柔軟に残し た上で耐戦略性の有無を議論すべきであり，この想定は本来相応しいものではない．加えて，自分の選好の全部を顕示する か否かのみを考慮しているため，一部分のみを戦略的に顕示する状況を分析できないことも望ましくない．
とする．男性達はゲームのプレイヤーとしてではなく，ゲームの結果としてマッチングを形成する意味で ゲームの要素としている． ゲームは次のようにプレイされる．まず，後述の意思決定基準に基づいて，女性達がそれぞれの戦略 sw1 ∈ Sw1, . . . , swq ∈ Swq を選択する．すると，彼女達の戦略の組(sw1, . . . , swq)∈ Sw1× · · · × Swq によって 知識プロファイルK が決定されて，K-GS結婚問題が構成される．すると，このK-GS結婚問題におけ るランダム・メカニズムに依存して，K-安定マッチングの集合M上に確率分布pMが決まる．その確率 分布pM の族を∆(M)とおく．ランダム・メカニズムとは，初期時点でのマッチングと複数存在するブ ロッキング・ペアのなかでどの男女が順にペアになるかを確率的に決定するものである．ここまでを写像 f : Sw1× · · · × Swq → ∆(M)であらわす．そして，ランダム・メカニズムによって実際にあるK-安定マッ チングが実現し，各女性にパートナーの男性が決定される．以上が，情報優位な女性達をプレイヤーとし たゲームのプレイである． 次に，その女性達が戦略を選択するときの意思決定基準を説明する．そこで，女性wi ∈ W について 考える．まず準備として，男性全員の集合Mを女性wiの選好しない順に並べ替えた集合をM(wi)と書 く．即ち，M(wi) = {m1, . . . , mk, . . . , ml, . . . , mp}のとき，1≤ k < l ≤ pを満たす任意のkとlに対して， mk≺wi mlである． K-安定マッチングの集合M上に確率分布pM が与えられることは，女性wiにとって各男性とペアに なる確率が付与されることを意味する．この確率分布を pM(wi) とし，その族を∆(M(wi))とおく．即ち， 確率分布 pM が各K-安定マッチングµj ∈ Mに付与する確率を pM(µj)とし，確率分布 pM(wi)が各男性 m∈ M(wi)に付与する確率をpM(wi)(m)とするとき，以下を満たす：すべての男性m∈ M(wi)に対して， pM(wi)(m)= ∑ j∈ { j : µj(wi)= m } pM(µj). ここまでの操作を写像gwi :∆(M) → ∆(M(wi))とする．このとき，f とgwi との合成写像hwi = gwi◦ f : Sw1 × · · · × Swq → ∆(M(wi))は，女性達の戦略の組(sw1, . . . , swq)∈ Sw1× · · · × Swq に男性達の線形順序集 合M(wi)上の確率分布pM(wi)を対応させる． この確率分布pM(wi)= hwi(sw1, . . . , swq)に対して，その累積分布関数Hwi : M(wi)→ [0, 1]を以下のよう に定義する：任意の男性mk ∈ M(wi)に対して， Hwi(mk)= mk ∑ m= m1 pM(wi)(m). 女性達の他の戦略の組についても同様に，集合M(wi)上の確率分布h0wi と累積分布関数H 0 wi が得られる． Definition 3.2 線形順序集合Mwi 上の2つの異なる確率分布hwi とh 0 wi に関して，hwi がh 0 wi を確率支配
する（hwi first degree stochastically dominates h
0 wi; hwiD1h 0 wi）とは，すべての男性m∈ Mwi に対して， Hwi(m)≤ H 0 wi(m) が成り立ち，かつ，少なくとも1人の男性に対して厳密な不等式が成り立つことである．
女性wiの意思決定基準を表現するのが次の定義である．
Definition 3.3 女性wiの戦略 swi ∈ Swi が他の女性達の戦略の組s−wi = (sw1, . . . , swi−1, swi+1, . . . , swq)に対
する確率支配のもとで最適反応（best response under first degree stochastic dominance; FSD-最適反応） であるとは，
hwi(twi, s−wi) D1hwi(swi, s−wi)
となる戦略twi ∈ Swi が存在しないことである．
続いて，均衡概念を定義する．
Definition 3.4 選好顕示ゲームGにおいて，女性達の戦略の組 s∗ = (s∗w1, . . . , s∗wq)が確率支配均衡（first degree stochastic dominance equilibrium）であるとは，すべての女性wi ∈ Wに対して戦略s∗wi が他の女性
達の戦略の組s∗−wi に対するFSD-最適反応であるときをいう． 確率支配均衡において，女性達全員もしくはその一部が自分の選好を顕示しない戦略を選択していると する．そして，その均衡状態におけるK-安定マッチング上の確率分布とすべての女性達が自分の選好を 顕示しているときの確率分布が異なっているならば，各女性たちは自分が好ましいようにK-安定マッチ ング上の確率分布を戦略的に操作できる可能性があるといえる．即ち，このような確率支配均衡が観察さ れるとき，マッチングを形成する以前に異性達の選好に関する情報の優劣が存在することが確率的な安定 マッチングへの分権的プロセスに対して影響を与えていることを含意する．以上で構築した選好顕示ゲー ムは，分権化マッチングにおける“各個人が潜在的なパートナー達全員の選好を知っている”という仮定 は，どのマッチングに到達するかに確率的変化を与えるという意味において重要であることを説明する1 つの手法であると考える． しかし，確率支配均衡を構成するFSD-最適反応を各女性が選択するためには，前述のランダムメカニ ズムが女性達にとっての共通認識である必要がある．つまり，初期時点で如何なるマッチングが実現する か，そしてそのマッチングがK-不安定でありブロッキング・ペアが複数存在した場合，それらのなかで どの男女が順にペアになるかという2つの確率構造に対して，共通の確率分布を事前にもつことが必要で ある．この事前分布の要請は，一般の不完備情報ゲームにおける共通の事前分布の存在の要請と似たもの であるといえる．
第
4
章
分権的プロセスにおける意思決定
4.1
意思決定基準の定式化
本節は，Roth and Vande Vate (1990)に代わる安定マッチングへの分権的プロセスを提示する．但し，
簡単化のため，以下では男性3人（M= {m1, m2, m3}）と女性3人（W= {w1, w2, w3}）のGale-Shapley結 婚問題とする．本章では，選好関係に強選好の仮定3.1のみをする．引き続き，ある男性mにとって女 性wが女性w0より厳密に好ましい，または，wがw0と同じ女性であるとき，wmw0と書く． Definition 4.1 マッチングµに対して，関数C : M∪ W → M ∪ Wが以下の性質(4.1.1)を満たすとき，C を選択関数と呼ぶ： C(i)= max i {w ∈ W : i wµ(w)} ∪ {i} if i ∈ M; max i {m ∈ M : i mµ(m)} ∪ {i} if i ∈ W. (4.1.1) 性質(4.1.1)を個人iが男性の場合に関して説明する．あるマッチングµが与えられると，男性iをµ におけるペアµ(w)よりも厳密に好ましいと思う女性wと，男性iがµにおけるペアである女性w= µ(i) が決まる*1 ．その女性（達）の集合が{w ∈ W : i w µ(w)}である．そして，男性i自身を加えた集合 {w ∈ W : i wµ(w)} ∪ {i}のなかで男性iにとって最も好ましい1人がC(i)である．個人iが女性の場合 も男女の役割を入れ替えれば同様に解釈できる． また性質(4.1.1)は，Adachi (2000)のプレマッチングの概念を基礎にしている．しかし，安定マッチン グを一意に定めるプレマッチングの性質(2.2.2)は，各個人の推論の連鎖としての意思決定であり，最終 的な安定マッチングが形成されるまでに起こるペアの変化は仮想的なものであった．一方の性質(4.1.1) は，実際にいま実現しているマッチングを観察することを通して，ペアの組み替えを希望するか否かの意 思決定をあらわしている．そして，初期時点として与えられるマッチングµと選択関数Cによって，男 性3人・女性3人のGale-Shapley結婚問題における分権的プロセスを説明することができる．但し，µ *1 µはマッチングであるから，i= µ(w)はw= µ(i)と同値である．
は定義2.2の(IR)個人合理性を満たす任意のマッチングであるとする*2 ．分権的プロセスは以下の3つ のステップから構成される： (1) 与えられたマッチングµに対して，各個人にとって次のマッチングにおいてペアになることを希 望する相手を対応させる関数がC である．そこで互いに互いを希望し合った男女(m, w)，即ち， C(m)= wかつC(w)= mなる男女(m, w)は次のマッチングνにおいてペアになるといえる．何故 ならば，選択関数によって互いが互いの解となっていることは，当事者の男性も女性も互いが両想 いであることを知っているなかで最も好ましい異性であることを含意しているからである．言い 換えれば，このときの男女(m, w)はマッチングµにおけるブロッキング・ペアの1つである．ま た，個人i∈ M ∪ W が独身でいることを希望した場合，即ち，C(i)= iであるとき，その個人iは 次のマッチングνで独身となるといえる． (2) ステップ(1)が終了すると，パートナーを一時的に失った男性µ(w)と女性µ(m)がともに存在する ことがある．また，マッチングµにおいてもともとパートナーをもたなかった個人が存在すること もある．このステップでは，それらの男女のなかで，互いにとって独身でいるよりもペアになるこ とを好む2人が存在する限り，その男女は次のマッチングνにおいてペアとする．故に，ステップ (1)終了後に発生した個人合理性を満たさない状況が改善される． (3) それ以外の男女はマッチングµにおけるペアをνにおいても維持する．ここでの男女は，ステップ (1)における男女のように互いが互いの選択関数の解とはならなかった男女であるといえる． この3つのステップが，各個人の意思決定を表現する選択関数Cに基づいて構成されるマッチングµか らνへの分権的プロセスである． 次の例によってこのプロセスを確認する： Example 4.1 M= {m1, m2, m3}，W= {w1, w2, w3}とする．また，選好プロファイルを以下のものとする： m1: w2, w1, w3, m1, w1: m1, m3, m2, w1; m2: w1, m2, w3, w2, w2: m3, m1, m2, w2; m3: w1, w2, w3, m3, w3: m1, m3, m2, w3. 以下の個人合理性を満たすマッチングµが与えられたとする（縦に並んだ男女がペアであり，パート ナーが空欄の個人は独身である．）： µ = ( m1 m2 m3 w1 w2 w3 ) . 選択関数Cは各個人に対して，以下の結果を対応させる： *2 もし個人合理性を満たさないマッチングが与えられた場合であっても，各個人は自分の選好は完全に知っていることを仮定 しているため，独身でいる方が好ましい不満足なペアは自分の意思決定のみによって自由に解消することができる．
