We investigate the possible structural changes one can perform on a game graph without destroying the winning regions of the players playing a parity game on it. More precisely, given a game graph $(G,p)$ for which we can efficiently compute winning regions, can we remove or add a vertex or edge or change a single priority and maintain at least part of the winning region? Also, what about restricted classes of graphs, such as planar, $k$-connected and the like?