In game theory, a mean payoff game is a zero-sum game played on the vertices of a weighted directed graph. The game is played as follows: at the start of the game, a token is placed on one of the vertices of the graph. Each vertex is assigned to either the Maximizer of the Minimizer. The player that controls the current vertex the token is on may choose one outgoing edge along which the token moves next. In doing so, the Minimizer pays the Maximizer the number that is on the edge. Then, again, the player controlling the next vertex the token gets can choose where it goes, and this continues indefinitely. The objective for the Maximizer is to maximize their long term average payoff, and the Minimizer has the opposite objective.
Formal definition A mean payoff game consists of a graph G = ( V M a x ∪ V M i n , E ) {\displaystyle G=(V_{Max}\cup V_{Min},E)} , and a function w : E → R {\displaystyle w:E\to \mathbb {R} } where V = V M a x ∪ V M i n {\displaystyle V=V_{Max}\cup V_{Min}} is the set of vertices, which are partitioned between the players, and where w ( e ) {\displaystyle w(e)} is the weight of an edge. Often, the graph is assumed to be sinkless, which means that every vertex has at least one outgoing edge. A play is a possible outcome of the game, which is an infinite walk on the graph, we could write this as a sequence of edges: π = e 1 , e 2 , e 3 , … {\displaystyle \pi =e_{1},e_{2},e_{3},\ldots } where the head of e i {\displaystyle e_{i}} equals the tail of e i + 1 {\displaystyle e_{i+1}} . The objective value of the game can then be written as follows:
O ( π ) = lim inf t → ∞ 1 t ∑ i = 1 t w ( e i ) {\displaystyle O(\pi )=\liminf _{t\to \infty }{\frac {1}{t}}\sum _{i=1}^{t}w(e_{i})}
A strategy for the Maximizer is a function σ : F W M a x → E {\displaystyle \sigma :FW_{Max}\to E} , where F W v {\displaystyle FW_{v}} is the set of finite walks that start at the initial vertex and end at some vertex v ∈ V M a x {\displaystyle v\in V_{Max}} , which returns an outgoing edge of the end vertex v {\displaystyle v} . A strategy τ {\displaystyle \tau } for the Minimizer can be defined analogously. If both players fix a strategy, say they pick strategies σ {\displaystyle \sigma } and τ {\displaystyle \tau } , then the outcome of the game is fixed, and the resulting play is the path π σ τ {\displaystyle \pi _{\sigma \tau }} . One of the fundamental results for mean payoff games is that they are positionally determined. This means in our case that the game has a unique value, and that each player has a strategy that can attain the value, and that strategy is positional, e.g. it only depends on the current vertex the token is on. In formulas, the following equation holds for the value V ( G , w ) {\displaystyle V(G,w)} :
V ( G , w ) = max σ ∈ (positional Max strategies) inf τ ∈ (Min strategies) O ( π σ τ ) = min τ ∈ (positional Min strategies) sup σ ∈ (Max strategies) O ( π σ τ ) {\displaystyle V(G,w)=\max _{\sigma \in {\text{(positional Max strategies)}}}\inf _{\tau \in {\text{(Min strategies)}}}O(\pi _{\sigma \tau })=\min _{\tau \in {\text{(positional Min strategies)}}}\sup _{\sigma \in {\text{(Max strategies)}}}O(\pi _{\sigma \tau })}
Solving mean payoff games Solving a mean payoff game can mean several things, although in practice finding one often also yields the other:
… excerpt ends here. Continue reading the full article.
