go the distance

研究と教育に関するあれこれ。

研究室訪問

卒業研究をどの研究室でするか。

3年生にとっては重大な問題。

先週から今週にかけて、ラボ訪問期間でした。多くの(といっても10名くらい)学生と面談しました。

 

今年度から本学では、研究室配属を「学生と教員の2集団間の最適なマッチング解を導く活動」とみなし、「受け入れ保留方式」というアルゴリズムで行うことになりました。

 論文「男女の結婚」では、同理論の例証として男女10人ずつについて各自の好みを尊重しながらマッチング主催者が最適に組み合わせる方法を示した。具体的な手順は次のようなものである。
 まず第一段階で、男性全員が第一希望の女性にプロポーズする。複数の男性からプロポーズを受けた女性は最も気に入った男性のプロポーズを受け入れる。一人の男性からだけプロポーズされた女性もそのプロポーズを受け入れる。誰からもプロポーズされなかった女性は次を待つ。
 第二段階で、第一希望の女性に断られた男性たちが第二希望の女性にプロポーズする。このとき、第一段階ですでに他の男性のプロポーズを受け入れている女性も、独身として第二希望の女性に含めることができる。
 このように男性たちの希望リストが最後の女性に至るまで、この手順を繰り返す。ただし、女性は前の段階でプロポーズを受け入れていても、より好ましい男性からプロポーズされれば、すでに受け入れたプロポーズを解消できる。こうして最終的に全員がパートナーを獲得できる。

 したがって、どんなに人びとの好みが多様でも、安定的なマッチングが必ず存在することを示すことができるのである(ゲール=シャプレー・アルゴリズム(計算方式))。この手順のポイントは、プロポーズを受け入れてもすぐには結婚せず、最後まで保留している点である。そのため、「受け入れ保留アルゴリズム」ともいわれる。

http://www.tdb-di.com/column/1210/index2.html

 

学生も私も満足できる解が得られるか、配属結果が楽しみです。