Az anarchia és a stabilitás ára

Imreh Csanád
SZTE Informatikai Tanszékcsoport

Az előadásban az algoritmikus játékelméleten belül az anarchia és a stabilitás ára fogalmakkal és néhány azokkal kapcsolatos eredményről lesz szó. Ezek a fogalmak azt mérik mennyivel kaphatunk jobb megoldásokat központilag koordinált szereplők mellett, mint öncélú ágensek koordinálatlan működésekor. Pontosabban megfogalmazva, arról van szó, hogy a legrosszabb/legjobb Nash egyensúlyi helyzetet hasonlítjuk össze egy koordinált optimummal (amit szociális optimumnak neveznek).

Elsőként néhány egyszerű (remélhetőleg komolyabb matematikai képzettség nélkül követhető) és talán meglepő példán keresztül mutatjuk be az alapfogalmakat.Majd ha az idő engedi, akkor megnézzünk néhány újabb kiterjesztést és azt is miként kapcsolódik ez a téma az approximációs és online algoritmusok területéhez.