Tidak dapat memahami bukti mengapa Algoritma Gale-Shapley mengawinkan setiap wanita dengan pasangan PESSIMALnya.
Saya baru disini. Ini adalah postingan pertama saya!
Hampir semua bukti untuk teorema ini menggunakan bukti dengan kontradiksi dan mereka berasumsi bahwa "harus ada perkawinan yang stabil $\mathcal M$ di mana seorang wanita menikah dengan pria yang dia sukai LEBIH KURANG dari pasangannya dalam The Mating Ritual. "
Pertanyaanku adalah; untuk tujuan kontradiksi, seharusnya kita tidak berasumsi bahwa "harus ada perkawinan yang stabil$\mathcal M$ di mana beberapa wanita menikah dengan pria yang dia sukai LEBIH dari pasangannya dalam The Mating Ritual. "
Karena di kepala saya sepertinya kami ingin menunjukkan bahwa setiap wanita TIDAK menikah dengan pasangan optimalnya. Sepertinya semua yang telah kami tunjukkan dalam bukti di bawah ini adalah bahwa seorang wanita tidak dapat melakukan lebih buruk daripada pasangannya yang pesimis. Saya yakin saya melewatkan sesuatu di sini!
Bukti lengkap untuk teorema ini di buku teks "Matematika untuk Ilmu Komputer" MIT ada di bawah (hanya bagian di atas yang tidak jelas bagi saya, yang lainnya masuk akal):
Teorema : The Mating Ritual mengawinkan setiap wanita dengan pasangan pesimalnya.
Bukti . Dengan kontradiksi. Asumsikan bahwa teorema tersebut tidak benar. Oleh karena itu, harus ada perkawinan yang stabil$\mathcal M$dimana beberapa wanita (sebut saja Nicole) menikah dengan seorang pria (panggil dia Tom) yang dia kurang suka dari pasangannya di The Mating Ritual (panggil dia Keith). Artinya:
Nicole lebih memilih Keith daripada Tom.
Kita tahu bahwa The Mating Ritual menikahkan setiap pria dengan pasangan optimalnya dan fakta bahwa Nicole dan Keith menikah dalam Ritual Mating, kita tahu bahwa
Keith lebih memilih Nicole daripada istrinya $\mathcal M$.
Ini berarti Keith dan Nicole merupakan pasangan nakal $\mathcal M$, yang bertentangan dengan stabilitas $\mathcal M$. $\blacksquare$
Bantuan sangat dihargai!
Jawaban
Jika klaim kami adalah "algoritma Gale-Shapley menetapkan setiap wanita pasangan pesimalnya", dan kami ingin membuktikannya dengan kontradiksi, maka kami ingin meniadakan pernyataan ini.
Penolakan dari pernyataan ini adalah bahwa tidak setiap wanita diberi pasangan pesimalnya di bawah Gale-Shapley. Dengan kata lain, ada beberapa wanita yang tidak ditugaskan sebagai pasangan pesimalnya (dalam pencocokan Gale-Shapley saya akan menelepon$\mathcal G$).
Mengikuti buktinya, hubungi wanita yang tidak ditugaskan menjadi pasangan pesimalnya $\mathcal G$ "Nicole", dan panggil pasangannya masuk $\mathcal G$ "Keith".
Apa artinya Keith bukan pasangan pesimalnya? Itu berarti bahwa pria lain, memanggilnya "Tom", adalah pasangannya yang pesimis. Dan apa artinya menjadi pasangan yang pesimal? Ini tidak berarti bahwa Nicole paling tidak menyukai Tom dari semua orang. Itu berarti bahwa Nicole paling tidak menyukai Tom dari semua orang yang mungkin dia nikahi dalam pasangan yang stabil. Khususnya:
- Harus ada beberapa pencocokan yang stabil$\mathcal M$yang cocok dengan Nicole dan Tom; itulah mengapa Tom adalah calon pasangan.
- Dalam pencocokan stabil apa pun , Nicole menikahi Tom atau orang lain yang lebih disukainya: itulah sebabnya Tom adalah pasangan yang pesimal.
- Secara khusus, dalam $\mathcal G$ (pencocokan kandang Gale-Shapley), Nicole lebih menyukai orang yang dinikahinya (Keith) daripada Tom.
Ini mencakup semua kesimpulan yang dibuat di paragraf pertama bukti.