Sevgili Gelişen Kariyerim okuyucuları, sizce ilişkilerimizi eşleşme algoritmasıyla kontrol edebilir miyiz? Hayatın dijitalleşmesiyle birlikte insanlar, diğer insanlarla internet üzerinden iletişim kurmaya başladı. İnternet ortamında sevgili ve eş bulan insanların sayısı oldukça çoğaldı ve popülerleşti. Bununla birlikte bunu sağlayan internet siteleri ve mobil uygulamalar da popüler bir hale geldi. Uygulamalar ve sitelerin işleyişleri farklılıklar barındırsa da ana temanın, kadınların ve erkeklerin eşlerinde görmek istedikleri kriterleri seçmeleri ve eşleşmenin bunun üzerinden yapılıyor olması. Karşılıklı olarak kriterleri uygun olan iki kişi eşleşip konuşuyor ve tanışıyorlar. Kararlı eşleşme problemi; elaman sayıları eşit olan iki küme arasında, tüm elamanları içeren en optimal eşleşmeyi bulmayı amaçlar. Sonuçta tüm elemanlar eşleneceği için problem kararlı olacaktır. Bu yazıda bu eşleşme problemine çözüm sunan, David Gale ve matematikçi Lloyd Shapley tarafından oluşturulan bir de Nobel ödülü almış bir algoritmadan bahsedeceğim.
İçindekiler
Gale – Shapley Kararlı Eşleşme Algoritması
Bu algoritma ilk olarak öğrenci-okul yerleştirmelerinde kullanılmıştır. Gale ve Shapley algoritmada öğrencilerin okullara mutlu olacakları biçimde yerleştirmeyi amaçlamıştır. Ancak kayıtlara kararlı eşleşme problemi olarak geçmiştir.
İki taraflı eşleşme algoritmaları birbirinden bağımsız iki kümenin tarafların istekleri veya belirlenen kısıtlar doğrultusunda en iyi şekilde eşleşmesini sağlayan algoritmalardır. Gerçek hayat problemlerinden örnek verilecek olursa, okullara öğrenci atanması, üniversitelere öğrenci yerleştirilmesi ve stajyerlerin hastanelere yerleştirilmesi gibi problemlerden bahsedilebilir. Çok tercihli yerleştirme problemi taraflardan en az birinin gerçekleşecek eşleşme için tercih bildirdiği problemlerdir. Tek taraf tercih yaparsa tek taraflı, iki tarafta tercih yaparsa çift taraflı eşleşme problemi olur. Dikkatinizi çekmek isterim ki, kararlı eşleşme probleminde iki tarafında tercihleri var. Yani aslında çift taraflı eşleşmeden bahsediyoruz.
Hadi bu algoritmanın adımlarına bir göz atalım.
Algoritmanın Adımları
1: Erkekler ve kadınlar çekicilik sırasına göre birbirini sıralar.
2: Her erkek, en üst sıradaki kadına bir evlilik teklifi yapar. Bir veya daha fazla evlilik teklifi alan kadın alınan teklifler arasında tercihlerinde en yüksek sırada olan hariç tümünü reddeder.
k (k>2) : Önceki turda reddedilen bir erkek, en üst sıradaki kendisini reddetmemiş olan kadına teklif verir.
Dur: Yeni evlilik teklifi yapılmadığında algoritma sona erer. Bu noktada her kadının tam olarak kabul ettiği bir teklifi var.
Kısaca algoritmanın ilk adımı adayların birbirlerini sıralamasıyken, ikinci adımı ise her erkeğin, en beğendiği kadına evlilik teklifi etmesiyle başlar. Bir veya daha fazla evlilik teklifi alan kadınlar ise alınan teklifler arasında kafasında oluşturduğu sırada en beğendiği hariç diğerlerini, reddeder. Kabul ettiği erkek ile nişanlanır. Eğer diğer turlarda daha beğendiği bir erkek tarafından evlilik teklifi gelir ise nişanı bozup bu yeni adam ile nişanlanır. Önceki turda cevap alamayan bir erkek ise, diğer en çok beğendiği kendisini reddetmemiş olan kadına evlilik teklifi eder. Algoritma yeni bir evlilik teklifi olmadığında sona erer. Bu noktada her kadının tam olarak kabul ettiği bir teklifi olur.
Algoritmada dikkat edilmesi gereken husus, erkek ve kadın sayısının eşit olması ve ilk mesajı atan tarafın sonuç için önemli olması. Sonuçlar teklif eden taraf için en iyi sonuçlardır. Buna rağmen, her iki durumda da tarafların karşılıklı olarak eş değiştirmeye istekli olduğu başka bir eşleşme olmadığı için eşleşmeye, kararlı bir eşleşmedir diyebiliriz. Bir kararlı eşleme problemi örneğiyle algoritmayı daha iyi anlayalım.
Evlilik Websitesi Örneği
Bugün bir evlilik sitesine kayıt olmuş Şükrü’yü düşünelim. Şükrü siteye kaydolduktan sonra adaylara bakıyor ve üç tane kadın aday olduğunu görüyor. Bu adaylar: Fatma, Hasibe, Ayşe. Kendi kriterleri doğrultusunda, bu kadınları en beğendiğinden daha az beğendiğine doğru kafasında sıraya koyuyor. En beğendiği kadın Hasibe. Ancak sitede Şükrü’nün rakipleri de bulunmakta. Kendi dışında iki erkek daha var: Hüsnü ve Celal. Diğer erkeklerin de aklında kendi beğendikleri kadınlardan oluşan sıralı listeleri bulunuyor ve hatta kadınların da. Kararlı eşleşme problemi adaylarının tercih listeleri şöyle olsun:
Şükrü: Hasibe, Ayşe, Fatma
Hüsnü: Hasibe, Ayşe, Fatma
Celal: Ayşe, Fatma, Hasibe
Hasibe: Celal, Hüsnü, Şükrü
Ayşe: Hüsnü, Celal, Şükrü
Fatma: Celal, Hüsnü, Şükrü
Adaylar birbirlerini en beğendiklerinden en az beğendiklerine doğru sıraladılar. Şükrü beklemek istemiyor ve Hasibe’ ye mesaj atıyor. Ancak Hasibe mesajına dönmüyor. Çünkü Şükrü’den başka Hasibe’ ye Hüsnü’de mesaj atmıştı. Hasibe Hüsnü’yü Şükrü den daha çok beğendiği için Hüsnü’ye cevap veriyor. Ancak Hasibe’nin asıl beğendiği kişi ise Celal. Bu yüzden, diğer turlarda Celal’den mesaj gelirse Lütfü’yü bırakıp yoluna Celal ile devam edecek. Şükrü’ye ne olacak derseniz, Şükrü vazgeçmeyecek. İkinci turda Hasibe’den sonraki en beğendiği kadına yani Ayşe’ye mesaj atıp, cevap vermesini umacak. Algoritma sona erdiğinde eşleşmeler aşağıdaki gibi olacaktır:
Hasibe-Hüsnü, Ayşe-Celal, Şükrü-Fatma
Bu atama kararlı olmasına rağmen optimal değildir.
Ayşe-Hüsnü, Hasibe-Celal , Fatma-Şükrü
şeklinde eşleşmiş olsalardı, Ayşe ve Hasibe ilk tercihlerine yerleştiği için memnuniyet, algoritma sonucu bulunan yukarıdaki atamaya göre daha yüksek olurdu.
Sonuç
Sonuç olarak kararlı eşleşme probleminin çözümüne yönelik kullandığımız Gale-Shapley algoritması, tercih sırasının etkisi, yapılacak atamanın optimal olmasından daha önemliyse kullanılmalıdır.
Yazıyı okurken algoritmadaki eksiklikler dikkatinizi çekmiş olabilir. Üçüncü bir cinsel tercih kümesi olduğunda ya da eşit sayıdaki erkek ve kadından oluşan bir kümede kadınların erkeklerden en az biriyle bile eşleşmeye yanaşmadığı durumlarda algoritma çıkmaza girecektir.
Artık kararlı eşleşme problemi çözümünü sağlayan algoritmanın nasıl çalıştığını biliyorsunuz. Korkularımızı, ideallerimizi ve bizi biz yapan şeyleri düşünün. İlişkileri çok daha gelişmiş algoritmalarla kontrol etmek mümkün olabilir mi?
Referans: University of California, Sibel Çağlar, Alperen Özlü
İnsan Derisine Basılabilen Biyometrik Sensörler Geliştirildi
