A magyarországi felvételi besoroló algoritmusok rövid bemutatása

Az alábbiakban közzétesszük a nemrég elvégzett, hazai felvételi algoritmusokat érintő kutatás összefoglalóját. A cikket a kutatást végző hazai matematikusok, vagyis Dr. Biró Péter, a University of Glasgow (Department of Computing Science, Számítástudományi Tanszék) és Dr. Fleiner Tamás, Budapesti Műszaki és Gazdaságtudományi Egyetem (Számítástudományi és Információelméleti Tanszék) kutatója készítették.

Magyarországon a középiskolai és a felsőoktatási felvételi eljárások koordinációja központosított rendszereken keresztül valósul meg. A programok alapvető célja a jelentkezők és az iskolák igényeinek egyaránt megfelelő, "igazságos" megoldások szolgáltatása. Ezek kiszámítása speciális párosító algoritmusok segítségével történik. A következő rövid összefoglalóban bemutatásra kerül az implementált alapalgoritmus elméleti háttere, főbb gyakorlati alkalmazásai, illetve a hazai rendszerek sajátosságai.

Elméleti háttér: stabil párosítások

A felvételi probléma alapmodelljében a szereplőket nevezzük egyszerűen diákoknak és iskoláknak. Tegyünk fel, hogy minden diák rangsorolja azon iskolákat, ahová jelentkezni szeretne. Ugyanígy, minden iskola sorrendet állít fel a hozzá jelentkező és alapszintet elérő diákok között, illetve megadja a keretszámát, amelynél több diákot nem kíván felvenni. A felvételi probléma megoldása egy párosítás, amelyben mindegyik diák legfeljebb egy helyre van felvéve és semelyik iskola nem lépi túl a keretszámát.

Milyen megoldást tekinthetünk "igazságosnak"?

Gale és Shapley 1962-ben publikált cikkében ["College admissions and the stability of marriage", American Mathematical Monthly, 69:9-15] az igazságosság alapfeltételeként definiálják a stabilitást. Egy párosítást stabilnak nevezünk, ha bármelyik össze nem párosított diák-iskola párt tekintve a következő indokok egyike biztosan teljesül: vagy a diák lett felvéve egy számára kedvezőbb helyre, vagy az iskola töltötte fel a keretszámát jobb diákokkal. A cikk szerzői egy igen természetes mechanizmust adtak a stabil megoldás létezésének bizonyítására.

Gale-Shapley algoritmus: Az eljárás első körében minden diák adja be a jelentkezését a rangsorán szereplő első helyre. Ezután minden olyan iskola, amelyik túl sok jelentkezést kapott, tartson meg annyi jelentkezőt a legjobbak közül, amennyi a keretszáma, a többieket utasítsa vissza. A második körben minden diák, akit visszautasítottak az első körben, adja be a jelentkezését a listáján szereplő második iskolába, és ismét minden iskola utasítsa vissza azokat a gyengébb jelentkezőket, akik nem férnek be a keretbe. Ezt a metódust ismételjük, amennyiszer szükséges.

A cikkben a következő két állítást látják be a szerzők a kapott megoldásról:

- Stabilitás: Ennek igazolása nagyon egyszerű. Az eljárás során minden iskolában növekszik a jelentkezők száma, illetve javul a jelentkezők összetétele, hiszen csak rosszabb diákok szorulhatnak ki a keretből. Ezért, ha egy diákot az eljárás során visszautasított egy iskola, akkor őt az eljárás végén is biztosan visszautasítaná. Ezen kívül már csak akkor nem lehet összepárosítva egy adott diák-iskola pár, ha a diák nem is küldte be a jelentkezését az iskolába, mivel az eljárás alatt végig jobb helyen volt aktív a jelentkezése; ez igaz a legutolsó párosításra is.

- Diák-optimalitás: Belátható, hogy nem létezik olyan stabil párosítás, amelyben akár csak egy diák is kedvezőbb helyre lenne felvéve, mint az algoritmus adta megoldásban. Ennek igazolása szintén nem igényel mély matematikai ismereteket, de terjedelme miatt itt nem kerül ismertetésre.
Ez az egyszerű felvételi eljárás tehát központi koordináció nélkül is a kívánt megoldást adná, de a gyakorlatban mégsem működőképes, mert túl lassú volna. Ha azonban egy központi program szimulálja az eljárást, akkor - a diákok és iskolák rangsorainak ismeretében - az algoritmus közvetlenül szolgáltatja a megfelelő megoldást. Az algoritmusnak további két rendkívül előnyös ismérve van.

- Gyors futásidő: Az az észrevétel már az eredeti cikkben is szerepel, hogy a körök száma az eljárásban nem lehet több, mint a jelentkezések száma, hiszen semelyik diák nem jelentkezik ugyanarra a helyre kétszer. Pontos implementációval ugyanakkor elérhető a lineáris futásidő is. Ez azt jelenti, hogy az algoritmus lépésszáma a jelentkezések számával egyenesen arányosan nő. Ha például a magyarországi felvételin alkalmazott program futásideje 10 másodperc, akkor egy nagyjából 6-szor akkora feladatot, például az Egyesült Királyság felvételi problémáját, ugyanaz a program körülbelül egy perc alatt oldaná meg.

- Stratégiailag biztos: A mechanizmus nem manipulálható, vagyis egyik diák sem járhat jobban akkor, ha nem az igazi preferenciája szerint cselekszik az eljárás során, avagy nem a valódi rangsorán küldi be a felvételi központba. Ez egy igen fontos tulajdonsága a mechanizmusnak.
A stabil párosítások elméletét mind a matematikában és algoritmuselméletben, mind pedig a közgazdaságtanban és játékelméletben intenzíven tanulmányozták az utóbbi évtizedekben, a megjelent publikációk száma több ezerre becsülhető. A tudományos érdeklődés alapvető magyarázata a gyakorlati alkalmazások nagy száma és sikeressége.

Alkalmazások világszerte

A legelső ismert alkalmazást, amelyben a Gale-Shapley algoritmus szolgáltatott stabil megoldást, az amerikai kórházi gyakornokok elhelyezésének koordinálására hozták létre. A központi programot először 1952-ben (vagyis 10 évvel a fenti cikk megjelenése előtt!) futtatták, amely jól mutatja, hogy erre a természetes megoldásra a piac szereplői és koordinálói maguktól is könnyen rátalálhatnak. A program a mai napig gyakorlatilag változatlan formában működik, és minden évben mintegy 30 ezer rezidenst allokálnak kórházakhoz ezen keresztül (lásd www.nrmp.org). Gyakornokok elhelyezésére egyre több országban és szakmában indítanak hasonló programokat.

Az iskolai felvételiket tekintve jóval kevesebb hiteles információ található a szakirodalomban. Magyarországon kívül még a spanyolországi és törökországi felsőoktatási felvételikről tudható, hogy központi program segíti őket, de a legtöbb országban vagy nincs ilyen koordináció (pl. Lengyelország, Szlovákia vagy az Egyesült Királyság), avagy nincs róluk leírás. A középiskolai programokat tekintve több országban és városban lehet sejteni a központi koordináció jelenlétét, de részletes leírás csak az újonnan bevezetett New York-i és bostoni programokról található. A központi felvételi rendszerek hasznosságáról, így például a kiszámítható hallgatói és osztálylétszámokból adódó gazdaságossági előnyökről sem született még tanulmány.

Központosított programokat, más, tágabb értelemben vett párosítási problémák megoldására is használnak a gyakorlatban. Ha például nem kétoldalú a piac, akkor az úgynevezett szobatárs probléma áll elő. Ilyen szituációkat oldanak meg az inkompatibilis beteg-donor párokat összepárosító vesecsere-programokban (USA, UK, Hollandia), vagy például a sakkversenyek párosító szoftverei is. Szintén fontos modellcsaládot kapunk, ha a kétoldalú piacokon figyelembe vesszük a lehetséges pénzügyi tranzakciókat. Itt fontos alkalmazásként említhetők az algoritmizált aukciók.