Gale-Shapley Algoritması: Kararlı Eşleşmeden Tıp Stajına Nobel Ödüllü Matematik

Şu klasik problemi düşünün. On kız, on erkek. Her kız her erkeği belli bir sıraya göre tercih eder; her erkek de her kızı bir sırada. Hedef: her kızı bir erkekle eşleştirmek, öyle ki hiçbir kız ve erkek çifti "biz şu anki eşlerimizden vazgeçip birlikte olmayı tercih ederiz" demesin. Bu, oluşturulan eşleşmenin kararlı (stable) olduğu anlamına gelir.

Bu soru, ilk bakışta romantik komedi kurgusu gibi görünür. Ama 1962'de Amerikalı matematikçiler David Gale ve Lloyd Shapley, American Mathematical Monthly'de yayımladıkları bir makalede şu olağanüstü sonucu kanıtladılar:

Her durum için, herkesin tercihleri ne olursa olsun, kararlı bir eşleşme her zaman vardır; üstelik onu bulan basit bir algoritma vardır.

Bu Gale-Shapley algoritması, sadece teorik bir egzersiz değildi. Sonraki 60 yıl boyunca tıp stajı yerleştirmesi, üniversite başvurusu, böbrek nakli zincirleri, okul-öğrenci eşleştirmesi gibi devasa pratik uygulamalara konu oldu. Lloyd Shapley, 2012 yılında bu çalışma için Nobel Ekonomi Ödülü'nü aldı (David Gale 2008'de ölmüş olduğu için ödüle dahil edilmedi).

Sorun: tam tanım

Daha kesin tanımlamayalım. n kız, n erkek var (eşit sayıda). Her kız, n erkeği bir öncelik sırasına göre listelemiş; aynısı her erkek için. Şimdi her kızı bir erkekle eşleştiren bir çiftler kümesi $M$ tanımlayalım.

Bu eşleşme $M$ "kararsız"dır eğer bloklayan bir çift vardır: yani bir kız $a$ ve bir erkek $b$ bulabilirsek, $a$ kendi mevcut eşinden $b$'yi daha çok tercih ediyor ve aynı zamanda $b$ kendi mevcut eşinden $a$'yı daha çok tercih ediyor. Bu durumda $a$ ve $b$, mevcut eşlerinden ayrılıp birlikte olmaya karar verebilir. Eşleşme kalıcı değil.

Kararlı eşleşme, böyle bloklayan bir çift olmayan eşleşmedir. Yani kimse kendi mevcut eşinden vazgeçecek ortak bir tercih bulamaz.

Gale-Shapley algoritması

Algoritma şu şekilde çalışır (kızlar erkeklerden teklif ister versiyonu):

1. Adım 1: Henüz eşi olmayan her kız, tercih listesindeki en üstteki erkeğe "teklif" yapar.
2. Adım 2: Her erkek, kendisine teklif edenler arasından (mevcut "geçici" eşini de dahil) en çok tercih ettiğini geçici eşi olarak tutar; diğerlerini reddeder.
3. Adım 3: Reddedilen kızlar, kendi tercih listelerinde bir sonraki erkeğe teklif yapar.
4. Bu süreç, hiçbir kız reddedilmeyene kadar devam eder.

Sonuç: bir kararlı eşleşme çıkar. Algoritma her zaman sonlanır (en fazla $n^2$ adımda) ve sonuç matematiksel olarak kararlı olmaya kanıtlıdır.

Kanıt fikri

Algoritmanın iki temel özelliği vardır:

1. Her zaman sonlanır. Kızlar tercih listelerinde sürekli aşağı doğru ilerler, asla geri dönmezler. Sonlu sayıda eleman olduğundan, sonsuza kadar devam edemez.
2. Sonuç kararlıdır. Çelişki yoluyla kanıt: diyelim ki sonucu olduktan sonra bloklayan bir çift var — kız $a$ ile erkek $b$. Bu, $a$'nın algoritma sırasında $b$'ye mutlaka teklif yaptığı anlamına gelir (çünkü $a$, $b$'yi mevcut eşinden daha çok tercih ediyor). Ama o teklif reddedildi ya da sonra başka bir kız tarafından "yer değiştirildi"; her durumda $b$ bir başka kızı $a$'ya tercih etti. Bu, bloklayan çift varsayımına aykırı.

Önemli bir asimetri

Gale-Shapley algoritmasının ilginç bir yönü vardır. Teklifleri kimin yapacağı, sonucu etkiler:

• Kız-en-iyi (woman-optimal): Eğer kızlar teklif yapan tarafsa, her kız mümkün olan en iyi karalı erkek eşine ulaşır; her erkek ise mümkün olan en kötü karalı kız eşine.
• Erkek-en-iyi (man-optimal): Eğer erkekler teklif yapan tarafsa, durum tam tersi.

Yani teklif yapan taraf avantajlıdır. Bu pratik bir gerçektir: ABD'deki National Resident Matching Program (NRMP) (tıp stajı yerleştirmesi) yıllarca "hastane teklif eder" modelini kullandı; 1995'te öğrenci lehine bir versiyona değiştirildi. Bu, doğrudan Gale-Shapley'in matematik öngörüsüne dayanıyordu.

Pratik uygulamalar

1. Tıp stajı yerleştirmesi (NRMP, 1952'den beri)

ABD'de tıp fakültesi öğrencilerinin staj yerlerine yerleştirilmesi 1950'lerden beri merkezi bir sistem ile yapılır. Bu sistem, 1962'den önce kararsız sonuçlar veriyordu — bazı stajyer-hastane çiftleri kendi anlaşmalarını yapıyor, sistemin sonuçlarını sabote ediyordu.

1962'de Gale-Shapley algoritması yayımlandı; NRMP onu kabul etti. Sonuçlar dramatik biçimde kararlı hale geldi. Bugün her yıl yaklaşık 40.000 stajyer, binlerce hastane ile bu algoritma kullanılarak eşleştirilir.

2. New York okul seçim sistemi (2003'ten beri)

New York'ta her yıl yaklaşık 80.000 lise öğrencisi, tercih ettikleri liselerle eşleştirilir. Önceki sistem korkunç şekilde verimsizdi: öğrencilerin önemli bir kısmı hiçbir tercihlerine yerleşemiyordu. Gale-Shapley tabanlı yeni sistemde (Alvin Roth ve takımı tarafından tasarlandı) öğrencilerin %80'inden fazlası ilk üç tercihine yerleşir.

3. Böbrek nakli zincirleri

Bir hastanın akrabası böbrek vermek isteyebilir ama doku uyumsuzluğu olabilir. Bu durumda, çoklu çiftler arasında takas zincirleri kurulur: A'nın akrabası → B hastasına; B'nin akrabası → C hastasına; C'nin akrabası → A hastasına. Bu zincirlerin tasarımı Gale-Shapley'in türevi algoritmaların bir uygulamasıdır.

Alvin Roth ve ekibi, bu sistemin tasarımıyla 2012 Nobel Ekonomi Ödülü'nü Lloyd Shapley ile paylaştı.

4. Üniversite kabulleri

Bazı ülkelerde (Türkiye'deki YKS dahil dönüştürülmüş varyantlar, Singapur, İrlanda, Macaristan) üniversite tercih sistemleri Gale-Shapley benzeri algoritmalar kullanır.

5. Web reklamcılığı

Bir reklam ağında reklamverenler ile reklam alanları arasındaki eşleştirme problemleri, Gale-Shapley'in genelleştirilmesidir. Google AdWords gibi sistemler benzer matematiksel temele dayanır.

Modern uzantılar

Gale-Shapley'in temel problemine pek çok modern uzantı vardır:

• Çok-yönlü eşleşme: Bir taraf birden fazla diğeri ile eşleşir (örneğin bir okul birden fazla öğrenci kabul eder).
• Tercih bağları: Bireyler birkaç seçeneği aynı sırada tercih edebilir; bu hâlde tek bir kararlı sonuç olmayabilir.
• İkincil kısıtlar: "İki kişi aynı şehirde olmalı" (çift adaylık) gibi ek kısıtlamalar.
• Strateji-uyumluluk: Hiçbir kişinin "yalan söyleyerek" daha iyi sonuç elde edemediği versiyonları (önemli bir tasarım hedefi).

Bu uzantılar, modern mekanizma tasarımı (mechanism design) denilen ekonomi-matematik alt dalının temel araştırma konularıdır.

Nobel Ödülü

Lloyd Shapley ve Alvin Roth, "istikrarlı tahsisat ve piyasa tasarımı pratiği" katkıları için 2012 Nobel Ekonomi Ödülü'nü paylaştı. Bu, matematiksel bir algoritmanın doğrudan Nobel düzeyinde ekonomi ödülü kazandığı nadir bir örnektir.

David Gale 2008'de öldüğü için (Nobel mevcutlara verilir) ödüle dahil edilmedi. Gale'in mirası, modern matematiksel ekonominin temellerinden biri olmasıdır.

Bir hayat dersi

Gale-Shapley algoritması, karmaşık görünen toplumsal problemlerin çoğu zaman matematiksel olarak çözülebilir olduğunu gösteren güzel bir örnektir. Tıp stajı, böbrek nakli, üniversite başvurusu — hepsi insan tercihlerini ve karmaşık koşulları içerir; ama özünde yatan matematik son derece sadedir.

Aynı zamanda, mekanizma tasarımının modern toplumsal organizasyonun önemli bir parçası olduğunu hatırlatır. Bir yarış var; ama yarışın kuralları kendisinden de önemlidir. İyi kurullar, herkesin daha iyi sonuçlar almasına yol açar.

Bir sonraki sefer bir kuyrukta beklediğinizde, bir başvuruda matematik algoritmaların arka planda çalıştığını duyduğunuzda, 1962'de Berkeley ve Princeton'da iki matematikçinin yazdığı küçük bir makalenin etkisini hatırlayabilirsiniz. İyi matematik, sadece sayıları sayar değil — onları doğru biçimde eşleştirir.