Games with Payoffs

Games with payoffs are a type of graph game where the players have payoffs associated with each state. The payoff of a state is a number that represents the value of that state to the player.

In more details, we can actually compute the payoff from the sequence of weights from the play (sequence of nodes) in various ways.

A first approach is to consider the maximum weight from the sequence of weights $\rho$, that we indicate as $\text{Sup}(\rho )={\text{sup}}_i{\rho }_i$, which is an extension of the qualitative objective Reach(Win), since the latter corresponds to the quantitative objective Sup using the weight $0$ for Lose and $1$ for Win.

The dual objective of is to consider the smallest weight $\text{Inf}(\rho )={\text{inf}}_i{\rho }_i$, which extends the qualitative objective Safe(Win) where the weight $0$ is used for Win and $1$ for Lose.

Similarly, we can extend:

• Buchi with $\text{LimSup}(\rho )=\underset{i}{\mathrm{limsup}}{\rho }_i$
• CoBuchi with $\text{LimInf}(\rho )=\underset{i}{\mathrm{liminf}}{\rho }_i$

Those games are uniformly positionally determined, meaning there exists an algorithm for computing the value function in polynomial time and space. For Sup and Inf the time complexity if $O(m)$, while it’s $O(knm)$ for LimSup and LimInf.

Mean Payoff Games

With mean payoff games we talk about taking the mean of the weights in the sequence (this is the natural approach to aggregate an infinite sequence of weights).

Since the summation of values in the sequence could not converge, we can take the superior limit or the inferior limit. In particular we can define: $\text{MeanPayoff}+(\rho )=\underset{k}{\mathrm{limsup}}\frac{1}{k}{\sum }_{i=0}^{k-1}{\rho }_i$and

$${\text{MeanPayoff}}^{-}(\rho )=\underset{k}{\mathrm{liminf}}\frac{1}{k}\sum _{i=0}^{k-1}{\rho }_i$$

Note

Note that ${\text{MeanPayoff}}^{+}(-\rho )=-{\text{MeanPayoff}}^{-}(\rho )$, where in $-\rho$ we are taking the opposite of each weight. The two types of mean payoff are dual objectives

Parity games can be reduced to games with payoff with threshold 0 (meaning that a player wins if the mean payoff is greater than 0).

Mean payoff games are prefix independent, meaning that $\text{MeanPayoff}\left({\rho }_0{\rho }_1\dots \right)=\text{MeanPayoff}\left({\rho }_p{\rho }_{p+1}\dots \right)$

Solving Mean Payoff Games

todo The computation of the mean payoff values runs in $O(n^{3}mW)$ time, while we need $O(n^{2}mW)$ to solve the mean payoff games, meaning determining wether a player can get a mean payoff greater than a threshold $c$.

Note that:

• $n$ is the number of vertices
• $m$ is the number of edges
• $W$ is the maximum payoff.
• $k$ is the length of the play.

We can solve Mean Payoff Games using a Value Iteration paradigm.

Energy Games

Weights can also be modelled as Energy, meaning that we consider negative weights as energy consumptions and positive weights ad recharges. We define $Energy(\rho )$ as the smallest initial budget such that the player energy can remain non-negative forever. This value can be computed in $O(mnW)$.

Note

Given a mean payoff graph $G$, we say that it satisfies ${\text{MeanPayoff}}^{-}>0$ if and only if it satisfies $\text{Energy}<\infty$

For the game to be solvable, we also need that $G$ doesn’t contain any negative cycles (a cycle where the sum of the weights is negative). The conditions:

1. ${\text{MeanPayoff}}^{-}>0$
2. $\text{Energy}<\infty$
3. All cycles in $G$ are non-negative are all connected, meaning that any one of the three implies the other twos. #todo (see the proof of this that can be interesting for the project.)

Solving Energy Games

Using this definition, we can define another value iteration algorithm that solves energy games, and so that also solves mean payoff games.

Discounted Payoff Games

In discounted payoff games, we introduce a $\lambda$ term:

$\text{DiscountedPayoff}(\rho )=(1-\lambda ){\sum }_{i=0}^{\infty }({\lambda }^i{\rho }_i)$

Since $\lambda \in (0,1)$, it will give more weight to the initial weights, and less to the following weights (because of the $i$ at the exponent, $\lambda$ shrinks).

The more $\lambda$ is near $1$, the more the payoff is similar to the mean payoff.

---

tags: game-theory - graph-theory resources: