安定な結婚問題

2003/04/01

東海大学理学部情報数理学科  松本哲志

ここ数年で、友人がほとんど結婚してしまいました。そこで、結婚に関する次のような問題がありますので、ご紹介したいと思います。

N人の男性とN人の女性がいます。彼らが集団お見合いをしました。 その結果、M1君がF1さんと M2君がF2さんと結婚したとします。 しかし、実はM1君がF2さんが好きであり、 F2さんもM1君が好きだったら、のちのち 問題が起こるかもしれません。

そこで、まず彼らはそれぞれ異性に対して好きな順に順序をつけます。
例えば、M1君は1番目がF2さん、 2番目がF3さんというふうに順序をつけるのです。

— 男性陣 —
M1の順序:F2 > F3 > F1
M2の順序:F2 > F1 > F3
M3の順序:F3 > F1 > F2

— 女性陣 —
F1の順序:M2 > M1 > M3
F2の順序:M1 > M3 > M2
F3の順序:M1 > M3 > M2

このときに、どのようにすれば安定した縁結びができるのかという問題です。情報数理学科の学生さんは是非考えてみてください。