合コンでペアのマッチングを最適化

2022/01/122024/01/06R,データサイエンス,データ分析の活用

はじめに

合コンに行った際に、男性同士で、誰が誰を狙うか考える事はないでしょうか？
私はよくあるのですが、いつも男性同士で相談が発生します。

女性の選好も踏まえて男性の狙いを決められたら良いのですが、女性の選好を聞くのは難しく、
また、選好を聞けたとしても、全員の利得を最大化するようなマッチング方法がすぐにはわからない事があります。
今回はこれを、数理的に解決していきましょう。

Gale-Shapleyアルゴリズムとは

マッチングのアルゴリズムにも色々とあると思いますが、本記事では、 Gale-Shapleyアルゴリズム（別名：DAアルゴリズム）という手法を用います。この手法は、ゲーム理論で使われている手法であり、2012年にノーベル賞を受賞した手法らしいです。

詳細は他のブログ（例えばここ）でも語られているのでそちらを見て頂きたいと思いますが、簡単にまとめると、

①男性はそれぞれ、最も好きな女性に告白する。
　告白された女性は、告白してきた男性の中で最も好きな男性をキープして別の男性は断る。
②告白を断られた男性は、次に好きな女性に告白する。
　告白された女性は、キープしている男性も含め、最も好きな男性をキープして、他の男性は断る。

後は②を全員がペアとなるまで繰り返すだけで、全員にとって望ましい結果が出るというアルゴリズムです。
（アルゴリズムの内部で告白しているだけなので、現実では誰が誰に告白しているかはわかりません。）

ここでいう望ましい結果というのは、駆け落ちが発生しない組み合わせを選定する事です。
駆け落ちが発生する状態というのは、「新しいペアを作る事で、二人とも現在より利得が上がる状態」の事です。これについては、後ほど具体例を挙げてご説明します。

Rで実行

Gale-Shapleyアルゴリズムは、matchingRというパッケージで簡単に実行できます。
以下では、matchingRを使ってマッチングを試していきます。

サンプルデータ作成

まずは、サンプルデータの作成から。
今回は3:3の合コンを想定してみましょう。解釈しやすくするために、男女に名前も付けておきます。

# 男性から見た女性の選好、女性から見た男性の選好のデータを作成します
set.seed(1)
prefM = cbind(sample(1:3), sample(1:3), sample(1:3))
prefW = cbind(sample(1:3), sample(1:3), sample(1:3))

# 解釈のため、メンバーに名前を付けておきます
colnames(prefM) = c("ひでき","ともき","たかし")
rownames(prefM) = c("みゆ","なつみ","ゆい")
colnames(prefW) = c("みゆ","なつみ","ゆい")
rownames(prefW) = c("ひでき","ともき","たかし")

上のコードを実行した結果を、表にしてみます。
まずは、prefM（男性から見た女性の選好）の中身を見てみます。

	ひでき	ともき	たかし
みゆ	1	1	3
なつみ	2	2	1
ゆい	3	3	2

男性から見た、女性の選好

ここで1つ注意点があります。
matchingRの計算では、数値が、選好の順序ではなく選好の大きさとして扱われています。
上の表だと、ひできは、ゆいを最も好きであり、みゆは最も好きでない、という解釈になります。
ともきは女の子に、ゆい、なつみ、みゆの順で好意を抱いています。ゆいが人気ですね。

上の点に注意して、prefW（女性からみた男性の選好）の中身も見ていきましょう。

	みゆ	なつみ	ゆい
ひでき	2	1	2
ともき	1	3	3
たかし	3	2	1

女性からみた、男性の選好

こちらも、念のため解釈を確認してみましょう。
なつみは、ともき、たかし、ひでき、の順で男性に好意を持っています。ゆいも、ともきを最も好いているようです。
女性からはともきが人気となっており、選好が重なっていてマッチングのしがいのあるデータになっています。

マッチング実行

それでは、マッチングを実行していきましょう。
“matchingR" がインストールされていない方は、インストールを済ませておいてください。
計算処理の実行は、1行で済みます。

# matchingRのインストール
install.packages("matchingR")

library(matchingR)
# 処理の実行
results <- galeShapley.marriageMarket(prefM, prefW)
results$proposals

実行すると、以下の結果が得られます。

# 実行結果
     [,1]
[1,]    2
[2,]    3
[3,]    1

結果を見ていきましょう。
1番目の男性は2番目の女性と、2番目の男性は3番目の女性と、3番目の男性は1番目の女性とマッチしている事が分かります。
ひできはなつみと、ともきはゆいと、たかしはみゆとマッチしたという結果です。

これが実際に良いマッチングになっているのかどうか、それぞれの選好から見ていきましょう。
マッチした組み合わせを赤字にしています。

男性からみた女性の選好	ひでき	ともき	たかし	女性からみた男性の選好	みゆ	なつみ	ゆい
みゆ	1	1	3	ひでき	2	1	2
なつみ	2	2	1	ともき	1	3	3
ゆい	3	3	2	たかし	3	2	1

男女それぞれからみた、異性の選好とマッチング結果

4人の男女は、最も好きな人とマッチできており、2番目に好きな人までで見ると、5人がマッチできている事がわかります。

なつみは最も選好の低かったひできとマッチする結果となっていましたが、
ともきもたかしも、それぞれがなつみよりも好きな女性とマッチできているので、駆け落ちは起こりません。
なつみには気の毒ですが、他の男女の幸せを願ってもらいましょう。

駆け落ちに関する補足

上の結果を見て、「ひできとともきは、女の子を交換した方が、全体の利得は大きくなるのでは…？」と考えた方がいらっしゃれば、非常に視点の鋭い方です。下の表で、ひできとともきが女子を取り換えた時の結果を見てみましょう。先程と同じく、ペアを赤文字で記します。

男性からみた女性の選好	ひでき	ともき	たかし	女性からみた男性の選好	みゆ	なつみ	ゆい
みゆ	1	1	3	ひでき	2	1	2
なつみ	2	2	1	ともき	1	3	3
ゆい	3	3	2	たかし	3	2	1