Speed of victory in adversarial population games
Population games involve two players, Laetitia and Terence, and an NFA with one initial and one final state. At the start, some number of tokens are placed on the initial state. At each turn, Laetitia chooses a letter and Terence moves each token along a transition labelled by . The goal of Laetitia is that at some point all tokens are gathered on the final state, while Terence tries to avoid it indefinitely. It was shown in [1] that we can decide whether Laetitia wins for all number of tokens . The proof uses an abstracted version of the game, called the \textbackslash{}textit{capacity game}, in which the number of tokens is not written explicitly. In the journal version [2], it was shown that if Laetitia wins then she has a strategy to win in steps, for all , with depending only on the NFA. On the other hand, we know that some games can be won in steps, or in steps. We think that automata can be split in four classes: winnable in constant, polylog, polynomial number of steps, or not winnable at all. To sum up, here is what we know: It is PSPACE-complete to decide whether a game is winnable in constant time, and if not then it requires at least polylog time. It is EXPTIME-complete to decide whether a game is winnable in polynomial time, and if not then it is not winnable at all. The open problem is to complete this picture by proving the following conjecture: It is decidable whether a game is winnable in polylog time, and if not then it requires at least polynomial time. Ideally, this would come with complexity bounds. [1] Bertrand, Dewaskar, Genest, Gimbert, , CONCUR 2017 [2] Bertrand, Dewaskar, Genest, Gimbert, Godbole , LMCS-15(3), 2019
