Algorithms for Mean-Payoff and Energy Games - Chaloupka, Jakub (2011)
Mean-payoff game (MPG) je hra dvou hráčů hraná na konečném ohodnoceném orientovaném grafu. Tito dva hráči, Max a Min, do nekonečna pohybují žetonem po hránách grafu. Maxův cíl je maximalizovat průměrnou hodnotu projitých hran, zatímco Min ji chce minimalizovat. Energy game (EG) je také hrána na konečném ohodnoceném orientovaném grafu, ale hra je obohacena neohraničeným čítačem. Čítač má nějakou danou nezápornou počáteční hodnotu a hodnota každé projité hrany je k němu přičítána. Maxův cíl je udržet čítač nezáporný, zatímco Min chce aby šel pod nulu. EGs můžou být zobecněny pro k čítačů, kde k je libovolné přirozené číslo. Ohodnocení hran jsou k-tice celých čísel a každá komponenta každé projité hrany je přičtena k příslušnému čítači. Max chce všechny čítače udržet nezáporné, zatímco Min chce alespoň jeden poslat pod nulu. Mean-payoff a energy games jsou silným nástrojem s mnoha aplikacemi, zejména v syntéze, analýze a verifikaci počítačových systémů.