Kestabilan model perkawinan dengan menggunakan algoritma deferred acceptance

Abstract

Model perkawinan membahas tentang pemilihan antara sekelompok pria terhadap sekelompok wanita ataupun sebaliknya, sehingga setiap orang dalam kelompok tersebut mendapat pasangan dari kelompok lain. Keadaan inilah yang dinamakan matching. Untuk memperoleh matching yang stabil harus diperiksa setiap pasangan dalam setiap kemungkinan matching yang terjadi apakah tiap-tiap pasangan dalam matching tersebut terdapat pria atau wanita yang lebih tertarik dengan pria ataupun wanita lain daripada pasangannya dalam matching tersebut. Keadaan inilah yang dinamakan blocking pair. Jika terdapat satu saja pasangan yang membentuk blocking pair maka matching menjadi taksstabil. Namun untuk menunjukkan bahwa dalam setiap pasangan tidak terdapat blocking pair sangat rumit dan panjang jika banyaknya pria maupun wanita cukup banyak. Karena itu diperlukan suatu algoritma yang secara pasti akan mendapatkan matching yang stabil pad saat algoritma berakhir. Algoritma ini disebut Algoritma Deferred Acceptance. Algoritma Deferred Acceptance dapat dilakukan dengan dua cara berbeda walaupun pada dasarnya mempunyai cara kerja yang sama, yaitu: Algoritma Penawaran Pria dan Algoritma Penawaran Wanita. Dengan kedua algoritma ini akan didapatkan matching stabil yang pada saat matching terbentuk, setiap pria akan berpasangan dengan seorang wanita kecuali pada kasus ketika banyaknya pria tidak sama dengan banyaknya wanita.