
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
Miközben az EU szakítana Moszkvával, egy tagország miniszterelnöke nem győzött hálálkodni Putyinnak
Sorba jelentette be a Moszkva számára kedvező döntéseket.
Furcsa kép terjeng egy ukrán MiG-29-esről: úgy látszik, Kijev lekoppintotta Oroszország rettegett fegyverét
Az éles bevetésre még ugyanakkor várni kell.
Forradalmi felfedezés: olyan anyagot fejlesztettek kínai tudósok, ami teljesen megváltoztathatja az eszközök töltését
Új világ jön a telefonoknál és okosóráknál.
Korábban soha nem exportált annyi cseppfolyósított földgázt az Egyesült Államok, mint augusztusban
Az LNG nagy része Európába érkezik.
A kreminnai csata lehet a modern kor Verdunje? Elképesztő dolgokat tártak fel friss felvételek Ukrajnában
Brutális pusztítás, kevesebb mint 200 négyzetkilométernyi területen.
Lerántotta a leplet Ukrajna a titokzatos fegyveréről: kiderült, mire képes a Paljancija
Új robotrepülőgép, nemzetközi porondon.
Fenntartási jelentés: a KFI projektek láthatatlan aknái az EPTK-ban
Akinek KFI projektje van, nem dőlhet hátra: itt az idő a fenntartási jelentések világával szembenézni.

Fenntartási jelentés a KFI pályázatoknál: így kerüld el az EPTK buktatóit
Akinek KFI projektje van, nem dőlhet hátra: itt az idő a fenntartási jelentések világával szembenézni.

Az ChatGPT is Redditezik - Az AI ugyanonnan tájékozódik, ahonnan mi
Az AI csak rendszerezi és újracsomagolja azt a kollektív zajt, amit mi nap mint nap a netre hordunk, kicsit ijesztő is nézni, milyen forrásokból dolgozik.... The post Az ChatGPT is Redditezik - Az A

Az UniCreditnél is kedvező kamat mellett érhető el az Otthon Start hitel
Szeptember elsejétől az UniCredit Banknál is elérhető a kedvező kamatozású Otthon Start hitel. A bank kamatkedvezménnyel, jóváírással és díjelengedéssel is várja az érdeklődőket. Az Uni
ESG és adózás: így kapcsolódik össze a társadalmi felelősségvállalás és a vállalati adományozás
Az elmúlt években egyre nagyobb figyelmet kapott az ESG, azaz a környezeti, társadalmi és vállalatirányítási szempontokat figyelembe vevő működés. Az ESG nem csupán trend vagy megfelelési k

A bitcoinmágnás finnek
Ott voltam, amikor Kína hatodjára is betiltotta a Bitcoint - áll egy, a kriptós közösségben évek óta keringő mémen. Az ország egykor dominálta a bányászatot,... The post A bitcoinmágnás fi

Az osztalék portfólióm - 2025. augusztus
Emelkedett a portfólióm hozama, egyrészt az Altria osztalékemelése, másrészt a nulla hozamú Walgreens kivezetése miatt. Az utóbbi nem éppen az ideális módszer egy portfólió hozamemelésére.
Novo Nordisk - elemzés
Végre találtam egy európai céget, ami kiszámíthatóan fizeti és emeli az osztalékot. A Finvizen keresgéltem kereskedési célpontok után, és ott találtam rá. Megnéztem a számait és a chartj

Limit, Stop, vagy Piaci? Megbízások, amikkel nem lősz mellé!
Ismerd meg a tőzsdei megbízások világát, és tanulj meg profin navigálni a piacokon!
Bikák és Medvék: Kivel jobb haverkodni a tőzsdén?
Hogyan ismerd fel, hogy épp emelkedő (bull) vagy csökkenő (bear) piacon jársz? Megtanulhatod, mikor érdemes növelni a kockázatvállalást, és mikor jobb óvatosan hátrálni.
Másfél millióig húzza a legtöbb lakás árát az Otthon Start - Mi lesz ebből?
Elindult az Otthon Start.
Velünk marad az árrésstop, de mit fizetünk érte valójában?
Utánajártunk, vajon mit mutatnak a számok és mi várható a következő hónapokban
Meddig fékezheti az inflációt az árrésstop?
Kozák Tamással, az OKSZ főtitkárával beszélgettünk.
