マッチング 1 対 1マッチング - 結 婚 ゲーム, 仕 事 の 割 り 当 て 多 対 1マッチング - インターンの 病 院 への 割 り 当 て, 内 部 進 学 者 の 学 部 への 配 属 学 科 所 属, 研 究 室 所 属
結 婚 ゲーム 例 男 性,, 女 性,, : > >, : > >, : > > : > >, : > >, : > > どのようなペアの 集 まり(マッチング)が 安 定 か? µ = : > (, ) のペアでは, ともによくなる : > 安 定 ではない υ =,, ベストな 相 手 とペア どのペアもよくならない 安 定 である
結 婚 ゲーム( 定 式 化 ) M = {m 1,, m p } 男 性 の 集 合 N = {w 1,, w q } 女 性 の 集 合 仮 定 : p = q (p q の 場 合 は 後 述 ) 各 m i は W の 上 に 選 好 順 序 > mi をもつ 各 w k は M の 上 に 選 好 順 序 > wk をもつ 仮 定 : 無 差 別 はない 結 婚 ゲーム : (M, W, {> mi } mi M, {> wk } wk W )
マッチング 結 婚 ゲーム : (M, W, {> mi } mi M, {> wk } wk W ) マッチング µ : W M 全 単 射 w µ(w) m µ -1 (m) µ = w 1 w p µ(w 1 ) µ(w p )
安 定 なマッチング 2つのマッチング µ = w 1 w k w p µ(w 1 ) µ(w k ) µ(w p ) = m i υ = w 1 w k υ -1 (m i ) w p υ(w 1 ) υ(w k ) m i υ(w p ) µ が υ を (w k, m i ) を 通 して 支 配 する ( (w k, m i ) は υ をブロックする) µ(w k ) = m i, m i > wk υ(w k ), w k > mi υ -1 (m i ) µ が υ を 支 配 する あるペア(w k, m i ) が 存 在 して µ が υ を (w k, m i ) を 通 して 支 配 する
コア 結 婚 ゲームのコア = {µ µ を 支 配 するマッチングが 存 在 しない} 一 般 のコア : 任 意 の 提 携 S M W に 関 して µ を 支 配 するマッチングが 存 在 しない 結 婚 ゲームのコア : 任 意 のペア (w k, m i ), w k W, m i M に 関 して µ を 支 配 するマッチングが 存 在 しない 結 婚 ゲームにおいて : 任 意 の 提 携 S M W に 関 して µ を 支 配 するマッチングが 存 在 しない,???
コア 結 婚 ゲームのコア : 任 意 のペア (w k, m i ), w k W, m i M に 関 して µ を 支 配 するマッチングが 存 在 しない 結 婚 ゲームにおいて : 任 意 の 提 携 S M W に 関 して µ を 支 配 するマッチングが 存 在 しない = : 明 らか (S として (w k, m i ) をとればよい) : µ, µ とする µ υ, S υ において,すべての i S が µ より 好 ましい 相 手 とペア w k S W, m i S M をとると, υ は µ を (w k, m i )に 関 して 支 µ に 矛 盾
コアに 属 するマッチングを 求 めるアルゴリズム (ゲール シャープレイのアルゴリズム) 男 性 側 女 性 側 例 男 性,, 女 性,, : > >, : > >, : > > : > >, : > >, : > >
コアに 属 するマッチングを 求 めるアルゴリズム (ゲール シャープレイのアルゴリズム) 例 男 性,, 女 性,, : > >, : > >, : > > : > >, : > >, : > > 男 性 側 女 性 側 ゲール シャープレイのアルゴリズム 安 定 なマッチング, ベスト : は > は > ブロックするペアなし
ゲール シャープレイのアルゴリズム 第 1ステップ : すべての 男 性 は 最 も 好 ましい 女 性 にプロポーズ 各 女 性 は 自 分 にプロポーズした 男 性 のうち 最 も 好 ましい 人 をリストに 残 し あとは 拒 否 拒 否 された 男 性 がいなければ 終 了 : > >, : > >, : > > : > >, : > >, : > > 第 2ステップ : 拒 否 された 男 性 は 拒 否 された 女 性 の 次 に 好 ましい 女 性 にプロポーズ 各 女 性 は 自 分 にプロポーズした 男 性 をリストに 入 れ,その 中 で 最 も 好 ましい 人 を 選 びあとは 拒 否 拒 否 された 男 性 がいなければ 終 了 第 3ステップ, 第 4ステップ,
ゲール シャープレイのアルゴリズム 必 ずマッチングに 到 達 する もし,すべての 女 性 に 拒 否 し 続 けられた 男 性 がいたとすると, 男 女 同 数 ゆえ,ペアを 組 めなかった 女 性 が 存 在 する 彼 女 にプロポーズした 男 性 存 在 しない 矛 盾 アルゴリズムは 有 限 回 のステップで 終 了 する あるステップで 終 了 しなければ, 拒 否 された 男 性 が 存 在 次 のステップで 拒 否 された 次 に 好 ましい 女 性 にプロポーズ 女 性 の 数 は 有 限, すべての 女 性 に 拒 否 されることはない, 有 限 回 のステップで 終 了
ゲール シャープレイのアルゴリズム 到 達 したマッチングは 安 定 である(コアに 属 する) 到 達 したマッチングを µ = w 1 w µ -1 (m) w p とし µ(w 1 ) µ(w) m µ(w p ) (w, m) が µ をブロックするとする m > w µ(w), w > m µ -1 (m) m > w µ(w) ゆえ,m は w にプロポーズしていない (*) m は µ -1 (m) とペアを 作 っている µ -1 (m) より 好 ましい 女 性 からはすべて 拒 否 されている w > m µ -1 (m) ゆえ w にこれまでにプロポーズしていたはずである (*)に 矛 盾
男 性 最 適 なマッチングと 女 性 最 適 なマッチング 男 性,, 女 性,, : > >, : > >, : > > : > >, : > >, : > > 男 性 側 女 性 側 女 性 側 男 性 側
男 性 最 適 なマッチングと 女 性 最 適 なマッチング 男 性,, 女 性,, : > >, : > >, : > > : > >, : > >, : > > 男 性 側 女 性 側 µ = 女 性 側 男 性 側 υ = 男 性 : : =, : >, : > µ のほうが 良 い 女 性 : : >, : =, : > υ のほうが 良 い
男 性 最 適 なマッチングと 女 性 最 適 なマッチング 安 定 なマッチング µ = w 1 µ -1 (m) w p が 男 性 最 適 ( 最 悪 ) µ(w 1 ) m µ(w p ) 任 意 の 安 定 なマッチング υ = w 1 υ -1 (m) w p に 対 して υ(w 1 ) m υ(w p ) m M µ -1 (m) υ -1 (m) µ -1 (m) > m υ -1 (m) (µ -1 (m) < m υ -1 (m) ) 安 定 なマッチング µ = w 1 w w p が 女 性 最 適 ( 最 悪 ) µ(w 1 ) µ(w) µ(w p ) 任 意 の 安 定 なマッチング υ = w 1 w w p に 対 して υ(w 1 ) υ(w) υ(w p ) w W µ(w) υ(w) µ(w) > w υ(w) (µ(w) < w υ(w) )
男 性 最 適 なマッチングと 女 性 最 適 なマッチング 男 性 側 がプロポーズ ゲール シャープレイのアルゴリズム 男 性 最 適 ( 女 性 最 悪 )なマッチング 女 性 側 がプロポーズ ゲール シャープレイのアルゴリズム 女 性 最 適 ( 男 性 最 悪 )なマッチング
男 性 最 適 なマッチングと 女 性 最 適 なマッチング 男 性 側 がプロポーズ 男 性 最 適 なマッチング ( 証 明 ) ゲール シャープレイのアルゴリズムにより 到 達 したマッチング µ* µ* において,すべての 男 性 に 対 し,このアルゴリズムで 拒 否 された 女 性 とのペア を 含 む 安 定 なマッチングは 存 在 しない を 証 明 する µ* において,すべての 男 性 が 安 定 マッチングの 中 で 最 も 好 ましい 女 性 とペア 帰 納 法 : 第 1ステップ それ 以 前 に 拒 否 された 男 性 なし 第 kステップにおいて,すべての 男 性 にとって,それ 以 前 のステップで 拒 否 された 女 性 とのペアを 含 む 安 定 なマッチングは 存 在 しないと 仮 定 第 k+1ステップ: 第 kステップで,w が m を 拒 否 したとし, (w, m) はいかなる 安 定 なマッチングにも 含 まれないことを 示 す
男 性 最 適 なマッチングと 女 性 最 適 なマッチング 帰 納 法 : 第 1ステップ それ 以 前 に 拒 否 された 男 性 なし 第 kステップにおいて,すべての 男 性 にとって,それ 以 前 のステップで 拒 否 された 女 性 とのペアを 含 む 安 定 なマッチングは 存 在 しないと 仮 定 第 k+1ステップ: 第 kステップで,w が m を 拒 否 したとし, (w, m) はいかなる 安 定 なマッチングにも 含 まれないことを 示 す w がキープしていた 男 性 を m とすると,m > w m m は w にプロポーズ w より 好 ましい 女 性 からは 拒 否 帰 納 法 の 仮 定 w より 好 ましい 女 性 とのペアを 含 む 安 定 なマッチングなし (w, m) を 含 む 安 定 なマッチング µ が 存 在 すると 仮 定 矛 盾 を 示 す
男 性 最 適 なマッチングと 女 性 最 適 なマッチング 第 k+1ステップ: 第 kステップで,w が m を 拒 否 したとし, (w, m) はいかなる 安 定 なマッチングにも 含 まれないことを 示 す w がキープしていた 男 性 を m とすると,m > w m (*) m は w にプロポーズ w より 好 ましい 女 性 からは 拒 否 帰 納 法 の 仮 定 w より 好 ましい 女 性 とのペアを 含 む 安 定 なマッチングなし(**) (w, m) を 含 む 安 定 なマッチング µ が 存 在 すると 仮 定 矛 盾 を 示 す µ =.. w µ -1 (m ).... m m.. µ 安 定 ゆえ,(**) から w > m µ -1 (m ) (*)と 合 わせ (w, m ) は µ をブロック µ が 安 定 であることに 矛 盾 ( 証 明 終 )
男 性 最 適 なマッチングと 女 性 最 適 なマッチング 男 性 最 適 なマッチングが 女 性 最 悪 であることの 証 明 到 達 した 男 性 最 適 な 安 定 なマッチングを µ とし, 任 意 の 安 定 なマッチング µ をとる µ =.. w µ -1 (m ).... m m.. µ =.. w µ -1 (m ).... m m.. 任 意 の w に 対 して, m(=µ(w)) m (=µ (w)) m > w m を 示 せばよい m > w m と 仮 定 µが 男 性 最 適 w > m µ -1 (m ) m > w m と 合 わせ,(w, m) が µ をブロック µ が 安 定 であることに 矛 盾 ( 証 明 終 )
男 性 と 女 性 の 人 数 が 異 なる 場 合 男 性,, 女 性, 独 身 でいる 状 態 を s で 表 す : > > s, : > > s, : > s > : > > > s, : > s > > 男 性 女 性 男 性 : s より 好 ましくない 女 性 にはプロポーズしない 女 性 : s より 好 ましくない 男 性 はプロポーズされてもリストに 載 せず 拒 否 s s s ゲール シャープレイのアルゴリズム 若 干 修 正 して 適 用 可 能
戦 略 的 な 行 動 をとる 場 合 (85-86ページ) 男 性,, 女 性,,, d : d > >,, d, s : > d >,, s : >,. d, s : >,, s : >,, s : s >,, d : > >, s ゲール シャープレイ アルゴリズム d : > s >, d d d は 選 好 を 偽 ることにより, よりよい とペアを 作 れる
多 対 一 のマッチング 内 部 進 学 者 の 学 部 への 配 属 S : 内 部 進 学 者 の 集 合, s S の D に 関 する 選 好 > s D : 学 部 の 集 合, d D の S に 関 する 選 好 > d 受 け 入 れ 可 能 人 数 q d ゲール シャープレイのアルゴリズム 1 学 生 は 自 分 の 好 ましい 学 部 から 順 にプロポーズする 2 学 部 は q d までリストにキープする 3 学 生 数 が q d を 超 えたら, > d に 基 づいて 拒 否 する 学 生 最 適 なマッチングに 到 達 する 実 際 の 適 用 例 : アメリカにおけるインターンの 病 院 への 配 属 (88ページから91ページ) 日 本 のある 大 学 における 付 属 高 校 からの 進 学 者 の 学 部 への 振 り 分 け 東 工 大 の 学 科 所 属, 研 究 室 所 属???
2つのサイドに 分 けられない 場 合 (ルームメイト 問 題 ) ルームメイト 問 題 :,,, D の4 人 の 寮 生 を2 人 ずつ2 部 屋 に 分 ける 各 寮 生 の 好 み: : > > D, : > > D, : > > D, D: > > コアは 空 : (D, ) (, ) ブロック (D, ) (, ) ブロック (D, ) (, ) ブロック
2つのサイドに 分 けられない 場 合 ( 非 分 割 財 の 交 換 ) 非 分 割 財 の 交 換 :,,, D が 非 分 割 財 ( 家 など)を 持 っており, 各 人 の 好 みは : > > D >, : > > D >, : > > D >, D: > > > D である シャープレイ スカーフのアルゴリズム(トップ トレーディング サイクル) 第 1ステップ: 各 プレイヤーは 自 分 の 最 も 好 む 財 を 指 定 サイクルができればその 中 のプレイヤーは 財 を 交 換 して 退 出 第 2ステップ: 残 ったプレイヤーはその 中 で 自 分 の 最 も 好 む 財 を 指 定 サイクルができればその 中 のプレイヤーは 財 を 交 換 して 退 出 以 下 同 様
トップ トレーディング サイクル : > > D >, : > > D >, : > > D >, D: > > > D シャープレイ スカーフのアルゴリズム(トップ トレーディングサイクル) 第 1ステップ: 各 プレイヤーは 自 分 の 最 も 好 む 財 を 指 定 サイクルができればその 中 のプレイヤーは 財 を 交 換 して 退 出 第 2ステップ: 残 ったプレイヤーはその 中 で 自 分 の 最 も 好 む 財 を 指 定 サイクルができればその 中 のプレイヤーは 財 を 交 換 して 退 出 以 下 同 様 D トップトレーディングサイクル 有 限 回 で 終 了 し コアを 導 く
課 題 1. 以 下 の 選 好 を 持 つマッチングゲームにおいて 男 性 側 からプロポーズ する 場 合 と 女 性 側 からプロポーズする 場 合 のそれぞれにおいてゲール シャープレイのアルゴリズムによって 得 られるマッチングを 求 め,コアに 属 することを 確 かめよ,,は 男 性 であり,,, は 女 性 である sは 独 身 の 状 態 を 表 す () : > > > s, : > > > s, : > > > s : > > > s, : > > > s, : > > >s () : > > s >, : > > s >, : > > s > : > > > s, : > > > s, : > > >s 2. 研 究 室 所 属 において, 現 行 の 方 法 を, 各 学 生 が 研 究 室 に 対 する 選 好 を 提 出 し, 各 教 員 が 学 生 に 対 する 選 好 ( 例 えば, 成 績 など)を 提 示 して, 学 生 側 からプロポーズし, 教 員 側 は 各 自 の 選 好 に 基 づいて,ゲール シャープレイ のアルゴリズムに 従 って, 定 員 ( 例 えば3 名 とか4 名 )まで 学 生 をとる という 方 法 に 変 えるという 案 について, 君 たちならば 賛 成 するか,それとも 反 対 する か, 理 由 を 添 えて 述 べよ