安定結婚問題の「絶望の定理」の証明

投稿者: Anonymous

グラフ理論において、安定結婚問題があります。

ある2部グラフの特定の安定マッチングにおいて、ペアを作れなかった人(たとえば男性数>女性数でのマッチングで存在)は、どのような安定マッチングにおいてもペアが作れないことを、安定結婚問題における「絶望の定理」と呼ぶらしいのですが、この定理の証明を見つけられずにいます。

証明自体、もしくは証明のソースをご存知の方はいらっしゃいますでしょうか。

解決

@argus さんの情報を情報をもとに、調べて行った結果、

https://cs.stackexchange.com/a/37942/37273
(man-oriented な Gale-Shapley で man-optimal (最大元)かつ woman-pessimal (最小元)が得られる)

https://math.stackexchange.com/q/978729/260854
(1. optimal, 任意の matching, pessimal の3つの間で、パートナーの有無は、単調増加(語弊あり?)する
2. ある参加者のパートナーの有無が stable matching 間で変わったとすると、1. の結果から玉突き事故のようなことが起こってしまうので、そんなことは起こらない)

によって、説明できそうでした。

回答者: Anonymous

Leave a Reply

Your email address will not be published. Required fields are marked *