Mean-Payoff Game

A mean-payoff game is a two-player zero-sum game on a finite directed graph whose vertices are assigned to the players Max and Min and whose edges have numerical rewards. Each graph vertex has an outgoing graph edge, and its owner chooses the next graph edge. Both players observe the complete preceding play and may choose strategies that depend on this history.

For the infinite walk traversing edges , the payoff to Max is

where is the reward of graph edge and denotes the infimum limit. Max seeks to maximize this payoff and Min seeks to minimize it. A positional strategy chooses an outgoing graph edge using only the current graph vertex.