Rezidens allokáció házaspárokkal

krtk blog A HUN-REN Közgazdaság- és Regionális Tudományi Kutatóközpont blogja.

Az igazságosság garantálásaként az egyik fő elvárás ezekben a programokban, hogy a talált megoldás stabil legyen, ami azt jelenti, hogy ne legyen olyan rezidens-kórház pár, hogy mind a rezidens jobban kedveli a kórházat, mint ahová osztottuk (vagy nem osztottuk szegényt sehova sem) és a kórháznak is vagy van üres helye, vagy jobban kedveli a rezidenst, mint valamelyik hozzá osztott másik hallgatót. Alapesetben ez egy jól ismert, úgynevezett stabil párosítási feladathoz vezet, melyet hatékonyan és egyszerűen meg lehet oldani. Mióta a rezidensek között házaspárok is részt vehetnek a programokban, akik együttes jelentkezéseket adhatnak be kórházpárokhoz – például mert azt szeretnék, hogy földrajzilag közeli kórházakban helyezkedhessenek el – matematikailag rendkívül bonyolulttá, méghozzá NP-nehézzé válik a stabil megoldások keresése, mely durván fogalmazva annyit jelent, hogy nagyon valószínű, hogy nem létezik rá gyors algoritmus. Ez még olyan rendkívül speciális esetekben is igaz, mint például amikor minden preferencia lista csak legfeljebb 2 hosszú. Ennek a nehézségnek a leküzdéseként a jelenlegi szoftverek főleg heurisztikákat használnak, melyek, bár eddig meglepően jól működtek, azonban a futásidejükre nincs matematikai garancia.

Ráadásul az sem biztosított, hogy találnak egy stabil megoldást, ugyanis a házaspárok jelenlétében megtörténhet, hogy egyáltalán nem is létezik ilyen.

A cikkünkben mi azt vizsgáltuk, hogy a házaspárok preferenciáira különböző megszorításokat téve mennyire válik kezelhetőbbé a feladat. Az általunk vizsgált fő megszorítás a preferenciákra, hogy feltesszük, hogy a házaspár mindkét tagjának vannak valamilyen mögöttes preferenciái a kórházi pozíciókon úgy, hogy amennyiben egy, a házaspár számára elfogadható kórházpárban mindkét tag legalább olyan jól jár a saját preferenciája szerint, mint egy másik kórházpárban, akkor az a házaspárnak is legalább olyan jó lesz a rangsora szerint. Ez egy teljesen természetes feltevés, melyet a legtöbb programban kötelezően kielégítenek a házaspárok által beküldhető preferenciák mivel a házaspár két tagjának saját beküldött preferenciái alapján konstruálják őket, a távol lévő kórházakat tartalmazó jelentkezéseket törölve.

Fő eredmények

A cikk fő eredménye, hogy konstruáltunk egy nagyon hatékony algoritmust, mely képes találni egy garantáltan stabil megoldást, amennyiben a házaspárok preferenciái teljesítik a fentebb említett feltételt, illetve azt, hogy ha a két tagot egy-egy, az adott tag számára elfogadható kórházba küldenénk, akkor az a párnak is elfogadható. Mivel stabil megoldás nem feltétlenül létezik, ezért az algoritmus során megengedjük, hogy a kórházak kapacitásait legfeljebb eggyel módosítsuk futás közben, és így már garantálni tudjuk egy stabil megoldás létezését is. A kapacitások módosításának megengedése mögött az egyik fő motiváció egy néhány évvel ezelőtti áttörő eredmény a problémával kapcsolatban, mely szerint még a feladat legáltalánosabb esetében is igaz az, hogy ha a kórházak kapacitásait meg lehet változtatni legfeljebb 2-vel, akkor garantálható egy stabil beosztás létezése. Sajnos ez az eredmény nem ad hatékony algoritmust egy ilyen megoldás megkeresésére, a mi cikkünk azonban nemcsak, hogy (egy speciális esetre) hatékony algoritmust adtunk, de a szükséges módosítást is sikerült lecsökkentenünk 2-ről 1-re.

Legfontosabb ötletünk az volt, hogy visszavezetjük a feladatot egy hatékonyan megoldható másik (absztraktabb) stabil párosítási problémára, ahol egy gráf csúcsait (akiknek egymáson vannak preferencia sorrendjei) akarjuk párosítani a gráf élei segítségével olyan módon, hogy ne legyen olyan (u,v) pár, ahol u és v is jobban szeretik egymást, mint a kapott párjukat, ha van ilyen. Ehhez a házaspárokat a típusuktól függő úgynevezett gadgetekkel (részgráfokkal) helyettesítettük. Ez az ötlet egy újszerű megközelítés a feladatra, mely az általános probléma megoldására is egy szignifikáns részeredménynek tekinthető.

Egyéb házaspár típusokat is vizsgáltunk, és olyan eseteket is találtunk, ahol a kapacitások módosítása nélkül is tudtunk hatékony algoritmusokat készíteni stabil megoldások keresésére. Míg eddig főleg csak szinte triviális speciális esetekre volt ismert hatékony algoritmus, a mi algoritmusunk egy minden eddiginél jóval tágabb feladatosztályra képesek rövid időn belül egy stabil megoldást keresni.

A fő ötletünk egy újszerű, eddig nem használt megközelítés a feladatra, mely egy nagyon fontos lépés afelé, hogy az általános esetre is találjunk hasonló, a kapacitásokat kicsit módosító, de garantáltan stabil megoldást találó és hatékony algoritmusokat.

Erre rendkívül nagy szükség lenne, hiszen ekkora fontosságú mechanizmusoknál rendkívül fontos, hogy a használt algoritmusok mögött matematikai garanciák is legyenek. Egy nyári konferencia keretében volt lehetőségem beszélgetni az amerikai rezidens allokációt lebonyolító cég egyik vezetőjével, Jonah Peranson-nal, aki szintén megerősítette az eredményeink relevanciáját és kifejezett érdeklődését fejezte ki a kutatás jövőbeli eredményeivel kapcsolatban.

A rezidens-elosztási feladatokkal kapcsolatos eredményeink ezen felül afelé is fontos lépést jelenthetnek, hogy Magyarországon is kidolgozhassunk egy ezt lebonyolító központi mechanizmust, mint ami a nyugati országok többségében már jelen van.

Köszönetnyilvánítás

A kutatást a Nemzeti Kutatási, Fejlesztési és Innovációs Hivatal Kooperatív Doktori Program Doktori Hallgatói Ösztöndíja (CA2258525) és OTKA (K143858) pályázata finanszírozta és támogatta.

Címlapkép forrása: Shutterstock