Abstract

When we reason about strategic games, implicitly we need to reason about arbitrary strategy profiles and how players can improve from each profile. This structure is exponential in the number of players. Hence it is natural to look for subclasses of succinct games for which we can reason directly by interpreting formulas on the (succinct) game description rather than on the associated improvement structure. Priority separable games are one of such subclasses: payoffs are specified for pairwise interactions, and from these, payoffs are computed for strategy profiles. We show that equilibria in such games can be described in Monadic Least Fixed Point Logic (MLFP). We then extend the description to games over arbitrarily many players, but using the monadic least fixed point extension of existential second order logic.