安定マッチング問題
男性のグループと女性のグループが与えられ、男性は女性の選好順序を、女性は男性の選好順序を持っている。男女でペアを作ったときブロッキングペアが存在しないマッチングを安定マッチングという。
ブロッキングペア(m,w)とは、ペアとなっていない男女で「wはmの現在のペアよりも好ましい」「mはwの現在のペア よりも好ましい」状態のペアをいう。
安定マッチング問題は、厳密には最適化問題ではないが、マッチングに関し重要な問題なので典型問題に含めている。ゲイル・シャプレーの解法により効率的に解くことができる。
実行方法
usage
Signature: stable_matching(prefm, preff)
Docstring:
安定マッチング問題
入力
prefm, preff: 選好
出力
マッチング
python
from ortoolpy import stable_matching
print(stable_matching([[2,0,1],[2,1,0],[0,2,1]], [[0,1,2],[2,0,1],[2,1,0]]))
結果
{2: 2, 0: 0, 1: 1}
python
# pandas.DataFrame
from ortoolpy.optimization import StableMatching
StableMatching('data/stable.csv')
| male | female | pref_male | pref_female | |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 |
| 4 | 1 | 1 | 1 | 2 |
| 8 | 2 | 2 | 1 | 0 |