Subbab 16.4 Teorema Pencocokan Stabil

Sekarang kita menyajikan sebuah masalah optimisasi ringan dengan penyelesaian yang cukup cerdik, yang disebut Teorema Pencocokan Stabil. Terdapat \(n\) calon pembeli rumah \(b_1\text{,}\) \(b_2,\dots,b_n\) dan \(n\) calon penjual rumah \(s_1\text{,}\) \(s_2,\dots,s_n\text{.}\) Kita akan mengatur \(n\) penjualan rumah, masing-masing melibatkan satu pembeli dan satu penjual. Dalam prosesnya, kita akan berusaha membuat semua orang senang—atau setidaknya menjaga agar keadaan tetap stabil.

Setiap penjual mengurutkan para pembeli secara linear menurut preferensinya, yaitu, untuk setiap \(i=1,2,\dots,n\text{,}\) terdapat permutasi \(\sigma_i\) dari \([n]\) sedemikian sehingga, jika \(s_i\) lebih memilih \(b_j\) daripada \(b_k\text{,}\) maka \(\sigma_i(j)\gt \sigma_i(k)\text{.}\) Penjual yang berbeda dapat mempunyai urutan preferensi yang sangat berbeda. Demikian pula, setiap pembeli mengurutkan para penjual secara linear (sebenarnya, rumah yang mereka jual!) menurut preferensinya, yaitu, untuk setiap \(i=1,2,\dots,n\text{,}\) terdapat permutasi \(\tau_i\) dari \([n]\) sedemikian sehingga, jika \(b_i\) lebih memilih \(s_j\) daripada \(s_k\text{,}\) maka \(\tau_i(j)\gt\tau_i(k)\text{.}\)

Pertanyaannya adalah apakah kita selalu dapat menghasilkan pencocokan stabil, apa pun preferensi masing-masing pihak. Jawabannya adalah “ya”, dan terdapat argumen yang cerdik. Bahkan, argumen tersebut menghasilkan algoritma yang efisien. Mula-mula, setiap pembeli mengetuk pintu depan penjual yang menduduki urutan pertama dalam daftarnya. Mungkin ada penjual yang didatangi lebih dari satu calon pembeli, sedangkan penjual lain tidak didatangi siapa pun. Namun, jika seorang penjual didatangi satu atau lebih pembeli, penjual itu mengundang masuk pembeli yang paling disukainya dan menyuruh pembeli lainnya, jika ada, pergi. Setiap pembeli yang ditolak pada tahap ini mendatangi pintu depan rumah yang berada pada urutan kedua dalam daftarnya. Sekali lagi, penjual yang didatangi satu atau lebih pembeli, termasuk pembeli yang sebelumnya sudah diundang masuk jika ada, memilih yang terbaik di antara mereka dan menyuruh yang lain pergi. Proses ini berlanjut sampai akhirnya setiap penjual mempunyai tepat satu pembeli di rumahnya.

Menarik untuk dicatat bahwa prospek setiap penjual membaik seiring waktu, yaitu, setelah memperoleh seorang pembeli, pilihannya hanya menjadi lebih baik. Sebaliknya, prospek setiap pembeli memburuk seiring waktu. Bagaimanapun, kita menyatakan bahwa pencocokan yang dihasilkan bersifat stabil. Untuk melihatnya, andaikan pencocokan itu tidak stabil dan pilih pembeli \(b\) dan \(b'\) serta penjual \(s\) dan \(s'\) sedemikian sehingga \(b\) dicocokkan dengan \(s\text{,}\) \(b'\) dicocokkan dengan \(s'\text{,}\) tetapi \(b\) lebih memilih \(s'\) daripada \(s\) dan \(s'\) lebih memilih \(b\) daripada \(b'\text{.}\) Algoritma mengharuskan pembeli \(b\) mulai dari urutan teratas dalam daftarnya dan bergerak turun. Karena akhirnya ia berhenti di pintu penjual \(s\text{,}\) sedangkan ia lebih memilih \(s'\) daripada \(s\text{,}\) pada suatu tahap algoritma pembeli \(b\) pernah berada di pintu \(s'\text{,}\) lalu penjual \(s'\) menolak pembeli \(b\text{.}\) Artinya, tepat pada saat itu \(s'\) sedang mempertahankan pembeli lain \(c\) yang lebih disukainya daripada \(b\text{.}\) Karena pilihan yang dipertahankan setiap penjual hanya membaik seiring waktu, ketika pencocokan selesai penjual \(s'\) memiliki pembeli \(b'\) yang lebih disukainya daripada \(b\text{.}\) Oleh karena itu, pencocokan tersebut sebenarnya tidaklah tidak stabil.