安定結婚問題（ Gale-Shapley アルゴリズム）
クリスマスだし、有名なマッチングアルゴリズムぐらい書いておこうと思って書いた。
安定結婚問題
安定結婚問題（あんていけっこんもんだい、英: stable marriage problem）とはデイヴィッド・ゲールと ロイド・シャプレイによって1962年に提示された問題である。 安定結婚問題は {\displaystyle n} n人の男性と {\displaystyle k} k人の女性、および、各個人の選好順序からなる。選好順序とは各個人の好みに基づき異性全員と自分自身を全順序で並べたリストである。ここで、「自分自身」とは誰とも結婚せずに独身のままでいることを意味し、「参加者全員が独身であるよりも望ましい相手と結婚している」マッチングは個人合理性（英: individuality rationality）を満たすと定義される。安定結婚問題の解は安定なマッチングである。安定結婚問題に対し、互いに現在組んでいる相手よりも好きであるペア（以下ブロッキングペアとする）が存在せず、全員が個人合理性を満たすマッチングを安定マッチング（英: stable matching）という。
シミュレーション
python3, numpy でやってみた。 無駄とバグはあるかもしれません。
n 人どうしのマッチングを考慮しており、各行ごとに 0 〜 n-1 をシャッフルした n 次正方行列を ndarray で生成し、ペアとなった結果を表示します。
n次正方行列による優先順位行列を用いて安定結婚問題を解くシミュレーション
結果
4人同士のマッチング
$ python3 gale_shapley.py 4 [[2 1 0 3] [0 2 3 1] [1 2 3 0] [2 0 3 1]] [[1 2 0 3] [1 3 0 2] [0 2 3 1] [0 2 1 3]] Engaged (0, 2) Engaged (1, 0) Engaged (2, 1) Already engaged (0, 2) Already engaged (1, 0) Engaged (3, 3) [[0 2] [1 0] [2 1] [3 3]]
5人同士のマッチング
$ python3 gale_shapley.py 5 [[3 4 2 0 1] [1 0 4 3 2] [0 4 3 1 2] [1 4 2 0 3] [0 4 2 1 3]] [[3 2 4 1 0] [3 1 2 4 0] [2 1 4 0 3] [2 1 0 4 3] [0 1 3 4 2]] Engaged (0, 3) Engaged (1, 1) Engaged (2, 0) Already engaged (1, 1) Discard (1, 1) Engaged (3, 1) Already engaged (2, 0) Engaged (4, 4) Already engaged (3, 1) Already engaged (2, 0) Already engaged (4, 4) Discard (4, 4) Engaged (1, 4) Already engaged (2, 0) Already engaged (1, 4) Engaged (4, 2) [[0 3] [1 4] [2 0] [3 1] [4 2]]
