Gale-Shapley Algoritması
Gale-Shapley Stable Marriage Algorithm · Ayrıca şöyle bilinir: Stable Marriage Problem, Deferred Acceptance, Two-Sided Matching
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.
Tam yöntemi oku
Bu bölümü okumak için ücretsiz hesapla giriş yapın.
Yöntem haritası
İlişkili yöntemlerin komşuluğu — keşfetmek için bir düğüm seçin.
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.
Güçlü yönler & sınırlılıklar
- 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
- 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
SSS
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.
Kaynaklar
- Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9-15. DOI: 10.1080/00029890.1962.11989827 ↗
- Roth, A. E. (1984). The economics of matching: Stability and incentives. Mathematics of Operations Research, 7(4), 617-628. DOI: 10.1287/moor.7.4.617 ↗
Bu sayfayı kaynak gösterin
ScholarGate. (2026, June 3). Gale-Shapley Stable Marriage Algorithm. ScholarGate. https://scholargate.app/tr/game-theory/gale-shapley-algorithm
Hangi yöntem?
Bu yöntemi en yakın akrabalarının yanına koyup yan yana okuyun — kütüphane kitapları masaya serer; seçim sizindir.
- Bayesci Nash DengesiOyun teorisi↔ karşılaştır
- Asil-Vekil ModeliOyun teorisi↔ karşılaştır
- En İyi Alım DöngüleriOyun teorisi↔ karşılaştır
- VCG MekanizmasıOyun teorisi↔ karşılaştır