Multiple Soutěž Žadatel Assignment Algoritmus je aplikace problematiky stabilní manželství a algoritmus Gale a Shapley k praktickému problému. Algoritmus, který poskytuje stabilní přiřazení, pracuje postupnými iteracemi podle strategie, která může upřednostňovat výběr kandidátů nebo kvalitu kurzů, nebo dokonce navrhnout přechodné řešení minimalizující počet výčitek. Používá se zejména ve Francii k určení přidělení studentů po počítačových národních klasifikačních zkouškách (někdy zkráceně ECNI).
Pokud jsou kandidáti zařazeni po výběrovém řízení, jejich přiřazení je jednoduché: nejlépe hodnocený student si zvolí cestu podle svého výběru a následující si zvolí cestu podle svého výběru mezi tou, kde ještě jsou místa. Nejsou zde žádné koncepční potíže. Tuto volbu lze provést naživo během schůzky, která se někdy nazývá „ posádková posluchárna “.
Když se ti samí kandidáti zúčastní několika výběrových řízení (a získají tak různá hodnocení), je problém o něco složitější, pokud chce někdo koordinovat úkoly. Jsme v přítomnosti populace N studentů a M různých proudů, přičemž každý proud má řadu míst, která jsou obecně omezená. Studenti, kteří proto prošli M soutěžemi, získali M žebříčku, po jednom v každém proudu. Každý student bude muset vyjádřit svůj výběr, a proto kurzy seřadit podle preferencí. Stejně tak můžeme vzít v úvahu, že každý sektor si studenty vybere seřazením podle preferenčního pořadí (toto pořadí je samozřejmě takové, jaké získalo v soutěži). Problém je tedy celkem symetrický (proudy vybírají studenty / studenti vybírají proudy) s obecně konflikty, které vznikají mezi výběrem proudů a výběrem studentů (všichni, kteří upřednostňují proud, nemusí být nutně klasifikováni v užitečné hodnosti ).
Musí tedy být nalezena metoda, jak rozhodnout o přiřazení studentů do různých proudů, přičemž se vezme v úvahu jak hodnocení studentů v různých soutěžích, tak jejich preference mezi různými proudy. Jednou z metod by bylo postupovat kanál po kanálu, ale mělo by to dvě hlavní nevýhody:
Tento problém nastal při přípravě prvního ročníku zdravotnických studií (PACES) v letech 2010–2011. a bylo to vyřešeno použitím algoritmu zvaného „algoritmus stabilního manželství“, který navrhli David Gale a Lloyd Shapley .
Uvažujme N mužů a N žen, které si přejeme vzít (tento algoritmus se zabývá pouze sňatky v populaci, ve které je definována bipartice). Pokud se dohodneme, že se na první pohled vzdálíme od romantismu lásky, budeme postupovat následovně: každý muž zařadí N ženy podle preferenčního pořadí; podobně každá žena zařadí N mužů podle preferenčního pořadí (bez vazeb). Algoritmus se poté pokusí sestavit seznam párů, u nichž je cizoložství nemožné: ve zvolené konfiguraci chce muž skutečně podvádět svou manželku, která upřednostňuje svého současného manžela před dotyčným a odmítne. tedy cizoložství. Stejně tak, pokud by si žena našla muže, který se jí líbí více, než její současný manžel, dotyčný muž by nesouhlasil a dal přednost své ženě před dotyčnou ženou. Odtud pochází termín stabilní manželství (není možné cizoložství).
Jak tento manželský problém souvisí s našimi studenty? Můžeme jednoduše udělat následující analogii:
Přiřazení studentů se tedy rovná „sňatku“ s nimi.
Analogicky s manželstvím a absencí možného cizoložství algoritmus zaručí následující: pokud je student A přiřazen ke kurzu, zatímco B není, může to být:
Z těchto důvodů je tento algoritmus používán například ve Spojených státech k alokaci interních (in) .
Během svateb (nebo úkolů) mohou nastat konfliktní situace. V tomto případě lze algoritmus nakonfigurovat buď tak, aby privilegoval volby mužů, nebo aby privilegoval volby žen (to je také důvod, proč algoritmus může fungovat pouze pro heterosexuální manželství).
V případě úkolů pro studenty prvního ročníku studia zdravotnictví (PACES) byly možné obě možnosti:
Druhé řešení bylo vybráno z následujících důvodů:
Předpokládejme 100 míst dostupných v medicíně a 100 míst dostupných v lékárnách. Pokud úkol upřednostňoval výběr kurzů (a nikoli studentů), mohli bychom v některých případech skončit s následující konfigurací:
Tito dva studenti jsou téměř stejně dobří v obou proudech. Chtěli by si vyměnit úkoly (což je nemožné), a proto budou frustrovaní. Skutečnost privilegování studentů při výběru se tomuto druhu situace vyhýbá.
Tento algoritmus funguje iterativně. Pokud se umístíme do případu zvoleného pro PACES, kde upřednostňujeme volby studentů, postupujeme následovně:
Tento algoritmus stabilních manželství je konvergentní (vždy konvergujeme k řešení) a stabilní (vždy najde stejné řešení pro identické počáteční podmínky, bez ohledu na pořadí, ve kterém zacházíme se studenty).
Všimněte si také, že když je student vyhozen ze streamu A a přiřazen k streamu B, je s ním zacházeno v streamu B přesně jako se studentem, který by si jako první volbu vybral stream B: započítá se pouze jeho hodnocení. Student tedy neztratí žádnou šanci v proudu B, pokud si jako první přání zvolí proud A (samozřejmě, pokud je přiřazen k proudu A, nebude moci vstoupit do proudu B).
Iterativní povaha algoritmu vysvětluje, proč by živá veřejná volba („posádkový přednáškový sál“) byla psychologicky katastrofická: začneme tím, že studentovi přiřadíme kurs jeho první volby, než ho budeme moci vyhodit. To však nezabrání transparentnosti a analýza úkolů jasně ukáže, že pokud je student A přiřazen ke kurzu a nikoli student B, znamená to, že A je v této větvi lépe klasifikován než B nebo je přiřazen do jiné větve, kterou upřednostňuje .
Nechť X, Y, Z jsou tři kurzy mající 2, 1 a 2 místa. Zvažte pět kandidátů A, B, C, D a E, jejichž výsledky a možnosti jsou definovány v následujících seznamech:
Klasifikace podle sektoru X [BCEAD] Y [CADEB] Z [BDECA]
Výběr kandidátů A [XYZ] B [YXZ] C [ZYX] D [YXZ] E [YXZ]
Z těchto dat můžeme spustit algoritmus:
Výsledek je uspokojivý, protože:
Algoritmus má velký zájem: zaručí nejlepší možné řešení pro studenty s přihlédnutím na jejich úroveň.
Strategie, kterou si studenti musí osvojit, je proto velmi jednoduchá: jako první volbu si zvolí sektor, který preferují (i když věří, že v tomto sektoru mají jen velmi malou šanci na úspěch). V nejlepším případě se spoustou štěstí (prostřednictvím hraní úkolů v jiných sektorech) jim budou přiděleni. V nejhorším případě se ve srovnání s jinými sektory ocitnou ve úplně stejné situaci, jako kdyby si okamžitě vybrali ostatní sektory.
Není proto třeba přijmout žádnou složitou strategii: jednoduše vyjadřuje preference v rozporu se starým postupem APB, který u některých univerzitních kurzů nemusí první volba snížit jeho šance na přijetí.