マッチング問題について

こんにちは！Fusic 機械学習チームの塚本です。

機械学習モデルの開発から運用までなんでもしています。もし、機械学習で困っていることがあれば、気軽にお問い合わせください。

---

なんとも今更なごくごく一般的な問題なんですが、それでもこの問題を対象とした問題は実世界でかなり溢れているなぁと思ったのでまとめておきます。

モチベーション

シフト作成なんかも、ものによってはこの問題に該当します。
シフトだとかなり一般的なんですが、それ以外の適用範囲として、（マッチングというくらいなので）１対１の相性のいい二人を決定する結婚問題が有名かなと思います。
その見方を変えて、例えば案件に誰を割り当てるのか？みたいなものにも適用できたりなんかもします。

他にも、弊社に360(さんろくまる）という360度フィードバックサービスが展開されていますが、こういったものにも適用できたりしそうです。

https://360do.jp/?utm_source=google&utm_medium=cpc&utm_campaign=ppc&gad_source=1&gclid=Cj0KCQiAgJa6BhCOARIsAMiL7V9vgdmU4NuVC0PNoQoBqb_eHEmWSAstn80QxMV4hHZT-viA_tJEPbIaAin4EALw_wcB

詳しくはみてほしいのですが、かんたんに概要を引用すると「上司や同僚・部下といった周囲の人間が対象者に対し、フィードバックを行う手法を360度フィードバックと呼びます。複数人が関わることで評価の客観性が向上し、納得度が高まるのが特徴です。」
と言ったものです。

自分を見直す機会だったり、それ自身が評価につながったりと用途は多岐だと思いますが、今回はこういった"誰と誰"（あるいは誰と何か）を結ぶかを考える時、大体この問題が適用できたりとかします。
実際にあるものなので、主にこれがモチベなんですが、こういう時にも数理最適化は出現します。

この問題の図のイメージだったり、概要だったりといろんなものが以下の記事が参考になります。
https://qiita.com/drken/items/e805e3f514acceb87602

グラフ

なにかと何かを結ぶ際、やはりグラフが出てくるわけですね。
今回対象としてるのが評価システムなため、評価者（集合）と被評価者（集合）があり、この二つを結ぶことになります。

（ちょっと文字にセンスないですが。。。）評価者集合をA、被評価者集合をBとした時、この二つを結ぶグラフの枝は$(a,b) \in A \times B$で表現されます。

参考記事にもある通り、最終的に最大流に帰着させていくので、Xとそれら全ての要素をソース点、Yはシンクと紐づけます。

定式化

360に限らず、誰が誰を評価すると言った関係は基本的にN対Nです。

概要

目的関数はなにを目的とするかはものによって変わりますが、例えば「誰が誰を評価するということに対して点数をつける」みたいなことを考えて、全体の点数が一番高くなるように関係性を決めるみたいなことが考えてその最大値を設定するような感じがシンプルかと思います。
あとは最大流と同じかと思います。

追加の制約条件

例えば、評価できる人数の最大値が個人によって決まっていたり、評価される側の人数が決まっていたりなどあるかと思います。

• 評価できる最大人数

$$\sum_{b \in \delta^-(a)} x_{a, b} \le N_a \ \ a \in A, N_a: aの評価できる人数の最大値$$

• 評価される人数

$$m_b \le \sum_{a \in \delta^+(b)} x_{a, b} \le M_b \ \ b \in B$$

あとはコードに落とすだけですね。
もちろん、追加の制約で大規模が難しくなることもありますが、これだけだけであれば結構大きい問題も解けたりします。