Gale-Shapley Algoritması
- Ortaya koyan
- David Gale, Lloyd Shapley
- Yıl
- 1962
- Tür
- algorithm
- Aile
- Game-theoretic
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
Gale-Shapley algoritması, kararlı evlilik problemini çözer: iki grubu (örneğin, tıp asistanlarını hastanelere, öğrencileri okullara) eşleştirerek, hiçbir çiftin kendi atanan partnerleri yerine birbirlerini tercih etmemesini sağlar.
David Gale ve Lloyd Shapley tarafından 1962'de tanıtılan algoritma, bir tarafın sırayla teklifte bulunduğu ve diğer tarafın yanıt verdiği, daha iyi seçenekler geldikçe tercihlerini güncellediği ertelenmiş kabul süreci aracılığıyla polinom zamanda kararlı bir eşleşmeyi garanti eder.
Yöntemin mantığı
Doktorları hastanelerle eşleştirdiğimizi düşünün. Algoritma, müzikli sandalye oyunu gibi işler: her doktor en çok tercih ettiği hastaneye teklifte bulunur; her hastane mevcut en iyi doktoru geçici olarak kabul eder. Hastaneler daha iyi teklifler aldıkça, önceki kabulleri potansiyel olarak reddederek tercihlerini güncellerler. Reddedilen doktorlar bir sonraki tercih ettikleri hastaneye teklifte bulunurlar. Süreç, hiçbir doktorun daha fazla teklifte bulunmak istemediği ve hiçbir hastanenin mevcut eşleşmesini değiştirmek istemediği noktaya kadar devam eder. Sonuç kararlıdır: hiçbir doktor-hastane çifti, atanmış partnerleri yerine birbirleriyle eşleşmeyi tercih etmez.
Tarih
David Gale ve Lloyd Shapley, 1962'de kararlı evlilik problemine çözümlerini yayınladılar ve kararlı eşleşmelerin iki taraflı piyasalar için her zaman var olduğunu kanıtladılar. Algoritmaları, tıp, eğitim ve iş piyasalarını kapsayan uygulamalarla eşleştirme teorisi üzerine geniş bir literatür başlattı. 2012'de Alvin Roth, eşleştirme teorisini gerçek piyasa tasarımına uygulayan deneysel ve teorik çalışmaları nedeniyle Ekonomi Nobel Ödülü'nü kazandı ve Gale-Shapley çerçevesinin pratik önemini doğruladı.
Ne zaman kullanılır?
Gale-Shapley algoritmasını, kararlılığın kritik olduğu iki taraflı piyasaları eşleştirirken uygulayın: tıp asistanı yerleştirme, öğrenci-okul ataması, böbrek değişimi, iş piyasası eşleştirmesi veya çevrimiçi flört piyasaları. Eşleştirmede kararlılık eksikliği (engelleme çiftleri) riski olduğunda kullanın. Algoritma, bir tarafın stratejik avantaja sahip olarak ilk hareketi yapabildiği durumlarda idealdir.
Sınırlar ve dikkat edilmesi gerekenler
- Pareto optimal değil: eşleşme toplam refahı maksimize etmeyebilir; partnerleri takas etmekten fayda sağlayabilecek engellenmiş çiftler olabilir
- Stratejik savunmasızlık: teklif veren taraf tercihlerini yanlış beyan ederek kazanabilir, yanıt veren taraf ise doğrudur
- Asimetri: sonuçlar hangi tarafın önce teklif verdiğine büyük ölçüde bağlıdır
- Kısıtlamaları ele almaz: algoritmik modifikasyon olmadan karmaşık tercihler (örneğin, çiftler, bölgesel tercihler) dahil etmek zordur
Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.
Güçlü yönleri
- Garantili kararlılık: nihai eşleşmede engelleme çifti bulunmaz
- Polinom zaman: O(n^2) karmaşıklık, büyük popülasyonlar için verimli hale getirir
- Basit uygulama: şeffaf tercih toplama ile pratikte yürütülmesi kolaydır
- Stratejik teşvikler: teklif veren taraf stratejik bir avantaja sahiptir, erken teklifleri geç olanlara tercih eder
- Evrensel uygulanabilirlik: dışbükeylik veya geçişlilik varsaymadan herhangi bir tercih profili için çalışır
Uygulama alanları
- Tıp asistanı eşleştirmesi: tıp fakültesi mezunlarını NRMP aracılığıyla hastane asistanlık programlarına eşleştirme
- Okul seçimi: öğrencileri tercihlerine ve kapasite kısıtlamalarına göre devlet okullarına atama
- Böbrek değişimi: uyumlu nakilleri en üst düzeye çıkarmak için organ bağışçılarını ve alıcılarını eşleştirme
- İş piyasası eşleştirmesi: iş arayanları iki taraflı işgücü piyasalarındaki işverenlerle buluşturma
- Çevrimiçi flört: eşleşme kararlılığını ve kullanıcı memnuniyetini artırmak için flört platformlarındaki kullanıcıları eşleştirme
Nasıl çalışır?
Nasıl çalışır?
Her iki gruptaki tüm bireyler için, diğer tarafa ilişkin sıralamalarını temsil eden tercih listeleri oluşturun.
Her turda, eşleşmemiş her kişi teklif veren tarafta, henüz teklifte bulunmadığı diğer taraftaki en yüksek sıralı kişiye teklifte bulunur.
Teklif veren kişi, eşleşmemişse veya teklif veren kişi mevcut partnerinden daha üst sıralarda yer alıyorsa, diğer taraftaki her kişi teklifi geçici olarak kabul eder; bu durumda önceki nişanı iptal eder.
Herkes eşleştiğinde ve başka teklif olmadığında algoritma durur ve kararlı bir eşleşme elde edilir.
Sık yapılan hatalar
- Yalnızca kararlılığın adalet veya refah için yeterli olduğunu varsaymak; kararlı eşleşmeler bir tarafa doğru oldukça eğimli olabilir
- Kararlılığı optimallikle karıştırmak; kararlı bir eşleşme refah maksimize edici olmak zorunda değildir
- Teklif veren tarafın stratejik avantajını göz ardı etmek: teklif veren tarafın üyeleri daha üst sıralarda yer alan partnerlerle eşleşme eğilimindedir
- Algoritmanın tam tercih listeleri varsaydığını unutmak; eksik tercihler modifikasyon gerektirir
Sık sorulan sorular
Eşleştirmede kararlılık neden önemlidir?
Kararlılık olmadan, eşleşen çiftler daha sonra atanmış partnerleri yerine birbirlerini tercih ettiklerini keşfedebilirler, bu da eşleşmeyi bozma teşviki yaratır. Kararlı eşleşmeler, yeniden müzakere olmaksızın eşleşmenin devam etmesini sağlayarak bu tür engelleme çiftlerini önler.
Gale-Shapley algoritması her zaman aynı eşleşmeyi mi üretir?
Hayır. Farklı tercih listeleri veya teklif sıraları farklı kararlı eşleşmeler üretebilir. Ancak, her zaman bir 'erkek-optimal' kararlı eşleşme (teklif verenlerin hepsi için en iyisi) ve bir 'kadın-optimal' kararlı eşleşme (yanıt verenlerin hepsi için en iyisi) vardır.
Gale-Shapley, gruplar üzerindeki tercihleri (örneğin, çiftler) nasıl ele alır?
Standart algoritma çiftleri veya diğer kısıtlamaları doğrudan ele almaz. Çiftler algoritması gibi uzantılar mevcuttur ancak daha karmaşıktır ve tüm tercih profilleri için kararlılığı garanti etmeyebilir.
İlgili yöntemler
Kaynaklar
Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9-15.
DOI kaynağını açKopyalandı.Roth, A. E. (1984). The economics of matching: Stability and incentives. Mathematics of Operations Research, 7(4), 617-628.
DOI kaynağını açKopyalandı.