Egalitáriánus stabil párosítások a stabil szobatárs feladatban
Stabil párosítások vizsgálata egyoldalú piacokon
Párosítási piacok jelen vannak az élet minden területén. Sok esetben - például a diákok iskolákhoz történő allokációjakor, vagy vesebetegek és donoraik összerendelésekor - a preferenciák és prioritások függvényében alakul ki, hogy ki kivel lesz párosítva. Vannak piacok, ahol az allokáció egy központi koordinátor segítségével megy végbe, a preferenciák alapján egy központosított mechanizmus vezet el egy igazságos, optimális megoldáshoz. Például a hazai felsőoktatási felvételi rendszer is ezen alapul.
A kétoldalú párosítási piacok egyik jelentős ága a stabilitás, ami preferenciákkal ellátott gráfokon van definiálva. Ilyen problémára klasszikus példa a középiskolai és egyetemi felvételi eljárás. A gráf csúcsait egyetemek és érettségizők alkotják, él pedig akkor fut egy érettségiző és egy egyetem között, ha a diák felvételizik az adott egyetemre. A preferenciákat egyik oldalról a jelentkező által beadott jelentkezési sorrend adja, másrészt az egyetemek is rangsorolják az érettségizőket a felvételi pontszámuk alapján. A cél egy párosítás központi kiszámítása, ahol minden egyetem úgy tölti fel a kvótáját, hogy egyetlen érettségizőnek se legyen olyan magasan rangsorolt, de elutasított jelentkezése, ahol az egyetem ennél az érettségizőnél gyengébb pontszámú diákot is felvett. Ezt a tulajdonságot hívják stabilitásnak.
Az egyoldalú piacok jellemzője, hogy egyazon objektumtéren belül próbáljuk összerendelni az elemeket úgy, hogy stabil maradjon az összetársítás. Reprezentatív példa erre a feladatra az izraeli Technion Műszaki Egyetem kollégiumi férőhelyeit kiosztó rendszer, ugyanis egy kollégiumi facilitáson belül az egymásról meghatározott preferenciák alapján párosítják össze a diákokat szobatársakká. Innen ered a feladat irodalomban elterjedt megnevezése, a stabil szobatárs probléma. A cél olyan összerendelés legyártása, amelyben nincs két olyan diák, akik ugyan összetársítva nem lettek, de kölcsönösen szívesebben költöztek volna össze egymással, mint kiosztott társaikkal.
Igazságos stabil párosítások keresése
Vizsgálódásunk célja, hogy a lehetséges stabil párosítások között keressünk bizonyos értelemben optimálisakat, ugyanis különböző stabil összerendelések esetén a hallgatóhoz rendelt egyetem egyéni rangsor szerinti átlagos sorszáma, vagy a szobatársak egyéni átlagos „rangja” különböző stabil párosításokban eltérhet. A feladat bizonyítottan NP-teljes. Ennek ellenére jelentős eredmények vannak a közelítő algoritmusok terén, amelyek hatékony algoritmus segítségével egy közel optimális megoldást adnak. Célunk ezen algoritmusok hatékonyságának javítása új módszerek kidolgozásával. A munka végeztével eljutunk oda, hogy az általános esetre érvényes, jól ismert 2-közelítéset lefaragjuk 9/7-es közelítéssé egy speciális esetben, amikor korlátozott méretűek a preferencialisták.
szerző
-
Juhos Attila
Mérnök informatikus szak, alapképzés
alapképzés (BA/BSc)
konzulensek
-
Fleiner Tamás
egyetemi docens, Számítástudományi és Információelméleti Tanszék -
Dr. Cseh Ágnes
tudományos főmunkatárs, HUN-REN KRTK KTI (külső)
