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

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

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

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

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

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

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

1. 何に取り組んだか

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

安定マッチング問題とは

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

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

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

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

ブロッキングペアの概念がやや分かりにくいのですが、この絵が直感的です。このようなペアがないマッチングを見つけることが目的です

（出典：https://medium.com/@UofCalifornia/how-a-matchmaking-algorithm-saved-lives-2a65ac448698）

今回取り組む問題の設定

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

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

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

何を使って解くか

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

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

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

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

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

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

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の値をとるような変数を作り、その変数を用いて上の関係を記述できます¹⁰。具体的には、「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ということを意味します。

選好の設定

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)

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

解く際に人の数と本の数が一致していないとややこしくなるので、本を複製することで対処します。複製した本の選好は全く同じ、人の選好は増やしたほうの本が直後にくるように改変します¹²。また、このとき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を用いて問題を記述していきます¹³。

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さんにとっての今のペアの順位」を表現する変数を作ります¹⁴。次に適当な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~数個のことが多く、それにむやみやたらに制約を入れると実行不能となることが多いかもです¹⁵。一応そのような制約をSoft constraintとして入れることで実行不能にならないように対応することもできます¹⁶。

3. 実際にやってみて

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

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

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

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

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

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

参考

• 安定マッチングについて
  • 数式が多少読めればとても分かりやすい入門用の教科書: 『マーケットデザイン入門:オークションとマッチングの経済学』坂井豊貴(著)
  • おすすめの一般向け読み物: 『Who Gets What―マッチメイキングとマーケットデザインの新しい経済学』アルビン・Ｅ・ロス(著), 櫻井祐子(訳)
  • 割と最近の研究まで紹介されているスライド: https://www.slideshare.net/YosukeYasuda1/ss-54841742
• CPについて
  • 自分が勉強するときに使っていた講義ノート: https://www.cis.upenn.edu/~cis189/
• OR-Toolsについて
  • 公式のドキュメント: https://developers.google.com/optimization/cp/cp_solver#first_sol_program
• その他
  • 色んな解き方で速度比較などしている論文。読んでないけど。: https://arxiv.org/abs/2108.05165