  Two-player games on graphs is central in many problems in formal verification
and program analysis such as synthesis and verification of open systems. In
this work we consider solving recursive game graphs (or pushdown game graphs)
that can model the control flow of sequential programs with recursion. While
pushdown games have been studied before with qualitative objectives, such as
reachability and $\omega$-regular objectives, in this work we study for the
first time such games with the most well-studied quantitative objective,
namely, mean-payoff objectives. In pushdown games two types of strategies are
relevant: (1) global strategies, that depend on the entire global history; and
(2) modular strategies, that have only local memory and thus does not depend on
the context of invocation, but only on the history of the current invocation of
the module. Our main results are as follows (1) One-player pushdown games with
mean-payoff objectives under global strategies is decidable in polynomial time.
(2) Two-player pushdown games with mean-payoff objectives under global
strategies is undecidable. (3) One-player pushdown games with mean-payoff
objectives under modular strategies is NP-hard. (4) Two-player pushdown games
with mean-payoff objectives under modular strategies can be solved in NP (i.e.,
both one-player and two-player pushdown games with mean-payoff objectives under
modular strategies is NP-complete). We also establish the optimal strategy
complexity showing that global strategies for mean-payoff objectives require
infinite memory even in one-player pushdown games; and memoryless modular
strategies are sufficient in two-player pushdown games. Finally we also show
that all the problems have the same complexity if the stack boundedness
condition is added, where along with the mean-payoff objective the player must
also ensure that the stack height is bounded.
