Eşleşme kuramı nedir?

Shutterstock

Öğrenci okul eşleşmeleri, yurt yerleştirmeleri veya böbrek takas işlemlerinde öğrenciler okullarla, böbrekler yeni sahipleriyle nasıl “en iyi” şekilde eşleştirilir?

Eşleşme kuramı’nın temelleri 1962 yılında yayınladıkları çalışma ile iki matematikçi David Gale ve Lloyd Shapley tarafından atıldı.[1] Bu çalışmada eşit sayıda kadın ve erkeğin oluşturduğu toplulukta “kararlı (istikrarlı) evlilikler” var mıdır sorusuna matematiksel bir yanıt aranmıştı.

Eşit sayıda üyesi olan iki grup düşünelim, bir grup erkeklerden diğeri kadınlardan oluşuyor. Her bir gruptan/cinsiyetten bireyler karşı gruptan birisiyle evlenmek istiyor. Herkesin karşı gruptan/cinsiyetten bireyleri içeren bir tercih listesi var.

Soru şu:

Kadınlar ve erkekleri birbirleriyle öyle bir şekilde eşleştirelim ki her kadın ve erkeğin bir eşi olsun ve evli olmayan kadın-erkek çiftlerinden hiçbiri birbirlerini kendi eşlerine tercih etmesinler.

Yani eşlerden birisi başkasını eşine tercih etse de o başkası onu eşine tercih etmesin.  Bu istenilen özellik önemli çünkü ikisi de birbirlerini kendi eşlerine tercih ederse, çiftler verilen eşleşmeye sadık kalmazlar ve kendi eşlerinden ayrılarak daha çok tercih ettikleri eşlerle bir araya gelirler. Dolayısıyla böyle bir eşleşme kararlı olmaz.

Gale ve Shapley kararlı eşleşmelerin her zaman var olduğunu bir algoritma tasarlayarak ve bu algoritmanın da her zaman kararlı eşleşmeler ürettiğini ispat ederek gösterdiler. Bu algoritma literatürde “gecikmeli-kabul” algoritması olarak bilinir.

Algoritma şöyle işliyor:

Erkekler (veya kadınlar) öncelikle en çok tercih ettikleri kadınlara (erkeklere) evlenme teklif ederler. Her bir kadın kendine gelen teklifler arasından en iyisini geçici olarak kabul eder ve diğer tüm teklifleri reddeder. Her bir reddedilen erkek ise kendi tercih listelerinde bir sonraki kadına evlilik teklif eder ve kadınlar da aynı şekilde kendilerine gelen teklifler ve hali hazırda ellerinde geçici olarak tuttukları teklifler arasında kendi tercihlerine göre en iyi olanı geçici olarak kabul eder ve gerisini reddeder. Bu algoritma her bir erkeğin geçici olarak bir kadın tarafından kabul edildiği durumda sonlanır. En son geçici kabuller de algoritmanın ürettiği nihai eşleşmeler olur.

Ekonomide eşleşme piyasaları

Ekonomide birçok piyasada para “tam fonksiyonel” çalışır ve tahsisi (kimin ne alacağı) fiyatlar kanalıyla belirlenir. Yani istediğinize yetecek kadar paranız varsa alabilirsiniz. Bu piyasalar genelde fiyatlar üzerine bir düzenleme olmayan yani fiyatların tamamıyla serbest piyasa prensiplerine göre belirlendiği piyasalardır. Bu tarz piyasaların aksine bazı piyasalarda para tam fonksiyonel değildir ve tahsisi tamamen fiyatlar aracılığı ile belirlenemez. Yani bir şeyi alacak paranız olsa bile bu yeterli değildir, bazen önemli bile değildir.  Almak istediğiniz o şeyin de sizi seçmesi gerekir. Böyle piyasalara eşleşme piyasaları denir. Örnek olarak, öğrenci-okul eşleşmeleri, yurt yerleştirmeleri, lojman tahsisleri, böbrek takas piyasalarını verebiliriz.

Yukarıda bahsettiğimiz, Gale ve Shapley’nin çalışması öğrenci-okul yerleştirme problemlerine adapte edildi.[2][3] Bu adaptasyonu görmek kolay. Evlilik problemindeki bir grubu öğrenciler diğer grubu da okullar olarak yorumlarsak analojiyi büyük ölçüde görmüş oluruz.  Tabii burada okulların birden fazla öğrenci ile eşleşmesine olanak sağlayan kontenjanları olacak. Yine aynı sebepten okulların tercihleri öğrenci grupları üzerinde olacak. Lise yerleştirmelerini düşünelim. Ankara Fen Lisesi (AFL)’nin belli bir kontenjanı var. Fakat bu kontenjandan çok daha fazla öğrenci AFL’de öğrenci olmak istiyor. Tabii burada AFL’deki kontenjanların tahsisi noktasında paranın hiçbir rolü yok. Bu tahsisi belirleyen unsur öğrencilerin sınavdaki başarı sıralamaları.  Dolayısıyla bu bir eşleşme piyasası ve daha önce olduğu gibi hedef kararlı eşleşmeleri bulmak.

Kararlı evlilik modeli birçok farklı eşleşme piyasasına da uyarlandı. Bunların içinde lojman (yurt) tahsisleri[4], ders tahsisleri[5], göçmen yerleştirmeleri[6], ve böbrek takasları[7] sayılabilir.

Böbrek takas problemi

Böbrek takasları problemine biraz daha detaylı bakalım. Bu problemde böbrek bekleyen hastalar var. Donörler var, bunlar genelde böbrek bekleyen hastaların yakınları oluyor. Bir de kadavralardan gelen böbrekler var.  Bu problemde hedef toplam böbrek transplantasyon sayısını maksimize etmek.

Bu sayıyı artırmanın bir yolu şu:

İki hasta var A ve B diyelim ve onların da donörleri var A’ ve B’ diyelim. Ama tıbbi olarak A hastasının donörü olan A’ ve B hastasının donörü olan B’ kendi yakınlarına böbreklerini veremiyorlar.  A’ donörü B hastasına ve B’ donörü ise A hastasına tıbbi olarak böbreklerini verebiliyor. Bu durumda hastalar kendi donörlerini birbirleriyle takas etmek yoluyla sağlıklı böbreklere ulaşabiliyorlar. Bu gibi durumlarda takas yoluyla yapılacak tahsisler böbrek transplantasyon sayısını artırarak bizi en ideal tahsise yakınlaştırıyor.

Araştırmacılar bu donör takaslarını içeren bir algoritma tasarlayarak böbrek transplantasyon sayılarını maksimize edebildiler [7]. Bu algoritmalar Amerika ve İngiltere olmak üzere belli ülkelerde kullanılmaktadır. Bu da eşleşme kuramının ve dolayısıyla Ekonomi biliminin insan hayatına en somut pozitif katkılarından birisidir.

Mustafa Oğuz Afacan
Sabancı Üniversitesi, Sanat ve Sosyal Bilimler Fakültesi, Ekonomi Programı
BAGEP 2019

Notlar/Kaynaklar:

[1] Gale, D., & Shapley, L. (1962). College Admissions and the Stability of Marriage. The American Mathematical Monthly, 69(1), 9-15.
[2] Balinski M., & Sönmez, T. (1999). A Tale of Two Mechanisms: Student Placement. Journal of Economic Theory, 84(1), 73-94.
[3] Abdulkadiroglu, A., & Sönmez, T. (1999). House Allocations with Existing Tenants. Journal of Economic Theory, 88, 233-260.
[4] Abdulkadiroglu, A., & Sönmez, T. (1999). House Allocations with Existing Tenants. Journal of Economic Theory, 88, 233-260.
[5] Sönmez, T., & Ünver, U. (2010). Course Bidding at Business Schools. International Economic Review, 51(1), 99-123.
[6] Delacretaz, D., & Kominers, S., & Teytelboym, A. (2019). Matching Mechanism for Refugee Resettlement, yayınlanmamış makale.
[7] Roth, A., Sönmez, T., & Ünver, M. (2004). Kidney Exchange. The Quarterly Journal of Economics, 119(2), 457-488.