Stabilitas untuk pasangan dalam Masalah Pencocokan Stabil

Dalam Matching Stabil Soal , dinyatakan bahwa ada dapat ada kasus di mana daftar orang bisa puas dengan keputusan mereka, namun daftar tidak dapat ketika algoritma dijalankan dengan proposal pria. $m$ $f$

Dari apa yang saya baca, kecocokan yang tidak stabil terjadi ketika dan lebih suka satu sama lain dengan pasangan mereka saat ini. $m$ $f$

Saya sedikit bingung dengan definisi Stable Matching untuk kasus ini. Saya akan membahas slide di sini .

Apakah pasangan stabil selama laki-laki puas meskipun preferensi perempuan belum cocok? $(m, f)$

combinatorics phwd
sumber

"Pria-pria itu puas" sedikit salah saji. Jika kita menjalankan algoritme Gale-Shapley tempat para pria melamar, kita akan berakhir dengan pencocokan stabil "pria-optimal". Ini adalah pencocokan yang secara keseluruhan terbaik untuk set pria di antara semua pertandingan stabil. Tetapi itu tidak berarti bahwa setiap orang cocok dengan pilihan pertamanya. Beberapa dari mereka masih ingin beralih jika mereka bisa; hanya saja tidak ada favorit mereka yang mau beralih dengan mereka. Dan beberapa wanita mungkin dicocokkan dengan pilihan pertama mereka, itu hanya belum tentu pencocokan stabil terbaik untuk wanita secara keseluruhan.

usul

Jawaban:

Ya, itu stabil. Tidak perlu menetapkan pilihan optimal untuk kedua belah pihak. Untuk membatalkan pernikahan, Anda memerlukan dua pesta yang bersedia, ketidakbahagiaan satu pihak dalam pernikahan tidak membuatnya tidak stabil di sini.

Kaveh
sumber

Oke, saya membaca kembali semuanya sekarang. Jadi pencocokan yang stabil di sini, ketika pria melamar, hanya memungkinkan untuk pilihan optimal dengan pria secara khusus "Man-optimalitas" sebagaimana dimaksud dalam slide, sehingga pasangan di mana wanita mendapatkan preferensi terbaik mereka tidak pernah tiba dalam algoritma ini tetapi hanya dalam versi di mana wanita berada yang melamar. Saya pikir saya membungkus kepala saya dengan stabil sekarang.

phwd