Mean-Payoff Pushdown Games

Krishnendu Chatterjee, Yaron Velner

Introduction

Mean-payoff pushdown games provide a robust framework for modeling the performance and resource consumption of recursive programs. While qualitative analysis (e.g., reachability) of pushdown systems is well-understood, quantitative analysis—such as determining long-run average power consumption or response time—presents significant challenges. This research explores the complexity landscape of these games, focusing on the distinction between global strategies, which consider the entire execution history and stack state, and modular strategies, which are context-independent and behave consistently regardless of the calling module.

Methodology

The authors establish their results through several theoretical techniques. For one-player systems, they utilize dynamic programming to compute summary functions, identifying "good cycles" where positive weight is accumulated without decreasing stack height. To analyze modular strategies, the authors introduce a novel technique of "manipulating" execution histories by "rewinding" cycles or "fast-forwarding" through certain paths. Additionally, undecidability in two-player global games is proven by reducing from the universality problem of weighted automata, while NP-hardness for modular strategies is established via a reduction from the classic 3-SAT problem.

Strategy and Memory Requirements

A pivotal insight of this work is the memory requirement for different strategy types. In global settings, the ability to observe the stack allows for complex encoding, but surprisingly, even one-player systems require infinite memory for mean-payoff objectives. In contrast, modular strategies—which align more closely with well-structured, modular software design—only require memoryless (positional) choices.

Memory requirements for global vs. modular strategies.

Complexity Results

The research reveals a stark "complexity split." While the inclusion of stack context in global strategies leads to undecidability in two-player games, restricting players to modular strategies makes the problem decidable and NP-complete. This suggests that modularity is not just a software engineering best practice but also a mathematical necessity for tractable quantitative verification.

Complexity map for mean-payoff pushdown games and systems.

Conclusion

By mapping the complexity of mean-payoff pushdown games, this paper identifies modular strategies as a promising path forward for practical program analysis. Future research will likely extend these findings to multi-dimensional objectives, balancing multiple performance metrics like latency and power consumption in recursive environments.

Summary updated

BibTeX
@inproceedings{chatterjee2012mean,
  author = {Krishnendu Chatterjee and Yaron Velner},
  title = {{Mean-Payoff Pushdown Games}},
  booktitle = {LICS},
  year = {2012},
  doi = {10.1109/lics.2012.30},
}
Figure