Uygulamalı Matematik

Gale Shapley Algoritması ve Kararlı Evlilik Problemi

Aşk ve ilişki durumumuzu algoritmalar aracılığı ile düzenlemek mümkün mü acaba? Sürüp sürmediği bilinmese de araştırmalara göre günümüzde evliliklerin yaklaşık üçte biri internet ortamında başlıyor. Hatta bu iş için kurulu çöpçatanlık siteleri bile mevcut. Peki bu siteler geri planda kimin için kimin doğru aday olduğunu nasıl bilebiliyor? Tahmin etmiş olabileceğiniz gibi cevap geri planda çalışan eşleştirme algoritmaları. Bu algoritmalar insanların profillerini tarayarak onların beğenilerine ve kişilik özelliklerine göre eşleşmelerini sağlıyor.

2012 yılında Nobel Ödülünü David Gale ve matematikçi Lloyd Shapley tarafından yaratılan bir eşleştirme algoritması aldı. Bu algoritma ile ilgili çalışmalar, ikilinin 1960’larda kolej başvurularıyla ilgili bir problemi çözmek istemesi ile başlamıştı. Her öğrencinin bir yer bulacağı daha da önemlisi ilk seçimlerini kazanamayan öğrencilerin bile mutlu olacağı bir yerleşim mümkün olabilir mi? Bu soru Kararlı Evlilik Probleminin (Stable Marriage Problem) başlangıcıdır.

Kararlı Evlilik Problemi

Hemen bir örnek ile algoritmayı aktarmakta çalışalım. Diyelim ki bir çöpçatanlık sitesi işletiyorsunuz. 200 tane müşteriniz var. 100 erkek ve 100 kadın. Her kadın, size tercih sırasına göre sıralı100 erkeğin bir listesini sunuyor. Listenin başında en çok evlenmek istediği kişi yer var, sonunda ise en az. Aynısını erkekler de yapıyor. Şimdi her müşteriyi karşı cinsten bir üyeyle eşleştirmeniz ve hepsinin evlendiğinden ve sonsuza dek nispeten mutlu yaşadığından emin olmanız gerekiyor. Elbette bazı müşterileri ilk tercihleri ile evlenemeyecek. Listedeki bir erkek, iki veya daha fazla kadın tarafından birinci sırada yazıldı ise, birileri daha azıyla yetinmek zorunda kalacak. Amacımız herkesi olabildiğince mutlu bir şekilde eşleştirecek bir formül bulmak. Bunun için eşleştirmemizin kararlı olması gerekiyor. Şimdi üzerinde çalışması daha kolay olacağı için üç kadın ve üç erkek üzerinden bu eşleştirmeyi inceleyelim.

Tercihlere Bakalım

Dört kadınımız (A, B, C, D) ve dört erkeğimiz ise (a,b,c,d) olsun. Öncelikle bu sekiz kişiye tercihlerini yazmalarını isteyerek işe başlayalım. Sonra da tercihleri incelemeye alalım. Amacımız herkesin bir eşi olacak biçimde, kadın ve erkeklerin ilk tercihleri olmasa bile ulaşabilecekleri en iyi seçeneğe göre eşleşebilmeleri.

Evlilik tekliflerini kadınlar yapsın. Mesela A’nın tercihleri (b,c,d,a); B’nin tercihleri (c,a,d,b); C’nin tercihleri (c,d,a,b) ve D’nin tercihleri de (c,b,a,d,) biçiminde olsun. Bu arada elbette erkeklerde kendi tercihlerini sıralamış durumda. Sıralamaya bakarsak “c” oldukça popüler. Bunun sonucunda kendisine B, C ve D den 3 tane evlilik teklifi geldi. Bu durumda şimdi “c” nin listesine göz atalım (B,C,D,A) demek ki mutlu bir çift elde edebildik: (B,c) Sonuçta her ikisi de ilk tercihleri ile eşleşmiş oldu. Şimdi ret cevabı alan iki kadının ilk tercihleri listeden çıkartalım ve ikinci tura başlayalım.

A’nın yeni listesi (b,c,d,a); C’nin listesi (d,a,b); ve D’nin listesi (b,a,d) biçiminde artık. Ve tekrardan evlilik teklifi aşaması var. Gördüğümüz gibi bu turda da şanslı erkeğimiz “b”. Sonuçta iki kişiden teklif aldı yani A ve D. Hemen “b”nin tercihlerine göz atalım. Onun listesi de (D,A,C,B) biçiminde olsun. Bu durumda yeni çiftimiz (D,b)’ye de mutluluklar dileriz. Şimdi ret edilen A’nın ilk tercihini çıkartalım ve bu biçimde devam edelim. Sonunda algoritma sona erer. Hepsi eşleşir ve sonsuza dek mutlu (ya da en azından bir istikrar içinde) yaşarlar.

Gale-Shapley Algoritması Başka Nerelerde Karşımıza Çıkıyor?

Gale-Shapley algoritması günümüzde dünyanın birçok yerinde farklı amaçlar için kullanılıyor. Özellikle öğrencileri tercih ettikleri okullara yerleştirmede de oldukça çok işe yarıyor. Elbette bu daha karışık bir süreç olsa da yine de herkesi mutlu edecek çözümler üretme kapasitesine sahip. Ancak bu algoritmadan yola çıkarak elde edilen ve sonucunda insanların hayatını kurtaran bir başka algoritma daha var.

Diyalize bağlı yaşayan böbrek hastaları kendilerine uygun böbreği bulabilmek için uzun süre beklemek zorunda kalır. Ama bazı klinikler böbrek hastalarını birbirleriyle eşleştirebilmek için “Kidney Exchange Matching Algorithm olarak bilinen özel bir algoritma kullanır. Bu algoritma sayesinde tüm nakil olasılıkları son derece hızlı bir biçimde gözden geçirilir. Bu sayede de doğru eşleşmeler sağlanır. Sonuçları herkesi mutlu eden bu eşleşmeler Gale ve Shapley’nin çalışmaları olmadan mümkün olamazdı.

Konu hakkında daha fazla bilgi edinmek isterseniz çevirisi Amine Bayraklı tarafından sitemiz için yapılan bu videoya da göz atmanızı öneririz.

İleri Okumalar:

Matematiksel

Sibel Çağlar

Merhabalar. Matematik öğretmeni olarak başladığım hayatıma 2016 yılında kurduğum matematiksel.org web sitesinde içerikler üreterek devam ediyorum. Matematiğin aydınlık yüzünü paylaşıyorum. Amacım matematiğin hayattan kopuk olmadığını kanıtlamaktı. Devamında ekip arkadaşlarımın da dahil olması ile kocaman bir aile olduk. Amacımıza da kısmen ulaştık. Yolumuz daha uzun ama kesinlikle çok keyifli.

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

Bu Yazılarımıza da Bakmanızı Öneririz

Başa dön tuşu