積極的差別是正政策

安定 ・ 理論的考察 学校選択市場 応用

平成

27

3

序論 1

第1章 理論 9

1.1 . . . . 9

1.2 Two sided ・ . . . . 11

1.2.1 ^結婚市場. . . . 12

1.2.2 大学入学市場 . . . . 33

1.3 One sided ^・ . . . . 42

1.4 学校選択市場 . . . . 62

1.5 . . . . 74

第2^{章 安定性} Non-damaging bossy ^{両立不可能性} 83 2.1 . . . . 83

2.2 Two Sided ・ . . . . 86

2.3 ^結果 . . . . 89

2.4 . . . . 93

第3章 安定 ・ 関 考察 95 3.1 . . . . 95

3.2 大学入学市場 . . . . 96

3.3 ^{提携 改善} . . . . 99

第4^{章 戦略 積極的差別是正政策} 107

4.1 . . . . 107

4.2 ^{職探 ・} . . . . 109

4.3 積極的差別是正政策 濫用耐性 安定性 . . . . 112

4.4 . . . . 122

第5章 積極的差別是正政策 関 不可能性定理 126 5.1 . . . . 126

5.2 学校選択市場 ・ . . . . 129

5.3 ^{積極的差別是正政策} . . . . 133

5.4 TTC . . . . 147

5.5 . . . . 153

第6^{章 厚生 改善} 積極的差別是正政策 考察 158 6.1 . . . . 158

6.2 ^{積極的差別是正政策 用 学校選択制} . . . . 160

6.3 積極的差別是正政策. . . . 163

6.4 ^{他 積極的差別是正政策 比較} . . . . 175

6.5 . . . . 182

結論 185

付録 A–1

本稿 ,「 ・ 」 基礎理論 理論 新 考察 与 ．

・ ,^近年,^{急速 研究 進展 経済学 新 分野 ，}“Microe-

conomics Engineering” .¹⁾

伝統的 経済学 市場 与件 ， 市場 誰 何 ，何 起

予測 ， 予測 中心 研究 . 対

・ ，市場 与件 考 ，経済学 理論 知見 実証研究 実験 経済学 教訓 統合 ，実際 市場 制度設計 市場 運営 目的 研究

．極論 ，伝統的 経済学 学問的 成果 現実 制度設計 活用

難 .²⁾ 対 ， ・ 現実 市場 詳細 観察 ，

市場 慎重 分析 ， 生 問題 対 具体的 解決法 研究 ， 問題 対 解決方法 提示 .³⁾

近年， 分野 研究 急速 発展 理由 一 ，現実 市場 要請

大 ．例 ， 電波周波数帯 割当

，公立学校 選択制度 臓器移植 制度設計 ， ・ 研究

成果 改善 .⁴⁾ 2000年以降， ・ 理論的 発展 日進月歩 進 ，

応用先 広範囲 ．

1) ・ 最初 文献 Roth, Alvin E. (2008) .

2) 視点 ，Vulkan, N., Alvin E. Roth, and Z. Neeman (2013) 言及 .

3) ・ 成功 関 ，Roth, Alvin. E. (2013) 参照．

4) ・ 研究 現実 適用 事例 詳細 ，Roth, Alvin E. and Marild Sotomayor (1990) 参照．

， 研究 理論 ・ 定式化 分析道具 適用 科 学的 面 ，一方， 理論 使 現実 問題 解決 場合，科学的 確立 知識 超

判断 要求 ，理論 化 状況 異 現実 状況 対

理論 適用 判断 職人技的 面 .⁶⁾

・ 研究対象 中 ，市場 機能 性質 有

，明 研究 ． ，「非協力 理論」 理論

一分野 用 分析 ． 分析 ，特定 環境 帰結

対 各個人 行動 注目 ．当然 ，特定 環境 問題

異 課題 ． 環境 問題 課題 解決・分析 ，現実 市場 制度 設計 非常 重要 ， 環境 問題 生 共通 課題 問題 分析

・ 研究 中心 ．

・ 検討・分析 市場 広 経済環境 一部部分 .

， 事実 考慮 構築 ，非常 困難 ． ，

・ 研究成果 適用 市場 ，厳密 化 ， 大

・ ． ， ・ 研究成果 実際

市場 実現 ， 市場 多 人々 参加 ， 大 「

」 結果 ， 市場 導 結果 望 ．言 換 ， ・

理論予測 現実 市場 実現 ， 市場外 取引 行

望 人々 存在 ，重要 ．

・ 研究対象 市場 ・ 制度設計 市場

理論通 結果 導 ， 中 市場以外 行動 機会 考慮 ，

内 市場 行動 ，各人 市場 参加 均衡 導

5)Vulkan, N., Alvin E. Roth, and Z. Neeman (2013) 参照.

6)例 ，経済学 一般的 想定 主体 合理的 ，現実 主体 合理的 .

制度設計 市場 理論通 結果 導 ，

• ^{「厚 市場」，}

• ^{「滞 市場」，}

• ^{「参加者 安全性」，}

• ^{「単純 」}

，重要 指摘 .⁷⁾

厚 市場 ， 限 多 取引 同時 行 可能 市場 意味

. ^{， 市場 理論通 結果 導 ，多 市場 ， 多}

中 好 選択 重要 ．

滞 市場 ，有効 取引 評価 十分 時間 資源 市場 意味 ． 市場 滞 物理的 意味 取引 実行 必要 資源 意味

，多 中 望 選択 必要 情報 場合 含

． ，市場 滞 場合，多種多様 取引機会 ， 取引 望 判断 困難 . ^{理論通 結果 導 ，多種多様 選択肢}

市場 享受 滞 問題 解消 市場

．

参加者 安全性 ，参加者 市場以外 取引 行 ， 市場 参加 方 安全

取引 行 意味 ．参加者 望 取引 行 情報 知性

重要 場合，市場 ， 戦略 参加者 実行可能 ，他 参加

者 戦略的 振 舞 結果 左右 ， 安全性 問題 ．

7)Roth, Alvin. E. (2013) 参照.

・ 差異 明確 ． ・ 研究 ，異 間

比較 実現 均衡 比較 主 行 ． ，

・ 研究 ，現実 問題 考慮 研究 行 ．例 ，現実 市場 ，市

場参加者 他 参加者 均衡以外 行動 生 考慮 ，均衡

同様 均衡以外 最悪 考慮 分析 必要 ． ， ・ ，

・ 前提 仮定 異 ，市場 制度設計者 全体

決 知 前提 ， ， 大 一部 対 制度設計 行

事実 研究 行 必要 ． ・ ，最終的 起 均衡

市場全体 制度設計 ， ，望 均衡 市場 制度設

計 ， 均衡 達成 ． ， 予想外 行動 現実 ，

市場 制度設計 修正 ．

市場 自身 参加 参加者 行動 両方 「単純化」

． 単純化 ，参加者 実現 結果 明確 ， 本当

実行 確認 効果 ． 単純 ，参加者 戦略 複

雑 ．戦略 複雑性 ， 重要 問題 可能性 . ，

結果 導 戦略 実行 費用 ，間違 意図的 誤 起

結果 ， 市場 参加者 戦略 複雑性 影響 受 ．

，市場参加者 減 可能性 ．

本稿 ，上記 視点 研究 ・ 基礎理論 一

「 理論」 焦点 絞 ． 理論 ，病院 研修医，法律家 裁判所，患

者 腎臓 Two sided ^{参加 人 片方}

参加者 方法 研究 分野 ． 考 際 ，提

案 「安定性」 満 ， 市場 提案 別

概念 理論 ，重要 中心的 概念 ．

理論 数学者 ・ 科学者 ，長年研究

，実践的 経済制度設計 非常 役立 ，経済学者 間 注目 ． 事実 顕著 表 ，2012^{年 ， 分野 貢献者 ，}Roth^教授 Shapley 教授 経済学賞 受賞 ．

本稿 ， ・ 基礎理論 理論 対 新 視点 理論的 発

展 下記 5本 論文 書 ．各章 次 構成 ．

第1^{章 ，}Gale, David and Lloyd Shapley (1962) ^{始 理論 現在} 進展 ，Abdulkadiro˘glu, Atila and Tyfun S¨onmez (2013) 同様 流 沿 ， 限

証明 与 解説 ．第2^{章 ，}Economics Bulletin ^掲載 Matsubae,

Taisuke (2010)“Impossibility of Stable and Non-Damaging Bossy Mechanism ” 研

究 ． 研究 ， 考察 安定 負 性質 明

研究 ．第3章 ，Matsubae, Taisuke (2012) “A Note on Stable Matching Mechanisms”

基 研究 ，片方 選好 単調 変化 ，安定 ・ 導出

結果 変化 明 研究 ．第4章 ，Matsubae, Taisuke

(2011a)“An Affirmative Action Policy as a Strategy on Two Sided Matching Market” ^基

研究 ． 研究 ， 理論 ，制度 考 積極的差別是正

政策 ，企業 戦略変数 場合 結果 生 分析 最初 研究

．第5^{章 ，}Matsubae, Taisuke (2011b)“Do the Minority Students Benefit from Affirmative Action Policy in School Choice Market ?: Reconsidered” 基 研究 ．積極的差別是 正政策 学校選択制 応用 既存研究 示 不可能性 解消 ，単純 形 積極的差別是正政策 強 可能性 実現 考察 研究 ．第 6^{章 ，}Matsubae, Taisuke (2013)“Group Affirmative Action Policy at School Choice” ^基

生 悪化 可能性 指摘 受 ，積極的差別是正政策 中身

吟味 改善 ， 学生 厚生 改善 考察 研究 ．最

後 ，本稿 明 研究結果 ，付録 ，本稿 研究

導出 求 記載 .⁸⁾

8) Python 2.7.8 用 書 ．Python , C言語 同様 汎用 言語

.

Abdulkadiro˘glu, Atila and Tyfun S¨onmez (2013) Matching Markets: Theory and Practice, Vol. I of Advances in Economics and Econometrics: Theory and Applications, Tenth World Congress: Cambridge University Press.

Gale, David and Lloyd Shapley (1962) “College Admissions and the Stability of Marriage,”

American Mathematical Monthly, Vol. 69, No. 9, pp. 9-15.

Matsubae, Taisuke (2010) “Impossibility of Stable and Non-Damaging Bossy,” Economics Bul- letin, Vol. 30, pp. 2092-2096.

(2011a) “An Affirmative Action Policy as a Strategy on Two Sided Matching Market,”

memeo.

(2011b) “Do the Minority Students Benefit from Affirmative Action Policy in School Choice Market?: Reconsidered,” memeo.

(2012) “A Note on Stable Matching Mechanisms,” memeo.

(2013) “A Group Affirmative Action Policy at School Choice,” memeo.

Roth, Alvin E. (2008) “Deferred Acceptance Algorithms: History, Theory, Practice, and Open Questions,” International Journal of Game Theory, Vol. 6, pp. 537-569.

Roth, Alvin. E. (2013) What Have We Learned from Market Design? in Handbook of Market Design: Oxford Press.

Modeling and Analysis, Econometric Society Monograph Series: Cambridge University Press.

Vulkan, N., Alvin E. Roth, and Z. Neeman (2013)Introduction in Handbook of Market Design:

Oxford Press.

本章 ，Abdulkadiro˘glu, Atila and Tyfun S¨onmez (2013) 同様 流 沿 ， 理論 研究 成果 紹介 .

1.1

市場 重要 機能 一 ．例 ，誰 仕事 ，

学校 入学 ，誰 誰 結婚 ， 経済的 場面 社会

場面 ，多 人々 重要 問題 ．

理論 研究 ，Gale^教授 Shapley^教授 American Mathematical Monthly 1962年 発表 “College Admissions and the Stability of Marriage” 最初 研究

.^{1) 彼 論文} ,^{次 単純} Two sided ^考察

．男性 女性（学生 学校） 相手 対 選好 ，彼

女 互 考 ．彼 論文 関心 ，互

納得 「安定 」 ． ， 男

女 ， 互 選好 男女 再 考 存在

分析 ．彼 論文 ， 安定 存在 ，

安定 求 , Deferred Acceptance (DA

) 提案 ． ，一方 主体 別 主

体 対 ，選好 順序 機能

1)Gale, David and Lloyd Shapley (1962)

． ，次 手続 . ^{最初 人 ，自身 最} 選好 人 . 受 入 可能 人数（例 ，結婚問題 一人）

多 受 ， 中 最 選好 人以外 人 拒否 ，拒

否 ， 人 受諾 ， 人 留保

．留保 人 受諾 ， 終了 決定 ．拒否

人 ，2番目 選好 新 人 ， 結果，新 拒否 人

（新 人 ，留保 人 選好 ，留保 人

新 拒否 人 ）． 一連 流 ，拒否 人 新 相手

続 ．誰 （ ）時点 ，留保

人 最終的 受諾 ， ．

彼 論文 ， 選好 対 安定 結果 存在 ,^{選好 厳密 順序}

， 市場 各 安定

見 可能 上記 DA ^{提示 ， 求 安定}

，任意 安定 ，最 好 安定

示 ． Two sided ^{市場 関連 示 ．最後 ，}

一対一 問題 拡張 ，一対多（大学入学問題） 問題 拡張 行 ． 現在， 市 高校 市 学生 公立学校 対 入学 ，以前 用

生 学生 対 不満 解消

，DA 使 ・ 再組織化 ． ，米国 病院 研

修医 問題 同様 適用 .²⁾

理論 研究 上記 理論 用 制度設計 ， 理

論 制度設計 ・ 設計 際 ，理論上予測 （

2)Gale, David and Lloyd Shapley (1962) 発表 以前(1950年代) ・

用 ．DA 多 場所，例 日本 早稲田高等学院 早稲田大学 学部

振 分 ， 用 ． ，Two-sided 生成 伝統的 方 ．

）問題 生 ， 問題 解消 新 研究 ． 上記 研究 関連 研究 ，1974年 ，Shapley教授 Scarf教授 “Cores and Indi- visibility” ^論文 Journal of Mathematical Economics ^{創刊号 掲載} .^{3) 論文} 扱 ，単純 交換経済 ．各主体 ，非分割財 一 市場

， 好 財 持 他 主体 探 ． 消費 財 数 高々一

．彼 ， 配分 分析 ．彼 ， 中

配分 存在 ，Gale^{教授 考案} Top Trading Cycles (TTC

) 配分 求 示 ．Gale教授 考案 TTC

拡張 ，発見 30年後 腎臓 臓器移植 割当

適用 ．

市場 研究 網羅 , ^{存在 ． 中 最 有名}

，Roth, Alvin E. and Marild Sotomayor (1990) ，1990年 Two sided 市場 研究 網羅 ．Roth, Alvin E. (2008) ^，DA ^{中心 歴史}

． 論文 ，基本的 Two sided 市場 着

目 ．Abdulkadiro˘glu, Atila and Tyfun S¨onmez (2013) ^，Two sided

One sided 注目 ． 研究 近 研究 S¨onmez, Tyfun and

M. Utku ¨Unver (2009) ^{．本章 ，後者 ， 近 研究 ．次節以降 ，}

・ 詳細 既存 主要 結果紹介 ．

1.2 Two sided ・

理論 最初 研究 Gale, David and Lloyd Shapley (1962) ^{，非常 関}

連 2 Two sided ^{市場 考察 ．} 2 ^{唯一 違 ，一対一}

考 ，一対多 考 差 ． ，一対一

3)Shapley, Lloyd and Herbert Scarf (1974) 参照。

「結婚市場」，一対多 「大学入学市場」 ．最初 「結婚市場」 紹介 行 ．

1.2.1 結婚市場

結婚市場 構成要素 ，2 交 主体 集合M := {m₁, m₂, . . . , m_n} W :=

{w1, w2, . . . , wp} ^{． ，}M∩W =∅ . ^集合M ^{男性 集合，集合}W ^女性 集合 ．各集合 代表的 元 m∈M w∈W 表現 ．両集合 代表的 要素 i∈M∪W ^{表記 ．各男性}m ^{，他 主体 集合}W ^自分自身{m} ^{上 完備性 推移性}

満 選好関係R_m .⁴⁾ wR_mw⁰ ¬(w⁰R_mw) 場合 ，wP_mw⁰ 表記 ．自分自 身 対 選好関係 ，誰 可能性 意味 .^{5) 選好関係}Rmi

，次 形 表記 ．

R_m=w₁, w₂, m_i, w₃, . . . , w_p.

選好 意味 ，m 最 選好 人 w₁ ，二番目 選好 人 w2 ．彼 三番目 選好 人 自分自身 ，誰 選好

． ， 男性m ，女性 集合 選択 機会 与 ，w₁ 存在

，w1 選択 ． w1 w2 選択 ，誰

選好 ．誰 下位 女性，例

w3 女性 ，男性m ^{呼 ．一般的 選好関係}

主体 除 形 表現 多 ． 主体以外

主体 ．任意 二人 主体 間 無差別 ，

4)選好関係 完備性 満 ，主体m 対 ，任意 w, w⁰∈W∪ {m} ^{対 ，}wRmw⁰ w⁰Rmw 成 立 ．選好関係 推移性 満 ，主体m 対 ，任意 w, w⁰ w⁰⁰ 対

，wRmw⁰ w⁰Rmw⁰⁰ ，wRmw⁰⁰ 成 立 ．

5)誰 対 別 解釈 ， ・ 解釈 場合 . ，

市場 外 取引 意味 .

主体 ， 間 無差別

，彼女 彼 選好関係 厳密 選好関係 ．

各女性w ^対 同様 ，男性 集合 彼女自身M∪ {w}^{上 順序 選好} 以下 表記 ．例 ，次 彼女 選好関係 表記 ．

R_w =m₁, m₂, w, m₃, . . . , m_n.

選好 意味 ，女性w 最 選好 人 m₁ ，二番目 選好 人 m2 ．彼女 三番目 選好 人 自分自身 ，誰

選好 ． ， 女性w ，男性 集合 選択 機会

与 ，m1 存在 ，m1 選択 ． m1 m2 選択

，誰 選好 ．

結婚市場 ，(

M, W,{Ri}_i∈M∪W)

三 組 表現 ，男性 女性 選好関係 ，一般的 厳密 選好関係 仮定 ．

結婚市場 結果 ， 割当 ．結婚市場 ，次

性質 満 写像µ:M∪W →M∪W ． 1. m∈M 対 µ(m)∈/ W ⇒µ(m) =m, 2. w∈W 対 µ(w)∈/M ⇒µ(w) =w,

3. m∈M w∈W 対 µ(m) =w ⇐⇒ µ(w) =m.

， 主体 別 主体， 自分自身 ． ，w

m ，m w 意味 ．

対 選好関係 ， 人 対 選好関係 同 ． ，

対 外部性 意味 ．例 ，自分自身 相手

同 ，他 人 相手 変化 対 選好

変化 意味 ．

µ ^{効率的 ， 主体}i∈M ∪W ^{対 ，}ν(i)Riµ(i)^，

主体j∈M∪W 対 ，ν(j)P_jµ(j) 他 ν 存在 意味 ．

µ ,主体i∈M∪W ，

{i}P_iµ(i)

． 任意 主体i ， µ 個人合理的 ．

，個人合理的 ， ．

µ (m, w)∈M×W ，

wP_mµ(m) mP_wµ(w)

(m, w) ^{存在 ． ，} µ ^相手

互 選好 存在 ， µ (m, w)

．

定義 1 (安定性). µ 個人合理的 存在 場合，

µ ^{安定 ．}

結婚市場 ，安定 効率的 ， 安定 集合

．

定理 1 (Gale, David and Lloyd Shapley (1962)). 結婚市場 安定 存在 ．

Gale^教授 Shapley^{教授 ，次 示 開発 分析 上記 定理} 示 .⁶⁾

【証明】

任意 結婚市場 対 ，安定 導出 男性 DA 次

.⁷⁾

男性 DA

1 男性 方 状況 考 ．( 彼 女性

)^{各男性 彼 最 選好 女性 対} . ,^{彼 選好} 女性 最初 位置 女性 ．各女性 彼女

男性 拒否 ，1 ^以上 受 各女性 ， 中 最 選好 男性 留保 ， 以外

男性 拒否 ． 男性 中 拒否 男性 ， 時点

女性 留保 状態 .

k≥2 ^任意 k ^， k−1 ^{拒否 任意 男性 ，}

女性 中 最 選好 女性 ．

k−1 ^{，留保 ， 女性 拒否 ，}

彼 ． 受 各女性 ，

男性 拒否 ，以前 留保 男性 新 男性 中 最 好 男性 留保 ， 以外 拒否 ．

，任意 男性 女性 拒否 後 終了 ．

6)Roth, Alvin E. (2008) ，Gale教授 安定性 定義 構築 ，安定 常 存在

予測 仲間 送 ， 受 一人 Shapley教授 ， DA 対応

証明 返信 ．

7)男性 女性 置 換 ，女性 DA .

時点 ， 男性 女性 留保 ，彼

女性 拒否 ． 後，女性 留保 男性 最終的

．任意 受 女性達 女性

拒否 男性達 ，誰 .⁸⁾

【 有限性】男性 女性 人数 有限 ，任意 女性 対 ，男性 1^回

以上 ， 有限時間 終了 ．

【 生 出 結果】 生 出 結果 ， ．

，各男性 任意 段階 高々1人 女性 留保 ，各女性 任意 段階 高々1

人 男性 留保 ．

【 結果 個人合理的】女性 男性 ， 人 決

， 結果 個人合理的 ．

【 結果 安定性】 生 出 µ 安定

見 ， 男性m ^女性w ^{， 生 出}

µ 対 ・ 仮定 ． ， µ 対

・ (m, w) ^存在 : wPmµ(m) mPwµ(w) . ^，女

性w 男性m ． ，彼 現在 相手

前 彼女w ^{． 終了 ，}

彼 女性w ^{留保 ，彼 ，彼女 男性}m ^{選好 男性}m⁰

拒否 ． ，w 男性m 選好

男性 µ ^{． ，最終的 ，}

男性m⁰ 選好 男性m⁰⁰ ，彼女 選好 推移性 満 ，女性w

，男性m ^現在 µ ^{相手 好 ． ，}m

8) ，無差別 選択肢 存在 ， 機能 ． ，無差別 選択肢 存

在 ，無差別 選択肢 中 一 選択 導入 必要 . Tie

Breaking Rule（ ・ ・ ） . 例 ，無差別 女性 中

順序 選択 ．異 主体 異 方法 無差別 選択肢 対 順序 方法 ．

w µ ^{・ ． ， ・ 存在}

矛盾 ． ， ，任意 個人

，安定 ．

上記 証明 示 ，男性 DA 結果 ，男性最適安定

，µ^{M 表記} ．男性 女性 役割 逆転 女性 DA

． 結果 女性最適安定 ，µ^{W 表記 ． 名前 由} 来 ，下記 定理2 ．

定理 2 (Gale, David and Lloyd Shapley (1962)). 男性 女性 厳密 選好関係

，男性最適安定 存在 ， 安定 他 安定 弱

意味 選好 ． ，男性 DA 導出

µ^{M 男性最適安定 ．}

【証明】

最初 用語 定義 ．w m 達成可能 ，µ(m) =w 安定 存在 ． 定理 示 ，DA 任意 ，達成可能 女性

拒否 男性 示 十分 ．

背理法 ， 女性 拒否 男性 ． 男性m , 達成可

能 女性w ^{最初 拒否 場合 考 ． ， ，女性}

w 他 男性m⁰ 留保 ． ，m⁰P_wm ．一方，DA 最初

達成可能 µ ^，wP_m0µ(m⁰) ^{． ，} 2 事実 ，(m⁰, w) µ ・ ． µ 安定

矛盾 ．

女性最適安定 対 同様 定理 示 可能 ．

定理 3. 男性 女性 選好関係 厳密 ， 男性 ，女性最適安定 任意 他 安定 弱 意味 選好 ．

【証明】

背理法 仮定 ， 男性m 対 ，µ^W(m)P_mµ(m) 安定 µ

存在 ．µ^W(m) =w ^女性w ^{，以前 定理}2 ^{他 安定}

弱 意味 選好 ． ，選好関係 厳密 ，mP_wµ(w) ．

，(m, w) µ ^{対 ・ ．} µ ^安定

矛盾 ．

，安定 複数 可能性 ． ， 安

定 実行 ，結婚 場合 結婚 場合 ．

，参加者 安定 実行 ，重要 問題

． ，次 田舎病院定理 問題 生 ．

定理 4 (田舎病院定理Roth, Alvin E. and Marild Sotomayor (1990), McVitie, D. G. and L. B.

Wilson (1970)). ^{自分自身以外 主体 集合 ， 安定}

同 ．

【証明】

µ^M 男性最適安定 ，µ 任意 安定 ．次 集合 定義 .

µ(W) = {m∈M :m=µ(w)Pww, ∀w∈W}, µ(M) = {w∈W :w=µ(m)Pmm, ∀m∈M}^．

µ^M(W) µ^M(M) ^{対 同様 定義 ．安定} 個人合理性 男性最適安定

性質 ，µ 自分自身以外 男性 µ^M 自分自身以外 可能 . µ(W)⊂µ^M(W) ^．µ^{M 女性 最悪 安定}

，µ^M 自分自身以外 女性 ，µ 自分自身以外

可能 ． ，µ^M(M)⊂µ(M) ^{． 定義 ，}|µ^M(M)|=|µ^M(W)|

|µ(M)|=|µ(M)| ^，|µ⁽W)|=|µ(W)| |µ^M(M)|=|µ(M)| ^．

，µ^M(W) =µ(W) µ^M(M) =µ(M) ^．

安定 集合 構造 考 ．安定 集合 対 構造 最初

研究 Knuth, Donald E. (1996) .⁹⁾ µ µ⁰ 2 考 ． 2

対 ，次 操作 考 ．λ=µ∨^Mµ⁰ :M∪W →M∪W ^，µ µ⁰

，男性 選好 女性 ． ，各女性 2

, ^{選好 男性 決 操作 ．}ν=µ∧^Mµ⁰:M∪W →M∪W

，µ µ⁰ ，男性 選好 女性 ． ，各女性 ，

2 , ^{選好 男性 決 操作 ．}

集合 関 ， 操作 行 場合， 結果 次 例

．

例 1. 3人 男性 女性 存在 ，M ={m₁, m₂, m₃},W ={w₁, w₂, w₃} ^{． 各自}

，次 選好関係 持 ．

P_m1 = w₂, w₁, w₃, m₁ P_w1 =m₁, m₃, m₂, w₁ P_m2 = w₁, w₃, w₂, m₂ P_w2 =m₃, m₁, m₂, w₂ Pm3 = w1, w2, w3, m3 Pw3 =m1, m3, m2, w3.

9) 一般的 ・ 対 構造 研究 ，Blair, Charles (1988), Mart´ınez, R., J. Mass´o, A. Neme, and J. Oviedo (2001), Sotomayor, Marilda (2000), Sotomayor, Marilda (2007), Fleiner, Tamas (2000)

Hatfield, John William and Paul Milgrom (2005) ．

可能 ，個人合理的 ． ， 組(m, w) ^互

． µ µ⁰ 次 与 ．

µ=



m1 m2 m3

w₁ w₂ w₃



 µ⁰ =



m1 m2 m3

w₃ w₁ w₂



.

λ ν ^{操作 ，}

λ=



m1 m2 m3 w1 w2 w3

w₁ w₁ w₂ m₂ m₃ m₃





ν =



m1 m2 m3 w1 w2 w3

w₃ w₂ w₃ m₁ m₂ m₁



.

， µ µ⁰ 安定 ， 操作 結果 安定

． ，安定 集合 構造 ．

定理 5 (Lattice theorem Knuth, Donald E. (1996)). 選好関係 厳密 ，µ

µ^{0 安定 ，}λ ν ^{操作 結果 ． ，}

安定 ．

【証明】

最初 ，λ ^{示 ． ，}λ(m) =w ⇐⇒ λ(w) =m

示 十分 ．

Only if part: λ(m) =w⇒ λ(w) =m ^{示 ．}λ(m) =w ^，λ ^{定義 ，}w µ µ⁰ 女性 中 m ， 選好 女性 ． 事実 仮定 ，

λ(w) = m ^{示 ． ，}m µ µ^{0 男性 中} w

， 選好 男性 意味 ．背理法 仮定 ， 成 立

．一般性 失 ，µ(w) ^男性m⁰ m ^{選好 ．}

， 定義 µ ，m w 異 女性w⁰

． ，λ 定義 選好関係 厳密性 ，男性m ^，wPmw^{0 ．}

，wP_mµ(m) mP_wµ(w) ． ，µ 対 (m, w) ・

意味 ． ，µ ^{安定 矛盾 ．}

If part: λ(w) =m ⇒ λ(m) = w 示 ．λ 誰 結婚 男性 集合 M⁰

：

M⁰ ={m: λ(m)∈W}={

m:µ(m)∈W orµ⁰(m)∈W} .

Only if part 結果 ，任意 w∈W m⁰ ∈M⁰ 対 ，λ(m⁰) =w λ(w) =m⁰

． ，

λ(M⁰)⊆ {w:λ(w)∈M}={

w:µ(w)∈M and µ⁰(w)∈M}

=W⁰.

，λ(M⁰)⊆W⁰ ．定義 ，

M⁰={

m:µ(m)∈W orµ⁰(m)∈W}

⊇ {m: µ(m)∈W} ⊇{

m: µ(m)∈W⁰}

=µ(W⁰).

µ 写像 ，µ(W⁰) W⁰ 同 大 ． ，M⁰ ⊇W⁰

．w = λ(m) = λ(m⁰) ^，m = m⁰ = λ(w) ^，λ ^{一対一 写像 ．}

，M⁰ λ(M⁰) 同 大 ． ，λ(M⁰) ⊇ W⁰ ．上記 事実 λ(M⁰) =W^{0 ．}m=λ(w) ^{仮定 ． ，}w∈W⁰=λ(M⁰) ^， m⁰ ∈M⁰

対 ，w=λ(m⁰) ． ，m⁰ =λ(w) ．λ(w) 一意 ，m

異 m^{0 対 成 立 ． ，}λ(w) =m ^．

λ 安定 示 ．

個人合理性：λ ^{個人合理性 満 ，}µ µ^{0 安定性 ． ，}

安定 ， 相手 ，

選好 方， 選好 方 相手 ．

・ 非存在：背理法 仮定 ， ・ (m, w) λ ^対

存在 ． ，m ・ ，λ 定義 µ µ⁰

w ^{方 選好 ．同様 ，}w m mu mu^{0 選好}

．一般性 失 ， µ ． ， µ (m, w)

・ 意味 ． m ^{安定 矛盾 ．}

ν 関 同様 証明 ．

定理5 直観 ，2 安定 ，男性 中 選好 女

性 選択 求 ，2人以上 男性 同 女性 選択

．

安定 集合 構造 用 ，以前 示 田舎病院定理 別証明 与 ．

【田舎病院定理 別証明】

任意 2 ^安定 µ µ^{0 ，}Mµ Mµ⁰ ， 女性 男性 集合 ．W_µ W_µ0 同様 ，

男性 女性 集合 ．

λ 以前定義 µ µ 操作 ． 操作 結果 男性 女性 集合

µ_λ W_λ ． m µ 誰 ，誰

誰 選好 ，λ ^{誰 ．}

，

M_λ =Mµ∪M_µ0.

一方，女性 ， 誰 ，λ