Vegyük például az egyetemi felvételit. Itt a hallgatók versengenek a jó egyetemekért, és az egyetemek a jó hallgatókért. Az eredmény egy párosítás, amely megadja, hogy kit melyik egyetem melyik szakjára vesznek fel. Egy párosítást igazságosnak (avagy Gale és Shapley szóhasználatával stabilnak) akkor nevezünk, ha egy diák jelentkezésének visszautasítása oka csak az lehet, hogy az adott szak kvótáját a diáknál jobb jelentkezőkkel töltötték fel. Ez a kitétel a felvételi ponthatárokat alkalmazó rendszereknél, így a hazai felsőoktatási felvételinél is automatikusan teljesül. Gale és Shapley viszont azt is megmutatta, hogy az általuk javasolt eljárás a stabil megoldások közül is pontosan azt választja, amely minden diáknak a legjobb, vagyis optimális. A hazai felsőoktatási pontszámító eljárás is ezen az eljáráson alapul, néhány heurisztikával kiegészítve. A hazai középiskolai felvételi eljárásban viszont a Gale-Shapley-eljárás teljesen tiszta formában jelentkezik, amely tudtommal igazi különlegességnek számít a világban.

Gale és Shapley eljárásának van két másik fontos tulajdonsága is. Az első, amelyet épp Al Roth bizonyított be egy 30 éve megjelent cikkében, hogy a diákoknak ebben az eljárásban mindig megéri a valódi preferenciáikat megadni, ugyanis lehetetlen, hogy egy számukra kedvezőbb helyre vegyék fel őket, ha más sorrendet adnak meg a jelentkezési lapjukon. A másik fontos tulajdonság, hogy a preferenciák és rangsorok ismeretében egy központi koordinátor villámgyorsan ki tudja számítani az optimális stabil megoldást. Az utóbbi tulajdonsággal elsősorban a számítástudományi kutatók foglalkoznak, és ez teszi a kutatási területet igazán interdiszciplinárissá, hiszen a közgazdászok által kigondolt megoldási koncepció mit sem ér, ha az optimális eredményt nem lehet hatékonyan kiszámítani egy nagyméretű feladatra.

Világszerte rengeteg alkalmazás alapul a Gale-Shapley eljáráson. Al Roth vizsgálódásának eredményeként derült ki például, hogy az amerikai rezidensek allokációja már 1952 óta ezzel az algoritmussal történik. A New York-i és bostoni középiskolákban néhány éve változtatták meg erre az eljárást, szintén Al Roth és társai javaslatára. Európában is sok hasonló felvételi rendszer működik, ezek pontos leírását épp az elmúlt években kezdtük meg egy európai kutatási hálózat keretében (lásd matching-in-practice.eu). Azonban szinte mindegyik alkalmazásnak van olyan speciális eleme, amely elrontja a modell és a megoldás szépségét, és sok munkát ad a mechanizmus tervezőinek. Példaként említhető, hogy az amerikai rezidensek elhelyezésekor a házaspárok közös listát adhatnak be, amelyen álláspárok szerepelnek, tipikusan helyileg közel lévő kórházakban (hiszen egy házaspárnak jelentős negatívum lenne a távkapcsolat). Ehhez hasonló problémát okoz, amikor a magyar diákok tanári szakpárokra jelentkeznek, illetve az is komoly tervezési problémákhoz vezet, hogy hazánkban a szakokra a felső kvóták mellett megadhatók alsó kvóták is (amellyel az egyetemek rögzítik a szakok elindulásához szükséges minimális létszámokat).

A Nobel-díj bizottság levelében egy másik alkalmazást, a vesecsere-programokat is kiemeli. Ezen központilag koordinált programok elméleti vizsgálatának és gyakorlati alkalmazásának úttörői szintén Al Roth és társai voltak. A krónikus vesebetegség egyetlen elfogadható életminőséget biztosító gyógymódja a veseátültetés. A halott donorok hiánya miatt napjainkban szinte minden fejlett országban előtérbe került az élődonoros átültetés. Mit tehetünk azonban, ha a jelentkező donor (tipikusan a beteg házastársa) nem kompatibilis a beteggel, például az egyiknek A-s a másiknak B-s a vércsoportja? Ha van egy másik ilyen házaspár épp fordított vércsoportokkal, akkor a két házaspár kicserélheti a veséket egymással: az első pár donorja a második pár betegének adja veséjét és viszont.

Ha több száz ilyen beteg-donor pár van az adatbázisban, és esetleg hosszabb cseréket is megengedünk, akkor felmerül a kérdés, hogy miként lehet kiszámítani egy optimális megoldást, ahol például a donációk száma maximális. Jómagam is egy ilyen párosító algoritmus megalkotásán dolgoztam Glasgowban kutatóként, amit aztán az Egyesült Királyság vesecsere-programjában élesben is használtak. Mit mondjak, leírhatatlanul jó érzés volt később látni azokat a BBC-n bemutatott filmeket, amelyben a programban végrehajtott transzplantációkat, és az így felépült betegek és szeretteik történetét mutatták be. Hasonlóan sikeres vesecsere-programok működnek például az USA-ban és Hollandiában is.

A hazai középiskolai és felsőoktatási felvételiben használt algoritmusok tehát a Gale-Shapley eljáráson alapulnak, ezért alapvetően igazságos, és közel optimális eredményt adnak. A felsőoktatási felvétel hatékonysága azonban egyszerűen javítható lenne két olyan módosítással, amelynek köszönhetően a szereplők jobban kifejezhetnék a preferenciáikat. A diákoknak meg kellene engedni, hogy a jelentkezési alapdíj fejében tetszőlegesen hosszú listákat adjanak meg. Az egyetemek cserébe az adott kvótákon túl tetszőlegesen szigorú felvételi kritériumokat határozhatnának meg (például ne kerülhessen be matematika tanári szakra az, aki nem írt egy legalább közepes emelt szintű felvételit matematikából).

Ezen túlmenően központi koordinációra lenne szükség az alsóbb szintű felvételiknél is, bölcsődékbe, óvodákba, általános iskolákba. A jelenlegi rendszerek ugyanis teljes mértékben átláthatatlanok, és igazságtalan, társadalmilag kedvezőtlen megoldáshoz vezetnek. Az intézményvezetőknél hagyott korlátlan jog a felvételi döntésre a korrupció melegágya. (Vajon melyik intézményvezető merné visszautasítani, mondjuk egy önkormányzati tisztviselő baráti kérését, hogy egy családtagjának biztosítson helyet?) Az össznépi trükközések, például az intézmény körzetébe a felvételi idejére történő ideiglenes bejelentkezések, pedig a valódi körzetes gyerekek jogos prioritását csorbítják, és szuboptimális megoldást (egyebek mellett jelentős autóforgalmat) okoznak.

A szerző az MTA KRTK KTI játékelmélet csoportjának kutatója és a BCE oktatója.

Kapcsolódó cikkek