  We introduce an algorithm which solves mean payoff games in polynomial time
on average, assuming the distribution of the games satisfies a flip invariance
property on the set of actions associated with every state. The algorithm is a
tropical analogue of the shadow-vertex simplex algorithm, which solves mean
payoff games via linear feasibility problems over the tropical semiring
$(\mathbb{R} \cup \{-\infty\}, \max, +)$. The key ingredient in our approach is
that the shadow-vertex pivoting rule can be transferred to tropical polyhedra,
and that its computation reduces to optimal assignment problems through
Pl\"ucker relations.
