ゲール・シャープレーアルゴリズムがすべての女性を彼女のPESSIMAL配偶者と結婚させる理由の証拠を理解することはできません。
私はここで新しいです。これは私の最初の投稿です！
この定理のほとんどすべての証明は、矛盾による証明を使用しており、「安定した結婚のセットがなければならない」と仮定しています。 $\mathcal M$ 交尾の儀式で、ある女性が配偶者よりも好きではない男性と結婚しているところです。」
私の質問は; 矛盾の目的のために、「安定した結婚のセットがなければならない」と仮定するべきではありません$\mathcal M$ 交尾の儀式で、ある女性が配偶者よりも好きな男性と結婚しているところです。」
私の頭の中では、すべての女性が彼女の最適な配偶者と結婚しているわけではないことを示したいように思われるからです。以下の証明で示したのは、女性は悲観的な配偶者よりも悪いことはできないということだけのようです。私はここで何かが欠けていると確信しています！
MITの「コンピュータサイエンスの数学」の教科書にあるこの定理の完全な証明は以下のとおりです（私にはわかりませんが、他のすべてが理にかなっているのは上記の部分だけです）。
定理：交尾の儀式は、すべての女性を悲観的な配偶者と結婚させます。
証明。矛盾によって。定理が真ではないと仮定します。したがって、安定した結婚のセットがなければなりません$\mathcal M$ある女性（彼女をニコールと呼ぶ）は、交尾儀式（彼をキースと呼ぶ）で彼女の配偶者よりも好きではない男性（彼をトムと呼ぶ）と結婚している。この意味は：
ニコールはトムよりキースを好む。
私たちは、交尾儀式がすべての人を彼の最適な配偶者と結婚させ、ニコールとキースが交尾儀式で結婚しているという事実を知っています。
キースは彼の配偶者よりニコールを好む $\mathcal M$。
これは、キースとニコールがで不正なカップルを形成することを意味します $\mathcal M$、これはの安定性と矛盾します $\mathcal M$。 $\blacksquare$
ヘルプは大歓迎です！
回答
私たちの主張が「ゲール・シャープレーアルゴリズムがすべての女性に悲観的な配偶者を割り当てる」であり、矛盾によってそれを証明したい場合は、このステートメントを否定したいと思います。
この声明の否定は、すべての女性がゲール・シャープレーの下で彼女の悲観的な配偶者を割り当てられているわけではないということです。言い換えれば、いくつかあり、彼女のpessimal配偶者が割り当てられていない女性は（ゲイル・シャプレーマッチングで、私は電話しますよ$\mathcal G$）。
証明に続いて、彼女の悲観的な配偶者を割り当てられていない女性を呼び出します $\mathcal G$ 「ニコール」、そして彼女の配偶者を $\mathcal G$ 「キース」。
キースが彼女の悲観的な配偶者ではないというのはどういう意味ですか？それは、彼を「トム」と呼ぶ他の誰かが彼女の悲観的な配偶者であることを意味します。そして、悲観的な配偶者であることはどういう意味ですか？ニコールがトムを一番好きだという意味ではありません。それは、ニコールがトムが安定したマッチングで結婚する可能性のあるすべての人の中で最も好きではないことを意味します。特に：
- なければならないいくつかの安定マッチング$\mathcal M$ニコールとトムに一致します。トムが潜在的な配偶者であるのはそのためです。
- で任意の安定マッチング、ニコール結婚トムまたは他の誰かのどちらか彼女がもっと好き：トムはpessimal配偶者である理由です。
- 特に、 $\mathcal G$ （ゲール・シャープレー安定結婚）、ニコールはトムよりも結婚する人（キース）が好きです。
これは、証明の最初の段落で行われたすべての結論をカバーしています。