The Territorial Raider game and graph derangements

A derangement of a graph G=(V,E) is an injective function f:V→V such that for all v∈V, f(v)≠v and (v,f(v))∈E. Not all graphs admit a derangement and previous results have characterized graphs with derangements using neighborhood conditions for subsets of V. We establish an alternative criterion for the existence of derangements on a graph. We analyze strict Nash equilibria of the biologically motivated Territorial Raider game, a multi-player competition for resources in a spatially structured population based on animal raiding and defending behavior. We find that a graph G admits a derangement if and only if there is a strict Nash equilibrium of the Territorial Raider game on G.