Continuous Positional Payoffs

12/16/2020
by   Alexander Kozachinskiy, et al.
0

What payoffs are positional for (deterministic) two-player antagonistic games on finite directed graphs? In this paper we study this question for payoffs that are continuous. The main reason why continuous positional payoffs are interesting is that they include multi-discounted payoffs. We show that for continuous payoffs positionality is equivalent to a simple property called prefix-monotonicity. In fact, we show that three major techniques of establishing positionality – inductive technique, fixed point technique and strategy improvement technique – are all sufficient to obtain this result. Finally, we study analogous questions for more general stochastic games. It turns out that all continuous stochastically positional payoffs are multi-discounted. As a byproduct, this refutes a conjecture of Gimbert (STACS 2007), who conjectured that all deterministically positional payoffs are stochastically positional.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset