DAアルゴリズムを実装してみた！

## 概要
経済学部の授業で常に安定性を満たすDAアルゴリズムについて学習しました。DAアルゴリズムは常に安定性を満たすアルゴリズムでマーケットデザインにおいて重要な役割を担っています。授業ではコードについて教わらなかったため、経済学とPythonの勉強として、DAマッチングを実現するシステムをpythonを用いて自力で作成してみました。

## DAアルゴリズム
DAアルゴリズムは、二部マッチングにおいて安定マッチングを実現するアルゴリズムです。安定マッチングは簡単にいうと、誰も抜け駆けしないようなマッチングのことです。誰かが勝手に抜けない（個人合理性を満たす）かつ、どのペアも抜け駆けしない状態のことです。

労働者が提案して、企業が受け入れる場合、労働者提案型DAアルゴリズムとなり、労働者にとっては最も望ましいマッチングになり、企業にとっては最も好ましくないマッチングになります。企業提案型DAアルゴリズムについても同様に考えることができます。

また各プレイヤーの選好によってマッチングを決めていくのですが、労働者提案型DAアルゴリズムでは、労働者にとって嘘の選好を申告して得をすることが理論上なくなります。これを耐戦略性を満たすといいます。一方でこの場合企業側は耐戦略性を満たさないため、嘘をつくと得をする可能性があります。

DAアルゴリズmの詳しい説明はこちらの記事がわかりやすかったです↓
https://miiitomi.github.io/p/matching/

## Pythonコード
**⚠️決して綺麗なコードとは言えません！**

ここではプレイヤー集合1（労働者）がプレイヤー集合2（企業）に提案するアルゴリズムを考えます。
プレイヤー集合の集合は辞書型で与えられるとします。
例えば、企業の選好が
```
{"c1":["w3","w2","w1"], "c2":["w1","w2","w3"]}
```
となるとき、企業c1はw3,w2,w1の順に好み、c2はw1,w2,w3の順で好むとします。
また
```
{"c1":["w3","w2","w1"], "c2":["w1"]}
```
となるとき、c2はw2,w3と組むなら誰とも組まない方がマシだと考えることとします。
以上をもとに、DAアルゴリズムを実装してみます。

```python
import copy

class DAalgorism:
    def __init__(self, preference_dict1, preference_dict2):
        self.set_values(preference_dict1, preference_dict2)


    def set_values(self, preference_dict1, preference_dict2):
        """
        初期値を設定する。プレイヤー集合1提案型DAアルゴリズムを考える。
        """
        self.player1 = preference_dict1 #提案可能なプレイヤー集合1の選好を示す辞書
        self.player2 = preference_dict2 #受入可能なプレイヤー集合2の選好を示す辞書

        self.player1_to_reffer = self.player1.copy() #参照用
        self.player1_count = {k:0 for k in list(self.player1.keys())} #提案回数
        self._proposals_dict = {k:[] for k in list(self.player2.keys())} #提案


    def apply_game(self, player_name, i=0):
        """
        player_nameがi番目の選好に応募する。
        i番目の選好が存在しない場合、何もしない。
        """
        if i < len(self.player1[player_name]): 
            preference = self.player1[player_name][i]
            self._proposals_dict[preference].append(player_name)


    def is_over_capacity(self, keep_list, q):
        return len(keep_list) > q


    def remove_least_preferred_player(self, preference_list2, keep_list2):
        """
        選好の低いプレイヤーを1人取り除く。
        """
        for player1 in preference_list2[::-1]:
            if  player1 in keep_list2:
                keep_list2.remove(player1)
                return keep_list2, player1 #取り除いた後の選好と、プレイヤーを返す。


    def choose_player(self, player_name, q):
       """
        プレイヤー2が選好をもとにプレイヤー1を選ぶ。
       """
       preference_list2 = self.player2[player_name]
       keep_list2 = self._proposals_dict[player_name]
       exile_list = []

       while True:
        if self.is_over_capacity(keep_list2, q):
            rlpp = self.remove_least_preferred_player(preference_list2, keep_list2)
            keep_list2 = rlpp[0]
            exile_list.append(rlpp[1])
        else:
            break

        self._proposals_dict[player_name] = keep_list2
        return exile_list


    def filter_players(self, keys_to_keep):
        """
        プレイヤー集合1の辞書から現時点でマッチングしていない人を厳選
        """

        referance_list = self.player1_to_reffer
        new_dict = {key: referance_list[key] for key in keys_to_keep if key in referance_list}
        return new_dict


    def do_step(self, q):

        # プレイヤー1が選考をもとにプレイヤー2に応募する。
        for player1 in list(self.player1.keys()):
            count = self.player1_count[player1]
            self.apply_game(player1,count)

        # プレイヤー2は選考をもとにプレイヤー1を厳選する。
        exiled_list = []
        for player2 in list(self.player2.keys()):
            exiled_players = self.choose_player(player2,q) 
            if exiled_players != None:
                for ep in exiled_players:
                    self.player1_count[ep] += 1
                exiled_list.extend(exiled_players)

        # 提案可能なプレイヤーを更新する。
        self.player1 = self.filter_players(exiled_list)

    def propose_combination(self,q=1):

        # 提案可能なプレイヤーがいなくなるまで繰り返す。
        while len(self.player1) > 0:
            self.do_step(q)

        return self._proposals_dict

    def exchange_players(self,q=1):
        """
        プレイヤー集合2提案型DAメカニズムに変更する。
        """
        self.player1 = self.player2.copy()
        self.player2 = self.player1_to_reffer.copy()

        self.player1_to_reffer = self.player1.copy()
        self.player1_count = {k:0 for k in list(self.player1.keys())}
        self._proposals_dict = {k:[] for k in list(self.player2.keys())}
        return self.propose_combination(q)
```
具体的な状況を当てはめて考えてみます。
労働者の選好が
```
{"w1":["c1","c2"], "w2":["c2"], "w3":["c2","c1"]}
```
のように表されるとします。w2はc1と組むなら誰ともマッチングしない方がいいと考えているようです。
一方で企業の選好が、
```
{"c1":["w3","w2","w1"], "c2":["w1","w2","w3"]}
```
のように表されるとします。

ここで労働者提案型DAアルゴリズムのときには企業は労働者を2名まで受け入れ、企業提案型DAアルゴリズムの時には労働者は学校を2校まで受入れるとします。

以上に基づき、労働者提案型DAメカニズムと企業提案型マッチングをそれぞれ行うとします。

```python
if __name__=="__main__":
    dict1 = {"w1":["c1","c2"], "w2":["c2"], "w3":["c2","c1"]}
    dict2 = {"c1":["w3","w2","w1"], "c2":["w1","w2","w3"]}
    da = DAalgorism(dict1,dict2)
    p1 = da.propose_combination(q=2)
    print("プレイヤー1提案型DAマッチング：")
    print(p1)

    # もし提案するプレイヤー集合を変更したいなら
    p2 = da.exchange_players(q=2)
    print("プレイヤー2提案型DAマッチング：")
    print(p2)
    
```
結果はこのようになりました。
```
プレイヤー1提案型DAマッチング
{'c1': ['w1'], 'c2': ['w2', 'w3']}
プレイヤー2提案型DAマッチング：
{'w1': ['c2'], 'w2': [], 'w3': ['c1']}
```
労働者提案型の時はc1とw1がマッチングし、c2とw2,w3がマッチングしました。
また企業提案型の時はw1とc2が、w3とc1がマッチングし、w2は誰ともマッチングしません。

こちらのコードはGithubにも上げておきました。
https://github.com/KANEI/DAalgorism/tree/main

## より実践的なことをしてみる
ChatGPTに「このpythonのコードをGASで書き換えて」というと簡単に書いてくれました。
そのコードを微調整して、Google Spreadsheetに選考を入力してくれると自動的に安定マッチングを行ってくれるシステムをGoogle Apps Scriptで作成しました。

### システムの概要

（今度は学校と生徒のマッチングを考えます。）

![スクリーンショット 2025-02-01 22.07.00.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3894554/1afcc870-84eb-b1f6-2985-e563be48ff8b.png)

studentのシートに先ほどの労働者の選好を入れます。
![スクリーンショット 2025-02-01 22.08.51.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3894554/26e277c7-7a23-2816-bf8b-7fe79b93756d.png)


collegeのシートに先ほどの企業の選考を入れます。
![スクリーンショット 2025-02-01 22.08.58.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3894554/a38d0997-1f7d-88fb-5998-ba257fb79d5d.png)

定員の数を2に設定して、生徒提案型DAのボタンを押すと次の結果を出力します。

![スクリーンショット 2025-02-01 22.25.46.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3894554/791d5cdb-70d6-e018-a713-f68c5b0e76bf.png)


対して、学校提案型DAのボタンを押すと次の結果を出力します。

![スクリーンショット 2025-02-01 22.13.11.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3894554/c74ecb74-8be0-3da1-c9e7-220d8d450b8d.png)

労働者提案型の時はc1とw1がマッチングし、c2とw2,w3がマッチングしました。
また企業提案型の時はw1とc2が、w3とc1がマッチングし、w2は誰ともマッチングしません。
これは上記のpythonの値と一致します！

### GASのコード
```JavaScript
class DAalgorism {
  constructor(preferenceDict1, preferenceDict2) {
    this.setValues(preferenceDict1, preferenceDict2);
  }

  setValues(preferenceDict1, preferenceDict2) {
    this.player1 = JSON.parse(JSON.stringify(preferenceDict1));
    this.player2 = JSON.parse(JSON.stringify(preferenceDict2));
    this.player1ToRefer = JSON.parse(JSON.stringify(this.player1));
    this.player1Count = {};
    for (const key of Object.keys(this.player1)) {
      this.player1Count[key] = 0;
    }
    this.proposalsDict = {};
    for (const key of Object.keys(this.player2)) {
      this.proposalsDict[key] = [];
    }
  }

  applyGame(playerName, i = 0) {
    if (!(playerName in this.player1) || !Array.isArray(this.player1[playerName])) return;
    if (i < this.player1[playerName].length) {
      const preference = this.player1[playerName][i];
      if (preference in this.proposalsDict) {
        this.proposalsDict[preference].push(playerName);
      }
    }
  }

  isOverCapacity(keepList, q) {
    return keepList.length > q;
  }

  removeLeastPreferredPlayer(preferenceList2, keepList2) {
    for (let i = preferenceList2.length - 1; i >= 0; i--) {
      const player = preferenceList2[i];
      if (keepList2.includes(player)) {
        const index = keepList2.indexOf(player);
        keepList2.splice(index, 1);
        return [keepList2, player];
      }
    }
    return [keepList2, null];
  }

  choosePlayer(playerName, q) {
    if (!(playerName in this.player2) || !(playerName in this.proposalsDict)) return [];
    
    const preferenceList2 = this.player2[playerName];
    let keepList2 = [...this.proposalsDict[playerName]];
    const exileList = [];

    while (this.isOverCapacity(keepList2, q)) {
      const [newList, exiled] = this.removeLeastPreferredPlayer(preferenceList2, keepList2);
      keepList2 = newList;
      if (exiled !== null) exileList.push(exiled);
    }

    this.proposalsDict[playerName] = keepList2;
    return exileList;
  }

  filterPlayers(keysToKeep) {
    const newDict = {};
    for (const key of keysToKeep) {
      if (this.player1ToRefer[key]) {
        newDict[key] = this.player1ToRefer[key];
      }
    }
    return newDict;
  }

  doStep(q) {
    for (const player of Object.keys(this.player1)) {
      if (player in this.player1Count) {
        const count = this.player1Count[player];
        this.applyGame(player, count);
      }
    }

    let exiledList = [];
    for (const player of Object.keys(this.player2)) {
      const exiledPlayers = this.choosePlayer(player, q);
      if (exiledPlayers.length > 0) {
        for (const ep of exiledPlayers) {
          if (ep in this.player1Count) {
            this.player1Count[ep]++;
          }
        }
        exiledList = exiledList.concat(exiledPlayers);
      }
    }

    this.player1 = this.filterPlayers(exiledList);
  }

  proposeCombination(q) {
    while (Object.keys(this.player1).length > 0) {
      this.doStep(q);
    }
    return this.proposalsDict;
  }
}


function getSheetDataAsDictionary(sheetname) {
  // スプレッドシートの取得（"sheetname" という名前のシート）
  var sheet = SpreadsheetApp.getActiveSpreadsheet().getSheetByName(sheetname);
  
  // データの取得（最初の行をヘッダー、残りをデータとして取得）
  var data = sheet.getDataRange().getValues();
  
  // ヘッダー行を取り出す（最初の行）
  var headers = data[0];
  
  // 辞書型でデータを格納（キーは列名、値はリスト）
  var result = {};
  
  // ヘッダーごとにリストを作成
  for (var j = 0; j < headers.length; j++) {
    result[headers[j]] = [];
  }
  
  // データ行をリストに追加
  for (var i = 1; i < data.length; i++) {
    for (var j = 0; j < headers.length; j++) {
      result[headers[j]].push(data[i][j]);
    }
  }
  
  return result;
}

function get_p(){
  var sheet = SpreadsheetApp.getActiveSpreadsheet().getSheetByName("README");

  // 入力されたqを取得
  q = sheet.getRange('B1').getValue()

  return Number(q)
}

function outputDictionaryAsTable(data) {
  var sheet = SpreadsheetApp.getActiveSpreadsheet().getSheetByName("output");

  // データ範囲を取得して、値を削除
  sheet.clearContents();

  // ヘッダー行を取得（辞書のキー）
  var headers = Object.keys(data);

  // 最初の行にヘッダーを設定
  sheet.getRange(1, 1, 1, headers.length).setValues([headers]);

  // 各列の最大データ長を取得
  var numRows = Math.max(...headers.map(key => Array.isArray(data[key]) ? data[key].length : 0));
  var rows = [];

  for (var i = 0; i < numRows; i++) {
    var row = [];
    for (var j = 0; j < headers.length; j++) {
      var key = headers[j];
      row.push((Array.isArray(data[key]) && i < data[key].length) ? data[key][i] : ""); // 存在しない部分には空文字
    }
    rows.push(row);
  }

  // 2行目以降にデータを設定
  if (rows.length > 0) {
    sheet.getRange(2, 1, rows.length, headers.length).setValues(rows);
  }

  Logger.log("データの出力が完了しました！");
}



// 実行例
function student_proposal() {
  const dict1 = getSheetDataAsDictionary("student");
  const dict2 = getSheetDataAsDictionary("college")
  const q = get_p()

  const da = new DAalgorism(dict1, dict2);
  const p1 = da.proposeCombination(q);
  Logger.log("Result 1: " + JSON.stringify(p1));

  outputDictionaryAsTable(p1)

}

function college_proposal(){
  const dict1 = getSheetDataAsDictionary("college");
  const dict2 = getSheetDataAsDictionary("student")
  const q = get_p()

  const da = new DAalgorism(dict1, dict2);
  const p2 = da.proposeCombination(q);
  Logger.log("Result 2: " + JSON.stringify(p2));

  outputDictionaryAsTable(p2)
}
```
ChatGPTには大変お世話になりました...!

## 振り返り
DAアルゴリズムはGale-Shapleyアルゴリズムとも呼ばれるらしく、そちらの方はコードの数が結構ありました。
特にわかりやすかったのが、こちらの記事です。
https://builtin.com/articles/gale-shapley-algorithm
男女のマッチングとして単純化しているもののコードが綺麗でとても参考になりました。

このほかにも地域で受け入れる人数に上限を儲けた時に、弱安定性を保証しながらマッチングを決めるFDAメカニズムなどもあるみたいです。

また選好を持たないモノと人を結びつけたいときには、PSメカニズムやRPメカニズムが使えます！

実践的な経済学であるマーケットデザイン・メカニカルデザインにさらに興味を持ちました！

## 参考図書
・栗野盛光・熊野太郎, 『マーケットデザイン総論』,共立出版, 2024
・小島武仁・河田陽向, 『マッチング理論とマーケットデザイン』, 日本評論社, 2024