İstikrarlı Evlilik Problemi

Aşk ve ilişki durumumuzu algoritmalar aracılığı ile düzenlemek mümkün mü acaba?

Günümüzde internet üzerinden eş bulmak popüler bir kavram. Bir araştırmaya göre son zamanlardaki evliliklerin üçte biri internet ortamında başlıyor, sürüyor mu o tartışılır elbette…

Ülkemizde çok yaygın olmamakla birlikte dünyanın geneline baktığımızda eş bulmak daha çok evlenmek isteyenlerin dahil olduğu siteler aracılığı ile yapılıyor. Peki bu siteler geri planda kimin için kimin doğru aday olduğunu nasıl bilebiliyor? Size modern çöpçatanlığı anlatmaya çalışalım bu yazımızda…

Bu internet siteleri geri planda eşleştirme algoritması çalıştırmakta. Bu algoritma insanların profillerini tarayarak onların beğenilerine, beğenmediklerine ve kişilik özelliklerine göre eşleşmelerini sağlıyor. Facebook’un bize arkadaş önermesinin ardından yatan gerçekte aynı bir yerde.

Aslında eşleştirme algortimalarının anlatılacak başka avantajları da var. 2012 yılında Nobel Ödülü ilk kez bir algoritma için verildi. David Gale ve matematikçi Lloyd Shapley tarafından yaratılan bir eşleştirme algoritması aldı bu ödülü.

Bu algoritmanın ardında yatan hikaye bu ikilinin 1960’larda kolej başvurularıyla ilgili bir problemi çözmek istemesi ile başlıyor. Öğrencileri kolejlere her öğrencinin bir yer bulabileceği daha da önemlisi ilk seçimlerini kazanamayan öğrencilerin bile mutlu olacağı biçimde yerleştirmek nasıl mümkün olabilir?

Bu soru İstikrarlı Evlilik Problemi olarak düştü kayıtlara…

Buradaki ‘İstikrarlı eşleşme’ nin anlamı çift haline gelen bireyler topluluğundaki hiçbir ikilinin birbirlerini tercih ettikleri halde başka bireylere atanmaması demek. Böylece, populasyon kendi içerisinde dengeye ulaşmış olup çift haline gelebilen bireylerin bu eşleşmeden alacakları tatmin duygusu maksimize edilmiş oluyor ve bütün bunlar olurken bireyler oyunun kurallarına göre oynayıp dışarıdan bir zorlama olmadan kendi tercihlerini yapıyorlar.

Şöyle anlatmaya çalışalım sizlere basitçe: Dört kadınımız (A, B, C, D) ve dörtte erkeğimiz (a,b,c,d) olsun ve hepside evlenmek istesin.

Öncelikle bu sekiz kişiye tercihlerini yazmalarını isteyerek başlayalım işe. Sonrada tercihleri incelemeye alalım. Amacımız herkesin bir eşi olacak daha da önemlisi evlilikleri istikrarlı 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 olsun ve ilk tercihlerine bunu söylesin.

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 ve B, C ve D den gelen 3 tane evlilik teklifi aldı. Bu durumda “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ı. Gördüğümüz gibi bu turda da şanslı erkeğimiz “b” sonuçta iki kişiden teklif aldı 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 mutluluklar.

Şimdi red edilen A’nın ilk tercihini çıkartalım ve devam edelim taki herkes kendine uygun bir eş bulana kadar.

Gale-Shapley algoritması günümüzde dünyanın birçok yerinde kullanılıyor. Özellikle öğrencileri tercih ettikleri okullara yerleştirmede. Elbette bu daha karışık bir süreç olsa da yine de herkesi mutlu edecek çözümler üretebilmekte.

Ancak bu algoritmadan yola çıkarak 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 kalmakta. Ama bazı klinikler günümüzde böbrek hastalarını birbirleriyle eşleştirebilmek için özel bir algoritma kullanmakta. “Kidney Exchange Maching Algorithm 

Bu algoritma sayesinde tüm nakil olasılıklarına son derece hızlı bir biçimde taranıyor ve doğru eşleşmeler sağlanabiliyor ve binlerce kişi yatağa bağlı yaşamaktan kurtulabiliyor.

Sonuçları herkesi mutlu eden bu eşleşmeler Gale ve Shapley’nin çalışmaları olmadan mümkün olamazdı.

Bilimsel çalışmalar bazen hiç de başlangıçta öngörülemeyen sonuçlara ulaşabilir. Yeni bir bilgi ile karşılaşıldığında peki ama bu ne işime yarayacak ki diye düşünürken şunu unutmamak lazım, kendi haliyle olmasa bile birilerine ilham verecektir bu çalışmalar ve başka sonuçları doğuracaktır, şimdi olmasa bile gelecekte…

Sibel Çağlar

İleri okumalar:

https://medium.com/@UofCalifornia/how-a-matchmaking-algorithm-saved-lives-2a65ac448698

http://www.eecs.harvard.edu/cs286r/courses/fall09/papers/galeshapley.pdf

https://www.nobelprize.org/nobel_prizes/economic-sciences/laureates/2012/popular-economicsciences2012.pdf

Yazıyı Hazırlayan: Sibel Çağlar

Kadıköy Anadolu Lisesi, Marmara Üniversitesi, ardından uzun süre özel sektörde matematik öğretmenliği, eğitim koordinatörlüğü diye uzar gider özgeçmişim…

Önemli olan katedilen değil, biriktirdiklerimiz ve aktarabildiklerimizdir bizden sonra gelenlere…

Eğitim sisteminin içinde bulunduğu çıkmazı yıllarca iliklerimde hissettikten sonra, peki ama ne yapabilirim düşüncesiyle bu web sitesini kurmaya karar verdim.

Amacım bilime ilgiyi arttırmak, bilimin özellikle matematiğin zihin açıcı yönünü açığa koymaktı.

Yolumuz daha uzun ve zorlu ancak en azından deniyoruz.

Bunlara da Göz Atın

Matematikçi Şairler Algoritması – Turgut Uyar

“nedir sonsuzdan bir önceki sayının adı diyelim sonsuz eksi bir sonsuz eksi bir hayatın adıdır …

Bir Cevap Yazın

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

ga('send', 'pageview');