A klasszikus rabló-pandúr játék ebben az új változatában részeg rablóval van dolgunk, aki a gráfon elhelyezkedõ rendõr(ök)tõl teljesen függetlenül mozog. Nyilván nem ugyanazokat a kérdéseket érdemes feltenni, mint a normál játék esetén, ahol mindkét fél optimális mozgást végez a másik mozgásait figyelembe véve. Például bizonyítható, hogy egyetlen rendõr véges idõben el tudja kapni a részeg rablót tetszõleges összefüggõ gráfban, míg normál rabló esetén ez egyáltalán nem igaz, gondoljunk például egy legalább 4 pontú körre. Az idei GRASTA Workshop-on vetették fel a következõ problémát: mennyivel rosszabb a rablónak, ha részeg? A cikk matematikai része megmutatja, hogy léteznek olyan gráfok (gráfsorozat), hogy a kívánt eltérés tetszõleges arányú lehet (tetszõlegesen nagy, de tetszõlegesen kicsi is). Viszont egyáltalán nem természetes, hogy az egyszemélyes játékban mi legyen a rendõr optimális stratégiája, illetve hogyan számítsuk ki a fent említett arányt. A megoldást a Markov döntési folyamatok szolgáltatják, és segítségükkel az arány tetszõleges pontossággal kiszámolható. Ha a fenti játékhoz hozzávesszük, hogy a rabló még láthatatlan is, akkor nagyon közel kerülünk a szintén híres gráfkeresési játékhoz, ami rögtön indokolttá teszi, hogy miért vetõdött fel a kérdés a GRASTA-n. A kérdés alapvetõen gráfelméleti, de a véletlen szerepe miatt jelentõs sztochasztikus apparátus szükséges a kérdések megválaszolásához.
Minden érdeklõdõt szeretettel várunk,
Péter