On the monotonicity of games generated by symmetric submodular functions

Submodular functions have appeared to be a key tool for proving the monotonicity of several graph searching games. In this paper we provide a general game theoretic framework able to unify old and new monotonicity results in a unique min-max theorem. Our theorem, provides a game theoretic analogue to a wide number of graph theoretic parameters such as linear-width and cutwidth.