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.

  • $\begingroup$ You can get the proper roman font for operators like $\operatorname{Outcome}$ that don't have a command of their own by using \operatorname{Outcome}. $\endgroup$
    – joriki
    Sep 8, 2018 at 13:55

1 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$,


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .