
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
Elindult Trump vámoffenzívája, de a stratégiai nyersanyagok mentesülnek
Az ellátásbiztonság prioritást élvez.
Nagy bajba került Románia: rendkívüli ülést tart a jegybank
Hatalmas pofont kapott az ország Trumptól.
Trump borít mindent - Mibe érdemes befektetni ebben a zűrzavarban?
Érkeznek a mindenkit érdeklő válaszok.
Totális vámháborút indított Trump – Itt vannak a piaci reakciók
Esnek a részvénypiacok, gyengül a dollár, új csúcson az arany.
EKB: Európa olcsón megússza a vámpoklot
Az előrejelzések szerint nem lesz katasztrofális GDP-hatása az intézkedésnek.
Trump azokat az országokat is alaposan megbüntette, ahol a Nike, az Adidas és a Puma gyárt
Nagyot estek az árfolyamok.
Itt a vámháború, száz éve is volt már egy
Trump beváltotta a fenyegetését és kirobbantotta a vámháborút az egész világ ellen. Az alap vámtétel 10% lesz, erre rakódnak rá az országok különvámjai. Mivel fő a kiszámíthatóság a v
Női korrupció: tanulságok a sakktábláról
Két tudós sakktáblákon bizonyította, hogy a nők kevésbé hajlamosak a tisztességtelenségre és a korrupt viselkedésre. Az 1990-es évektől kezdve látványosan növekedett a nők térnyerése a.
Hatékony HR-folyamatok 2. rész: A teljesítménytől a megtartásig
A vállalati sikerhez vezető út továbbra is az embereken keresztül vezet. A hatékony HR-folyamatokat bemutató blogsorozatunk második részben tovább haladunk a humánerőforrás-kezelés fejlettebb
Mennyit bukhatsz ingatlan bérbeadás esetén az adózáson?
HitelesAndrás - Keress, kövess, költözz! Mennyit bukhatsz ingatlan bérbeadás esetén az adózáson? Ha ingatlan bérbeadásra adod a fejed, érdemes tisztában lenni azzal, hogy milyen adózási leh
Az osztalék portfólióm - 2025. március
Megcsináltam azt az optimalizálást, amit a legutóbbi posztomban leírtam. A vásárlásokkal lehettem volna kicsit türelmesebb, de hosszú távon nem nincs különösebb jelentősége, és az aljakat
Uniós zöld szabályok: komoly kihívás előtt a MENA-régió földgázexportőrei
A szigorodó uniós szabályozások hamarosan komoly nehézségek elé állíthatják a MENA-régió földgázexportőreit.
Felzárkózni Amerikához: komoly ára lesz, de szükséges
\"A háborúhoz három dolog kell: pénz, pénz, és pénz!\" Az év eleje óta az európai stratégiai függetlenedés és az Egyesült Államokhoz való katonai felzárkózás kérdései...
The post Felz
Vagyontervezés új környezetben - gyere el a debreceni szakmai reggelinkre!
Hogyan tervezz okosan a gyorsan változó pénzügyi és adózási környezetben? Gyere el április 15-én Debrecenbe a HOLD és az Andersen közös szakmai reggelijére. Az esemény...
The post Vagyonterv


- Nagy Márton: csökkenhet a lakossági állampapírok prémiuma, és jön a szigorúbb állampapírtartás
- Drámai jóslat érkezett a nyári időjárásról: nagyon fájdalmasan érintheti Magyarországot
- Megtudtuk: komolyan érdeklődik az Egyesült Államok a Paksi Atomerőmű és több SMR-szerződés iránt is
- Óraátállítás 2025: kezdődik a nyári időszámítás
- Már csak egyetlen hatalom áll Donald Trump útjában – Meg fogják állítani?
Tőzsde kezdőknek: Hogyan ne égesd el a pénzed egy hét alatt!
Előadásunkon bemutatjuk a Portfolio Online Tőzsde egyszerűen kezelhető felületét, a számlatípusokat és a gyors kereskedés lehetőségeit. Megismerheted tanácsadó szolgáltatásunkat is, amely segít az első lépések megtételében profi támogatással.
Warren Buffett helyett én: Kezdők útmutatója a befektetéshez
Fedezd fel a befektetés világát úgy, ahogy még sosem! Ez a webinárium egyszerűen és érthetően mutatja be az alapelveket, amelyekre még a legnagyobb befektetők, mint Warren Buffett is esküsznek.
Harmadik ciklusára készül Donald Trump? Ez lehetséges?
Beindult a jogi csűrés csavarás.
Új tervei vannak a kormánynak – De mennyire reálisak a számok?
Ezt elemeztük a Checklist keddi adásában.
Az amerikaiak is beszállnak a paksi projektbe?
Jöhetnek a kis moduláris reaktorok?
Eladó új építésű lakások
Válogass több ezer új lakóparki lakás közül Budán, Pesten, az agglomerációban, vagy vidéken.