安定的なマッチを作る、GSアルゴリズム

はじめに

人的リソースの配置をどのようにするか、という問題は様々な企業がよく発生する問題です。例えば、新入社員や転職者を新たに雇い入れた際

• どの拠点に何人配置するのか
• どの新人にはだれを教育担当にあてるのか
• どの新人にはどの業務を任せるのか

等々、いわゆるマッチングは頻繁に発生します。
こうした問題は安定結婚問題と呼ばれます。
安定結婚問題、マッチした双方にとって利のある組み合わせで、かつ全体のバランスが取れている状況を作ることができれば理想的です。逆に言うと、その状況が作れない場合、離職、ハラスメント、リソース不足などの企業にとって良くない事象の火種になりかねません。
本記事では、この安定結婚問題を解く手法の一つであるGSアルゴリズムをご紹介いたします。

GSアルゴリズムによる安定結婚問題の解法

部署A、部署B、部署Cがあり、各部門に一名ずつ新入社員Aさん、Bさん、Cさんを配置する、というシチュエーションだとします。

手順1 アンケート

各部署、各新入社員にそれぞれアンケートを取ります。部署へは「新入社員の中から誰を優先的に欲しいか」、逆に侵入社員へは「どの部署に優先して入りたいか」を問います。
アンケート結果を集計すると、以下のようになりました。

	第一希望	第二希望	第三希望
部署A	Xさん	Yさん	Zさん
部署B	Xさん	Zさん	Yさん
部署C	Zさん	Xさん	Yさん
Xさん	部署C	部署B	部署A
Yさん	部署B	部署C	部署A
Zさん	部署B	部署A	部署C

手順2 マッチング

マッチングをしていきます。今回は部署の方からオファーをかけていくやり方をしてみます。

1. まず部署Aが第一希望の人材Xさんにオファーを出します。
   オファーされた側の人材は、「すでにマッチングしている相手がない場合は、オファーを断ることはできない」、というルールになっています。
   Xさんは部署Aのオファーを受けて入れてX-Aのマッチングが一時的に成立します。

2. 次に部署Bが同じく第一希望のXさんにオファーを出します。
   この際、Xさんはすでに部署Aとのマッチングが成立していますが、もしオファーをかけられた対象が、自分にとってより望む部署であれば、既存マッチを解消して、再度マッチングすることができます。
   今回の例ではXさんは、部署Aより部署Bに行きたがっていますから、X-Aのマッチが解消され、X-Bの一時マッチが成立します。

3. 次に部署CがZさんにオファーを出します。これはそのままマッチ成立です。

4. さて先ほどXさんを失ってしまった部署Aは改めて第二希望のYさんにオファーを出します。Yさんはフリーなので、これもそのままマッチが成立しますね。

結果

• A-Y
• B-X
• C-Z

のマッチングが成立しました。
これがGSアルゴリズムの計算方法になります。

GSアルゴリズムの面白ポイント

駆け落ちが発生しない

このアルゴリズムによって作られたマッチングでは駆け落ちが生じません。
駆け落ちとは、今回の例でいうと、「とある部署はよりほしい新入社員がいて、その新入社員も今の部署よりその部署に入りたがっている」という状況が生じない、ということになります。
例えば部署Aは本来Yさんより、Xさんの方が欲しかったわけですが、Xさんは第一希望の部署に入ってますから、部署Aに行くやる気はわかない、という状況になっており、この状況がすべての部署、全ての新入社員について発生している状況になっています。

一見するとこれがベスト、しかし？

今回は手順2で部署の方からオファーをかけていく方式で計算しました。（日本では踏襲的に部署側が選定している会社の方が多いではないでしょうか。）一方もし、新入社員側がオファーを出す、というルールになった場合、結果はどうなるでしょうか。

1. Xさんが部署Cにオファーを出し、C-Xのマッチ成立
2. Yさんが部署Bにオファーを出し、B-Yのマッチ成立
3. Zさんが部署Bにオファーを出す。B-Yのマッチが解消され、B-Zのマッチが成立
4. Yさんが部署Cにオファーを出すも、NG
5. Yさんが部署Aにオファーを出し、A-Yのマッチが成立

結果

	マッチ1	マッチ2	マッチ3
部署からオファーした場合	A-Y	B-X	C-Z
新入社員からオファーした場合	A-Y	B-Z	C-X

結果成立した組み合わせが変わりました。この結果についても先に述べた「駆け落ちが生じない」状況は生じており、全体最適の観点からいえば、どちらも同じだけの成果を残した選び方をできているといえそうです。

ではこの二つの違いはどう解釈できるのか、結論から言ってしまうと、実は 「希望が通った割合」 が部署と侵入社員で異なるのです。数えてみると以下のようになっていることが分かります。

	部署からオファー	新入社員からオファー
第一希望の通った部署数	2つ
第二希望の通った部署数	1つ	3つ
第三希望の通った部署数
第一希望の通った新入社員数		2人
第二希望の通った新入社員数	1人
第三希望の通った新入社員数	2人	1人

表の左右を比較すると 「オファーを出した側がより希望を通した結果になっている」 ということが分かります。
お互いの希望の内容によっては、いずれからオファーを出しても、同じ結果に落ち着くこともあります。一方でこのような駆け落ちができないマッチング結果が複数ありうるような希望だった場合、GSアルゴリズムでは必ずオファーを出した側が希望をより通した結果に落ち着きます。

おわりに

複数の選択肢がある中で互いが互いを選びあう場面は、人生の中のかなり大きな比重を占めるようなイベントで発生島ています。就職先、結婚相手など、もちろんこうした場面で必ずGSアルゴリズムによって決定がなされているわけではありませんが、人間の頭の中でこれと似たような調整が行われているのは間違いありません。
GSアルゴリズムは、選ばれる側ではなく、選ぶ側に居続けることが、自分の希望を通していく上で、重要であることを示唆しているようです。

株式会社LOKIARでは、こうした数理最適化の手法を用いて、業務の効率化を実現するための意思決定をサポートする物流コンサルティング、システム開発業務を承っております。ぜひお気軽にお問合せくださいませ。物流について相談する

また、弊社では開発にご助力いただける方を募集しています。
まずはカジュアルに情報交換させて頂ければと思いますので、
ぜひこちらからお問い合わせください。