Algoritma Gale-Shapley
- Diperkenalkan oleh
- David Gale, Lloyd Shapley
- Tahun
- 1962
- Jenis
- algorithm
- Keluarga
- Game-theoretic
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Algoritma Gale-Shapley memecahkan masalah perkawinan stabil: bagaimana mencocokkan dua kelompok (misalnya, residen medis dengan rumah sakit, siswa dengan sekolah) sedemikian rupa sehingga tidak ada pasangan yang lebih memilih satu sama lain daripada pasangan yang ditugaskan.
Diperkenalkan oleh David Gale dan Lloyd Shapley pada tahun 1962, algoritma ini menjamin pencocokan yang stabil dalam waktu polinomial melalui proses penerimaan yang ditunda di mana satu pihak mengajukan proposal secara berurutan dan pihak lain merespons, merevisi pilihan saat pilihan yang lebih baik tiba.
Intuisi di balik metode
Bayangkan mencocokkan dokter dengan rumah sakit. Algoritma ini bekerja seperti permainan kursi musik: setiap dokter mengajukan proposal ke rumah sakit yang paling disukainya; setiap rumah sakit menerima dokter terbaik yang tersedia untuk sementara. Saat rumah sakit menerima proposal yang lebih baik, mereka merevisi pilihan mereka, berpotensi menolak penerimaan sebelumnya. Dokter yang ditolak mengajukan proposal ke rumah sakit pilihan berikutnya. Proses berlanjut sampai tidak ada dokter yang ingin mengajukan proposal lebih lanjut dan tidak ada rumah sakit yang ingin menukar pasangan mereka saat ini. Hasilnya stabil: tidak ada pasangan dokter-rumah sakit yang keduanya lebih memilih untuk dicocokkan satu sama lain daripada pasangan yang ditugaskan.
Sejarah
David Gale dan Lloyd Shapley menerbitkan solusi mereka untuk masalah perkawinan stabil pada tahun 1962, membuktikan bahwa pencocokan yang stabil selalu ada untuk pasar dua sisi. Algoritma mereka memunculkan literatur luas tentang teori pencocokan dengan aplikasi yang mencakup kedokteran, pendidikan, dan pasar tenaga kerja. Pada tahun 2012, Alvin Roth memenangkan Hadiah Nobel Ekonomi atas karya eksperimental dan teoritisnya dalam menerapkan teori pencocokan ke desain pasar nyata, memvalidasi pentingnya praktis kerangka kerja Gale-Shapley.
Kapan digunakan
Terapkan algoritma Gale-Shapley saat mencocokkan pasar dua sisi di mana stabilitas sangat penting: penempatan residen medis, penugasan siswa ke sekolah, pertukaran ginjal, pencocokan pasar tenaga kerja, atau pasar kencan online. Gunakan ketika ada risiko ketidakstabilan pencocokan (pasangan pemblokir) yang dapat merusak pencocokan setelah penugasan. Algoritma ini ideal ketika satu pihak dapat bergerak lebih dulu dengan keuntungan strategis.
Batasan dan pertimbangan
- Tidak optimal Pareto: pencocokan mungkin tidak memaksimalkan kesejahteraan total; pasangan pemblokir mungkin ada yang semuanya mendapat manfaat dari bertukar pasangan
- Kerentanan strategis: pihak pengusul dapat memperoleh keuntungan dengan salah merepresentasikan preferensi, sementara pihak yang merespons bersifat jujur
- Asimetri: hasil sangat bergantung pada pihak mana yang mengajukan proposal terlebih dahulu
- Tidak menangani kendala: sulit untuk memasukkan preferensi kompleks (misalnya, pasangan, preferensi regional) tanpa modifikasi algoritma
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Stabilitas terjamin: tidak ada pasangan pemblokir dalam pencocokan akhir
- Waktu polinomial: kompleksitas O(n^2), membuatnya efisien untuk populasi besar
- Implementasi sederhana: mudah dieksekusi dalam praktik dengan pengumpulan preferensi yang transparan
- Insentif strategis: pihak pengusul memiliki keuntungan strategis, lebih memilih proposal awal daripada yang terakhir
- Dapat diterapkan secara universal: berfungsi untuk profil preferensi apa pun tanpa mengasumsikan konveksitas atau transitivitas
Penerapan
- Pencocokan residensi medis: memasangkan lulusan sekolah kedokteran dengan program residensi rumah sakit melalui NRMP
- Pilihan sekolah: menugaskan siswa ke sekolah negeri berdasarkan preferensi dan batasan kapasitas
- Pertukaran ginjal: mencocokkan donor dan penerima organ untuk memaksimalkan transplantasi yang kompatibel
- Pencocokan pasar kerja: menghubungkan pencari kerja dengan pemberi kerja di pasar tenaga kerja dua sisi
- Kencan online: mencocokkan pengguna di platform kencan untuk meningkatkan stabilitas pencocokan dan kepuasan pengguna
Cara kerjanya
Cara kerjanya
Buat daftar preferensi untuk semua individu di kedua kelompok, yang mewakili peringkat mereka terhadap pihak lain.
Dalam setiap putaran, setiap orang yang belum cocok di pihak pengusul mengajukan proposal kepada orang yang paling disukai di pihak lain yang belum pernah mereka ajukan proposal sebelumnya.
Setiap orang di pihak penerima sementara menerima proposal jika mereka belum cocok, atau jika pengusul memiliki peringkat lebih tinggi daripada pasangan mereka saat ini, dalam hal ini mereka mencabut pertunangan sebelumnya.
Algoritma berhenti ketika setiap orang cocok dan tidak ada proposal lebih lanjut yang terjadi, menghasilkan pencocokan yang stabil.
Kesalahan umum
- Mengasumsikan stabilitas saja sudah cukup untuk keadilan atau kesejahteraan; pencocokan yang stabil bisa sangat condong ke satu pihak
- Mencampuradukkan stabilitas dengan optimalitas; pencocokan yang stabil belum tentu memaksimalkan kesejahteraan
- Mengabaikan keuntungan strategis pihak pengusul: anggota pihak pengusul cenderung cocok dengan pasangan berperingkat lebih tinggi
- Lupa bahwa algoritma mengasumsikan daftar preferensi lengkap; preferensi yang tidak lengkap memerlukan modifikasi
Pertanyaan yang sering diajukan
Mengapa stabilitas penting dalam pencocokan?
Tanpa stabilitas, pasangan yang cocok mungkin kemudian menemukan bahwa mereka lebih memilih satu sama lain daripada pasangan yang ditugaskan, menciptakan insentif untuk mengakhiri pencocokan. Pencocokan yang stabil mencegah pasangan pemblokir semacam itu, memastikan pencocokan tetap ada tanpa negosiasi ulang.
Apakah algoritma Gale-Shapley selalu menghasilkan pencocokan yang sama?
Tidak. Daftar preferensi yang berbeda atau urutan proposal dapat menghasilkan pencocokan yang stabil yang berbeda. Namun, selalu ada pencocokan stabil yang 'optimal untuk pria' (terbaik untuk semua pengusul) dan pencocokan stabil yang 'optimal untuk wanita' (terbaik untuk semua penerima).
Bagaimana Gale-Shapley menangani preferensi atas kelompok (misalnya, pasangan)?
Algoritma standar tidak secara langsung menangani pasangan atau kendala lainnya. Ekstensi seperti algoritma pasangan ada tetapi lebih kompleks dan mungkin tidak menjamin stabilitas untuk semua profil preferensi.
Metode terkait
Sumber
Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9-15.
Buka referensi DOIDisalin.Roth, A. E. (1984). The economics of matching: Stability and incentives. Mathematics of Operations Research, 7(4), 617-628.
Buka referensi DOIDisalin.