Gale ve Shapley algoritması
Gale ve Shapley'in algoritması bir bir algoritma bu çözer stabil evlilik problemi .
İlke ve algoritma
İlke ve tanımlar
1962'de
David Gale ve
Lloyd Shapley , istikrarlı evlilik sorununu çözmenin hala mümkün olduğunu kanıtladılar. Ayrıca bir çözüm bulmak için bir
algoritma sundular .
Bu algoritmayı sunmanın yollarından biri aşamalar halinde çalışmaktır. Her aşamada, her bir erkek, hiç teklif etmediği kişiler arasından tercih ettiği kadına (zaten bir ilişki içinde olup olmadığına bakmadan) kendini teklif eder. Daha sonra her kadın kendisine yapılan önerileri (muhtemelen halihazırda birlikte olduğu kişi de dahil olmak üzere) değerlendirir, sonra tercih ettiği adama "belki" ve diğerlerine "hayır" der.Gale-Shapley algoritmasını resmi olarak yazmak için, algoritmanın yazılmasında ve çalışmasında yer alan kavramları aşağıda tanımlıyoruz.
Hem kardinal hem de sözde bağlantısız olan bir dizi erkek ve bir dizi kadın düşünün .
M{\ displaystyle \ textstyle M}W{\ displaystyle \ textstyle W}değil{\ displaystyle \ textstyle n}
- Bir çağrı yapan çiftler kümesi bir dizi bu tür herhangi bir eleman , sadece tek bir çift en fazla görüntülenene . Bu, istikrarlı evliliklerin sorunlarının incelenmesinde çok eşliliğin hesaba katılmadığını söylemek anlamına gelir.S⊂M×W{\ displaystyle \ textstyle S \ alt küme M \ kere W}M∪W{\ displaystyle \ textstyle M \ fincan W}S{\ displaystyle \ textstyle S}
- Herhangi bir adam için , bir çağrı tercihi üzerinde sıkı bir toplam sipariş ilişkisi ilişkisini kaydetti . Eğer ve bunun söylenir tercih etmek ister: . Herhangi bir kadın için, tanımlama , tercih edilmesi ile ilgili belirtildiği gibi, yukarıdaki gibi.m∈M{\ displaystyle \ textstyle m \ M olarak}m{\ displaystyle \ textstyle m}W{\ displaystyle \ textstyle W}>m{\ displaystyle \ textstyle> _ {m}}w∈W{\ displaystyle \ textstyle w \ W olarak}w′∈W{\ displaystyle \ textstyle w '\ W olarak}m{\ displaystyle \ textstyle m}w{\ displaystyle \ textstyle w}w′{\ displaystyle \ textstyle w '}w>mw′{\ displaystyle \ textstyle w> _ {m} w '}w∈W{\ displaystyle \ textstyle w \ W olarak}w{\ displaystyle \ textstyle w}>w{\ displaystyle \ textstyle> _ {w}}
Tüm erkeklerin ve tüm kadınların tercih ilişkileri ailesine dikkat çekiyoruz, yani:
L{\ displaystyle \ textstyle L}M{\ displaystyle \ textstyle M}W{\ displaystyle \ textstyle W}L=((>m)m∈M;(>w)w∈W){\ displaystyle \ textstyle L = ((> _ {m}) _ {m \ içinde M} \,; (> _ {w}) _ {w \ W içinde})}
- Bir aile ve bir dizi nişanlı çift göz önüne alındığında , bir çiftin , çiftler varsa ve aşağıdaki gibi bir istikrarsızlık olduğunu söylüyoruz : ve .L{\ displaystyle \ textstyle L}S{\ displaystyle \ textstyle S}(m;w′)∈M×W{\ displaystyle \ textstyle (m; w ') \, M \ kere W}S{\ displaystyle \ textstyle S}(m;w)∈S{\ displaystyle \ textstyle (m; w) \ S olarak}(m′;w′)∈SS içinde {\ displaystyle \ textstyle (m '; w') \}w′>mw{\ displaystyle \ textstyle w '> _ {m} w}m>w′m′{\ displaystyle \ textstyle m> _ {w '} m'}
Sözde kodEntrée : Deux ensembles finis M (d’hommes) et W (de femmes) de cardinal n ;
Une famille L de relations de préférences ;
Sortie : Un ensemble S de couples engagés (homme ; femme) ;
fonction mariageStable {
Initialiser tous les m ∈ M et w ∈ W à célibataire
tant que ∃ homme célibataire m qui peut se proposer à une femme w {
w = femme préférée de m parmi celles à qui il ne s'est pas déjà proposé
si w est célibataire
(m, w) forment un couple
sinon un couple (m', w) existe
si w préfère m à m'
(m, w) forment un couple
m' devient célibataire
sinon
(m', w) restent en couple
}
Retourner l’ensemble S des couples engagés
}
Özellikleri
Bu algoritma , bir erkek grubu verildiğinde , hem kardinal hem de ayrık olduğu varsayılan bir kadın grubu , bir tercih ilişkileri ailesi ve algoritma tarafından döndürülen bir dizi kararlı çift (erkek; kadın) sağlar:
M{\ displaystyle \ textstyle M}W{\ displaystyle \ textstyle W}değil{\ displaystyle \ textstyle n}L{\ displaystyle \ textstyle L}S{\ displaystyle \ textstyle S}
Algoritma döngüsünün yineleme sayısı en fazla
değil2{\ displaystyle \ textstyle n ^ {2}}
Gale-Shapley algoritmasının gözlemlerinden hemen sonra gelen bazı açıklamalarda bulunarak başlıyoruz:
- Herhangi bir kadın , ilk nişan teklifini alır almaz, algoritmanın uygulanmasının sonuna kadar meşgul kalır. Ek olarak, algoritmanın yürütülmesi sırasında onunla etkileşime giren ortakların listesi , tercih ilişkisi anlamında "daha iyi ve daha iyi" hale gelir . Başka bir deyişle, her zaman ortak değişimi bir ortak algoritma bir yürütme sırasında elimizde: .w∈W{\ displaystyle \ textstyle w \ W olarak}w{\ displaystyle \ textstyle w}w{\ displaystyle \ textstyle w}w{\ displaystyle \ textstyle w}m∈M{\ displaystyle \ textstyle m \ M olarak}m′∈M{\ displaystyle \ textstyle m '\ M olarak}m′>wm{\ displaystyle \ textstyle m '> _ {w} m}
- Herhangi bir adam , algoritmanın uygulanmasının başlangıcından ikincisinin sonuna kadar bağlılık ve bekarlık arasında geçiş yapabilir. Buna ek olarak, algoritmanın yürütülmesi sırasında onunla meşgul olan ortakların listesi , tercih ilişkisi anlamında "daha da kötü" hale gelir . Başka bir deyişle, her zaman ortak değişimi bir ortak algoritma bir yürütme sırasında elimizde: .m∈M{\ displaystyle \ textstyle m \ M olarak}m{\ displaystyle \ textstyle m}m{\ displaystyle \ textstyle m}m{\ displaystyle \ textstyle m}w∈W{\ displaystyle \ textstyle w \ W olarak}w′∈W{\ displaystyle \ textstyle w '\ W olarak}w>mw′{\ displaystyle \ textstyle w> _ {m} w '}
Yukarıda belirtilen özelliği göstermek için, algoritmanın her yinelemesinde kesin olarak artan bir miktar (tamsayı) göstereceğiz. Olalım çiftlerin kümesi bir önerim yapılan algoritmanın başlangıç ve arasındaki yineleme ve setin kardinalitesi . Benzer şekilde, set , algoritmanın başlangıcı ile yineleme arasında yapılan teklifler kümesine karşılık gelir . Böylece sahibiz:
VS(t){\ displaystyle \ metin stili C (t)}(m;w){\ displaystyle \ metin stili (m; w)}m{\ displaystyle \ textstyle m}w{\ displaystyle \ textstyle w}tinci{\ displaystyle \ textstyle t ^ {\ text {th}}}değil(t){\ displaystyle \ metin stili n (t)}VS(t){\ displaystyle \ metin stili C (t)}VS(t){\ displaystyle \ metin stili C (t)}tinci{\ displaystyle \ textstyle t ^ {\ text {th}}}-
∀{\ displaystyle \ forall} t,{\ displaystyle \ textstyle t,} değil(t)<değil(t+1){\ displaystyle n (t) <n (t + 1)} ;
-
∀{\ displaystyle \ forall} t,{\ displaystyle \ textstyle t,} değil(t)≤değil2{\ displaystyle n (t) \ leq n ^ {2}}.
Bu nedenle, algoritmada en fazla yalnızca yinelemeler olabilir .
değil2{\ displaystyle \ textstyle n ^ {2}}
Herkes bir çift olur
Bir kadın zaten bir ilişki içindeyse (bir erkeğe "belki" dedikten sonra), algoritmanın geri kalanı için böyle kalır. Sonunda, bu nedenle, bekar bir erkek ve kadın olamaz, çünkü erkek bir noktada mutlaka kendisini kadına teklif etmiş olacaktır.
Daha resmi olarak, herhangi bir öğesinin bir çiftte tam olarak bir kez ve yalnızca bir kez göründüğünü göstereceğiz . Bunun için mülkün
M∪W{\ displaystyle \ textstyle M \ cup \ textstyle W}S{\ displaystyle \ textstyle S}
(P){\ displaystyle \ textstyle (P)} : " Adam , tek olan tüm kadınlara sunulan henüz "
∀{\ displaystyle \ forall}m∈M{\ displaystyle \ textstyle m \ in \ textstyle M}m{\ displaystyle \ textstyle m}⇒m{\ displaystyle \ Rightarrow \ textstyle m}w∈W{\ displaystyle \ textstyle w \ in \ textstyle W}Bir olduğu
değişmez algoritması. Saçma olarak akıl yürütelim ve bunun bir değişmez olmadığını varsayalım . O zaman, belirli bir anda, yani belirli bir döngü dönüşünde yanlıştır. Yani: Bir erkek , bekar olan tüm kadınlara sunulan, . Yani, zorunlu olarak, tüm kadınlar diğer erkeklerle nişanlıdır. Bununla birlikte, aynı kardinalin ve aynı kadının setleri ve varlığı, algoritmaya göre iki farklı erkekle ilişki kuramaz ( yukarıdaki evlilik Kararlı işlevi ), bu , bir kadınla nişanlandığı anlamına gelir . Bu nedenle, ilk iddia ile bir çelişkimiz var: " değişmez değil". Dolayısıyla bu bir değişmezdir ve bu nedenle bu, algoritmanın tüm döngü dönüşleri için geçerlidir.
(P){\ displaystyle \ textstyle (P)}(P){\ displaystyle \ textstyle (P)}∃{\ displaystyle \ var}m0{\ displaystyle \ textstyle m_ {0}} ∈M{\ displaystyle \ in \ textstyle M}m0{\ displaystyle \ textstyle m_ {0}}∧{\ displaystyle \ land} m0{\ displaystyle \ textstyle m_ {0}}w∈W{\ displaystyle \ textstyle w \ in \ textstyle W}w∈W{\ displaystyle \ textstyle w \ in \ textstyle W}M{\ displaystyle \ textstyle M}W{\ displaystyle \ textstyle W}m0{\ displaystyle \ textstyle m_ {0}}(P){\ displaystyle \ textstyle (P)}(P){\ displaystyle \ textstyle (P)}Bu nedenle, algoritmadan çıkarken döngünün durumu yanlıştır. Yani: adam , etkileşim halinde olduğu tüm kadınlara sunulan . Ya . O Eğer tüm kadınlara teklif edildiği , daha sonra da bu algoritmanın bir değişmez olduğu, bu sonuncusu sonunda doğrudur. Yani, özellikle şöyle:
∀{\ displaystyle \ forall}m∈M{\ displaystyle \ textstyle m \ in \ textstyle M}m{\ displaystyle \ textstyle m}∨{\ displaystyle \ lor} m{\ displaystyle \ textstyle m}w∈W{\ displaystyle \ textstyle w \ in \ textstyle W}m∈M{\ displaystyle \ textstyle m \ in \ textstyle M}m{\ displaystyle \ textstyle m}w∈W{\ displaystyle \ textstyle w \ in \ textstyle W}(P){\ displaystyle \ textstyle (P)}
" Is bekâr tüm kadınlara sunulan henüz contraposée söyler," devreye girer. Bu nedenle, algoritmanın sonunda tüm erkekler meşgul olur. Batarken, Sonuç ve aynı kardinal ve aynı kadın iki farklı erkeklerle meşgul olamaz, biz bütün kadınlar eşit meşgul olduğu sonucuna varıyoruz. Yani, algoritmanın sonunda herkes bir çift oluyor.
m{\ displaystyle \ textstyle m}⇒m{\ displaystyle \ Rightarrow \ textstyle m}w∈W{\ displaystyle \ textstyle w \ in \ textstyle W}m{\ displaystyle \ textstyle m}m∈M{\ displaystyle \ textstyle m \ in \ textstyle M}M{\ displaystyle \ textstyle M}W{\ displaystyle \ textstyle W}
Evlilikler istikrarlı
Algoritmanın sonunda, hem evli bir kadın Alice hem de Bob'un birlikte olmadığı bir erkek verelim. Bob Alice'i karısına tercih ederse, bu onun karısına evlenme teklif etmeden önce Alice'e evlenme teklif ettiği anlamına gelir. Alice kabul etmişse, sonunda artık yanında olmadığı için, onun yerine tercih ettiği biriyle yer değiştirmesi ve bu nedenle Bob'u kocasına tercih etmemesidir. Alice reddetmişse, bunun nedeni zaten Bob'a tercih ettiği biriyle birlikte olmasıydı.
Daha resmi olarak, saçma bir şekilde düşünelim ve evliliklerden birinde istikrarsızlık olduğunu varsayalım. Yani, orada tanımı gereği, bu araçlar o gibi tercih etmek ve tercih etmek . De ve bir algoritmaya göre, birbirine tutturulmuştur, son teklif bu araçlar için yapıldı . Bir öneri var mıydı hiç ?
(m;w),(m′;w′)∈S\ textstyle S içinde {\ displaystyle \ textstyle (m; w), (m '; w') \m{\ displaystyle \ textstyle m}w′{\ displaystyle \ textstyle w '}w{\ displaystyle \ textstyle w}w′{\ displaystyle \ textstyle w '}m{\ displaystyle \ textstyle m}m′{\ displaystyle \ textstyle m '}m{\ displaystyle \ textstyle m}w{\ displaystyle \ textstyle w}m{\ displaystyle \ textstyle m}w{\ displaystyle \ textstyle w}m{\ displaystyle \ textstyle m}w′{\ displaystyle \ textstyle w '}- Hiçbiri yoksa, bu , onu reddetmeyen başka bir kadınla zaten nişanlanmış olduğu anlamına gelir (çünkü algoritmanın sonunda birlikte nişanlanmışlardır) ve bu nedenle bu tercih eder . O halde, ilk iddia ile bir çelişkimiz var.m{\ displaystyle \ textstyle m}w{\ displaystyle \ textstyle w}m{\ displaystyle \ textstyle m}w{\ displaystyle \ textstyle w}w′{\ displaystyle \ textstyle w '}
- Eğer bir tane varsa, o zaman onlar birbirleriyle nişanlanmadıkları için reddedilmiş demektir . Yani bu , bir erkekten (kabul ettiği) bir teklif almasına neden olur . Böylece, o anlamak tercih etmek . Şimdi, algoritmanın sonunda ortağıdır . Bu nedenle:m{\ displaystyle \ textstyle m}w′{\ displaystyle \ textstyle w '}w′{\ displaystyle \ textstyle w '}m″∈M\ textstyle M içinde {\ displaystyle \ textstyle m '' \w′{\ displaystyle \ textstyle w '}m″{\ displaystyle \ textstyle m ''}m{\ displaystyle \ textstyle m}m′{\ displaystyle \ textstyle m '}w′{\ displaystyle \ textstyle w '}
- Ya ;
m′=m″{\ displaystyle \ textstyle m '= m' '}
- Ya tercih etmek .
w′{\ displaystyle \ textstyle w '}m′{\ displaystyle \ textstyle m '}m″{\ displaystyle \ textstyle m ''}
Ama her iki durumda da, bunu almak tercih etmek . O halde, ilk iddia ile bir çelişkimiz var.
w′{\ displaystyle \ textstyle w '}m′{\ displaystyle \ textstyle m '}m{\ displaystyle \ textstyle m}
Sonuç olarak, her durumda, ilk ifadede bir çelişki ile karşılaşırız. Bu nedenle, bu yanlıştır ve evliliklerden birinde istikrarsızlık yoktur. Sonuç olarak, tüm evlilikler sabittir.
Çözümün optimalliği
Çözüm kararlı olsa da, tüm bireyler için mutlaka optimal bir çözüm olmayabilir. Algoritmanın geleneksel biçimi, öneren kişiler için idealdir, ancak seçim yapanlar için zorunlu değildir. İşte bir örnek :
Üç talip A, B ve C ve ilgili tercih sırası:
A: YXZ, B: ZYX, C: XZY, X: BAC, Y: CBA, Z: ACB
olan üç talip vardır.
Bu evlilik sorununun üç istikrarlı çözümü vardır:
- yarışmacıların ilk tercihleri ve üçüncü seçenlerin (AY, BZ, CX)
- tüm katılımcıların ikinci seçeneği vardır (AX, BY, CZ)
- seçiciler ilk tercihlerine sahipler ve yarışmacılar üçüncü seçimlerine sahipler (AZ, BX, CY)
Yukarıda sözde kod örneği olarak sunulan algoritma ilk çözümü verir.
Yukarıdaki bölümlerle aynı gösterimleri kullanarak şunu göstereceğiz:
Her erkek en sevdiği partneri ile nişanlanır.
Bazı kavramları tanımlayarak başlıyoruz:
- Bir kadın bir olduğu söylenir geçerli ortağı bir adamın bir dizi varsa hepsi bireyleri içeren ve içerdiği istikrarsızlık olmadan; işlenen çiftler (kadın erkek) ait .w∈W{\ displaystyle \ textstyle w \ W olarak}m∈M{\ displaystyle \ textstyle m \ M olarak}S{\ displaystyle \ textstyle S}(m;w){\ displaystyle \ metin stili (m; w)}
- İyi ortak bir ifade, , tek ortak geçerlidir : olarak , geçerli bir ortaktır tercih etmekm∈M{\ displaystyle \ textstyle m \ M olarak}best(m)∈W{\ displaystyle \ textstyle en iyi (m) \ W olarak}m{\ displaystyle \ textstyle m}
∀{\ displaystyle \ forall} w∈W∖{best(m)}{\ displaystyle \ textstyle w \ W \ setminus \ {en iyi (m) \}}(w{\ displaystyle \ textstyle (w}m⇒m{\ displaystyle \ textstyle m \ Rightarrow m}best(m){\ displaystyle \ textstyle en iyisi (m)}w){\ displaystyle \ textstyle w)}
- Biz tarafından ifade = {( ; ) / } yapan çiftler kümesi olarak.S∗{\ displaystyle \ textstyle S ^ {*}}m{\ displaystyle \ textstyle m}best(m){\ displaystyle \ textstyle en iyisi (m)}m∈M{\ displaystyle \ textstyle m \ M olarak}
Gale-Shapley algoritmasının herhangi bir çalıştırmasının geri döndüğünü göstereceğiz .
S∗{\ displaystyle \ textstyle S ^ {*}}
S∗{\ displaystyle \ textstyle S ^ {*}} tüm erkekleri ve kadınları içerir:
Nitekim, tanımı gereği tüm erkekleri içerir . Ek olarak, bir erkeğin tanım gereği yalnızca bir en iyi ortağı vardır . Yani iki farklı kadınla nişanlanamaz. O göreceğiz aynı favori kadın , başka bir adam ile meşgul olamaz, farklı yer . Bir dizi nişanlı çiftin tanımı gereği acildir. Nitekim değilse, biz :, olabilir söylemek olduğunu ve her ikisi de aynı kadını tercih ediyorum. Ama sonra, en az iki kez ortaya çıkacaktı , bu imkansız çünkü bir dizi nişanlı çift. Böylece setler gibi ve benzer şekilde kardinaldir, tüm kadınları da içerir.
S∗{\ displaystyle \ textstyle S ^ {*}}m∈M{\ displaystyle \ textstyle m \ M olarak}m∈M{\ displaystyle \ textstyle m \ M olarak}best(m)∈W{\ displaystyle \ textstyle en iyi (m) \ W olarak}m{\ displaystyle \ textstyle m}best(m)∈W{\ displaystyle \ textstyle en iyi (m) \ W olarak}m∈M{\ displaystyle \ textstyle m \ M olarak}m′∈M{\ displaystyle \ textstyle m '\ M olarak}m{\ displaystyle \ textstyle m}S∗{\ displaystyle \ textstyle S ^ {*}}best(m)=best(m′){\ displaystyle \ textstyle en iyi (m) = en iyi (m ')}m{\ displaystyle \ textstyle m}m′{\ displaystyle \ textstyle m '}best(m){\ displaystyle \ textstyle en iyisi (m)}S∗{\ displaystyle \ textstyle S ^ {*}}S∗{\ displaystyle \ textstyle S ^ {*}}M{\ displaystyle \ textstyle M}W{\ displaystyle \ textstyle W}S∗{\ displaystyle \ textstyle S ^ {*}}
S∗{\ displaystyle \ textstyle S ^ {*}} istikrarsızlık yok :
Bize saçma tarafından nedenini edelim ve varsayalım bir istikrarsızlık var olan . Yani istikrarsızlık tanımı gereği tercih etmek demektir . Bu, tanımıyla çelişir , çünkü o zaman tercih edilenin geçerli bir ortağıdır . Bu nedenle istikrarsızlık yoktur.
S∗{\ displaystyle \ textstyle S ^ {*}}(m;w)∈M×W{\ displaystyle \ textstyle (m; w) \, M \ kere W}w≠best(m){\ displaystyle \ textstyle w \ neq en iyi (m)}m{\ displaystyle \ textstyle m}w{\ displaystyle \ textstyle w}best(m){\ displaystyle \ textstyle en iyisi (m)}best(m){\ displaystyle \ textstyle en iyisi (m)}w{\ displaystyle \ textstyle w}m{\ displaystyle \ textstyle m}best(m){\ displaystyle \ textstyle en iyisi (m)}S∗{\ displaystyle \ textstyle S ^ {*}}
Algoritma şunu döndürür :
S∗{\ displaystyle \ textstyle S ^ {*}}
Saçma ile mantık yürütelim ve bir set döndüren algoritmanın çalıştırılmasının olduğunu varsayalım . Yani öyle bir adam var . Algoritma sırasında bir kadın tarafından reddedildiğini hemen anlıyoruz (çünkü aksi takdirde bir kadınla nişanlanacak ve algoritmaya göre, tanım gereği imkansız olan tercih edilen geçerli bir partner olacaktı ). Belirli bir erkeğin belirli bir sağlıklı kadın tarafından ilk kez reddedildiğini düşünün . Sonra algoritması tarafından gibi ilk öneride , o kadar gerekliydi: . Gerçekten de değilse, bu demektir tercih için ikinci tanımına imkansızdır. Algoritmaya göre, tarafından reddedilmesine izin veren iki olası durum vardır :
S≠S∗{\ displaystyle \ textstyle S \ neq S ^ {*}}m∈M{\ displaystyle \ textstyle m \ M olarak}(m;best(m))∉S{\ displaystyle \ textstyle (m; en iyi (m)) \ notin S}m{\ displaystyle \ textstyle m}m{\ displaystyle \ textstyle m}w≠best(m){\ displaystyle \ textstyle w \ neq en iyi (m)}w{\ displaystyle \ textstyle w}m{\ displaystyle \ textstyle m}best(m){\ displaystyle \ textstyle en iyisi (m)}t0{\ displaystyle \ textstyle t_ {0}}m0∈M{\ displaystyle \ textstyle m_ {0} \ M olarak}w0∈W{\ displaystyle \ textstyle w_ {0} \ W olarak}m0{\ displaystyle \ textstyle m_ {0}}best(m0){\ displaystyle \ textstyle en iyisi (m_ {0})}w0=best(m0){\ displaystyle \ textstyle w_ {0} = en iyi (m_ {0})}m0{\ displaystyle \ textstyle m_ {0}}w0{\ displaystyle \ textstyle w_ {0}}best(m0){\ displaystyle \ textstyle en iyisi (m_ {0})}m0{\ displaystyle \ textstyle m_ {0}}best(m0){\ displaystyle \ textstyle en iyisi (m_ {0})}
- Ya şu anda bir erkekle halihazırda meşgul olan ve tercih edenlere bir teklifte bulundu ;m0{\ displaystyle \ textstyle m_ {0}}best(m0){\ displaystyle \ textstyle en iyisi (m_ {0})}m′∈M{\ displaystyle \ textstyle m '\ M olarak}t0{\ displaystyle \ textstyle t_ {0}}best(m0){\ displaystyle \ textstyle en iyisi (m_ {0})}m′{\ displaystyle \ textstyle m '}m0{\ displaystyle \ textstyle m_ {0}}
- Ya kabul ettiği bir adamla nişanlandı ve anında bir teklif aldı . Yani bu tercih etmek demektir .best(m0){\ displaystyle \ textstyle en iyisi (m_ {0})}m0{\ displaystyle \ textstyle m_ {0}}t0{\ displaystyle \ textstyle t_ {0}}m″∈M{\ displaystyle \ textstyle m '' \ M olarak}best(m0){\ displaystyle \ textstyle en iyisi (m_ {0})}m″{\ displaystyle \ textstyle m ''}m0{\ displaystyle \ textstyle m_ {0}}
Her iki durumda da, bu olmadığı anlamına gelir böyle bir adam olarak tercih etmek . Tarafından reddedildikten sonra (şu anda ), o zaman taahhüdümüz var (erkek, kadın) .
m1∈M{\ displaystyle \ textstyle m_ {1} \ M olarak}best(m0){\ displaystyle \ textstyle en iyisi (m_ {0})}m1{\ displaystyle \ textstyle m_ {1}}m0{\ displaystyle \ textstyle m_ {0}}m0{\ displaystyle \ textstyle m_ {0}}best(m0){\ displaystyle \ textstyle en iyisi (m_ {0})}t0{\ displaystyle \ textstyle t_ {0}}(m1;best(m0))∈M×W{\ displaystyle \ textstyle (m_ {1}; en iyi (m_ {0})) \ M \ times W}
Ancak, tanımı gereği , için geçerli bir ortaktır . Yani tanım gereği geçerli bir ortağı, bu kararlı çiftler (erkek, kadın) bir dizi varlığını neden gibi istikrarsızlık olmaksızın: . Ya ile ilgili kadın in olduğu gibi, demek: . Algoritmasına göre, ettik: .
best(m0){\ displaystyle \ textstyle en iyisi (m_ {0})}m0{\ displaystyle \ textstyle m_ {0}}S′{\ displaystyle \ textstyle S '}(m0;best(m0))∈S′{\ displaystyle \ textstyle (m_ {0}; en iyi (m_ {0})) \ S içinde '}w1∈W{\ displaystyle \ textstyle w_ {1} \ W olarak}m1{\ displaystyle \ textstyle m_ {1}}S′{\ displaystyle \ textstyle S '}(m1;w1)∈S′{\ displaystyle \ textstyle (m_ {1}; w_ {1}) \ S içinde '}w1≠best(m0){\ displaystyle \ textstyle w_ {1} \ neq best (m_ {0})}
Seti elde etmeyi sağlayan Gale-Shapley algoritmasının yürütülmesine ilişkin çalışmayı sürdürüyoruz . As ilk adam (şu ilişkili çünkü algoritma yürütülürken reddedilmesi için ) ve anın sonunda bu , birlikte devreye girer , bunu anlamak reddedilen değildi andan önce ve bu nedenle ilk öneri o için yapıldı . Öyleyse tercih et .
S{\ displaystyle \ textstyle S}m0{\ displaystyle \ textstyle m_ {0}}t0{\ displaystyle \ textstyle t_ {0}}t0{\ displaystyle \ textstyle t_ {0}}m1{\ displaystyle \ textstyle m_ {1}}best(m0){\ displaystyle \ textstyle en iyisi (m_ {0})}m1{\ displaystyle \ textstyle m_ {1}}t0{\ displaystyle \ textstyle t_ {0}}best(m0){\ displaystyle \ textstyle en iyisi (m_ {0})}m1{\ displaystyle \ textstyle m_ {1}}best(m0){\ displaystyle \ textstyle en iyisi (m_ {0})}w1{\ displaystyle \ textstyle w_ {1}}
Özetlemek gerekirse, bu nedenle elimizde:
-
(m1;w1)∈S′{\ displaystyle \ textstyle (m_ {1}; w_ {1}) \ S içinde '} ;
-
(m0;best(m0))∈S′{\ displaystyle \ textstyle (m_ {0}; en iyi (m_ {0})) \ S içinde '} ;
-
best(m0){\ displaystyle \ textstyle en iyisi (m_ {0})}tercih etmek ;m1{\ displaystyle \ textstyle m_ {1}}m0{\ displaystyle \ textstyle m_ {0}}
-
m1{\ displaystyle \ textstyle m_ {1}}tercih etmek ;best(m0){\ displaystyle \ textstyle en iyisi (m_ {0})}w1{\ displaystyle \ textstyle w_ {1}}
Yani tanım gereği istikrarsızlıktır . Ancak, istikrarsızlık olmadan tanımlanır. Bu nedenle, tanımıyla çelişiriz . Bu nedenle, başlangıç varsayımının yanlış olduğu ve Gale-Shapley'in algoritmasının uygulamasından farklı bir dizi nişanlı çift (erkek; kadın) döndürmeyen hiçbir uygulaması olmadığıdır . Bu nedenle, bu algoritmanın tüm yürütmeleri geri döner .
(m1;best(m0)){\ displaystyle \ textstyle (m_ {1}; en iyi (m_ {0}))}S′{\ displaystyle \ textstyle S '}S′{\ displaystyle \ textstyle S '}S′{\ displaystyle \ textstyle S '}S∗{\ displaystyle \ textstyle S ^ {*}}S∗{\ displaystyle \ textstyle S ^ {*}}
Her kadın en az sevdiği partneriyle nişanlanır.
Bazı kavramları tanımlayarak başlıyoruz:
- Bir erkeğin , tüm bireyleri içeren ve içerdiği dengesizlik olmayan bir dizi kararlı çift (erkek; kadın) varsa, kadının geçerli bir ortağı olduğu söylenir .m∈M{\ displaystyle \ textstyle m \ M olarak}w∈W{\ displaystyle \ textstyle w \ W olarak}S{\ displaystyle \ textstyle S}(m;w){\ displaystyle \ metin stili (m; w)}
- En kötü ortağı arasında gösterilen, , tek ortak geçerlidir : olarak , geçerli bir ortaktır tercih etmekw∈W{\ displaystyle \ textstyle w \ W olarak}wÖrst(w)∈M{\ displaystyle \ textstyle en kötü (w) \ M olarak}w{\ displaystyle \ textstyle w}
∀{\ displaystyle \ forall} m∈M∖{wÖrst(w)}{\ displaystyle \ textstyle m \ içinde M \ setminus \ {en kötü (w) \}}(m{\ displaystyle \ metin stili (m}w⇒w{\ displaystyle \ textstyle w \ Rightarrow w}m{\ displaystyle \ textstyle m}wÖrst(w)){\ displaystyle \ textstyle en kötü (w))}
Genel olarak , her kadının en kötü partneri ile nişanlandığını göstereceğiz .
S∗{\ displaystyle \ textstyle S ^ {*}}
Çelişki tarafından iddia ve orada var olduğunu varsayalım öyle ki: . Yani, tanımı gereği , geçerli bir ortağı yoktur ait gibi tercih etmek . Gerçekten de, eğer değil, yani iş ortağı azından sevdim doğrular biz olur bu yüzden, ve: .
(m;w)∈S∗{\ displaystyle \ textstyle (m; w) \ S ^ {*}} içindem≠wÖrst(w){\ displaystyle \ textstyle m \ neq en kötü (w)}wÖrst(w){\ displaystyle \ textstyle en kötü (w)}m′∈M{\ displaystyle \ textstyle m '\ M olarak}w{\ displaystyle \ textstyle w}w{\ displaystyle \ textstyle w}m{\ displaystyle \ textstyle m}m′{\ displaystyle \ textstyle m '}m{\ displaystyle \ textstyle m}w{\ displaystyle \ textstyle w}m=wÖrst(w){\ displaystyle \ textstyle m = en kötü (w)}
Gibi geçerli bir ortağıdır , tanımı gereği, taahhüt çiftlerin bir dizi olduğu kadar istikrarsızlık olmadan: . Ya ile ilgili kadın in olduğu gibi, demek: . Yani geçerli bir ortağıdır ve: . Üstelik gibi , bunu anlamak o ve bu nedenle tercih etmek .
m′{\ displaystyle \ textstyle m '}w{\ displaystyle \ textstyle w}S′{\ displaystyle \ textstyle S '}(m′;w)∈S′{\ displaystyle \ textstyle (m '; w) \ S'}w′∈W{\ displaystyle \ textstyle w '\ W olarak}m{\ displaystyle \ textstyle m}S′{\ displaystyle \ textstyle S '}(m;w′)∈S′{\ displaystyle \ textstyle (m; w ') \ S'}w′{\ displaystyle \ textstyle w '}m{\ displaystyle \ textstyle m}w′≠w{\ displaystyle \ textstyle w '\ neq w}(m;w)∈S∗{\ displaystyle \ textstyle (m; w) \ S ^ {*}} içindew=best(m){\ displaystyle \ textstyle w = en iyi (m)}m{\ displaystyle \ textstyle m}w{\ displaystyle \ textstyle w}w′{\ displaystyle \ textstyle w '}
Özetlemek gerekirse, bu nedenle elimizde:
-
(m′;w)∈S′{\ displaystyle \ textstyle (m '; w) \ S'} ;
-
(m;w′)∈S′{\ displaystyle \ textstyle (m; w ') \ S'} ;
-
w{\ displaystyle \ textstyle w}tercih etmek ;m{\ displaystyle \ textstyle m}m′{\ displaystyle \ textstyle m '}
-
m{\ displaystyle \ textstyle m}tercih etmek .w{\ displaystyle \ textstyle w}w′{\ displaystyle \ textstyle w '}
Yani tanım gereği istikrarsızlıktır . Ancak, istikrarsızlık olmadan tanımlanır. Bu nedenle, tanımıyla çelişiriz . Bu nedenle, ilk varsayımın yanlış olduğu ve en kötü partnerinden farklı bir erkekle ilişkisi olmayan hiçbir kadın olmadığıdır . Bu nedenle, genel olarak , her kadın en kötü partneri ile nişanlanır.
(m;w){\ displaystyle \ metin stili (m; w)}S′{\ displaystyle \ textstyle S '}S′{\ displaystyle \ textstyle S '}S′{\ displaystyle \ textstyle S '}S∗{\ displaystyle \ textstyle S ^ {*}}S∗{\ displaystyle \ textstyle S ^ {*}}
Uygulama
Gale-Shapley algoritması örneğin Java'da uygulanabilir. Zaman zaman karmaşık bir yapıya sahiptir , burada istikrarlı evlilik sorunu için düşünülen kadın ve erkek sayısı:
Ö(değil2){\ displaystyle \ metin stili O (n ^ {2})}değil{\ displaystyle \ textstyle n}
public static int[] Gale_Shapley(int[] M, int[] W, int[][] MPref, int[][] WPref) {
int n = M.length;
LinkedList<Integer> Libre= new LinkedList<Integer>();
int[] Prochain = new int[n] ;
int[] Actuel = new int[n];
for (int i = 0 ; i<n ; i++) {
Libre.add(M[i]);
Prochain[i] = 0;
Actuel[i] = 0;
}
while (!Libre.isEmpty()) {
int m = Libre.get(0);
int w = MPref[m-1][Prochain[m-1]];
if (Actuel[w-1] == 0) {
Actuel[w-1] = m;
Libre.remove(0);
} else {
int i = 0;
int m0 = Actuel[w-1];
while (WPref[w-1][i] != m && WPref[w-1][i] != m0) {
i++;
}
if (WPref[w-1][i] == m) {
Actuel[w-1] = m;
Libre.remove(0);
Libre.add(m0);
}
}
Prochain[m-1]++;
}
return Actuel;
}
Bu işlevle ilgili çeşitli nesneler aşağıda açıklanmış ve işleyişi açıklanmıştır.
Gale-Shapley işlevinin unsurları
- ve öğeleri , her iki dizi için bu sırayla 1 ile arasındaki tamsayıları içeren boyuttaki tamsayı dizileridir. Bu iki tablo , istikrarlı evlilik sorunu için düşünülen kadın ve erkek gruplarını temsil etmektedir .
M{\ displaystyle \ textstyle M}W{\ displaystyle \ textstyle W}değil{\ displaystyle \ textstyle n}değil{\ displaystyle \ textstyle n}M′{\ displaystyle \ textstyle M '}W′{\ displaystyle \ textstyle W '}
- ve öğeleri , tamsayıların iki boyutlu dizileridir ve 1 ve her iki dizi için tamsayılar içerir . Onlar her erkeklerin tercihlerinin ailesini temsil (için ) ve tüm kadınların tercihleri ailesini (için ). İki tablodan birindeki her satır, bir bireyin tercih ilişkisine karşılık gelir. Eğer ve ardından tam sayıdır tekabül ait bırakanların favori kadın in . Aynısı için de geçerlidir .
MPref{\ displaystyle \ textstyle MPref}WPref{\ displaystyle \ textstyle WPref}değil×değil{\ displaystyle \ textstyle n \ kere n}değil{\ displaystyle \ textstyle n}M′{\ displaystyle \ textstyle M '}MPref{\ displaystyle \ textstyle MPref}W′{\ displaystyle \ textstyle W '}WPref{\ displaystyle \ textstyle WPref}m∈{1;...;değil}{\ displaystyle \ textstyle m \ in \ {1; \ ldots; n \}}ben∈{1;...;değil}{\ displaystyle \ textstyle i \ in \ {1; \ ldots; n \}}MPref[m-1][ben-1]{\ displaystyle \ textstyle MPref [m-1] [i-1]}j∈{1;...;değil}{\ displaystyle \ textstyle j \ in \ {1; \ ldots; n \}}ben{\ displaystyle \ textstyle ı}m{\ displaystyle \ textstyle m}W′{\ displaystyle \ textstyle W '}WPref{\ displaystyle \ textstyle WPref}
- Öğe , bekar olan erkeklerin (içindeki numaralarıyla tanımlanır) saklandığı bağlantılı bir listedir .
Lbenbre{\ displaystyle \ textstyle Libre}M′{\ displaystyle \ textstyle M '}M{\ displaystyle \ textstyle M}
- Öğe , büyüklükte tam sayılardan oluşan bir dizidir . Fonksiyon döngüsünün bir sonraki turunda bir erkeğin hangi kadına sunması gerektiğini belirler. Yani, eğer , ilişkili erkek tercihi ile ilgili olarak rütbe içinde . Başka bir deyişle, işlevin her döngü ile ilişkili adam in (o seçilmiş kişi ise) içinde kadına teklifini ile ilişkili . daha sonra döngü dönüşünün sonunda 1 artırılır. İşlevin başlangıcında, döngüye girmeden önce, her yerde 0'larla başlatılır (bu, her erkeğin tercih ettiği kadına ilk önermesini yapacağı anlamına gelir).
PrÖvsh-debendeğil{\ displaystyle \ textstyle Sonraki}değil{\ displaystyle \ textstyle n}m∈{1;...;değil}{\ displaystyle \ textstyle m \ in \ {1; \ ldots; n \}}PrÖvsh-debendeğil[m-1]{\ displaystyle \ textstyle Sonraki [m-1]}m{\ displaystyle \ textstyle m}M′{\ displaystyle \ textstyle M '}m{\ displaystyle \ textstyle m}M′{\ displaystyle \ textstyle M '}W′{\ displaystyle \ textstyle W '}MPref[m-1][PrÖvsh-debendeğil[m-1]]{\ displaystyle \ textstyle MPref [m-1] [Sonraki [m-1]]}PrÖvsh-debendeğil[m-1]{\ displaystyle \ textstyle Sonraki [m-1]}PrÖvsh-debendeğil{\ displaystyle \ textstyle Sonraki}
- Öğe , büyüklükte tam sayılardan oluşan bir dizidir . Bu (kendi numarasıyla tanımlanır akım ortakları depolayan tüm kadınların) (kendi numarasıyla tanımlanır ). Öyleyse, eğer , bu kadın bir erkekle nişanlıysa, kadının eşiyle ilişkili sayı mı, bekar ise 0 mı. İşlevin başlangıcında, döngüye girmeden önce , bu nedenle her yerde 0'larla başlatılır, çünkü tüm kadınlar bekardır.
ATvstsenel{\ displaystyle \ textstyle Güncel}değil{\ displaystyle \ textstyle n}M{\ displaystyle \ textstyle M}W′{\ displaystyle \ textstyle W '}W{\ displaystyle \ textstyle W}w∈{1;...;değil}{\ displaystyle \ textstyle \ {1; \ ldots; n \}}ATvstsenel[w-1]{\ displaystyle \ textstyle Mevcut [w-1]}w{\ displaystyle \ textstyle w}ATvstsenel{\ displaystyle \ textstyle Güncel}
Açıklanması Gale-Shapley'in işlevi
Fonksiyonun açıklaması aşağıdaki gibidir:
Liste boş olmadığı sürece , yani en az bir evli olmayan erkek olduğu sürece, böyle bir adam seçilir ( işlevde). Tercih ettiği kadını, kendisini teklif etmediği herkes arasında (pozisyonda) görüyoruz.
Lbenbre{\ displaystyle \ textstyle Libre}m{\ displaystyle \ textstyle m}w{\ displaystyle \ textstyle w}
- Eğer bekar sonra ve birlikte meşgul ve o listeyi bırakır, böylece artık bekar .
w{\ displaystyle \ textstyle w}(ATvstsenel[w-1]==0){\ displaystyle \ textstyle (Geçerli [w-1] == 0)}m{\ displaystyle \ textstyle m}w{\ displaystyle \ textstyle w}(ATvstsenel[w-1]=m){\ displaystyle \ textstyle (Geçerli [w-1] = m)}m{\ displaystyle \ textstyle m}Lbenbre{\ displaystyle \ textstyle Libre}
- Aksi takdirde, başka bir adamla ( işlevde) nişanlanır . Daha sonra en sevdiği partnerini ve arasında ararız . Bunu yapmak için, biz en küçük indeksi bakmak böyle olduğu veya tanımına göre, . O tercih ederse etmek , o ile kayıt ve listeyi terk artık tek iken, çünkü tek olur ve liste katıldı . Eğer tercih etmek , sonra hiçbir şey değişir, kalıntılar ile uğraşan ve bu nedenle listede, bekar kalır .
w{\ displaystyle \ textstyle w}m0{\ displaystyle \ textstyle m0}m{\ displaystyle \ textstyle m}m0{\ displaystyle \ textstyle m0}ben∈{1;...;değil}{\ displaystyle \ textstyle i \ in \ {1; \ ldots; n \}}WPref[w-1][ben-1]{\ displaystyle \ textstyle WPref [w-1] [i-1]}m{\ displaystyle \ textstyle m}m0{\ displaystyle \ textstyle m0}WPref{\ displaystyle \ textstyle WPref}m{\ displaystyle \ textstyle m}m0{\ displaystyle \ textstyle m0} (WPref[w-1][ben-1]==m){\ displaystyle \ textstyle (WPref [w-1] [i-1] == m)}w{\ displaystyle \ textstyle w}m{\ displaystyle \ textstyle m} (ATvstsenel[w-1]=m){\ displaystyle \ textstyle (Geçerli [w-1] = m)}m{\ displaystyle \ textstyle m}Lbenbre{\ displaystyle \ textstyle Libre}m0{\ displaystyle \ textstyle m0}Lbenbre{\ displaystyle \ textstyle Libre}w{\ displaystyle \ textstyle w}m0{\ displaystyle \ textstyle m0}m{\ displaystyle \ textstyle m}w{\ displaystyle \ textstyle w}m0{\ displaystyle \ textstyle m0}m{\ displaystyle \ textstyle m}Lbenbre{\ displaystyle \ textstyle Libre}
Son olarak, her ne durum vis-à-vis döngünün sonunda (tek veya birlikte yapan ) o işlevin yürütülmesi geri kalanında tek kalırsa, o zaman başka bir kadına buna yeni bir öneri yapmak zorunda kalacaktır daha az sevecek . Son olarak, işlev , oluşturulan çiftleri doğrudan okumayı mümkün kılan tabloyu döndürür .
m{\ displaystyle \ textstyle m}w{\ displaystyle \ textstyle w}w{\ displaystyle \ textstyle w}m{\ displaystyle \ textstyle m} (PrÖvsh-debendeğil[m-1]++){\ displaystyle \ textstyle (Sonraki [m-1] ++)}ATvstsenel{\ displaystyle \ textstyle Güncel}
Java'da Gale-Shapley algoritmasının bir uygulamasını elde ettiğimizi görebiliriz. Ek olarak, bu işlevin maliyetinin gerçekten de olduğunu fark ettik .
Ö(değil2){\ displaystyle \ metin stili O (n ^ {2})}
Kitaplıklar
-
C : İstikrarlı evlilik sorunu ve üniversiteye kabul sorunu için Gale-Shapley algoritması pakette mevcuttur matchingMarkets.
-
API : MatchingTools API, algoritma için bir uygulama programlama arabirimi sağlar.
-
Python : Gale-Shapley algoritması kitaplıkta mevcutturQuantEcon/MatchingMarkets.py
Notlar ve referanslar
-
(in) D. Gale ve LS Shapley, "College Admissions and the Stability of Marriage", Amer. Matematik. Ay. , uçuş. 69, 1962, s. 9-14
-
(in) Harry Mairson (in) , "The Stable Marriage Problem", The Brandeis Review , Cilt. 12, 1992 ( çevrimiçi sürüm ).
-
(in) Numberphile, " Kararlı Evlilik Problemi " üzerine Youtube.com ,4 Eylül 2014( 7 Ekim 2014'te erişildi )
-
.
Donald Knuth, Kararlı Düğünler ve Diğer Kombinatoryal Problemlerle İlişkileri , Montreal, Les Presses de l'Université de Montréal1976, 106 s. ( ISBN 978-2-7606-0529-9 , çevrimiçi sunum )
-
(en) Jon Kleinberg ve Éva Tardos , Algoritma Tasarımı , Addison Wesley,2005, 838 s. ( ISBN 978-0-321-29535-4 ) , s. 1.
-
T. Klein , " R'de Kararlı Eşleşmelerin Analizi: Paket Eşleştirme Pazarları ", Vinyet - R Paket eşleştirme Pazarları ,2015( çevrimiçi okuyun )
-
" matchingMarkets: Kararlı Eşleşmelerin Analizi " , R Projesi
-
" MatchingTools API "
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">