割当問題 - 九州大学

=⇒ 最適選好マッチング
例えば... 参加者の多数決で意思を決定する状況
その中間
=⇒ 安定マッチング
例えば... 全ての個人が納得をすればよい状況
個人の利益を追求
=⇒ 最大マッチング
例えば... 強力な意思決定者が存在する状況
全体の利益を追求
割り当ての質とモデル
マス・フォア・インダストリ研究所
九州大学
神山 直之
割当問題の数理モデル
+ 計算量理論，グラフ理論
可能性のある割り当て
の部分集合
各参加者が高々一つの
割り当てに含まれる
点の間を結ぶ線は可能
性のある割り当て
定義 (マッチング)
左右の点の集合は各集
団を表わしている
定義 (二部グラフ)
二部グラフとマッチング
効率的に解くことができる割当モデルを紹介
発表内容
理論的にも興味深い
2
(マトロイド等の離散構造との関連)
現実問題と数理モデルが非常に近い
1
本日その中でも割当問題を紹介
例えば，施設配置やスケジューリング，データマイニングなど...
最適化は様々な場面で現れる
min{f (x) | x ∈ F}
私の研究分野：離散最適化
私の問題意識と研究分野
× 個々の選好は考慮出来ない
○ サイズが最大
√
○ 効率よく求めることができる (O(m n) 時間)
出力：サイズが最大のマッチング
入力：二部グラフ
定義 (最大マッチング問題)
最大マッチング
=⇒ 解の質の良さ + 計算時間
どのような割り当てが望ましいのか？
疑問
厚生労働省「新たな医師臨床研修制度」HP 参照
病院と医学生
オークション
仕事のスケジューリング
研究室と学生
例えば...
二つのグループ間の割当を決める問題
定義 (割当問題)
割当問題
1
2
1
2
2
1
1
2
お互い現在の相手より好ましい組が存在
定義 (安定ではないマッチング)
1
2
1
2
2
1
1
2
出力：安定なマッチング
1
2
1
2
2
1
1
2
入力：二部グラフ + 各点の相手に対する選好順序
定義 (安定マッチング問題)
安定マッチング
一度加えた辺を賢く交換する必要がありそう．
．
．
最大？ =⇒ NO!! (先ほどの例を思い出す)
貪欲に加えることのできる辺を加えていく
基本的なアイデア
アルゴリズム
そもそも安定なマッチングが存在するのか？⇒
Yes!!
○ 個々の選好は考慮出来ている
× サイズが小さい
○ 効率よく求めることができる (O(m) 時間)
任意の問題例に対して少なくとも一つ安定マッチング
が存在し効率的に求めることができる
定理 (Gale & Shapley)
存在性
マッチングに入っていない点から始まりマッチングに
入っていない点で終わる向きに沿った道
増加路
有限界でアルゴリズムは停止する
2
1
1
2
1
2
2
1
1
2
1
2
1
2
2
1
1
2
1
2
1
2
2
1
1
2
M は断られていない最も好ましい女性 W にプロポーズ
する
W は相手がいないもしくは現在の相手より好ましけれ
ば乗り換える
相手がいないかつ全ての女性に断られていない男性 M がい
る限り以下を繰り返す
アルゴリズム
最大マッチングのサイズは高々n
√
計算時間 O(mn) ⇒ O(m n) [Hopcroft & Karp]
増加路を見つけるのに O(m) 時間
計算時間
あるマッチングが最大である必要十分条件は交換可能
グラフにおいて増加路が存在しないことである
定理
増加路がある限り辺を増やす
マッチングに加えられていない辺を右向き
増加路に沿って辺を入れ替えるとサイズが増える
アルゴリズム
マッチングに加えられている辺を左向き
交換可能グラフ
アルゴリズム
構成的に証明可能？⇒
Yes!!
△ 個々の選好はそこそこ考慮出来ている
△ サイズがそこそこ大きい
○ 効率よく求めることができる
注：安定ではない最適選好マッチングが存在する
あるマッチング M が最適選好マッチングである十分条
件は M が安定マッチングであることである
NO...
そもそも安定なマッチングが存在するのか？⇒
マトロイドを用いた拡張が可能 (例えば，多対多)
上記のアルゴリズムは実はある関数の不動点を求めて
いる
どの安定マッチングもサイズは同じ
定理
存在性
補足
各プロポーズの判定は O(1) 時間 ⇒ O(m) 時間
合計で高々m 回のプロポーズ
それぞれの男性は各女性に高々一回しかプロポーズし
ない
計算時間
アルゴリズム
2
1
3
1
2
1
2
2
1
3
1
2
1
2
可能ならば最も大きい最適選好マッチングを求めたい
1
2
1
2
3
1
2
各最適選好マッチングによってサイズが変わる
サイズが最大の最適選好マッチングを多項式時間で見
つけることが可能
定理 (Huang & Kavitha)
最大性
支配するマッチングが存在
定義 (最適選好ではないマッチング)
1
2
1
2
3
1
2
出力：最適選好なマッチング
入力：二部グラフ + 各点の相手に対する選好順序
定義 (最適選好マッチング問題)
最適選好マッチング
2
1
3
1
2
1
2
ご清聴ありがとうございました
良いソフトウェアの開発
普及活動
理論的に高速なだけではなく非常に実用的
アルゴリズムが整備されている
実際に使用されている例も
モデルが現実の問題に近い
最大マッチング，安定マッチング，最適選好マッチング
目的に応じた様々な割当モデルを紹介
まとめと課題
1
2
1
2
3
1
2
好ましい点が多いほうのマッチングが他方のマッチン
グを支配する
各点においてどちらのマッチングが好ましいかを判定
二つのマッチングを考える
定義 (支配関係)
最適選好性