Algoritma Gale-Shapley

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.