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 kurulmuş çö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. Facebook’un bize arkadaş önermesinin ardından yatan gerçekte aynı.

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şladı. Her öğrencinin bir yer bulabileceği 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. Evlenmek isteyen bir grup erkek ve kadın olsun. Bizim de amacımız herkesi olabildiğince mutlu bir şekilde eşleştirecek bir formül bulmak. Bunun sonucunda da dört mutlu evli çift oluşturmak. Bunun için eşleştirmemizin kararlı olması gerekiyor. Yani gerçekte sahip oldukları eşlere karşı birbirini tercih eden iki kişi olmamalı. ( Bu algoritmada hayal kırıklığına yer yok!)

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 yapıyor bu örneğimizde. 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 red 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 red edilen A’nın ilk tercihini çıkartalım ve devam edelim. Amacımız sonunda herkesin kendine uygun bir eş bulması.

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 Maching 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 için aşağıdaki videoya da göz atmanızı öneririz.

Çevirisi Amine Bayraklı tarafından yapılan aşağıdaki video bu algoritmayı açıklamakta.

Sibel Çağlar

Göz atmak isterseniz…

İ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

Başa dön tuşu