Pemecah Masalah Pernikahan Stabil

Tentang Pemecah Masalah Pernikahan Stabil

Pemecah Masalah Pernikahan Stabil adalah implementasi interaktif dari algoritma Gale-Shapley deferred-acceptance, algoritma pencocokan tahun 1962 yang dibuktikan oleh David Gale dan Lloyd Shapley selalu menghasilkan pasangan yang stabil antara dua kelompok berukuran sama jika diberikan peringkat lengkap setiap anggota terhadap sisi lainnya. Alat ini mengambil daftar preferensi Anda, menjalankan algoritma langkah demi langkah, dan menunjukkan hasilnya sebagai pencocokan stabil, visualisasi bipartit beranimasi, heatmap preferensi, dan bukti terverifikasi bahwa tidak ada pasangan pemblokir.

Apa Itu Masalah Pernikahan Stabil?

Diberikan dua set yang terpisah dengan ukuran yang sama — misalnya n pria dan n wanita, atau n pelamar dan n posisi — serta daftar preferensi lengkap dari setiap anggota yang memberi peringkat pada setiap anggota di sisi lain, sebuah pencocokan adalah pemasangan satu-ke-satu antara kedua set tersebut. Pencocokan disebut stabil jika tidak ada pasangan (a, b) di luar pencocokan yang keduanya lebih suka bersama daripada tetap dengan pasangan yang ditugaskan kepada mereka.

Secara formal, pencocokan M stabil jika tidak ada pasangan pemblokir — yaitu pasangan (a, b) dengan a dipasangkan dengan b' dan b dipasangkan dengan a' sehingga:

Jika kedua kondisi tersebut terpenuhi, baik a maupun b akan meninggalkan pasangan mereka saat ini, yang membuat pencocokan menjadi tidak stabil. Pencocokan stabil adalah pencocokan di mana tidak ada pasangan seperti itu.

Algoritma Gale-Shapley

Gale dan Shapley membuktikan — secara konstruktif — bahwa pencocokan stabil selalu ada untuk set preferensi apa pun, dan mereka memberikan algoritma yang efisien untuk menemukannya. Algoritma ini berjalan dalam putaran:

1. Setiap pengusul yang tidak bertunangan mengajukan usulan kepada penerima peringkat tertinggi di daftar mereka yang belum menolak mereka.
2. Setiap penerima yang mendapat satu atau lebih usulan memilih yang paling mereka sukai (dibandingkan dengan tunangan sementara saat ini) dan menerimanya secara sementara; yang lainnya ditolak.
3. Pengusul yang ditolak menjadi bebas kembali dan pindah ke pilihan berikutnya pada putaran berikutnya.
4. Algoritma berakhir ketika setiap pengusul sudah bertunangan — yang dijamin akan terjadi dalam maksimal n² usulan.

Properti Teoretis Utama

Keberadaan & Keunikan

Pencocokan stabil selalu ada (Gale & Shapley, 1962), tetapi tidak selalu unik. Untuk set preferensi tertentu, bisa ada beberapa pencocokan stabil, dan mereka membentuk urutan kisi (lattice) berdasarkan preferensi bersama.

Optimalitas Pengusul

Ketika satu sisi mengusulkan, Gale-Shapley menghasilkan pencocokan stabil optimal-pengusul: setiap pengusul menerima pasangan terbaik yang mungkin bisa mereka dapatkan dalam pencocokan stabil mana pun. Dengan argumen simetris, ini juga merupakan pencocokan pesimal-penerima — sisi penerima mendapatkan pasangan stabil terburuk mereka. Mengubah sisi pengusul di kalkulator ini sering kali mengubah hasilnya.

Ketahanan Strategi bagi Pengusul

Di bawah Gale-Shapley, pengusul tidak memiliki insentif untuk salah melaporkan preferensi mereka: mengatakan yang sebenarnya adalah strategi dominan bagi mereka. Namun, penerima terkadang bisa mendapat untung dari pelaporan yang strategis — salah satu alasan pasar residen rumah sakit di Amerika Serikat dirancang dengan mahasiswa sebagai sisi pengusul.

Teorema Rumah Sakit Pedesaan

Set agen yang tidak cocok adalah identik di semua pencocokan stabil. Jadi, jika instansi Anda memiliki ukuran yang tidak seimbang (di luar cakupan alat klasik ini), orang yang sama akan tetap tidak cocok dalam setiap solusi stabil.

Format Input

Kalkulator ini mengharapkan satu baris per anggota, dengan nama diikuti oleh titik dua dan daftar preferensi lengkap yang dipisahkan oleh koma:

Persyaratan:

• Kedua grup harus memiliki jumlah anggota yang sama persis.
• Setiap anggota harus memberi peringkat pada setiap anggota grup lainnya — tidak boleh ada daftar parsial.
• Nama dapat menggunakan huruf, angka, garis bawah, tanda hubung, spasi, dan huruf Unicode umum.
• Mendukung hingga 15 anggota per sisi untuk animasi interaktif yang cepat.

Cara Menggunakan Kalkulator Ini

1. Masukkan preferensi untuk Grup A di area teks kiri — satu baris per anggota, daftar peringkat lengkap.
2. Masukkan preferensi untuk Grup B di area teks kanan — satu baris per anggota, format yang sama.
3. Pilih sisi yang mengusulkan. Pilih Grup A atau Grup B. Coba keduanya untuk membandingkan hasil optimal-A vs optimal-B.
4. Klik "Selesaikan Pencocokan Stabil." Kalkulator akan menjalankan Gale-Shapley dan menghasilkan pasangan stabil, statistik, animasi, dan bukti stabilitas.
5. Geser animasi dengan kontrol putar / langkah / atur ulang untuk melihat setiap usulan, penerimaan, pertukaran, dan penolakan secara berurutan.
6. Periksa heatmap. Setiap sel menunjukkan peringkat; sel yang dikelilingi garis kuning membentuk pencocokan akhir — perhatikan seberapa tinggi atau rendah posisi sel tersebut untuk melihat seberapa "puas" masing-masing pihak.

Contoh Pengerjaan — Klasik 3×3

Pria: Alex, Bryan, Chris. Wanita: Bea, Claire, Diana. Preferensi:

Menjalankan Gale-Shapley dengan pria yang mengusulkan menghasilkan Alex–Bea, Bryan–Claire, Chris–Diana dalam satu putaran (setiap pilihan pertama pria cocok dengan wanita yang pilihan pertamanya adalah orang lain — tidak ada konflik). Pencocokan ini stabil: tidak ada pasangan pria-wanita yang keduanya akan lebih baik jika bertukar pasangan, jadi tidak ada pasangan pemblokir.

Aplikasi di Dunia Nyata

Mengapa Lloyd Shapley Memenangkan Hadiah Nobel

Pada tahun 2012, Royal Swedish Academy of Sciences menganugerahkan Hadiah Nobel Ekonomi kepada Lloyd Shapley (untuk teorinya, bersama David Gale yang telah wafat) dan Alvin Roth (untuk penerapan teori tersebut ke pasar nyata, termasuk merancang ulang pencocokan residensi medis AS dan jaringan pertukaran ginjal). Penghargaan tersebut mengutip "teori alokasi stabil dan praktik desain pasar."

Pertanyaan yang Sering Diajukan

Apa itu masalah pernikahan stabil?

Masalah pernikahan stabil menanyakan: jika diberikan dua kelompok berukuran sama di mana setiap anggota memberi peringkat semua anggota kelompok lainnya dari yang paling disukai hingga yang kurang disukai, dapatkah kita memasangkan semua orang sehingga tidak ada dua orang yang lebih suka meninggalkan pasangan mereka saat ini demi satu sama lain? Pasangan seperti itu disebut pencocokan stabil. Algoritma Gale-Shapley menyelesaikan masalah ini dalam waktu O(n²) dan selalu menemukan pencocokan stabil.

Bagaimana cara kerja algoritma Gale-Shapley?

Algoritma Gale-Shapley deferred-acceptance berjalan dalam putaran. Di setiap putaran, setiap pengusul yang saat ini belum bertunangan mengajukan usulan kepada penerima peringkat tertinggi dalam daftar mereka yang belum menolak mereka. Setiap penerima menerima sementara usulan terbaik yang diterima sejauh ini dan menolak sisanya; setiap pengusul yang tergeser menjadi bebas kembali. Algoritma berakhir ketika tidak ada pengusul yang bebas, yang terjadi dalam maksimal n² usulan.

Apakah pencocokan stabil itu unik?

Tidak. Sebuah instansi masalah pernikahan stabil dapat memiliki banyak pencocokan stabil. Namun, ketika satu sisi mengusulkan, Gale-Shapley selalu menghasilkan pencocokan stabil optimal-pengusul: setiap pengusul mendapatkan pasangan terbaik yang mungkin mereka dapatkan dalam pencocokan stabil apa pun. Secara simetri, ini juga merupakan pencocokan pesimal-penerima untuk sisi lainnya. Mengubah sisi pengusul sering kali menghasilkan pencocokan stabil yang berbeda.

Apa itu pasangan pemblokir?

Pasangan pemblokir adalah pasangan (a, b) yang saat ini tidak cocok di mana a lebih menyukai b daripada pasangannya saat ini DAN b juga lebih menyukai a daripada pasangannya saat ini. Jika ada pasangan pemblokir, pencocokan tersebut tidak stabil karena keduanya lebih suka berpasangan satu sama lain. Pencocokan stabil tidak memiliki pasangan pemblokir, yang diverifikasi kalkulator ini secara otomatis setelah setiap penyelesaian.

Apa aplikasi nyata dari pencocokan stabil?

Algoritma Gale-Shapley menggerakkan National Resident Matching Program yang menempatkan mahasiswa kedokteran ke residensi di Amerika Serikat, sistem pilihan sekolah di Boston dan New York, penerimaan perguruan tinggi di beberapa negara, rantai pertukaran donor ginjal, dan sistem penetapan teman sekamar. Lloyd Shapley dan Alvin Roth memenangkan Hadiah Nobel Ekonomi 2012 sebagian karena karya ini.

Apakah kedua grup harus berukuran sama?

Dalam formulasi klasik pernikahan stabil, ya. Kedua belah pihak harus memiliki jumlah anggota yang sama dan masing-masing harus memberikan peringkat lengkap untuk sisi lainnya. Varian yang tidak seimbang (seperti pencocokan stabil dengan daftar tidak lengkap atau masalah residen rumah sakit) memang ada tetapi membutuhkan algoritma yang dimodifikasi. Kalkulator ini mewajibkan ukuran yang sama dan daftar preferensi yang lengkap.

Bacaan Lebih Lanjut

• Stable marriage problem — Wikipedia
• Gale-Shapley algorithm — Wikipedia
• National Resident Matching Program — Wikipedia
• 2012 Nobel Prize in Economic Sciences — Shapley & Roth