この記事はデータ構造とアルゴリズム Advent Calendar 20日目の記事です．
メカニズムデザインとは
アルゴリズムといえばコンピュータ内の処理のイメージがあるかとは思います．しかしながら，コンピュータ内の処理に限らず，実世界の中で活用されるアルゴリズムも数多く存在します．
Wikipediaにもあるように，メカニズムデザインとは，それぞれの参加者（人，国，企業など）がインセンティブを損なわないように資源配分などを行えるようなルール（＝アルゴリズム）を設計するものです．
ゲーム理論の一分野として捉えることもでき，もともとは経済学の一分野でした．
しかしながら，近年では計算機科学・AIの文脈でも用いられます．（例：AAAI-19 でのチュートリアル）
安定結婚問題
アルゴリズムとしては Gale-Shapley algorithm が有名で，この研究により Shapley は 2012 年にノーベル経済学賞を受賞しています．
最近では、富士通の開発した保育所割り当てのAIに応用されています （クラウド Watch の記事）。
問題
- 入力
- 男性の集合 $M$
- 女性の集合 $W$
- 各男性 $m \in M $ の $W$ に対する選好順序リスト $\succ_M = (\succ_m)_{m \in M}$
- 各女性 $m \in W $ の $M$ に対する選好順序リスト $\succ_w = (\succ_w)_{w\in W}$
- 出力
- $M \cup W$ を頂点とするマッチング $X$
- ただし、$ \forall (v_1, v_2) \in X, v_1 \in M, v_2 \in W$ を満たす
この入力・出力を決定するアルゴリズムをうまく設計する問題を考えます．
うまく設計するとは？
満たすべき代表的な性質として，安定性があります．
安定性
出力したマッチングに不満があるペアが存在した場合，出力されたマッチングに従ってペアを組まない可能性があります．例えば，以下のような場合です．
| $\succ_M$ | 1位 | 2位 |
|---|---|---|
| $\succ_{m_1}$ | $w_1$ | $w_2$ |
| $\succ_{m_2}$ | $w_2$ | $w_1$ |
| $\succ_W$ | 1位 | 2位 |
|---|---|---|
| $\succ_{w_1}$ | $m_1$ | $m_2$ |
| $\succ_{w_2}$ | $m_2$ | $m_1$ |
このとき，マッチング： $\{(m_1, w_2), (m_2, w_1)\}$ は不安定です．
$m_1$ は $w_2$ よりも $w_1$ の方が好きですし，$w_1$ は $m_2$ よりも $m_1$ の方が好きです．
したがって，$(m_1, w_1)$ のペアの方が $m_1,w_1$ 双方にとって良い結果となるために，マッチングの結果を無視して駆け落ちをする可能性があります．
これは極端な例ですが，このようなペアを出力しないことがアルゴリズムには求められます．
Gale-Shapley algorithm
動作
- 各男性 $m$ は選好順序が最上位の女性 $w$ に婚約を申し込む
- 各女性 $w$ は婚約を申し込まれた男性の中で
- 自身の選好順序 $\succ_w$ でより上位の男性の婚約を受理
- それ以外の男性の婚約を拒否する
- 婚約が受理されていない男性 $m$ は，婚約を拒否されていない女性の中で，自身の選好順序 $\succ_m$ で最上位女性に婚約を申し込む
- 各女性 $w$ は婚約を申し込まれた男性と（いる場合は）すでに婚約した男性をあわせた中で
- 自身の選好順序 $\succ_w$ でより上位の男性の婚約を受理
- それ以外の男性の婚約を拒否する
- 以上 3.4. の動作を新たに婚約を申し込む男性が現れなくなるまで繰り返す
- 婚約をしている男女のペアをマッチングとして出力する
なぜ安定性を満たすのか
ここでは数式を用いずに，簡単に説明します．
男性側
男性側は好きな女性から順に婚約を申し込んでいます．
したがって，「ある男性 $m$ を拒否した女性 $w$ $\Rightarrow$ $w$ は $m$ よりも好む男性 $m'$ とペアになっている」が成立します．
そのため，男性 $m$ は女性 $w$ は駆け落ちする誘引を持ちません．
女性側
男性側は好きな女性から順に婚約を申し込んでいます．
したがって，「ある男性 $m$ が女性 $w$ に婚約を申し込む前にアルゴリズムが停止した $\Rightarrow$ $m$ は $w$ よりも好む女性 $w'$ とペアになっている」が成立します．
そのため，男性 $m$ は女性 $w$ 駆け落ちする誘引を持ちません．
アルゴリズムの応用
安定結婚問題は男性と女性の集合のマッチングを考えています．
この男性と女性を他のものに置き換えれば，様々な応用ができます．
例えば，男性を保育所，女性を入所希望者とすれば保育所のマッチング，男性を部署，女性を会社員とすれば部署配属のマッチングの問題を解くことが出来ます．
その他のアルゴリズム
ここでは安定結婚問題を取り上げましたが，他にもさまざまな問題やアルゴリズムが存在します．
- クリスマスのプレゼント交換はどのように行うと全員がより満足する結果となるか
- クリスマスケーキをどのように切り分けるか
- 「クリスマス」という検索ワードで表示される広告の優先順序の決定
終わりに
今回は言葉での説明が多くなりましたが，実際は数式で厳密に定義・証明されていますので，興味のある方はコメントいただければと思います．
アルゴリズムの応用範囲は広く，コンピュータの処理にとどまらず様々な場所で応用されます．
特に，メカニズムデザインの分野は制度設計などに応用されるため，実世界に強く影響するアルゴリズムと言えます．
また，これらのアルゴリズムは個人のインセンティブを損なわないように，より良い結果をもたらすように設計されているため，考え方が組織運営・チームビルディングにも応用することが可能です．
ぜひ，皆さんのアルゴリズム力を様々な分野で活用してください！