Témaszám: K143858
A javasolt kutatásban olyan párosítási és cserepiacokat szeretnénk vizsgálni, ahol számos központi koordinációs mechanizmus lett bevezetve az elmúlt évtizedekben. Gale és Shapley nagy hatású cikke egy egyetemi felvételikről 1962-ben jelent meg, az általuk javasolt stabil párosítások koncepciója és a kapcsolódó algoritmus számos gyakorlati alkalmazásban került implementálásra, például az amerikai rezidens programmal (NRMP) már 1952-ben, és a hazai középiskolai és egyetemi felvételi eljárásban. Shapley és Scarf alapvető cserepiaci modellje David Gale TTC algoritmusával 1974-ben lett publikálva, és ezt javasolták többek között vesecsere-programok megoldására, de használták az Ohio-i iskolák felvételi eljárásában is. A kapcsolódó elméleti kutatások és alkalmazások tervezésének eredményeinek elismerésére Roth és Shapley 2012-ben közgazdasági Nobel-díjat kapott.
A kutatásunkban párosítási és csereprogramokat szeretnénk vizsgálni algoritmikus és játékelméleti szempontokból. A tervezett eredményeink elméleti jellegűek, melyek az egyes megoldási koncepciókhoz tartozó feladatok – például a kooperatív játékok magja – számítási bonyolultságát jelentik. De a kutatásunknak gyakorlati jelentősége is lehet, hiszen a hatékony algoritmusok potenciálisan használhatóak lesznek valódi alkalmazásokban, például egyetemi felvételiben, munkapiacon, vesecsere-programokban vagy pénzügyi klíring esetén. A nehézségi eredmények pedig ahhoz adnak segítséget, hogy a szervezőknek milyen heurisztikákra vagy robusztus optimalizálási technikákra érdemes hagyatkozniuk.
