Ini mungkin terdengar lebih seperti pertanyaan ilmu sosial lebih dari yang TCS, tetapi tidak. Saat membaca " Algoritma Acak " yang menggambarkan Masalah Pernikahan yang Stabil, orang dapat membaca yang berikut (p54)
"Dapat ditunjukkan bahwa untuk setiap pilihan daftar preferensi terdapat setidaknya satu pernikahan yang stabil. (Anehnya, ini tidak terjadi dalam masyarakat monogami homoseksual dengan jumlah penduduk genap) ..."
Apakah ada ekstensi yang sangat sederhana dari Masalah Pernikahan Stabil yang memungkinkan beberapa jenis kondisi mapan yang mencakup masyarakat monogami homoseksual, atau masyarakat di mana sekelompok populasi tertentu mengikuti serangkaian aturan yang berbeda dengan aturan yang lebih besar?
Dalam afirmatif, apakah ada algoritma yang melakukan pencocokan seperti itu?
sumber
Jawaban:
Ada dugaan terbuka mengenai 3 tipe orang. Misalkan Anda memiliki pria dan wanita pria sehingga pria memiliki daftar preferensi pada wanita, wanita memiliki daftar preferensi pada anjing, dan anjing memiliki daftar preferensi pada pria. Apakah selalu ada pernikahan yang stabil?
(Untuk struktur preferensi lain pada masyarakat tipe 3, jawabannya diketahui negatif).
Komentar lain adalah bahwa pernikahan yang stabil mewakili inti yang tidak kosong dan ada kondisi yang diketahui oleh Scarf yang menyiratkan adanya inti yang tidak kosong. Diketahui bahwa kondisi Syal puas untuk masalah pernikahan stabil asli dan untuk masalah alokasi rumah. (Tetapi gagal untuk masalah pria / wanita / anjing).
Beberapa referensi:
sumber
Apa yang Anda tanyakan tidak lagi disebut "Masalah Pernikahan yang Stabil." Sebaliknya, ini disebut "Masalah Teman Sekamar Yang Stabil." Menurut Wikipedia :
Wikipedia membahas jawaban untuk pertanyaan Anda. Dikatakan kasus stabil tidak selalu dapat ditemukan, namun, ada algoritma yang efisien, karena Irving (1985), yang akan menemukan pencocokan tersebut jika ada.
Edit:
Beberapa relaksasi alami dapat dipahami oleh SRP: Alih-alih mensyaratkan bahwa "tidak ada dua peserta x dan y, masing-masing lebih suka yang lain daripada pasangannya di M," yang satu dapat mensyaratkan bahwa:
sumber
sumber