Interpreting the definition of Determinacy for Quantitative Games

Question

I was trying to understand the definition of determinacy as stated in Lectures in Game Theory for Computer Scientists

Their definition is something like this:

$(V, E)$ is a graph with $V = V_0 \uplus V_1$. Strategies for player $i$ (with $i \in \{0, 1\}$) are functions $V_i^+ \to V$ respecting the edge relation $E$. Given a starting vertex $v \in V$ and strategies $\mu$ and $\chi$ for players 0 and 1 respectively, $Outcome(v, \mu, \chi)$ is the infinite sequence of vertices that are obtained by following these strategies. A payoff function $\pi : V^\omega \to \mathbb{R}$ is a function that associates a real number to each such play. Intuitively, player 1 wants to maximize this value.

Now, they define a game along with a payoff to be determined, if

$$\sup_\mu \inf_\chi \,\pi(Outcome(v, \mu, \chi)) = \inf_\chi \sup_\mu \,\pi(Outcome(v, \mu, \chi)) $$

Their intuition for this is as follows:

[...] player 0 (player Min) does not undermine her objective of minimising the payoff if she announces her strategy to player 1 (player Max) before the play begins, rather than keeping it secret and acting ‘by surprise’ in every round. An analogous interpretation holds for player 1.

I do not fully understand the motivation for this definition. My understanding of the notion of a game being determined is that every instance of it should have a winning strategy for at least one of the players.

I'd appreciate some help with how to break down this definition.

Answer 1

The definition you refer to--in every instance of the game one player should have a winning strategy--applies to qualitative games in which each player simply wins or loses.

With a payoff function $\pi : V^\omega \to \mathbb{R}$, Player $0$ tries to minimize her payoff to Player $1$, who in turn tries to maximize Player $0$'s payoff to him. That's where the $\sup$ and $\inf$ come from.

In a qualitative game, Player $0$ has a winning strategy if she can use that strategy to good effect no matter how Player $1$ plays. (In particular, a winning positional strategy must work even against non-positional strategies of Player $1$.)

In a determined qualitative game, the best Player $0$ can do, no matter what Player $1$ does, is the same as the best Player $1$ can do, no matter what Player $0$ does. For example, if Player $0$ has a winning strategy, her best payoff is $0$, which is also the best payoff Player $1$ can obtain from her.

The generalization of a winning strategy for Player $0$ to quantitative games is a strategy that minimizes Player $0$'s payoff, no matter what strategy Player $1$ employs.

For a fixed vertex $v$,

$$\pi(\operatorname{Outcome}(v,\mu,\chi))$$

is a real-valued function of both players' strategies, while

$$\inf_\mu \pi(\operatorname{Outcome}(v,\mu,\chi))$$

is a function of $\chi$, which gives, for each strategy of Player $1$, the best Player $0$ can do. Likewise,

$$\sup_\chi \pi(\operatorname{Outcome}(v,\mu,\chi))$$

is a function of $\mu$, which gives, for every strategy of Player $0$, the best Player $1$ can do. Hence when

$$\sup_\chi \inf_\mu \pi(\operatorname{Outcome}(v,\mu,\chi)) = \inf_\mu \sup_\chi \pi(\operatorname{Outcome}(v,\mu,\chi))$$

the best Player $0$ can do, no matter what Player $1$ does, equals the best Player $1$ can do, no matter what Player $0$ does. This generalizes the notion of determinacy for qualitative games.

The order of the $\sup$ and $\inf$ operations can be interpreted as the order in which the players announce their strategies. That explains the interpretation suggested by the author.