
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.
Csáji Gergely Kál a HUN-REN Közgazdaság- és Regionális Tudományi Kutatóközpont Közgazdaságtudományi Intézetének tudományos segédmunkatársa
Címlapkép forrása: Shutterstock
Még a gyógyszergyártók se tudják pontosan, mit jelent nekik Trump újabb vámja
Nagy a bizonytalanság.
Történelmi pillanat: átadták a BMW debreceni gyárát, Orbán Viktor is beszédet mondott
Kulcsfontosságú a gyár és az új modell is a BMW-nek.
Bejelentette Moszkva: stratégiai győzelmet arattak az északi fronton
Azt mondják, innentől lényegesen gyorsabb lesz a támadás a szektorban.
Váratlan változás jön a balatoni vasútvonalon: így lehet majd utazni az északi parton
Akadozni fog a közlekedés.
Perlusz László: eltűnő munkahelyeket hozhat a túl nagy béremelés
A VOSZ főtitkára beszélt erről.
Vigyázat, szűkül Budapesten az otthon startos lakáskínálat
A fővárosban a leglátványosabb az arány csökkenése.
Új 6,5%-os magyar állampapír érkezik, de nem a lakosságnak
Kiemelten kedvező befektetési lehetőség jön egy speciális kör számára.
A kertészkedés egészséges, és nem csak a friss zöldségek miatt
Friss kutatások szerint már heti két és fél óra kertészkedés is elegendő lehet ahhoz, hogy csökkentsük a túlsúly, a magas vérnyomás, a cukorbetegség és más egészs
Magyar ingatlanpiac: hórukk országban mérsékelt verseny
A héten Zsolt pihenőt kapott, Balázs és Ádám pedig Tibor Dávid Masterplast CEO-val beszélgetett a magyar ingatlanpiac évtizedes kérdéseiről. Dögunalmas szakmai adásunkban szó lesz a... The p

Külföldre költözés matematikája
Hamarosan itt a választás, ilyenkor sokan szokták megfogadni, hogy valamilyen eredmény esetén emigrálnak. Ezeket általában nem kell komolyan venni, valószínűleg üres lenne az ország, ha tényl
Agrárgazdaság átadása: a generációváltás és a vagyontervezés kulcsa az agráriumban
Az agrárgazdaság átadása az elmúlt években az agrárium egyik legaktuálisabb kérdésévé vált. A rendszerváltás idején önálló gazdálkodóvá vált generáció mára elérte vagy hamarosan

A baby boomer generáció gazdasági jelentősége
Kulcsszereplők a jövő gazdasági növekedésében.
Megnyílt a biogáz-kassza: 40 milliárd támogatás kerül szétosztásra
A most megjelent felhívás a biogáz- és biometán-projektek teljes értékláncát támogatja: az alapanyag-logisztikát és tárolást, az előkészítést, a fermentorokat és gázkezelést, valamint

Mindent a TBSZ-ről: Ha érdekel a megtakarításaid jövője, hallgasd meg élő webinarunkat!
Mindent a TBSZ-ről – webinár 60 percben, ebédszünet alatt! Ha még nem hallottál róla, vagy már találkoztál a fogalommal, de nem vagy biztos a részletekben,... The post Mindent a TBSZ-ről:

Otthon Start: Kivételes, 2,75%-os kamattal állt elő az MBH Bank, de csak bizonyos köröknek
A lakáshitelpiac egyik legkedvezőbb ajánlata várja az MBH Bank Flotta Kiemelt Partner Program tagjait. Az Otthon Start lakáshitel 3%-os kamata helyett fix, évi 2,75%-os kamat mellett vehetik igénybe

Tőzsdei túlélőtúra: Hogyan kerüld el a leggyakoribb kezdő hibákat?
A tőzsdei vagyonépítés során kulcsfontosságú az alapos kutatás és a kockázatok megértése, valamint a hosszú távú célok kitűzése és kitartó befektetési stratégia követése.
Tőzsdézz a világ legnagyobb piacain: Kezdő útmutató
Bemutatjuk, merre érdemes elindulni, ha vonzanak a nemzetközi piacok, de még nem tudod, hogyan vágj bele a tőzsdézésbe.
A magyar mezőgazdaság életben maradása múlik ezen: víz nélkül nem fog menni
Túl sok függ az időjárás szeszélyeitől.
Ismét téma a nyugdíjemelés: kik kaphatnának sokkal többet havonta?
Mi az a minimálnyugdíj, és hogy lehetne hatékonyan alkalmazni?
Semmi sem állítja meg a forint dicsőséges menetelését?
Lehet még erősebb a hazai fizetőeszköz?
