Generic algorithm for parity and mean payoff games

In this talk, we present linear graphs for generic positional objectives in the context of infinite duration two player games over finite graphs such as the parity or mean payoff objectives. These were originally designed to capture the new quasi-polynomial value iteration algorithms for parity games. We show that this framework also allows to formalize other families of algorithms such as strategy-improvement algorithms, or (in the context of parity games), attractor-based algorithms.

Authors

• Pierre Ohlmann

Keywords

No keywords are indexed for this paper.