狠狠撸

マッチング?マーケットデザイン
実践?理論?課題の紹介
安田洋祐
大阪大学大学院経済学研究科准教授
Eメール: yasuda@econ.osaka-u.ac.jp
ウェブ: https://sites.google.com/site/yosukeyasuda/jp
2018年6月 1

本日の報告の流れ
1. マーケットデザインの進展
2. 安定マッチングの理論
? Gale-Shapley (1962) のアルゴリズム
3. 理論の拡張と更なる実践
a. 選好の一般化…補完的採用
b. 配分制約…研修医偏在問題
c. 事前の効率性…GS vs. Boston (DA vs. IA)
d. その他の拡張
2018年6月 2人工知能学会｜安田洋祐

マーケットデザインの進展
ゲーム理論が創る制度の仕組み

2012年のノーベル経済学賞
- ゲーム理論の実践＝マーケットデザイン

マーケットデザイン = 制度設計
- 理論から実践へ！
マーケットデザインとは？
? ゲーム理論で得られた知見をいかして、現実の市
場や制度を修正?設計する新しい分野
– 「マーケット」はいわゆる市場よりも広い概念！
? 理論だけでなく、実験やシミュレーションを通じて事
前に実用性の検証を行う ? 工学的
? 経済学者の提案した新たな制度がそのまま現実に
応用され役にたっている ? 実践的
→ どんな実践例があるのかを見てみよう！
2018年6月人工知能学会｜安田洋祐 5

代表的な実践例
- すでにたくさんの成功事例が！
? オークション設計
– 周波数オークション
– 国債の販売方法
– 検索連動型広告
? マッチングメカニズム
– 研修医マッチング
– 臓器交換メカニズム
– 公立学校選択制

代表的な実践例
- すでにたくさんの成功事例が！
? 「お金?価格」
– 周波数オークション
– 国債の販売方法
– 検索連動型広告
? 「相手?相性」
– 研修医マッチング
– 臓器交換メカニズム
– 公立学校選択制

経済学とCSのコラボレーション
Algorithmic Game Theory HB of Market Design

安定マッチングの理論
マッチングを制する者は人生を制す

マッチング問題とは何か？
- ヒトとヒトとのマッチング
? 人と人、人と組織をどう
やってマッチさせるの
がよいか？
? 望ましいマッチングの
仕組みをゲーム理論を
使って分析！

様々なマッチング問題
- 下に行くほどより複雑な問題に
? 1対1（One-to-One）
– 【結婚市場】男女のマッチング
? 1対多（One-to-Many）
– 【労働市場】労働者と企業のマッチング
– 【学校選択?入試】生徒?学生と学校のマッチング
? 多対多（Many-to-Many）
– 【ビジネス】卸売と小売業者のマッチング

安定マッチングの理論
- Gale-Shapleyの偉大な発見とは？
? 安定マッチング：「どんな個人やペアが逸脱してもそ
の人（たち）が得できないようなマッチング」
– すべての参加者にとって
– マッチしたくない相手とは絶対にくっつかず
– 自分がマッチできる可能性のある相手の中で最適なパー
トナーとくっつける！
? 安定マッチングの性質
– どんなマッチング問題でも常に1つは存在する
– （すべての）安定マッチングはパレート効率的
– Gale-Shapley (GS) アルゴリズムによって見つかる

不安定なマッチング
- 男性が順番に女性を選ぶと（逐次独裁者法）
? 男性陣の好み ? 女性陣の好み
? 結果は必ずパレート効率的！（ロスは生じない）
? しかし【ともき－るい】には逸脱するインセンティブが…
2018年6月 13
こうきだいきともき
1位るいるいあい
2位ひとみあいるい
3位あいひとみひとみ
るいひとみあい
1位ともきともきだいき
2位こうきこうきともき
3位だいきだいきこうき
人工知能学会｜安田洋祐

ペアで“ブロック”することができる
- 実はお互いの好みが反映されていなかった
? 男性陣の好み ? 女性陣の好み
? 【ともき－るい】はお互いの状況を改善できる
? もとの状態は「不安定」なマッチングだった…
2018年6月 14
こうきだいきともき
1位るいるいあい
2位ひとみあいるい
3位あいひとみひとみ
るいひとみあい
1位ともきともきだいき
2位こうきこうきともき
3位だいきだいきこうき
?
相
思
相
愛
?

安定マッチングの求め方
- （男性側から提案する）GSアルゴリズム
1. すべての参加者が好み（ランキング）を提出
2. 次の作業をマッチメイカーが機械的に行う
1. 男性が第一希望の女性に一斉にプロポーズ（告白）
2. 女性はその中で、自分の好みに一番近い人を選んで
「キープ」、残りの男性をリジェクト（拒否）
3. 男性はリジェクトされるたびにその次の好みの女性にプ
ロポーズ
4. 女性は現状より好みの男性が来るたびにキープ相手を
乗り換えて、残りをリジェクト
3. ストップした段階でマッチング結果が確定！

2018年6月 16
Roth(2002)の表 The economist as engineer: Game theory, experimentation,
and computation as tools for design economics. Econometrica, 70(4), 1341-1378.

GSアルゴリズムの性質
- インセンティブの問題も少ない
? インセンティブ（情報取得）の問題
– 提案側は誰一人として嘘をついても得できない
– 受入側は場合によっては嘘が得になるが…
? 結果が安定マッチングになるようなどんなメカニズムも
嘘をつくインセンティブを完全に無くすことはできない
? メカニズムの拡張
– アンマッチ（受入拒否）を許しても結果は安定に
– 同順位がある場合には予めタイブレークが必要
– 1対多のマッチング問題にも簡単に拡張できる

GSアルゴリズムの注意点
- どちらがプロポーズするかはかなり重要
? 安定マッチングは一般には複数存在する
– 今回の例では（たまたま）安定マッチングは一つ
? 2通りのGSメカニズムが異なる結果を導く場合
– 男性側提案 ? 男性陣にとって最適な安定マッチング
– 女性側提案 ? 女性陣にとって最適な安定マッチング
– 安定マッチングが一つの場合はどちらもこれを導く
? 男性（女性）最適な安定マッチングとは？
– 個々の男性（女性）が、安定マッチングで決まるパート
ナーの中からベストの女性（男性）とマッチする

GSアルゴリズムの実践例
- ぜひいろんな場所で活用してみよう！
? すでに実施されている採用例
– 研修医マッチング（日本、米国、英国）
– 法曹の実務研修（カナダ）
– 公立学校選択制（ニューヨーク市、ボストン市）
– 早稲田の内部進学（高校→大学）
– 東大の学部?学科決定（「進振り」制度）
? これから使えそうな応用例
– ゼミ?研究室?学科配属
– 新入社員と希望配属部署のマッチ

理論の拡張と更なる実践
現実への実践と理論の発展が車の両輪

選好の一般化
? 集合に対する選好
– 生徒（One側）が個々の学校（Many側）ではなく、
学校の集合に対して選好を持つ場合
– 代替的な選好を持つかどうかが鍵
? 外部性
– 学校の利得が、自分の生徒たちだけでなく他の
学校のマッチング結果にも左右される
– 生徒の利得が、自分と同じ学校にいる他の生徒
たちから影響を受ける

S’
s
S”
S’でも選ばれない
S”から選ばれない
“代替的”（Substitutable）な選好

S’
s
S”
S’から選ばれる
S”で選ばれない
s’
この２人に補完性
（Complementarity）
がある！
代替性が満たされないと…

配分制約
? 各学校に対する下限制約
– 定員（上限制約）と違って扱いが難しい
? アファーマティブ?アクション
– ある属性の生徒の数や割合に制限
? 各地域ごとの上限／下限制約
– 日本でも地方の研修医不足への対策が

事前の効率性
? 「A > B > C」という共通の選好順位を持つ
? 各学校に行きたい好みの強さが異なる
学校A 学校B 学校C
生徒1 4 1 0
生徒2 4 1 0
生徒3 3 2 0

GSアルゴリズムの結果
? 全員が同じランキングを提出 – 割り当てはランダムに
? ランダムな配分における生徒の期待効用
– 生徒1，2： 4×1/3 + 1×1/3 = 5/3
– 生徒3： 3×1/3 + 2×1/3 = 5/3
生徒1 1/3 1/3 1/3
生徒2 1/3 1/3 1/3
生徒3 1/3 1/3 1/3

Bostonをプレイした場合の結果
? Bostonメカニズムでの生徒の期待効用
– 生徒1，2： 4×1/2 + 0×1/2 = 2
– 生徒3： 2×1 = 2
生徒1 1/2 0 1/2
生徒2 1/2 0 1/2
生徒3 0 1 0

その他の拡張
? ペア数
– 安定マッチングは成立ペア数を減らす危険性
? 広い意味でのインセンティブ問題
– 選好形成のためのサーチコスト：就活
– 優先順位形成のための投資：保活
– ハード／ソフトな制約：ナース配属

安定性 vs. ペア数
? 2人の医者と2人の患者（P2: 貧しい患者）
? 唯一の安定マッチング: D1-P1 (D2, P2 single)
? パレート効率的な代替配分: D1-P2, D2-P1
=> マッチング不成立だとP2は命を落とすかもしれない…
Agent D1 D2 P1 P2
1st
P1 P1 D1 D1
2nd
P2 - D2 D2
29

参考文献（マーケットデザイン）

狠狠撸

マッチング?マーケットデザイン

Recommended

More Related Content

Similar to マッチング?マーケットデザイン (20)

More from Yosuke YASUDA (20)

マッチング?マーケットデザイン