Many problems in complexity can be reduced to winning a game.
Here is a nice example by Bauwens in:
Complexity of complexity and maximal plain versus prefix-free Kolmogorov complexity
More examples are given in the end.
Game arguments in computability theory and algorithmic information theory
Kolmogorov complexity and games
Game interpretation of Kolmogorov complexity
An application of complexity to […] parity games
