Go to Qiita Advent Calendar 2024 Top
LoginSignup
31
10

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

BrainPad Advent CalendarAdvent Calendar 2021Day 12
@_jinta

安定マッチングを使ってお仕事の割り当てをした話

Last updated at Posted at 2021-12-12

こんにちは、本記事は2021年BrainPadアドベントカレンダーの12日目の記事です。
今日は、面倒なお仕事の割り振りを、CPで安定マッチング問題を解くことで解決した話をします。

私の所属する会社には毎年新卒のデータサイエンティスト、機械学習エンジニアが沢山入ってきます1。様々なバックグラウンドの新卒が入って来るため、研修・育成は手厚いほうなのではないかと思います。そのなかのひとつに**「新卒1年目は毎日業務時間1hを使って課題図書を読んで勉強する」**というものがあり、6冊くらい統計学やパターン認識や数理最適化の教科書を読んでいます2。勉強することでお給料を貰っているわけですから、素晴らしい制度です。

さて、データサイエンスやら機械学習やらの分野は日進月歩で発展しており、教科書も毎年のように新しい本が出版されております。新卒の勉強会でも読む本をアップデートすべく、後輩に読んでもらう本の選定をすることになりました。なんやかんやで候補を出したはいいものの、勘や口コミだけで決めるわけにもいかず、実際に読んでレベル感や扱っているトピックを検証する必要があります。一人で全部読むのはしんどいので、手分けして読むことになります。

ここで**「誰にどの本を読んでもらうか」**という問題を解く必要が出てきます。面倒ですね3。

ということで、これを安定マッチング問題とみなしてアルゴリズムにやってもらおう、というのが今回のお話の経緯になります

目次です
１．今回取り組んだ問題はどのような問題なのか整理
２．実際にpythonで解いてみる
３．使ってみて思ったこと

という流れで書いていきます。時間がない方は１、２は飛ばして３だけ読むのがおススメです

1. 何に取り組んだか

まずは安定マッチング問題について軽く説明したあと、今回の問題の設定、何を使って解いたかについて述べます。

安定マッチング問題とは

Wikipediaの記事をそのまま引用すると、こんな感じです（出典: https://ja.wikipedia.org/wiki/安定結婚問題 ）

安定結婚問題に対し、互いに現在組んでいる相手よりも好きであるペア（以下ブロッキングペアとする）が存在せず、全員が個人合理性を満たすマッチングを安定マッチング（英: stable matching）という。

流石にこれだけを読んでもよく分からないと思うので整理すると

  • 2グループあって、それらの間でのペア（マッチング）を決める問題である
    • 例えば男女が数人ずついて、カップルの組合せを決めたいような状況
    • 選好（好きな相手の順位表）があるような状況に適用可能
  • マッチングは1対1でも1対多でも可
  • 安定性という、マッチングが満たすべき条件がある
    • 安定性 ＝ ブロッキングペアがないこと
    • ブロッキングペアとは、お互いに今のマッチングの相手よりも好むようなペアのことを指す

ブロッキングペアの概念がやや分かりにくいのですが、この絵が直感的です。このようなペアがないマッチングを見つけることが目的です
blocking_pair.gif
（出典：https://medium.com/@UofCalifornia/how-a-matchmaking-algorithm-saved-lives-2a65ac448698）

今回取り組む問題の設定

冒頭でも紹介した通り、n人いてm冊の本を読みます。誰が何を読むかを決めたいです4。
1人だと主観を逃れられないので5、1冊を2人が読むとします。逆に1人が複数冊読むことはありません。

選好は、みんなに読みたい本の順位を聞いて作成しました。本の方も人の選好を設定します。なお、選好にはタイ（同順位）がないものとします6。

さらに、せっかくなので普段一緒に仕事している人と同じ本の担当になるのは避けたい、という条件も追加で入れることとしましょう。

何を使って解くか

安定マッチング問題を解くアルゴリズムとして、DAアルゴリズム（Gale-Shapleyアルゴリズムとも言う）が有名です。このアルゴリズムはいい所がいくつかあって、安定性の他にも

  • 耐戦略性：参加者は嘘をつく（本心と違う選好を表明する）インセンティブを持たない7
  • 効率性：解は安定性を満たす任意のマッチングにパレート支配されない

などが成り立ちます。アルゴリズムの説明は省略しますが、ググれば沢山出てくると思います。

まあこのDAアルゴリズムで解くのでもいいのですが、今回の「この人とこの人は同じタスクにアサインしたくない」のように、追加的な仮定を置きたい場合にどうすればいいのかが自明ではありません。実問題を解くときは細かい調整をしながらアルゴリズムを組むらしいのですが、ゲーム理論の専門家でもないとちょっとハードルが高く感じます。

そこで、比較的自由度が高く制約を追加できるCPを使ってこの問題を解く、という方針でいきたいと思います。CPというのは制約プログラミング（Constraint Programming）の略で、条件を満たす解を見つけるプログラミングパラダイムのことです8。利点としては制約を直感的に入れられることがあります。また、条件を満たす解を全て求めることも可能です。すべてをアルゴリズムで決めるのではなく、アルゴリズムを頼りつつも微妙に手で調整したいときにはこのような特徴は嬉しいでしょう。

一方で、CPで解いた場合、耐戦略性などの利点は消えてしまいます。このあたりはトレードオフになると思うので、状況を見て使うアルゴリズムを判断したいところです。今回の状況で嘘をつくインセンティブがどのくらいあるかというと、まあおそらくほぼないので問題にはならないでしょう9。

2. Pythonで実際に解いてみる

今回はOR-Toolsというgoogleのオープンソースの最適化ツールで解いていきます。
これ以降は単なるプログラミングの話なので、興味ない大半の方は３. の結論まで飛んでください。

なお、使用していたのはバージョン9.1でした。

ortoolsのcp_model ５行解説

OR-Toolsには様々なソルバーや機能がありますが、今回はCPを解くので、cp_modelモジュールを用います。
これが主題ではないのですが、見慣れないと思うので簡単に説明します。以下を満たすa, bを求める例を解きます。
$$a >b, \ a\in (0,1), \ b\in (0,1,2)$$

from ortools.sat.python import cp_model 

model = cp_model.CpModel()                  ## モデルの作成

a = model.NewIntVar(0, 1, 'a')              ## 変数の作成
b = model.NewIntVar(0, 2, 'b')

model.Add(a > b)                            ## 制約の追加

solver = cp_model.CpSolver()                ## ソルバーの設定
status = solver.Solve(model)                ## 求解

print("status:", solver.StatusName(status)) ## 解を求められていればOPTIMALと出力
print(solver.Value(a), solver.Value(b))     ## 解の出力

だいたい上のコードを見れば分かる通り、「モデルの作成 → 変数の作成 → 制約の追加 → ソルバーの設定 → 求解 → 解の確認」という流れになります（５行とは）。ポイントとしては、

  • 変数の作成
    • IntVarのほかにBoolVarなどがある。NewIntVarの場合、[下限、上限、変数名]を引数に与える
  • 制約の追加
    • Addに式を与えられる。他にAllDifferentとかAddMaxEqualityとか制約を追加する機能が色々ある
  • ソルバーの設定
    • parameterとかも設定できる
  • 求解
  • 解けてるかどうかを確認
    • 解が見つかればOPTIMAL、実行可能解がなければINFEASIBLEと出力される
  • 解の出力
    • solver.Value(...)に見たい変数を与えると解を返してくれる

今回用いるortoolsの制約について補足

追加で、今回用いるちょっとクセのある制約を２つ紹介します

1. AddElement
model.AddElement(index, var_arr, target)
で、var_arr[index] = targetという関係を指定できます。ここでvar_arrは要素が変数(定数も可)であるようなリストです。indexは数字が入るイメージですが、ここに変数を使うこともできます。

まあ、具体例を見たほうがイメージしやすいと思うので後で改めて言及します。

2. Reification
CPソルバーでは「Ａという制約が成り立つときのみＢという制約を課す」といった制約間の関係も記述することが出来ます。

ortoolsでは、制約が成り立つとき1、成り立たないとき0の値をとるような変数を作り、その変数を用いて上の関係を記述できます10。具体的には、「bool_varが真⇒constraintが真」という関係を表現するOnlyEnforceIfを用いて、以下のように書きます

# 制約を変数として扱う
model.Add(x > 10).OnlyEnforceIf(bool_var)
model.Add(x <= 10).OnlyEnforceIf(bool_var.Not())
# bool_var2については略すが、似た感じで記述

# 「制約1⇒制約2」を課す
model.AddImplication(bool_var, boo_var2)

ではこれらを使って実際に解いていきましょう

実装

6人と3冊の例を見ていきます。選好はこんな感じです（分かりにくいですが、≻は不等号(>)ではなく選好を表す記号です）。
例えば人2は本2を最も好み、次いで本3を好み、最後が本1ということを意味します。

人 選好
1 1≻2≻3
2 2≻3≻1
3 1≻3≻2
4 1≻3≻2
5 2≻3≻1
6 2≻1≻3
本 選好
1 1≻3≻6≻5≻2≻4
2 5≻6≻3≻4≻1≻3
3 1≻2≻4≻5≻6≻3

選好の設定

person_pref = [
    [1, 2, 3], 
    [3, 1, 2], 
    [1, 3, 2], 
    [1, 3, 2], 
    [3, 1, 2], 
    [2, 1, 3]
]

book_pref = [
    [1, 5, 2, 6, 4, 3], 
    [5, 3, 6, 4, 1, 2], 
    [1, 2, 6, 3, 4, 5]
] 

n = len(person_pref)

各人の選好をリストとして保持し、それをさらにリストに格納しておきます11。なお、上の表と書き方が違って恐縮ですが、person_pref[i][j]はiさんが本jを何番目に評価しているかを意味します。例えば人2は本1の順位が3番、本2の順位が1番、本3の順位が2番ということを意味します。

解く際に人の数と本の数が一致していないとややこしくなるので、本を複製することで対処します。複製した本の選好は全く同じ、人の選好は増やしたほうの本が直後にくるように改変します12。また、このときindexが0から始まるように全てをマイナス1します。

import itertools

pref_book = [[i-1 for i in b] for b in book_pref] + [[i-1 for i in b] for b in book_pref]
pref_person = [list(itertools.chain.from_iterable([(v-1, v-1 + n//2) for v in t])) for t in person_pref]

print(pref_person)
# [[0, 3, 1, 4, 2, 5],
#  [2, 5, 0, 3, 1, 4],
#  [0, 3, 2, 5, 1, 4],
#  [0, 3, 2, 5, 1, 4],
#  [2, 5, 0, 3, 1, 4],
#  [1, 4, 0, 3, 2, 5]]

print(pref_book)
# [[0, 4, 1, 5, 3, 2],
#  [4, 2, 5, 3, 0, 1],
#  [0, 1, 5, 2, 3, 4],
#  [0, 4, 1, 5, 3, 2],
#  [4, 2, 5, 3, 0, 1],
#  [0, 1, 5, 2, 3, 4]]

問題の記述

先ほど紹介したOR-Toolsを用いて問題を記述していきます13。

from ortools.sat.python import cp_model

# モデルの作成
model = cp_model.CpModel()

# 変数の作成
n = len(pref_person)
P = [model.NewIntVar(0, n - 1, 'book[{}]の担当者'.format(i)) for i in range(n)]
B = [model.NewIntVar(0, n - 1, 'person[{}]の担当書'.format(i)) for i in range(n)]

# 制約の追加1
for p in range(n):
    model.AddElement(B[p], P, p)
# P[B[p]] = p という制約を追加

for b in range(n):
    model.AddElement(P[b], B, b)

まず変数ですが、ここではマッチング相手のindexが入るような変数を人、本それぞれについて作成します。P、Bがそれらの変数を格納しているリストになります。P[b]に本bのペアの人のindexが、B[p]にpさんのペアの本のindexが格納されることを意図しています。

この変数について、「Aさんのペアである本のペアはAさんである」が成り立つ必要があります。この制約を入れるときに、先ほど紹介したAddElementsを用いることができます。

復習すると、model.AddElement(index, var_arr, target)で、var_arr[index] = targetという関係を表現することができるのでした。今回はPが担当者の変数が入っているリスト、B[p]がpさんが担当する本なので、AddElement(B[p], P, p)で「pさんが担当する本の担当者はpさん」という関係を制約していることになります。

続いて安定性の条件の制約を入れます。

for p in range(n):
    rank_matched_b = model.NewIntVar(0, n-1, f'person[{p}]にとってのペアの順位')
    model.AddElement(B[p], pref_person[p], rank_matched_b)
    for b in range(n):
        # pさんにとって本bが今のペアよりも順位が高い(prefの数字が小さい)ときに1となる変数を作成
        b1 = model.NewBoolVar('b1')
        model.Add(pref_person[p][b] < rank_matched_b).OnlyEnforceIf(b1)
        model.Add(pref_person[p][b] >= rank_matched_b).OnlyEnforceIf(b1.Not())

        rank_other_p = model.NewIntVar(0, n-1, f'book[{b}]にとっての[{p}]の順位')
        model.AddElement(P[b], pref_book[b], rank_other_p)
        # 本bにとってpさんが今のペアよりも順位が低い(prefの数字が大きい)ときに1となる変数を作成
        b2 = model.NewBoolVar('b2')
        model.Add(pref_book[b][p] > rank_other_p).OnlyEnforceIf(b2)
        model.Add(pref_book[b][p] <= rank_other_p).OnlyEnforceIf(b2.Not())

        model.AddImplication(b1, b2)

for b in range(n):
    rank_matched_p = model.NewIntVar(0, n-1, f'book[{b}]にとってのペアの順位')
    model.AddElement(P[b], pref_book[b], rank_matched_p)
    for p in range(n):
        # 本bにとってpさんが今のペアよりも順位が高い(prefの数字が小さい)ときに1となる変数を作成
        b1 = model.NewBoolVar('b1')
        model.Add(pref_book[b][p] < rank_matched_p).OnlyEnforceIf(b1)
        model.Add(pref_book[b][p] >= rank_matched_p).OnlyEnforceIf(b1.Not())

        rank_other_b = model.NewIntVar(0, n-1, 'matching of person')
        model.AddElement(B[p], pref_person[p], rank_other_b)
        # pさんにとって本bが今のペアよりも順位が低い(prefの数字が大きい)ときに1となる変数を作成
        b2 = model.NewBoolVar('b2')
        model.Add(pref_person[p][b] > rank_other_b).OnlyEnforceIf(b2)
        model.Add(pref_person[p][b] <= rank_other_b).OnlyEnforceIf(b2.Not())

        model.AddImplication(b1, b2)

安定性とは「pさんにとって本bが今のペアよりも順位が高いならば、本bにとってpさんが今のペアよりも順位が低い」というものでした。もしこれが成り立たなければ、pさんと本bはブロッキングペアということになってしまいます。

これを実装するには前述したreificationを用います。まずAddElementを用いて「pさんにとっての今のペアの順位」を表現する変数を作ります14。次に適当なBooleanの変数 (b1) を作り、それが「pさんにとって本bが今のペアよりも順位が高いときに1、そうでないときに0」をとるようにOnlyEnforceIFを用いて設定します。

同様に「本bにとってpさんが今のペアよりも順位が低い」ことを示すBoolVarのb2を作成し、b1であればb2である、という制約をAddImplicationで加えればOKです。

これを任意のp, bについて書きます。また、「本bにとってpさんが今のペアよりも順位が高いならば、pさんにとって本bが今のペアよりも順位が低い」という逆方向の制約も入れます。

求解

solver = cp_model.CpSolver()
status = solver.Solve(model)

# 解の確認
print("status:", solver.StatusName(status))
for i in range(n):
    print(f'book[{i}]の担当者:', solver.Value(P[i]), ', ', f'person[{i}]の担当書:', solver.Value(B[i]))

で解いて、結果を出力します。以下のような安定なマッチングが求まりました。

book[0]の担当者: 0, person[0]の担当書: 0
book[1]の担当者: 3, person[1]の担当書: 2
book[2]の担当者: 1, person[2]の担当書: 5
book[3]の担当者: 5, person[3]の担当書: 1
book[4]の担当者: 4, person[4]の担当書: 4
book[5]の担当者: 2, person[5]の担当書: 3

制約の追加

普段一緒に仕事している人と同じ本の担当になるのは避けたい、という制約を忘れていました。人０，５は普段一緒に仕事をしているので、同じ本に割り当てるのは避けたいものとしましょう。

この制約も加えて解きます。

model.Add(B[0] + n//2 != B[5])
model.Add(B[5] + n//2 != B[0])

solver = cp_model.CpSolver()
status = solver.Solve(model)
for i in range(n):
    print(f'book[{i}]の担当者:', solver.Value(P[i]), ', ', f'person[{i}]の担当書:', solver.Value(B[i]))

結果
book[0]の担当者: 0 , person[0]の担当書: 0
book[1]の担当者: 5 , person[1]の担当書: 2
book[2]の担当者: 1 , person[2]の担当書: 3
book[3]の担当者: 2 , person[3]の担当書: 5
book[4]の担当者: 4 , person[4]の担当書: 4
book[5]の担当者: 3 , person[5]の担当書: 1

ということで、これで解きたい問題を解くことができました。制約をひとつ追加したことで、先ほどと結果が違っていることが分かります。

ここでひとつ注意です。普通の安定マッチング問題は必ず解をもちますが、上のように追加で制約を入れた時には必ずしも解をもつとは限りません。むしろ追加的な制約のないマッチング問題でも解は1~数個のことが多く、それにむやみやたらに制約を入れると実行不能となることが多いかもです15。一応そのような制約をSoft constraintとして入れることで実行不能にならないように対応することもできます16。

3. 実際にやってみて

ということで、実際にやってみたという話でした。

安定マッチングの応用としてよく出てくる例は学校選択とか臓器提供とか大規模なものが多いですが、今回くらいの小規模な問題でも使いどころはあると感じました。

ありだと思った理由の一つ目は、割り当てる人にとって意思決定というストレスのかかる作業を代替できるというメリットがあることです。システム2のはたらきは消耗品であるので、不要な場所で使うのは避けるべきです。って心理学の本に書いてありました17。また、AI・ビッグデータの飛躍的な広がりによって予測のコストが下がる中で、予測と補完的な要素である意思決定の需要は増しています18。意思決定をサポートする手法の重要性も高まっていくことでしょう。

実際に使うときはこだわりたい条件なども色々あるでしょうが、アルゴリズムの結果をそのまま使う必要はありません。アルゴリズムの解をもとに、やばそうなところは目で見て判断して変更などは可能なので、参考程度に使うことは全然出来そうです。それでもゼロから意思決定するよりははるかに楽になると思われます。先ほども述べた通り、DAアルゴリズムなどと違って安定性を満たす解を全て求めることも容易です。

ありだと思った二つ目の理由が、今は独断で決めていても、本当は恣意的なマッチングを避けるべきケースは意外とあるのではないかということです。学校選択とかだとこれは非常に重要ですが、会社などの組織の中でも透明性があるに越したことはないでしょう。

ちなみに僕は自分が割り当てられない解を出せまいかと思い、何回も微妙に設定を変えて計算しなおしましたが19、とある本との相性が良すぎて回避することは全くできませんでした。悪いことはできないもんですね

参考

  1. 僕の同期は分析官が15人くらいです。来年の新卒は分析官が20人以上、全体だと41人いるみたいです。 ↩

  2. 詳しくは白金鉱業FMというPodcastの第33回で紹介されているので、ぜひどうぞ！ ↩

  3. とは言っても規模的には10数人くらいなので、適当にわしゃわしゃっと組んでしまえばそれで済む話なのですが、なぜこの人がこれの担当になったのかを説明するのが面倒です（別にそんなことを責められる可能性はゼロなんですけどね......笑） ↩

  4. そもそもこれは安定マッチングの問題として解くべきなのか、という話はありますが、考えだすと長くなりそうなのでとりあえずここでは置いておきます。 ↩

  5. 諸説あります。 ↩

  6. 実際に解いた設定とは微妙に違います。まあ記事ということでご容赦ください。 ↩

  7. 正確には嘘をつくインセンティブを持たないのは片方の群の人だけです。これはDAアルゴリズムの設定によります。学校選択のように、非対称でどちらか片方の嘘のほうが問題になるケースはともかく、男女の例とかだとあまり意味を持たない性質な気もします。 ↩

  8. ぷろぐらみんぐぱらだいむ？なにそれ？って感じですよね。僕も正直よく分かっていませんが、この記事を読む上では「CP solverを使うと条件を満たす解を見つけることができる」ということだけ分かっていれば大丈夫です。一番雑に解こうと思うと、ありうる解の候補を片っ端から見ていって条件に当てはまるか判定していけばいつか条件を満たす解が求まる（あるいは全て解じゃなければ実行不能ということになる）だけです。実際はもっと頭がいいアルゴリズムが中では使われてます。 ↩

  9. 安定マッチングの有名な応用先としては学校選択や研修医のマッチングなどがあります。このような大きな問題については、頑張って情報収集して嘘をつくインセンティブがあるでしょう。ということもあって、学術的にはこの耐戦略性も非常に重視されるような気がします。このあたりの嘘をつく人々については2012年のノーベル経済学賞を受賞したロスの『Who Gets What』におもしろいエピソードが沢山あったので、おすすめです。一般向けの本なので楽しんで読めると思いますし、普通に勉強にもなります。 ↩

  10. このように、制約を変数として扱うことを専門用語でreificationと言うようです。マルクスの用語の「物象化」とはおそらく無関係です。 ↩

  11. prefは英語で選好を意味するpreferenceの略です。たぶんperferとかと同根です。 ↩

  12. 他のアルゴリズムを使ったり実装を工夫すれば、たぶん選好に手を加えなくてもいい感じに対処できます。 ↩

  13. 実装はhttp://www.hakank.org/google_or_tools/ を参考にしています。 ↩

  14. なお、「pさんにとっての本bの順位」は変数が絡まないため、単純にperf_personにアクセスすれば取得できることに注意です。 ↩

  15. 実際に自分が解いたのはタイ（同順位）がある問題だったので、多少は解が多かった気がしますが、それでもあまり追加的な制約を入れる余地はありませんでした。ちなみにタイがある場合はOR-Toolsだとここにあるような実装で実現できるみたいです。今回紹介したのと結構違うことをやっていて面白いです。タイがある場合はDAアルゴリズムでもうまくいかないことがあるらしく、このスライドで阪大の安田先生が色々紹介されています。 ↩

  16. 必ずしも満たさなくてもいいけど、違反するとペナルティがかかるような制約をsoft constraintと言います。次の講義ノートなどで紹介されています： https://www.cis.upenn.edu/~cis189/files/Lecture8.pdf ↩

  17. 『意思決定の心理学 脳とこころの傾向と対策』阿部 修士著にありました。ちなみに本書で読んだ内容だったかは忘れましたが、ジョブズとか偉い人がいつも同じ服を着るのは、無駄なところで意思決定をしてすり減らさないようにしているから、という話があります。真偽のほどは知らないです。 ↩

  18. これは『予測マシンの世紀: AIが駆動する新たな経済』アジェイ アグラワル他著 からです。 ↩

  19. 本記事では煩雑になるので無視しましたが、本に対して人の数が多かったので、何人か「お仕事なし」に割り当てられる人がいました。 ↩

31
10
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
31
10

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?