Gale-Shapley Algoritmasının neden her kadınla KESİN eşiyle evlendiğinin kanıtı anlaşılamıyor.
Ben burada yeniyim. Bu benim ilk yazım!
Bu teoremin neredeyse tüm kanıtları çelişkili ispat kullanır ve "istikrarlı bir evlilikler dizisi olması gerektiğini varsayarlar. $\mathcal M$ The Mating Ritual'da bir kadının eşinden DAHA AZ sevdiği bir erkekle evli olduğu yer. "
Sorum şu; çelişki amacıyla, "istikrarlı bir evlilikler dizisi olması gerektiğini varsaymamalıyız$\mathcal M$ The Mating Ritual'da bir kadının eşinden daha çok sevdiği bir erkekle evli olduğu yer. "
Çünkü aklımda her kadının en uygun eşiyle evli olmadığını göstermek istiyoruz gibi görünüyor. Görünüşe göre aşağıdaki kanıtta gösterdiğimiz tek şey bir kadının karamsar eşinden daha kötüsünü yapamayacağıdır. Eminim burada bir şey kaçırıyorum!
MIT'nin "Bilgisayar Bilimleri için Matematik" ders kitabındaki bu teoremin tam kanıtı aşağıdadır (sadece yukarıdaki kısım benim için açık değildir, diğer her şey mantıklıdır):
Teorem : Çiftleşme Ritüeli, her kadını karamsar eşiyle evlendirir.
Kanıt . Çelişki yoluyla. Teoremin doğru olmadığını varsayın. Bu nedenle istikrarlı bir evlilikler dizisi olmalı$\mathcal M$Bir kadının (ona Nicole deyin) The Mating Ritual'daki (ona Keith deyin) eşinden daha az sevdiği bir erkekle evli olduğu (ona Tom deyin). Bu şu demek:
Nicole, Keith'i Tom'a tercih eder.
The Mating Ritual'ın her erkeği en uygun eşiyle evlendirdiğini ve Nicole ile Keith'in Çiftleşme Ritüeli'nde evli olduğunu biliyoruz, bunu biliyoruz.
Keith, Nicole'u eşine tercih ediyor $\mathcal M$.
Bu, Keith ve Nicole'un $\mathcal M$istikrarı ile çelişen $\mathcal M$. $\blacksquare$
Yardım çok takdir edilmektedir!
Yanıtlar
İddiamız "Gale-Shapley algoritması her kadına kötümser eşini veriyor" ise ve biz bunu çelişki ile ispatlamak istiyorsak, bu ifadeyi çürütmek istiyoruz.
Bu ifadenin olumsuz yanı, her kadına kötümser eşinin Gale-Shapley altında atanmamasıdır. Başka bir deyişle, karamsar eşi atanmamış bir kadın var (arayacağım Gale-Shapley eşleşmesinde$\mathcal G$).
Kanıtı takiben, karamsar eşi atanmamış kadını arayın. $\mathcal G$ "Nicole" ve eşini içeri çağırın $\mathcal G$ "Keith".
Keith'in karamsar eşi olmadığı ne anlama geliyor? Bu, ona "Tom" diyen başka bir adamın karamsar eşi olduğu anlamına gelir . Ve karamsar eş olmak ne demektir? Bu Nicole'un Tom'u herkesten az sevdiği anlamına gelmez. Bu, Nicole'ün istikrarlı bir eşleşmede muhtemelen evlenebileceği herkesten en az Tom'u sevdiği anlamına geliyor. Özellikle:
- Olmalı bazı istikrarlı eşleştirme$\mathcal M$Nicole ve Tom ile eşleşen; bu yüzden Tom potansiyel bir eş.
- Herhangi bir istikrarlı eşleşmede Nicole ya Tom'la ya da daha çok sevdiği biriyle evlenir: Tom bu yüzden karamsar eştir.
- Özellikle $\mathcal G$ (Gale-Shapley sabit eşleşmesi), Nicole evlendiği kişiyi (Keith) Tom'dan daha çok seviyor.
Bu, ispatın ilk paragrafında yapılan tüm sonuçları kapsar.