Gale–Shapley algoritması - Gale–Shapley algorithm

In matematik , ekonomi ve bilgisayar bilimleri , Gale-Shapley algoritması (olarak da bilinen ertelenmiş kabul algoritması veya önermek-ve-reddetmek algoritması ) bir olan algoritma bir çözüm bulmak için kararlı eşleştirme sorunu için adlandırılmış, David Gale ve Lloyd Shapley bunu hem üniversiteye giriş sorununu hem de istikrarlı evlilik sorununu çözmek olarak tanımlamıştı . Polinom zaman alır ve zaman, algoritmaya giriş boyutunda doğrusaldır . Bu bir olan dürüst bir mekanizma çözümü her zaman en uygun olacak kime öneren katılımcılar, bakış açısından.

Arka fon

İstikrarlı eşleştirme problemi, en temel biçiminde, girdi olarak eşit sayıda iki tür katılımcı (örneğin $n$ erkek ve $n$ kadın veya $n$ tıp öğrencisi ve $n$ stajyer) ve her katılımcı için tercihlerini belirten bir sıralama alır. diğer türden katılımcılar arasından kiminle eşleştirileceği. Kararlı bir eşleşme her zaman vardır ve Gale-Shapley algoritması tarafından çözülen algoritmik problem bir tane bulmaktır. Aşağıdaki durumlarda bir eşleştirme kararlı değildir :

Orada bir elementtir A bazı verilmiş eleman tercih birinci eşleşti setin B hangi öğenin üzerine ikinci eşleşti kümesinin bir zaten eĢleĢtirilir ve
B ayrıca , B'nin zaten eşleştirildiği öğeye göre A'yı tercih eder .

Başka bir deyişle, her iki katılımcının da mevcut partnerine başka birini tercih ettiği bir eşleşme ( A , B ) olmadığında bir eşleşme sabittir .

Çözüm

Gale-Shapley algoritmasının bir örneğini gösteren animasyon

1962'de David Gale ve Lloyd Shapley, eşit sayıda kadın ve erkek için SMP'yi çözmenin ve tüm evlilikleri istikrarlı hale getirmenin her zaman mümkün olduğunu kanıtladılar. Bunu yapmak için bir algoritma sundular. 1984'te Alvin E. Roth , esasen aynı algoritmanın 1950'lerin başlarından beri Ulusal Yerleşik Eşleştirme Programında pratik kullanımda olduğunu gözlemledi .

Gale-Shapley'in algoritması "mermi" (veya "bir dizi içerir yineleme "):

İlk turda, önce a ) nişanlı olmayan her erkek en çok tercih ettiği kadına evlenme teklif eder ve sonra b ) her kadın en çok tercih ettiği talibine "belki" ve diğer tüm taliplerine "hayır" cevabını verir. Daha sonra, o ana kadar en çok tercih ettiği taliple geçici olarak "nişanlı" olur ve bu talip de aynı şekilde geçici olarak onunla nişanlanır.
Sonraki her turda, ilk olarak a ) nişanlı olmayan her erkek, henüz evlenme teklif etmediği en çok tercih edilen kadına evlenme teklif eder (kadının halihazırda nişanlı olup olmadığına bakılmaksızın) ve sonra b ) her kadın şu anda evliyse "belki" yanıtını verir. nişanlı değil veya bu adamı mevcut geçici partnerine tercih ediyorsa (bu durumda, nişanlanmayan mevcut geçici partnerini reddediyor). Nişanlanmaların geçici doğası, halihazırda nişanlı olan bir kadının "takas etme" (ve bu süreçte, o zamana kadar eşini "terk etme") hakkını korur.
Bu işlem herkes meşgul olana kadar tekrarlanır.

Bu algoritmanın çalışma zamanı karmaşıklığı , erkek veya kadın sayısının nerede olduğudur. Girdi tercih listeleri de ile orantılı boyuta sahip olduğundan , çalışma zamanı girdi boyutunda doğrusaldır. ${\ Displaystyle O(n^{2})}$ ${\görüntüleme stili n}$ ${\görüntüleme stili n^{2}}$

Bu algoritma şunları garanti eder:

herkes evlenir: Sonunda, hem nişanlı olmayan bir erkek hem de bir kadın olamaz, çünkü bir noktada ona teklif etmiş olmalı (çünkü bir erkek eninde sonunda, gerekirse herkese teklif edecektir) ve teklif edildiğinde, mutlaka nişanlanacaktır ( birine) bundan sonra.
Evlilikler istikrarlı: Bırakın Alice ve Bob nişanlansınlar ama birbirleriyle değil. Algoritma tamamlandıktan sonra hem Alice'in hem de Bob'un birbirlerini mevcut ortaklarına tercih etmeleri mümkün değildir. Bob, Alice'i mevcut partnerine tercih ediyorsa, mevcut partnerine evlenme teklif etmeden önce Alice'e teklif etmiş olmalıdır. Eğer Alice teklifini kabul ettiyse, ancak sonunda onunla evli değilse, onu daha çok sevdiği biri için terk etmiş olmalı ve bu nedenle Bob'u şu anki partnerinden daha fazla sevmiyor. Alice teklifini reddetmişse, o zaten Bob'dan daha çok sevdiği biriyle birlikteydi.

algoritma

algorithm stable_matching is
    Initialize m ∈ M and w ∈ W to free
    while ∃ free man m who has a woman w to propose to do
        w := first woman on m's list to whom m has not yet proposed
        if ∃ some pair (m', w) then
            if w prefers m to m' then
                m' becomes free
                (m, w) become engaged
            end if
        else
            (m, w) become engaged
        end if
    repeat

Çözümün optimalliği

Ertelenmiş kabulün erkekler için ideal olduğunun kanıtı

Farklı kararlı eşleşmelerin varlığı şu soruyu gündeme getirir: Gale-Shapley algoritması tarafından hangi eşleşme döndürülür? Erkekler için mi, kadınlar için mi yoksa orta seviye için mi daha iyi? Yukarıdaki örnekte, algoritma erkekler için en uygun çözümde tek bir turda birleşir, çünkü her kadın tam olarak bir teklif alır ve bu nedenle bu teklifi seçerek her erkeğin kabul edilmiş bir teklifi olmasını sağlayarak maçı bitirir.

Bu genel bir gerçektir: Erkeklerin kadınlara evlenme teklif ettiği Gale-Shapley algoritması her zaman tüm istikrarlı eşleşmeler arasında tüm erkekler için en iyisi olan istikrarlı bir eşleşme sağlar. Benzer şekilde, eğer kadınlar teklif ederse, sonuçta ortaya çıkan eşleşme, tüm istikrarlı eşleşmeler arasında tüm kadınlar için en iyisidir . Bu iki eşleşme, kararlı eşleşmeler kafesinin üst ve alt öğeleridir .

Bunu görmek için sağdaki resme bakın. A, erkekler önerme algoritması tarafından oluşturulan eşleşme olsun ve B en az bir adam için daha iyi olan alternatif bir kararlı eşleşme olsun, diyelim ki m ₀ . B'deki m _0'ın , A'daki eşleşmesine tercih ettiği w ₁ bir kadınla eşleştirildiğini varsayalım . Bu, A'da m _0'ınw _1'i ziyaret ettiği , ancak kadının onu reddettiği anlamına gelir (bu, m _0'dan gelen yeşil okla gösterilir). için ağırlık _{, 1} ). w ₁ tercih ettiği bir adam lehine onu reddettim, diyelim ki m ₂ . Bu nedenle B, W ₁ eşleştirilir m ₀ , ancak için "serbest formatlı tahliller" (istekleri ancak eşsiz) m ₂ (Bu kırmızı okla gösterilir w ₁ için m ₂ ).

B sabit bir eşleşme olduğundan, B'deki m ₂ , onun w ₁ , diyelim ki w ₃ olarak tercih ettiği bir kadınla eşleştirilmelidir . Bu, A'da m _2'ninw _1'e varmadan önce w _3'ü ziyaret ettiği anlamına gelir, bu da w _3'ün onu reddettiği anlamına gelir . Benzer düşüncelerle ve grafik sonlu olduğundan, sonunda her erkeğin A'da döngüdeki bir sonraki kadın tarafından reddedildiği, döngüdeki bir sonraki erkek lehine onu reddeden yönlendirilmiş bir döngüye sahip olmalıyız. Ancak, böyle bir "reddetme döngüsü" hiçbir yerde başlayamayacağı için bu imkansızdır: çelişkiyle, örneğin m _0'da başladığını varsayalım - komşu kadın tarafından reddedilen ilk erkek ( w ₁ ). Varsayım olarak, bu reddetme ancak m ₂w _{1 '} e geldikten sonra olur . Ancak bu ancak w ₃m _2'yi reddettikten sonra olabilir - m _0'ın ilk olması ile çelişki .

Stratejik düşünceler

GS algoritması, erkekler (teklif eden taraf) açısından doğru bir mekanizmadır. Yani, hiç kimse tercihlerini yanlış sunarak kendisi için daha iyi bir eşleşme elde edemez. Ayrıca, GS algoritması erkekler için grup stratejisi kanıtıdır , yani hiçbir erkek koalisyonu, koalisyondaki tüm erkeklerin kesinlikle daha iyi durumda olacağı şekilde tercihlerinin yanlış beyan edilmesini koordine edemez. Bununla birlikte, bazı koalisyonların tercihlerini, bazı erkeklerin daha iyi durumda olduğu ve diğer erkeklerin aynı ortağı elinde tutacağı şekilde yanlış beyan etmesi mümkündür.

GS algoritması kadınlar için doğru değildir (inceleyen taraf): her kadın tercihlerini yanlış sunabilir ve daha iyi bir eşleşme elde edebilir.

Yazılım paketlerinde uygulama

R : İstikrarlı evlilik ve hastaneler/sakin sorunu için Gale–Shapley algoritması (ertelenmiş kabul algoritması olarak da bilinir) matchingMarketsve matchingRpaketlerinin bir parçası olarak mevcuttur .
API : MatchingTools API, Gale–Shapley algoritması için ücretsiz bir uygulama programlama arabirimi sağlar.
Python : Gale–Shapley algoritması, matchingkitaplıkta diğer birçok iyi bilinen eşleştirme oyunu algoritmasıyla birlikte bulunur ve QuantEcon/MatchingMarkets.pypaket, genelleştirilmiş eşleştirme oyunları için birkaç tane daha içerir.
MATLAB : Gale-Shapley algoritması, Amerika Birleşik Devletleri Deniz Kuvvetleri Araştırma Laboratuvarı'nın ücretsiz Tracker Component Library'sinin bir assign2DStableparçası olan fonksiyonda uygulanmaktadır .

Tanıma

Shapley ve Roth, "istikrarlı tahsisler teorisi ve piyasa tasarımı pratiği" için 2012 Nobel İktisadi Bilimler Ödülü'ne layık görüldü ; Gale 2008 yılında ölmüştü.

Languages

In other projects

Gale–Shapley algoritması - Gale–Shapley algorithm

İçindekiler