Perpanjangan Masalah Pernikahan Stabil?

11

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?

IgorCarron
sumber
1
Kedengarannya seperti pertanyaan yang menyenangkan, terutama jika Anda tinggal di Utah!
Dave Clarke
1
Pertanyaannya agak terbuka. Secara alami Anda dapat menjamin bahwa solusi untuk masalah teman sekamar yang stabil ada jika Anda mengubah definisi pasangan pemblokiran dan / atau membatasi struktur preferensi pencocokan. Sebagai contoh sepele, Anda dapat menemukan rumusan masalah di mana setiap pencocokan maksimal adalah "stabil", dan kemudian ada algoritma serakah sederhana untuk menemukan pencocokan tersebut. Tapi saya rasa ini bukan yang ingin Anda dengar; bisakah Anda menguraikan lebih banyak?
Jukka Suomela
1
Dua buku bagus tentang Masalah Pernikahan Stabil dan kerabatnya adalah: Pencocokan Dua Sisi oleh Alvin Roth dan Marilda Sotomayor dan Masalah Pernikahan Stabil oleh Dan Gusfield dan Robert W. Irving.
Joseph Malkevitch
1
"Pernikahan yang stabil dan hubungannya dengan masalah kombinatorial lainnya" oleh Knuth juga direkomendasikan. Anda dapat menemukan versi pindaian edisi Prancis di situs web: www-cs-faculty.stanford.edu/~uno/ms.html
Dai Le

Jawaban:

11

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:

  • N
  • Sebuah makalah yang menunjukkan berbagai aplikasi untuk lemma penting Syal dan mengutip beberapa lainnya: (Secara khusus, versi fraksional teorema Gale-Shapley untuk hypergraphs oleh Aharoni dan Holzman dijelaskan): R. Aharoni, dan T. Fleiner, On a lemma dari Scarf, J. Combin. Teori Ser. B 87 (2003), 72--80.
  • Sebuah solusi dari masalah pria-wanita-anjing ketika ada paling banyak 4 dari setiap jenis kelamin muncul dalam sebuah makalah oleh Eriksson et al (Math Soc Sci 2006).
Gil Kalai
sumber
@Prof. Kalai: Tolong tunjukkan saya referensi yang bagus tentang kondisi inti Scarf yang tidak kosong untuk kasus pernikahan yang stabil?
Dai Le
Coba kertas asli Scarf yang saya tambahkan ke jawabannya.
Gil Kalai
10

Apa yang Anda tanyakan tidak lagi disebut "Masalah Pernikahan yang Stabil." Sebaliknya, ini disebut "Masalah Teman Sekamar Yang Stabil." Menurut Wikipedia :

Dalam matematika, terutama dalam bidang teori permainan dan kombinatorik, masalah teman sekamar stabil (SRP) adalah masalah menemukan pencocokan stabil - pencocokan di mana tidak ada pasangan elemen, masing-masing dari set pasangan yang berbeda, di mana setiap anggota dari pasangan lebih suka yang lain untuk pertandingan mereka. Ini berbeda dari masalah pernikahan stabil karena masalah teman sekamar stabil tidak mengharuskan satu set dipecah menjadi himpunan bagian pria dan wanita. Siapa pun dapat memilih siapa pun dalam set yang sama.

Biasanya dinyatakan sebagai:

Dalam contoh tertentu dari masalah Teman Sekamar Stabil (SRP), masing-masing peserta 2n memberi peringkat yang lain dalam urutan preferensi yang ketat. Pasangan yang cocok adalah seperangkat pasangan peserta yang terpisah (tidak berurutan). M yang cocok dalam instance SRP stabil jika tidak ada dua peserta x dan y, yang masing-masing lebih suka yang lain daripada pasangannya di M. Pasangan semacam itu dikatakan memblokir M, atau menjadi pasangan pemblokiran sehubungan dengan M.

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:

  1. Setidaknya sebagian orang tertentu puas dengan teman sekamarnya. Di sini, kepuasan dapat diartikan berbeda. Misalnya:
    • Sepasang (x, y) dikatakan puas jika y adalah pilihan pertama x, dan sebaliknya.
    • Sepasang (x, y) dikatakan puas jika salah satu dari x atau y adalah pilihan pertama orang lain.
    • Sepasang (x, y) dikatakan tidak puas jika ada pasangan (z, w) sehingga x suka z lebih dari y, dan z suka x lebih dari w.
    • ...
  2. Paling tidak sebagian kecil orang tidak puas dengan teman sekamarnya. (Persyaratan ini mungkin berbeda bahwa di atas tergantung pada interpretasi kepuasan .)
MS Dousti
sumber
Saya kira OP sudah mengetahui semua ini, dan pertanyaannya adalah bagaimana mengubah aturan permainan sehingga pencocokan yang stabil dijamin ada.
Jukka Suomela
Juga, contoh tandingan paling sederhana melibatkan 4 simpul di mana preferensi pertama dan kedua dari 3 dari mereka mendefinisikan 3 siklus.
Per Vognsen
2
Saya kira orang biasanya menggunakan istilah "pencocokan stabil" untuk merujuk pada varian masalah apa pun, dan "pernikahan stabil" vs. "teman sekamar stabil" jika mereka ingin menekankan bahwa mereka mempelajari versi masalah bipartit vs non-bipartit. . Tapi seperti biasa, yang terbaik adalah mendefinisikan persyaratan Anda dan tidak menganggap bahwa ini adalah standar ...
Jukka Suomela
Saya ragu untuk memilih jawaban ini karena paragraf pertama, yang tampaknya hanya menyinggung beberapa orang.
Tsuyoshi Ito
@ Tsuyoshi Ito: Saya tidak bermaksud menyinggung siapa pun. Setelah berpikir dua kali, saya menghapus paragraf pertama sekaligus.
MS Dousti
7

nm

mhum
sumber
Tapi ini lagi-lagi pencocokan bipartit: Anda memiliki dua jenis entitas yang berbeda, "orang" vs "rumah" (sama seperti Anda memiliki "pria" vs "wanita" dalam masalah pernikahan stabil tradisional). Pertanyaannya tampaknya secara khusus tentang pencocokan non-bipartit.
Jukka Suomela
Anda mungkin ada benarnya. Saya berpikir masalah ini dapat mengatasi "masyarakat di mana sebagian populasi tertentu mengikuti serangkaian aturan yang berbeda dari kelompok yang lebih besar".
mhum
Begitu ya, saya pikir itu merujuk pada masyarakat di mana kita memiliki sub-populasi homoseksual. Mari kita lihat apakah kita mendapatkan klarifikasi untuk pertanyaan itu.
Jukka Suomela
Ya yang saya maksudkan adalah masyarakat di mana kita memiliki subset dari populasi yang berperilaku dengan seperangkat aturan yang berbeda.
IgorCarron