Matthias Mnich (TUHH)

Mean-Payoff Games: A Powerful Tool between Mathematics and Computer Science, between Theory and Applications

Mean-payoff games are a powerful tool for modeling the verification process of large pieces of software, like those developed for performing experiments at the Large Hadron Collider, the world’s largest and highest-energy particle collider at CERN. From a theory perspective, mean-payoff games are two player deterministic zero-sum games with full information that were introduced by Ehrenfeucht and Mycielski 1979. The determination of winning strategies forms an interesting problem in complexity theory, which is known to be in NP and co-NP, but until now has withstood a solution in polynomial time. We give an introduction to this fascinating piece of mathematics from an algorithmic perspective, and present novel algorithms which significantly outperform previous methods to solve several interesting classes of mean-payoff games.