#tcfm おすすめです

Rui Ueyamaさんが、毎回、ゲストを招待して、(主に低レイヤー寄りの)深い話をされている、Turing Complete FMというネットラジオがあるんですが。
主催者自身もLLVMのリンカを作っているガチのプログラマで、ゲストも小学生の頃からx86のリファレンスを愛読してOS自作を始めた方や、Nintendo Switchのエミュレータを開発している方、Google Chromeの開発者など、かなり濃い人たちです。

マッチングアルゴリズム

tcfmの第23回で出た話なのですが。
ゼミの配属など、第一希望、第二希望、……と書いていって、できるだけ希望は叶えてくれるけれど定員溢れたら次の希望に回される、という場面を考えます。

こういった場合「本当はxxに行きたいけれど、倍率が高そうだからooに……」みたいな意思決定をしますが。
そのような「戦略」なしで、素直に行きたい順に書けばうまくいく、「こう書いておけば、より志望度が高いところに行けたのに」が起こらないようなアルゴリズムがあれば、みんな幸せになれるはず。

そして、そのアルゴリズムは存在する。という話でした。

問題の前提条件

n人の学生が、m個のゼミのうち、どこかに配属される
各学生は、行きたいゼミを第1希望〜第m希望まで書いて提出する
各ゼミは定員が決まっていて、また、独自の評価基準を持っている(あるゼミでは低評価な学生が、別のゼミでは高評価な可能性もある。もちろん、すべてのゼミが同じ評価基準であっても、アルゴリズムは機能する)
各ゼミは、評価基準に従い、できるだけ評価の高い学生を取ろうとする
各学生にとって、戦略的投票が不要な(つまり、本当に行きたい順番とは異なる順番を提出することで、本当に行きたい順番を提出した場合よりも志望度が高いゼミに配属されることがない)マッチングアルゴリズムを作りたい

実は、ここに書いた問題設定には穴があって。学生名とゼミ名をソートして順に割り当てるなど、希望を一切無視すれば、戦略的投票が不要なマッチングという条件は満たされるのですが。
そこらへんはどう定式化したらいいか分からなかったので「戦略的投票が不要かつ、雰囲気的には希望ができるだけ叶えられるアルゴリズム」という、なんかゆるいものだと捉えています。

アルゴリズム

tcfm内で説明されていたのは、次のようなアルゴリズムです

各学生は、ゼミの第1希望〜第m希望のリストを作成する
各学生は第1希望のゼミに訪問する
各ゼミは訪問者(および、仮決定者)を、独自の評価基準に従って、評価の高い順にソートする
各ゼミは、定員に達するまで、高評価の学生を「仮決定」としてマークする。また、溢れた学生の中に仮決定マークがついている学生がいたら、仮決定マークを剥がす
仮決定マークがついていない学生は、次に希望するゼミに訪問する
全員に仮決定マークが付くまで3に戻る
各学生の配属ゼミを現在仮決定マークがついているゼミに確定する

ポイントは、後からやってきた人が優秀だったら、既に仮決定していた人が追い出されることです。
これにより、第1希望で無難なところを選んでも後から追い出されるリスクは変わらず、第1希望が通らなくても第2希望のゼミで自分が優秀だったら、他の人を追い出して入れますので、妥協する必要はなくなります。

実装

Pythonで実装します。
また、(実際にはやってられんと思いますが)実装を分かりやすくするため、各ゼミは全学生を事前に面接し、評価の順序を持っているものとします。

tcfm23.py

from collections import namedtuple, deque, Counter
import random

n_student = 100
n_semi = 20

# 各学生は、希望するゼミのリストを持っている (作るのめんどいので[0..n_semi]をランダムシャッフルする)
Student = namedtuple("Student", "id wish")
students = [Student(i, list(range(n_semi))) for i in range(n_student)]
for stu in students:
    random.shuffle(stu.wish)

# 今回は、ゼミも事前に学生を面接し、希望する学生の順位を持っているものとする
# (評価基準さえ変わらなければ、事前に持っている必要はない。また、作るのめんどいのでランダムシャッフルする)
# また、capacityはゼミの定員。今回は全ゼミ5人とする
Semi = namedtuple("Semi", "id wish capacity")
semis = [Semi(i, list(range(n_student)), 5) for i in range(n_semi)]
for sem in semis:
    random.shuffle(sem.wish)

# まだ決まってない学生たちのキュー。2つ目の数字は、次に試すのが第何希望かを示していて、
# まずは第一希望、つまりstudent.wish[0]のゼミへ行くので、初期値はゼロにしている。
q = deque((student, 0) for student in students)

# ゼミごとの仮決定者
provisional = [{} for _ in range(n_semi)]

while q:
    student, i = q.popleft()
    wish = student.wish[i]
    semi = semis[wish]
    prov = provisional[wish]

    # この学生は、ゼミにとって何番目にほしい学生か?
    rank = semi.wish.index(student.id)

    prov[rank] = (student, i)
    if len(prov) > semi.capacity:
        # 一番いらない学生を仮決定者から消して、キューに入れる
        worst = max(prov.keys())
        student, i = prov[worst]
        del prov[worst]
        q.append((student, i+1))

# 各学生がどのゼミIDに配属されたかを表すリストを作る
result = [0] * n_student
for i_semi, prov in enumerate(provisional):
    for student, _ in prov.values():
        result[student.id] = i_semi

# で、結局みんな、第何希望に配属されたの?
ranks = [stu.wish.index(i_semi) + 1 for stu, i_semi in zip(students, result)]
counter = Counter(ranks)
for i,n in sorted(counter.items()):
    print("第{}希望: {}".format(i, n))

# ちなみに、希望が叶わなかった残念な人の成績を見てみる。
print("")
rank = max(counter.keys())
student = ranks.index(rank)
for i, i_sem in enumerate(students[student].wish[:rank]):
    semi = semis[i_sem]
    arr = list("." * n_student)
    for j_stu, j_sem in enumerate(result):
        if j_sem != i_sem:
            continue
        arr[semi.wish.index(j_stu)] = "*"
    arr[semi.wish.index(student)] = "@"
    print("第{}希望:".format(i + 1), "".join(arr))

実行結果

乱数を使っているので、動かすたびに違う結果が出ますが、

みんな、第何希望に行けたの?

第1希望: 62
第2希望: 24
第3希望: 6
第4希望: 4
第5希望: 1
第6希望: 2
第9希望: 1

みんな、そこそこ希望しているところに行けています。
ところで、第9希望になってしまった方は、各ゼミからどういった評価をされていたのでしょうか?

希望が叶いづらかった人の評価

第1希望: .........................*........**................*.........*..............@......................
第2希望: .......*...*....**.......*.................................................................@........
第3希望: ...*.......*...*...................*............*............................@......................
第4希望: ............*..**.....*........*.........................................................@..........
第5希望: ....................................*.......*....*....*................*........@...................
第6希望: .*...*...*............*...*...................................@.....................................
第7希望: ............*........*............*.*.................*...@.........................................
第8希望: **..*...................*........................................*....@.............................
第9希望: .........*.............*......@.......*........*....................................................

*が、配属された人の評価位置、 @が、希望が通りにくかった人の評価です。
なかなか厳しいところにいますね。つらい。

まとめ

tcfmで紹介されていたアルゴリズムを実装して動かしてみました。
tcfmでも、マッチングアルゴリズムを使えば多くの人が希望したところに行けるようになるかもしれないのに、みんな、知らないので使っていない、という話でした。
ゼミ決めの他にも、新入社員の部署配属などにももちろん使えます。

マッチングアルゴリズム、機会があれば、試しに使ってみてはいかがでしょう？

#tcfm 第23回で紹介されていたマッチングアルゴリズムを実装してみた

#tcfm おすすめです

マッチングアルゴリズム

問題の前提条件

アルゴリズム

実装

実行結果

まとめ