Since parity game solving is in TFNP ("Total Function Nondeterministic Polynomial") (and the decision version is is NP ∩ coNP), I wonder whether it is contained in PLS ("Polynomial Local Search") or PPA ("Polynomial Parity Argument")? Add PPP ("Polynomial Pigeonhole Principle") if you want, even so this would probably mean that it is already contained in PPAD ("Polynomial Parity Arguments on Directed graphs"), and hence in PPA.
Or is it rather the other way round and parity game solving can be shown to be hard for PLS or PPAD? But that would be surprising, since a recursive algorithm that solves parity games is known (even if it is not efficient in the worst case).
Edit 12 March 2017: I recently learned that parity game solving has been shown to be possible in quasipolynomial time. Here are the quoted references:
Deciding Parity Games in Quasipolynomial Time (PDF), by Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan.
A short proof of correctness of the quasi-polynomial time algorithm for parity games, by Hugo Gimbert and Rasmus Ibsen-Jensen.
Succinct progress measures for solving parity games, by Marcin Jurdziński and Ranko Lazić.
An implementation and comparison with previous approaches is available (classic strategy improvement "wins" on random instances, but gets "slow" on Friedmann’s trap examples):
An Ordered Approach to Solving Parity Games in Quasi Polynomial Time and Quasi Linear Space, by John Fearnley, Sanjay Jain, Sven Schewe, Frank Stephan, Dominik Wojtczak