Birden fazla yarışmadan sonra aday atamak için algoritma

Çoklu Rekabet Başvuru Atama Algoritması bir uygulamadır istikrarlı evlilik sorunu ve Gale ve Shapley algoritması pratik bir soruna. Kararlı bir atama sağlayan algoritma, adayların seçimlerini veya kursların kalitesini tercih eden veya hatta pişmanlık sayısını en aza indiren bir ara çözüm öneren bir stratejiye göre ardışık yinelemelerle çalışır. Özellikle Fransa'da bilgisayarlı ulusal sınıflandırma sınavlarından sonra öğrencilerin atamalarını belirlemek için kullanılır (bazen ECNI olarak kısaltılır).

Sorun

Adaylar bir yarışmadan sonra sıralandıklarında, ödevleri basittir: en iyi dereceye sahip öğrenci kendi seçtiği yolu seçer ve aşağıdakiler, sıralamalarına göre, hala yerlerin bulunduğu yerler arasından kendi seçtikleri yolu seçer. Burada kavramsal bir zorluk yok. Bu seçim, bazen " garnizon konferans salonu " olarak adlandırılan bir toplantı sırasında canlı olarak yapılabilir .

Aynı adaylar birkaç yarışmaya katıldığında (ve böylece farklı sıralama dereceleri elde ettiğinde), görevlerin koordinasyonu isteniyorsa sorun biraz daha karmaşıktır. N öğrenci popülasyonunun ve M farklı akarsuyun varlığındayız , her akarsuyun genellikle sınırlı sayıda yeri vardır. Bu nedenle M yarışmalarını geçen öğrenciler, her bir derlemede bir olmak üzere M sıralaması elde ettiler. Her öğrenci bir seçim yapmalı ve bu nedenle dersleri tercih sırasına göre sıralamalıdır. Aynı şekilde her sektörün öğrencileri tercih sırasına göre sıralayarak seçeceğini düşünebiliriz (bu sıralama tabii ki yarışmada elde edilen bir sıralama). Bu nedenle sorun oldukça simetriktir (akışlar öğrencileri seçer / öğrenciler akışları seçer) ve genel olarak akışların seçimi ile öğrencilerin seçimi arasında ortaya çıkan çatışmalar (bir akışı tercih eden herkes mutlaka yararlı sıralamada sınıflandırılmaz. ).

Bu nedenle, öğrencilerin farklı yarışmalardaki sıralamalarını ve farklı akışlar arasındaki tercihlerini dikkate alarak öğrencilerin farklı akışlara atanmasına karar vermek için bir yöntem bulunmalıdır. Bir yöntem, kanaldan sonra devam etmektir, ancak bunun iki büyük dezavantajı olacaktır:

sektörler arasında bir hiyerarşi ortaya çıkarırdı
bir öğrenci, avını gölgede bırakmaktan kaçınmak için (yani riski en aza indirmek için) bir başkasının kendi tercihine sahip olmasına rağmen, iyi sınıflandırıldığı yolu seçme eğiliminde olacaktır.

Bu sorun , 2010-2011'de sağlık araştırmalarının (PACES) ilk yılını oluştururken ortaya çıktı . David Gale ve Lloyd Shapley tarafından önerilen “kararlı evlilik algoritması” adlı bir algoritmanın kullanılmasıyla çözüldü .

Kararlı evlilik algoritması

Evlenmek istediğimiz N erkek ve N kadını ele alalım (bu algoritma sadece iki partili tanımlanmış bir popülasyondaki evliliklerle ilgilidir). İlk bakışta aşk romantizminden uzaklaşmayı kabul edersek, şu şekilde ilerleyeceğiz: her erkek N kadını tercih sırasına göre sıralayacaktır; aynı şekilde, her kadın N erkeği tercih sırasına göre (bağsız) sıralayacaktır. Daha sonra algoritma, zinanın imkansız olduğu çiftlerin bir listesini oluşturmaya çalışacaktır: aslında, seçilen konfigürasyonda, bir erkek karısını aldatmak isterse, karısını söz konusu adama tercih edecek ve reddedecektir. bu nedenle zina. Aynı şekilde, bir kadın, şu anki kocasından daha çok beğeneceği bir erkek bulsa, söz konusu erkek, söz konusu kadına karısını tercih ederek aynı fikirde olmayacaktır. İstikrarlı evlilik (zina mümkün değildir) terimi buradan gelmektedir.

Bu evlilik sorunu öğrencilerimizle nasıl ilişkilidir? Aşağıdaki benzetmeyi basitçe yapabiliriz:

öğrenciler erkeklere karşılık gelir (örneğin)
farklı akarsulardaki mevcut yerler kadınlara karşılık gelir

Bu nedenle, öğrencilere atama yapmak, onları kurslarla "evlendirmek" anlamına gelir.

Bu algoritma neyi garanti ediyor?

Evlilikler ve olası zinanın yokluğu ile benzerlik kurarak, algoritma aşağıdakileri garanti edecektir: eğer bir öğrenci A bir derse atanmışsa, B öğrencisi değilse, bu şu şekilde olabilir:

ya A bu sektörde B'den daha iyi sınıflandırılır (ve bu durumda doğrudur)
ya B kendisinin tercih ettiği bir kursa atanmıştır (bu durumda da şikayet etmek zorunda değildir)

Bu nedenler, bu algoritmanın örneğin Amerika Birleşik Devletleri'nde dahili (in) tahsisi için kullanılmasını sağlar .

Bu algoritmayı çalıştırmak için iki seçenek

Düğünler (veya görevler) sırasında çatışma durumları ortaya çıkabilir. Bu durumda, algoritma ya erkeklerin seçimlerine ayrıcalık tanımak ya da kadınların seçimlerini ayrıcalıklı kılmak için yapılandırılabilir (bu aynı zamanda algoritmanın yalnızca heteroseksüel evlilikler için çalışmasının nedenidir).

Sağlık çalışmalarının ilk yılında (PACES) öğrenciler için ödev verilmesi durumunda , her iki seçenek de mümkündü:

ya sektörlerdeki öğrencilerin sıralamalarına öncelik verin, böylece her sektör en iyi dereceye sahip öğrencileri toplar
ya öğrenci seçimlerine öncelik verin, böylece öğrenciler tatmin olsun (mümkün olduğunca)

İkinci çözüm aşağıdaki nedenlerden dolayı seçildi:

öğrenciler olabildiğince memnun kalacak
sektörler motive olmuş öğrencileri kurtaracak
hatta derslerin ilgisini çekse bile, biraz daha iyi sınıflandırılmış bir öğrenciden biraz daha motive olan bir öğrenciyi kurtarmak muhtemelen tercih edilir (etkilenen öğrenciler zaten "iyi" öğrencilerdir).
bu, aşağıdaki paragrafta sunulan durumların kesişmesini önler

Geçiş durumu

Tıpta 100 yer ve eczanede 100 yer olduğunu varsayalım. Ödev ders seçimini (öğrencilerin değil) tercih etseydi, bazı durumlarda aşağıdaki yapılandırmayı elde edebilirdik:

Bir öğrenci sıralandığını 150 th tıpta ve son (atanmış 100 inci (o sırada nerede tıpta mevcut) uzay ama eczane tercih 151 th ).
Öğrenci B sıralanır 150 inci eczane ve atanan son (için 100 inci eczanelerde mevcut) uzay ama (o sırada nerede tıp tercih ediyorum 151 th ).

Bu iki öğrenci her iki derlemede de neredeyse eşit derecede iyidir. Görevlerini değiştirmek isterler (ki bu imkansızdır) ve bu nedenle hayal kırıklığına uğrayacaklardır. Öğrencilere seçimde ayrıcalık tanınması gerçeği bu tür durumlardan kaçınıyor.

Bu algoritma nasıl çalışır?

Bu algoritma yinelemeli olarak çalışır. Öğrencilerin tercihlerine öncelik verdiğimiz PACES için seçilen duruma kendimizi yerleştirirsek , şu şekilde ilerliyoruz:

bir öğrenci seçeriz, herhangi birini (nihai sonuç öğrencileri tedavi ettiğimiz sıraya bağlı olmayacaktır)
bu öğrenci tercih ettiği şubeye geçici olarak atanır
1. adımı bir çelişki olana kadar başka bir öğrenciyle tekrar ederiz (seçilen kursta yeterli yer kalmaz); bu durumda, akıştan etkilenen tüm öğrencilere bakarız ve bu akıştaki en düşük sırayı eledik. Bu öğrenci söz konusu akıştan kalıcı olarak çıkarılır ve geçici olarak ikinci seçiminin akışına atanır (veya ikinci seçiminin akışına atandıysa üçüncü olarak)
daha fazla değişiklik kalmayana kadar 1. adımdan yineleriz
çözüm daha sonra bulunur

Bu istikrarlı evlilik algoritması yakınsak (her zaman bir çözüme yakınlaşırız) ve istikrarlıdır (öğrencilere hangi sıra ile davranırsak davranalım, aynı başlangıç koşulları için her zaman aynı çözümü bulacaktır).

Ayrıca bir öğrenci bir A akışından çıkarıldığında ve bir B akışına atandığında, B akışında tam olarak ilk tercihi olarak B akışını seçecek bir öğrenci gibi muamele görür: yalnızca derecesi dikkate alınır. Bu nedenle bir öğrenci, ilk isteği olarak A akışını seçerse B akışında herhangi bir şans kaybetmez (açıkçası, eğer A akışına atanırsa, B akışına giremez).

Algoritmanın yinelemeli doğası, canlı bir kamu seçiminin ("garnizon konferans salonu") neden psikolojik olarak felaket olacağını açıklıyor: Bir öğrenciyi muhtemelen onu çıkarmadan önce ilk tercihi olan derse atayarak başlıyoruz. Ancak bu, şeffaflığı engellemez ve ödevlerin analizi, öğrenci B'ye değil de bir derse A öğrencisi atanırsa, A'nın bu dalda B'den daha iyi sınıflandırıldığı veya tercih ettiği başka bir branşa atandığı anlamına gelir. .

Algoritmanın bir örnekteki sırası

X, Y, Z sırasıyla 2, 1 ve 2 sıralı üç ders olsun. Sonuçları ve seçenekleri aşağıdaki listelerde tanımlanan beş A, B, C, D ve E adayı düşünün:

Sektör X [BCEAD] Y [CADEB] Z [BDECA] bazında sınıflandırmalar

Adayların seçimi A [XYZ] B [YXZ] C [ZYX] D [YXZ] E [YXZ]

Bu verilerden algoritmaya başlayabiliriz:

Her öğrenciye tercih ettikleri ders atanır: A X / B Y / C Z / D Y / E Y $\ sağ ok$ $\ sağ ok$ $\ sağ ok$ $\ sağ ok$ $\ sağ ok$
Y akışı taşıyor (1. sıra, 3 BDE adayı; en düşük sıradaki 2 B ve E elenir ve ikinci seçenek akışına atanır): A X / B X / C Z / D Y / E X $\ sağ ok$ $\ sağ ok$ $\ sağ ok$ $\ sağ ok$ $\ sağ ok$
Akış X dolup taşıyor (2 sıra, 3 ABE adayı; en düşük sıradaki A elenir ve birinin seçimine göre aşağıdaki akışa atanır): A Y / B X / C Z / D Y / E X $\ sağ ok$ $\ sağ ok$ $\ sağ ok$ $\ sağ ok$ $\ sağ ok$
Akış Y taşıyor (1 sıra, 2 AD adayı; en düşük sıradaki D elenir ve bir sonraki seçim akışına atanır): A Y / B X / C Z / D X / E X $\ sağ ok$ $\ sağ ok$ $\ sağ ok$ $\ sağ ok$ $\ sağ ok$
Akım X dolup taşıyor (2 sıra, 3 BDE adayı; en düşük sıradaki D elenir ve birinin seçtiği aşağıdaki akışa atanır): A Y / B X / C Z / D Z / E X $\ sağ ok$ $\ sağ ok$ $\ sağ ok$ $\ sağ ok$ $\ sağ ok$
Artık taşan sektör yok, yinelemelerin sonu. Sonucu alıyoruz: A Y / B X / C Z / D Z / E X $\ sağ ok$ $\ sağ ok$ $\ sağ ok$ $\ sağ ok$ $\ sağ ok$

Sonuç tatmin edicidir çünkü:

Sektör X'te, B ve E atanır; C, E'den daha iyi sınıflandırılmıştır, ancak tercih ettiği bir yola atanmıştır (Z)
Y dalında A atanır; C, A'dan daha iyi sınıflandırılmıştır, ancak tercih ettiği bir yola atanmıştır (Z)
Z dalında C ve D atanır; B, ikisinden daha iyi sınıflandırılmıştır, ancak Z'ye tercih ettiği X yoluna atanmıştır; E, C'den daha iyi sınıflandırılmıştır, ancak Z'ye tercih ettiği X yoluna atanmıştır.

Öğrenciler isteklerini formüle ederken hangi stratejiyi benimsemelidir?

Algoritma önemli bir ilgi vardır: hesaba saflarını alarak öğrencilere mümkün olan en iyi çözümü garanti edecek.

Öğrencilerin benimsemeleri gereken strateji bu nedenle çok basittir: Tercih ettikleri sektörü ilk seçenek olarak koyarlar (bu sektörde çok az başarı şansına sahip olduklarına inansalar bile). En iyi ihtimalle, bol şansla (diğer sektörlerdeki görevlerin oynanması yoluyla), orada görevlendirilecekler. En kötüsü, diğer sektörleri daha baştan seçmişler gibi kendilerini diğer sektörlere kıyasla tam olarak aynı durumda bulacaklar.

Karmaşık bir strateji benimsemeye yanlı olup olmadığı basitçe aykırı tercihlerini ifade etmek ilk tercihi kabul edilme şansını azaltabilecek bazı üniversite derslerine değil eski APB prosedürü.

Notlar ve referanslar

(fr) “Sağlık araştırmalarının ilk yılı reformu: her branşa kabul edilen öğrencileri belirlemek için bir aracın uygulanması”, Pédagogie Médicale 2012; 13 (1): 65–72 ( [1] ).
(in) Harry Mairson (in) , "The Stable Marriage Problem", The Brandeis Review , Cilt. 12, 1992 ( çevrimiçi sürüm ).
" Adalet için onlarla evlenelim!" » , Araştırma Üzerine ,1 st Ekim 2006( 6 Ekim 2014'te erişildi )
" Lloyds S. Shapley ve Alvin E.Roth " üzerine, Melchior ,2012( 6 Ekim 2014'te erişildi )
(in) " Lloyd S. Shapley - Gerçekler " , Nobelprize ( 6 Ekim 2014'te erişildi )