Költségallokálás konkáv utazóügynök játékokban

Abstract

A dolgozat egy rövid elméleti bevezetővel kezdődik, amiben ismertetem az utazóügynök problémát, egy lehetséges megoldási algoritmussal együtt. Ezután a kooperatív játékelmélet alapjait mutatom be, az általános TU játékokból kiindulva, majd a költségjátékok, allokációk, és azok tulajdonságai sorba vétele után ismertetem az általam használt három költségallokációs módszert: a Shapley-értéket, a tau-értéket és a nukleoluszt. Ezek után összekapcsolom az utazóügynök problémát a játékelmélettel. Látni fogjuk, hogy a probléma által generált költségfüggvény mindenképp monoton és szubadditív lesz, azonban a konkavitás nem feltétlen fog teljesülni. Ezután egy elégséges feltételt adok a játék konkavitására: ha a játékosok elhelyezkedéséből kapott síkidom konvex, vagy ha csak három játékos van, akkor a játék mindenképp konkáv lesz. Ezután egy ellenpéldával bizonyítom, hogy négy játékos esetén már nem feltétlen teljesül a konkavitás. A konkáv utazóügynök játékok vizsgálata során látni fogjuk, hogy e tulajdonságnak számos kedvező következménye van egy költségjáték esetén, hiszen ez elég biztosíték arra, hogy a mag ne legyen üres, illetve hogy a Shapley-érték, a nukleolusz és (legfeljebb négy játékos esetén) a tau-érték is a magban helyezkedjen el. Végül bevezetek egy egyszerűsített képletet a tau-érték számolására arra az esetre, ha tudjuk, hogy e módszer magbeli allokációhoz vezet. Az dolgozat utolsó részében a gyakorlatban, példákon vizsgálom meg a fenti allokációkat. Ennek során bevezetek egy új fogalmat, a csalási hajlandóságot, ami megmutatja, hogy egy játékosnak hány százalékos hasznot hozhat, ha összejátszik az utazóügynökkel és közösen meghamisítják a játékos valódi elhelyezkedését, ezáltal lecsökkentik a fizetendő hozzájárulását. Látni fogjuk, hogy a csalás ellen egyik allokáció sem nyújt tökéletes védelmet, azonban a példák az irányba fognak mutatni, hogy a nukleolusz ellenálló képessége meghaladja a másik két módszerét.