Bíró Péter

Al Roth és Lloyd Shapley 2012-ben közgazdasági Nobel-díjat kapott a stabil allokációs mechanizmusok elméleti kutatásáért és gyakorlati alkalmazásáért. Éppen 50 évvel korábban jelent meg Lloyd Shapley és David Gale cikke az egyetemi felvételik problémájáról egy matematikai népszerűsítő folyóiratban. Ez a dolgozat alapvető és kristálytiszta példát mutat az elméleti alapokon nyugvó, de gyakorlati alkalmazásra fókuszáló mechanizmustervezésre. Ennek a kutatási irányzatnak a legjelentősebb képviselőse napjainkban Al Roth. Mit is jelent a mechanizmus-tervezés? Egy olyan szabályozott eljárás megalkotását, amely révén egy gazdasági-társadalmi helyzetben a szereplők szempontjából igazságos, s ha lehet, optimális eredmény alakulhat ki.

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 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 a nevezett eljárással. 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 (http://www.matching-in-practice.eu/) keretében. 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ív externáliát jelentene a távkapcsolat). Ehhez hasonló jellegű problémát okoz, amikor a magyar diákok tanári szakpárokra jelentkeznek, illetve az is komoly kihívást jelent a párosító algoritmus tervezésében, hogy hazánkban a szakokra a felső kvóták mellett megadhatók alsó kvóták is, amelyekkel 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-programot is kiemeli. Az alkalmazás 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 2007 és 2010 között, amit az Egyesült Királyság vesecsere-programjában valóban használtak. Hasonlóan sikeres vesecsere-programok működnek például az USA-ban és Hollandiában is. 2016 őszétől egy európai COST Action keretében négy éven keresztül lesz lehetőségünk bekapcsolódni a kérdés elméleti és gyakorlati vizsgálatába.

Az elmúlt években több ilyen témájú konferenciát is sikerült hazánkba hozni. 2011 őszén a Matching in Practice kutatóhálózat 3. workshopja jött Budapestre, idén decemberben ennek a konferencia-sorozatnak a 12. eseményét tervezzük megrendezni. 2012-ben egy nagyszabású interdiszciplináris konferenciát tartottunk MATCH-UP 2012 címmel, ahová a világ minden tájáról eljöttek a terület szakértői. 2013-ban pedig nyári iskolát tarthattunk a Computational Social Choice COST Action keretében a párosítási piacok tervezéséről. Idén ősszel egy egynapos konferenciát tervezünk „A párosítás-elmélet 100 éve Magyarországon” címmel. Kőnig Dénes első, párosításokról szóló matematikai cikke 1916-ban jelent meg, amit még sok fontos cikk követett tőle, majd Egerváry Jenőtől, később Gallai Tibor publikált jelentős eredményeket, majd 1986-ban Lovász László és Michael Plummer írt közösen könyvet a párosításelméletről. Jelenleg is több kitűnő matematikus folytat kutatást a párosítások témakörben mind preferenciák nélküli, mind preferenciákat feltételező esetben, elsősorban az ő előadásaikat fogjuk hallani a nemzetközi fórumon.

Hadd jegyezzem meg, hogy az elméleti kutatások mellett számos alkalmazást lenne érdemes beindítani vagy megreformálni hazánkban. A vesecsere-program beindítása kétség kívül hasznos lenne, de véleményem szerint az alsóbb szintű (bölcsődei, óvodai, általános iskolai) felvételi eljárások átláthatóságán és igazságosságán is lehetne javítani központilag koordinált programok révén.

2016. június