The complexity of Arrival is particularly interesting in the context of other games on graphs, such as Condon's simple stochastic games, mean-payoff games, and parity games [1]}, [2]}, [3]}, for which the two-player variants are known to be in \(\cap \) , whereas the one-player variants have polynomial time algorithms. Arrival however is a zero-player game which has no known polynomial time algorithm and furthermore it was shown by Fearnley et al. [4]} that a one-player generalisation of arrival is in fact -complete, in stark contrast to these two-player graph games.
