---
date: Sunday, February 23^rd^, 2025
katex-css: true
title: Minimax, three ways
---

This is a short technical note written in the process of working out
some definitions for a paper about using an approximate minimax regret
training objective to mitigate goal misgeneralisation in advanced deep
reinforcement learning systems. I define a minimax objective in three
different ways, and show that the definitions are equivalent under
certain assumptions.

Thanks to my colleagues [Karim Abdel
Sadek](https://karim-abdel.github.io/) and [Michael
Dennis](https://www.michaeldennis.ai/) for helping me understand the
necessary game theory and decision theory to figure this out.

```{=tex}
\newcommand\Reals{\mathbb{R}}
\newcommand\argmax{\operatornamewithlimits{arg\,max}}
\newcommand\argmin{\operatornamewithlimits{arg\,min}}
\renewcommand\max{\operatornamewithlimits{\vphantom{arg\,}max}}
\renewcommand\min{\operatornamewithlimits{\vphantom{arg\,}min}}
\newcommand\Actions{\mathcal{A}}
\newcommand\States{\mathcal{S}}
```
## Background

In the aforementioned paper, we study the generalisation properties of
approximate optima under different objectives. We want to study
approximate optima, rather than exact optima, because the former is more
like what our training methods will find in practice.

However, one of the objectives we want to study is minimax regret, which
is an objective that actually involves two optimisers: we want to take
the minimum of a function that involves a maximum. It wasn't immediately
obvious to me what the appropriate approximate relaxation was for this
type of adversarial optimisation.

My colleagues and I came up with a few candidate definitions. I got to
work trying to prove they were equivalent in some appropriate sense. I
got stuck, so I retreated to the exact case, reasoning that if I can
understand how the definitions relate to each other in the exact case,
then I should be in a better position to understand the relationships
between the approximate relaxations.

This note doesn't discuss what regret is. It's not really important for
today---we're just interested in the *minimax* part. I also don't
discuss why we are interested in minimax regret as an objective. For
more background, see the paper (when it comes out), or [this old essay
by Savage (1951)](https://doi.org/10.1080/01621459.1951.10500768) that
abstracted minimax regret as a general principle for making decisions
under uncertainty from the statistics literature.

This note also doesn't much discuss the approximate relaxations. Here
I'm just writing out the proofs from the exact case, partly as a way of
checking my work, and partly because I think the proofs are pretty neat.

Update: For the approximate case, see [this sequel
note](approximinimax-three-ways).

## Three formal definitions...

Suppose we have a function
$r : \mathcal{A}\times \mathcal{S}\to \mathbb{R}$. As I said, it doesn't
matter what the function represents. It also doesn't matter much what
the sets $\mathcal{A}$ and $\mathcal{S}$ are. All we really need to know
is that we want to find a first argument $a \in \mathcal{A}$ so as to
minimise the maximum possible value for any value of the second argument
$s \in \mathcal{S}$. (The only assumption I make on $r$, $\mathcal{A}$,
and $\mathcal{S}$ is that all the maxima and minima I refer to exist.)

Such abstraction is sufficiently cumbersome that I would prefer to use
slightly more concrete terminology. The symbols are chosen to suggest
that $r(a, s)$ is the *regret* from taking *action* $a \in \mathcal{A}$
when the world is in *state* $s \in \mathcal{S}$. The objective would
then be phrased, we want to find an action that minimises the maximum
regret under any world state.

The question is, how should we formalise this objective? Here are three
ways.

### The standard definition from decision theory

The first is the standard decision theory definition, and is a
straightforward transliteration of the above description:

**Definition 1:** *An action $a \in \mathcal{A}$ is* minimax(1) *if $$
    a \in \operatornamewithlimits{arg\,min}_{a' \in \mathcal{A}} \operatornamewithlimits{\vphantom{arg\,}max}_{s' \in \mathcal{S}} r(a', s').
  $$*

While this definition is straightforward, it's difficult to see how to
replace the maximiser with an approximate version, since it's nested
inside a minimum.

### The standard definition from game theory

In an attempt to address this shortcoming, we appeal to game theory,
where we find plenty of tools for studying competition between
optimisers:

**Definition 2:** *An action $a \in \mathcal{A}$ is* minimax(2) *if
there exists $s \in \mathcal{S}$ such that both $$
    s \in \operatornamewithlimits{arg\,max}_{s'\in\mathcal{S}} r(a, s')
    \quad\textit{and}\quad
    a \in \operatornamewithlimits{arg\,min}_{a'\in\mathcal{A}} r(a', s).
  $$*

This condition says that $(a, s)$ is a Nash equilibrium of a two-player,
zero-sum game where the first player selects an action
$a \in \mathcal{A}$ and the second player selects a state
$s \in \mathcal{S}$, respectively aiming to minimise or maximise the
regret $r(a, s)$. A minimax(2) action is then any action that is part of
a Nash equilibrium.

It's easy to see how to relax this definition: just replace both of the
constraints with approximate version, effectively permitting each player
a small incentive to change strategy (making it a [near-Nash
equilibrium](https://en.wikipedia.org/wiki/Epsilon-equilibrium)).

However, not all games have Nash equilibria, or even near-Nash
equilibria. For example, suppose for some reason we want to find a pure
strategy equilibrium rather than a mixed strategy equilibrium. It is
well-known that some games lack a pure strategy equilibrium (e.g.,
rock/paper/scissors). Moreover, even for mixed strategies, if the
strategy space is not compact, there may not be a Nash equilibrium.

In such cases, minimax(2) is not well defined. In contrast, minimax(1)
is well-defined for any $r$, $\mathcal{A}$, $\mathcal{S}$ as long as the
maxima and minima exist. Intuitively, we don't need there to be an
equilibrium for us to be able to talk about minimising the worst
possible response.

### An alternative definition

This brings us to the third definition, which, as far as I can tell, is
not a standard way of defining minimax, but has the potential to capture
the nice properties of both minimax(1), namely not relying on an
equilibrium, and of minimax(2), namely separating out the maximiser and
the minimiser so that each can be relaxed.

**Definition 3.1:** *A* max map *is any function
$\sigma: \mathcal{A}\to \mathcal{S}$ such that for all
$a \in \mathcal{A}$, $$
    \sigma(a) \in \operatornamewithlimits{arg\,max}_{s' \in \mathcal{S}} r(a, s')
  .
  $$*

**Definition 3.2:** *Let $\sigma$ be any max map. An action
$a \in \mathcal{A}$ is* minimax(3$\sigma$) *if $$
    a \in \operatornamewithlimits{arg\,min}_{a' \in \mathcal{A}} r(a', \sigma(a'))
  .
  $$*

This definition is not as straightforward as the previous ones. Let's
unpack it. Note that this definition depends on a choice of a *max map*
$\sigma$ that has the specified property. Intuitively, $\sigma$
represents a model of a deterministic, worst-case response
$\sigma(a) \in \mathcal{S}$ to every possible action
$a \in \mathcal{A}$.

Given a max map $\sigma$, we then define minimax(3$\sigma$) actions by
optimising the *single-argument* function $a \mapsto r(a, \sigma(a))$.
Compared to definition 1, we factor out the inner optimisation problem
into computing the max map. Compared to definition 2, it's like we're
playing a game in our head against a model of a particular optimal
adversary, rather than playing a real game against a real
adversary.[^1]^,^[^2]

What we gain from the extra complexity is the following. Like
minimax(1), minimax(3$\sigma$) is well-defined even if the zero-sum game
has no Nash equilibrium. Moreover, like minimax(2), we can clearly relax
both the maximisation (by relaxing the condition on the max map
$\sigma$) as well as the minimisation (by relaxing the condition on the
action $a$).

## ... and their equivalence

Of course, it remains to prove that this definition actually captures
the same kinds of actions as the other two. As a starting point, we also
prove to ourselves that the first two definitions are equivalent to each
other (this is a well-known result, but I am interested in the proof).

The following diagram summarises the equivalences between the three
definitions. The symbols $\mathcal{A}^{(1)}$, $\mathcal{A}^{(2)}$, and
$\mathcal{A}^{(3\sigma)}$ represent the conditions minimax(1),
minimax(2), and minimax(3$\sigma$), respectively. P1 through P6 indicate
numbered propositions establishing each relationship. P2$'$ and P5$'$
are primed because these relationships involve an additional assumption
(that an equilibrium exists).

`<img
  src="minimax-three-ways-map.png"
  alt="Map of the relationships between different minimax definitions."
  style="width: 40ch; max-width: 100%"
/>`{=html}

### Aside: The max--min inequality and equilibria of zero-sum games

Before we prove these equivalences, we take a brief detour into some
basic properties of zero-sum games. First, we note the following
inequality that holds for any function $r$ and any sets $\mathcal{A}$,
$\mathcal{S}$ (as long as the minima and maxima exist; though in this
case if they do not, the lemma holds with infima and suprema instead).

**Lemma 1** (max--min inequality)**:** $$
  \operatornamewithlimits{\vphantom{arg\,}max}_{s' \in \mathcal{S}} \operatornamewithlimits{\vphantom{arg\,}min}_{a' \in \mathcal{A}} r(a', s')
  \leq
  \operatornamewithlimits{\vphantom{arg\,}min}_{a' \in \mathcal{A}} \operatornamewithlimits{\vphantom{arg\,}max}_{s' \in \mathcal{S}} r(a', s')
.
$$

*Proof.* Let
$a \in \operatornamewithlimits{arg\,min}_{a' \in \mathcal{A}} \operatornamewithlimits{\vphantom{arg\,}max}_{s' \in \mathcal{S}} r(a', s')$
and let
$s \in \operatornamewithlimits{arg\,max}_{s' \in \mathcal{S}} \operatornamewithlimits{\vphantom{arg\,}min}_{a' \in \mathcal{A}} r(a', s')$.
Then we have $$\begin{align*}
  \operatornamewithlimits{\vphantom{arg\,}max}_{s' \in \mathcal{S}} \operatornamewithlimits{\vphantom{arg\,}min}_{a' \in \mathcal{A}} r(a', s')
  &= \operatornamewithlimits{\vphantom{arg\,}min}_{a' \in \mathcal{A}} r(a', s)
  &\text{(by definition of $s$)}
\\&\leq r(a, s)
  &\text{(by definition of min)}
\\&\leq \operatornamewithlimits{\vphantom{arg\,}max}_{s' \in \mathcal{S}} r(a, s')
  &\text{(by definition of max)}
\\&= \operatornamewithlimits{\vphantom{arg\,}min}_{a' \in \mathcal{A}} \operatornamewithlimits{\vphantom{arg\,}max}_{s' \in \mathcal{S}} r(a', s').
  &\text{(by definition of $a$)}
  \tag*{$\square$}
\end{align*}$$

We will also need the following, related result, which says that, if our
zero-sum game has an equilibrium, then the max--min inequality is an
equality. (The converse also holds, but we do not need it for this
note.)

**Lemma 2:** *Suppose there exists
$(a, s) \in \mathcal{A}\times \mathcal{S}$ such that
$s \in \operatornamewithlimits{arg\,max}_{s'\in\mathcal{S}} r(a, s')$
and
$a \in \operatornamewithlimits{arg\,min}_{a'\in\mathcal{A}} r(a', s)$.
Then $$
    \operatornamewithlimits{\vphantom{arg\,}max}_{s'\in\mathcal{S}} \operatornamewithlimits{\vphantom{arg\,}min}_{a'\in\mathcal{A}} r(a', s')
    =
    \operatornamewithlimits{\vphantom{arg\,}min}_{a'\in\mathcal{A}} \operatornamewithlimits{\vphantom{arg\,}max}_{s'\in\mathcal{S}} r(a', s')
  .$$*

*Proof.* We already know from lemma 1 that LHS $\leq$ RHS. Under these
conditions we also have LHS $\geq$ RHS as follows: $$\begin{align*}
  \operatornamewithlimits{\vphantom{arg\,}max}_{s' \in \mathcal{S}} \operatornamewithlimits{\vphantom{arg\,}min}_{a' \in \mathcal{A}} r(a', s')
  &\geq \operatornamewithlimits{\vphantom{arg\,}min}_{a' \in \mathcal{A}} r(a', s)
  &\text{(by definition of max)}
\\&= r(a, s)
  &\text{(by definition of $a$)}
\\&= \operatornamewithlimits{\vphantom{arg\,}max}_{s' \in \mathcal{S}} r(a, s')
  &\text{(by definition of $s$)}
\\&\geq \operatornamewithlimits{\vphantom{arg\,}min}_{a' \in \mathcal{A}} \operatornamewithlimits{\vphantom{arg\,}max}_{s' \in \mathcal{S}} r(a', s').
  &\text{(by definition of min)}
  \tag*{$\square$}
\end{align*}$$

Intuitively, lemma 1 says that if the minimiser chooses their action as
a function of the state, they will always do at least as well as if they
must choose a constant action without knowledge of the state. Lemma 2
then says that an equilibrium can only exists when the minimiser can do
no better by choosing their action with (vs. without) knowledge of the
strategy of the maximiser, and vice versa.

I really like the symmetry in these two proofs. Notice that the sequence
of terms we relate is the same in both cases, we just somewhat reorder
the definitions we apply to them and how we relate them with
inequalities or equalities. Neat!

*Remark.* Lemmas 1 and 2 are some basic results that are related to the
famed [minimax theorem](https://en.wikipedia.org/wiki/Minimax_theorem)
of von Neumann that was the foundation of game theory.

-   Von Neumann proved that the max--min inequality is an equality for
    all two-player zero-sum games with mixed strategies over finite
    action spaces. (Since that time, minimax theorems have been proven
    for more general classes of functions). Lemma 1 shows the trivial
    side of this equality, which holds for all functions as long as min
    and max are defined ([and
    beyond](https://en.wikipedia.org/wiki/Max%E2%80%93min_inequality)).

-   It's also true that, if the max--min inequality is an equality, then
    an equilibrium exists. Therefore, von Neumann's minimax theorem
    showed that all discrete zero-sum games with mixed strategies have
    equilibria. Lemma 2 is the converse: if an equilibrium exists, the
    max--min inequality is an equality.

Proving a minimax theorem requires some more advanced techniques, and
certain assumptions on the function and the sets. Luckily, for this note
we can bypass such details by just assuming an equilibrium exists.

### Equivalence of minimax(1) and minimax(2)

Now, we are ready to prove the equivalence of definitions 1 and 2.
First, we show that minimax(2) implies minimax(1). For this direction,
we implicitly assume that an equilibrium exists (in supposing that
minimax(2) holds), so we don't have to worry about the case where there
are no equilibria in the zero-sum game.

**Proposition 1:** *Let $a \in \mathcal{A}$ be minimax(2). Then $a$ is
minimax(1).*

*Proof.* Suppose $a$ is minimax(2). So, there exists $s \in \mathcal{S}$
such that both
$s \in \operatornamewithlimits{arg\,max}_{s'\in\mathcal{S}} r(a, s')$
and
$a \in \operatornamewithlimits{arg\,min}_{a'\in\mathcal{A}} r(a', s)$.
Then, $$\begin{align*}
    \operatornamewithlimits{\vphantom{arg\,}max}_{s' \in \mathcal{S}} r(a, s')
    &= r(a, s)
    &\text{(by definition of $s$)}
  \\&= \operatornamewithlimits{\vphantom{arg\,}min}_{a' \in \mathcal{A}} r(a', s)
    &\text{(by definition of $a$)}
  \\&\leq \operatornamewithlimits{\vphantom{arg\,}max}_{s' \in \mathcal{S}} \operatornamewithlimits{\vphantom{arg\,}min}_{a' \in \mathcal{A}} r(a', s')
    &\text{(by definition of max)}
  \\&\leq \operatornamewithlimits{\vphantom{arg\,}min}_{a' \in \mathcal{A}} \operatornamewithlimits{\vphantom{arg\,}max}_{s' \in \mathcal{S}} r(a', s').
    &\text{(by lemma 1)}
  \end{align*}$$ In summary,
$\operatornamewithlimits{\vphantom{arg\,}max}_{s' \in \mathcal{S}} r(a, s')
      \leq
        \operatornamewithlimits{\vphantom{arg\,}min}_{a' \in \mathcal{A}} \operatornamewithlimits{\vphantom{arg\,}max}_{s' \in \mathcal{S}} r(a', s')$.
Observe, the LHS of this inequality is part of the minimisation
operation on the RHS. Therefore, we must have an equality, and $a$ is a
minimiser or the operand on the RHS. Therefore, we have the minimax(1)
condition $$
    a \in \operatornamewithlimits{arg\,min}_{a' \in \mathcal{A}} \operatornamewithlimits{\vphantom{arg\,}max}_{s' \in \mathcal{S}} r(a', s')
  .
  \tag*{$\square$}
  $$

Notice that, while the max--min inequality is an equality under these
assumptions (by lemma 2, and also very nearly a byproduct of this
proof), we only needed the inequality this time. This is a good sign,
because when it comes to the approximate case, we would only want to
assume that there is an approximate equilibrium without additionally
making the stronger assumption that there also exists an exact
equilibrium.

Now, for the converse direction. This direction can't hold if the
zero-sum game has no equilibria: then we can have a minimax(1) action
but there are no minimax(2) actions. However, we prove that this is the
only case in which the converse doesn't hold: as long as the zero-sum
game has an equilibrium, then, by lemma 2, the max--min inequality is an
equality, an equilibrium exists, and the minimax(1) action is part of an
equilibrium.

**Proposition 2:** *Suppose there exists some $a' \in \mathcal{A}$ that
is minimax(2). Let $a \in \mathcal{A}$ be minimax(1). Then $a$ is
minimax(2).*

*Proof.* To say there exists an $a' \in \mathcal{A}$ that is minimax(2)
is the same as saying an equilibrium exists, so lemma 2 applies. Let $a$
be minimax(1), we have
$a \in \operatornamewithlimits{arg\,min}_{a' \in \mathcal{A}} \operatornamewithlimits{\vphantom{arg\,}max}_{s' \in \mathcal{S}} r(a', s')$.
Let
$s \in \operatornamewithlimits{arg\,max}_{s' \in \mathcal{S}} \operatornamewithlimits{\vphantom{arg\,}min}_{a' \in \mathcal{A}} r(a', s')$.
Then we have $$\begin{align*}
  r(a, s)
    &\geq \operatornamewithlimits{\vphantom{arg\,}min}_{a' \in \mathcal{A}} r(a', s)
    &\text{(by definition of min)}
  \\&= \operatornamewithlimits{\vphantom{arg\,}max}_{s' \in \mathcal{S}} \operatornamewithlimits{\vphantom{arg\,}min}_{a' \in \mathcal{A}} r(a', s')
    &\text{(by definition of $s$)}
  \\&= \operatornamewithlimits{\vphantom{arg\,}min}_{a' \in \mathcal{A}} \operatornamewithlimits{\vphantom{arg\,}max}_{s' \in \mathcal{S}} r(a', s')
    &\text{(by lemma 2)}
  \\&= \operatornamewithlimits{\vphantom{arg\,}max}_{s' \in \mathcal{S}} r(a, s')
    &\text{(by definition of $a$)}
  \\&\geq r(a, s).
    &\text{(by definition of max)}
  \end{align*}$$ The first and final terms are equal. Therefore, the two
inequalities must be equalities. Each gives us part of the minimax(2)
condition, $$
    a \in \operatornamewithlimits{arg\,min}_{a'\in\mathcal{A}} r(a', s)
    \quad\text{and}\quad
    s \in \operatornamewithlimits{arg\,max}_{s'\in\mathcal{S}} r(a, s').
  \tag*{$\square$}
  $$

This proof is cute in that it packages together the proof of both
minimax(2) conditions into one chain of relations. The structure is also
very similar to the structure of the proof of proposition 1. The text
after the "summary" in that proof essentially appends
"$\leq \operatornamewithlimits{\vphantom{arg\,}max}_{s'\in\mathcal{S}} r(a, s')$
(by definition of min)" to the end of the chain of relations. Then both
proofs are based on the same 'cycle' of terms. Based on the different
assumptions, different relations are replaced with inequalities. But
once we complete the cycle, it becomes clear that all the terms are
actually equal. I think that's pretty neat.

### Equivalence of minimax(1) and minimax(3$\sigma$)

OK. So far so good, but that was all very standard game theory. Now let
us turn to the more interesting cases involving the new, alternative
definition! We'll start by showing that minimax(1) and
minimax(3$\sigma$) are equivalent.

When I say "minimax(3$\sigma$)," I'm leaving $\sigma$ unspecified. I
mean we should be able to take *any* $\sigma$ that meets the condition
in the definition, and prove that the equivalence holds for the version
of the definition specific to that $\sigma$. That means the below
statements and proofs need to be conditioned on $\sigma$.

**Proposition 3:** *Let $\sigma: \mathcal{A}\to \mathcal{S}$ be any max
map. Let $a \in \mathcal{A}$ be minimax(1). Then $a$ is
minimax(3$\sigma$).*

*Proof.* Suppose $a$ is minimax(1). So, we have
$a \in \operatornamewithlimits{arg\,min}_{a' \in \mathcal{A}} \operatornamewithlimits{\vphantom{arg\,}max}_{s' \in \mathcal{S}} r(a', s')$.
Then, $$\begin{align*}
    r(a, \sigma(a))
    &\leq \operatornamewithlimits{\vphantom{arg\,}max}_{s' \in \mathcal{S}} r(a, s')
    &\text{(by definition of max)}
  \\&= \operatornamewithlimits{\vphantom{arg\,}min}_{a' \in \mathcal{A}} \operatornamewithlimits{\vphantom{arg\,}max}_{s' \in \mathcal{S}} r(a', s')
    &\text{(by definition of $a$)}
  \\&= \operatornamewithlimits{\vphantom{arg\,}min}_{a' \in \mathcal{A}} r(a', \sigma(a')).
    &\text{(by definition of $\sigma$)}
  \end{align*}$$ This suffices to prove the minimax(3$\sigma$)
condition: $$
    a \in \operatornamewithlimits{arg\,min}_{a' \in \mathcal{A}} r(a', \sigma(a')).
    \tag*{$\square$}
  $$

Note that for the inequality, we actually have an equality by definition
of $\sigma$. However, all we need is the inequality to establish that
$a$ is a minimiser. It wouldn't matter here if we used the equality
instead, but when it comes time to relax to the approximate case, we
don't want to use the definition of $\sigma$ more than we have to,
because each time we use it we introduce an approximation error.

Now, for the converse. Once again, the proof is highly symmetrical to
the previous one.

**Proposition 4:** *Let $\sigma: \mathcal{A}\to \mathcal{S}$ be any max
map. Let $a \in \mathcal{A}$ be minimax(3$\sigma$). Then $a$ is
minimax(1).*

*Proof.* Suppose $a$ is minimax(3$\sigma$). So, we have
$a \in \operatornamewithlimits{arg\,min}_{a' \in \mathcal{A}} r(a', \sigma(a'))$.
Then, $$\begin{align*}
    \operatornamewithlimits{\vphantom{arg\,}max}_{s' \in \mathcal{S}} r(a, s')
    &= r(a, \sigma(a))
    &\text{(by definition of $\sigma$)}
  \\&= \operatornamewithlimits{\vphantom{arg\,}min}_{a' \in \mathcal{A}} r(a', \sigma(a'))
    &\text{(by definition of $a$)}
  \\&\leq \operatornamewithlimits{\vphantom{arg\,}min}_{a' \in \mathcal{A}} \operatornamewithlimits{\vphantom{arg\,}max}_{s' \in \mathcal{S}} r(a', s').
    &\text{(by definition of max, min)}
  \end{align*}$$ This suffices to prove the minimax(1) condition: $$
    a \in \operatornamewithlimits{arg\,min}_{a' \in \mathcal{A}} \operatornamewithlimits{\vphantom{arg\,}max}_{s' \in \mathcal{S}} r(a', s').
    \tag*{$\square$}
  $$

The final step is a little more subtle than previous invocations of the
definitions of max and min. We're using the fact that
$\operatornamewithlimits{\vphantom{arg\,}max}_{s' \in \mathcal{S}} r(a', s') \geq r(a', \sigma(a'))$
*for all $a' \in \mathcal{A}$, simultaneously.* Increasing the operand
of the minimum everywhere may change the minimising argument, but it
can't decrease the value of the minimum. Note, again, that we actually
have an equality here by definition of $\sigma$. However, we can get
away with only an inequality, which should pay off in the approximate
case.

### Equivalence of minimax(2) and minimax(3$\sigma$)

It follows from propositions 1, 2, 3, and 4 that minimax(2) and
minimax(3$\sigma$) are also equivalent (for any $\sigma$, when an
equilibrium exists). So, we are done!

However, when it comes time to relax these definitions into approximate
versions, following each of these equivalence proofs will involve
introducing approximation errors as we go. The best results will come
from the most direct relationship between the definitions, in particular
using each approximation condition as few times as possible. Therefore,
it is also of interest to write out the direct proofs that minimax(2)
and minimax(3$\sigma$) are equivalent, to make sure there is no
redundancy in the argument.

Let's complete the picture by studying the relationship between these
conditions directly, starting by proving that minimax(3$\sigma$) implies
minimax(2):

**Proposition 5:** *Let $\sigma: \mathcal{A}\to \mathcal{S}$ be any max
map. Suppose there exists some $a' \in \mathcal{A}$ that is minimax(2).
Let $a \in \mathcal{A}$ be minimax(3$\sigma$). Then $a$ is minimax(2).*

*Proof.* Suppose $a$ is minimax(3$\sigma$). That is to say,
$a \in \operatornamewithlimits{arg\,min}_{a'\in\mathcal{A}} r(a', \sigma(a'))$.
We want to show there exists some $s$ in equilibrium with $a$. Let's
start by taking
$s \in \operatornamewithlimits{arg\,max}_{s' \in \mathcal{S}} \operatornamewithlimits{\vphantom{arg\,}min}_{a \in \mathcal{A}}r(a', s')$.
It follows that $$\begin{align*}
  r(a, s)
    &\geq \operatornamewithlimits{\vphantom{arg\,}min}_{a' \in \mathcal{A}} r(a', s)
    &\text{(by definition of min)}
  \\&= \operatornamewithlimits{\vphantom{arg\,}max}_{s' \in \mathcal{S}} \operatornamewithlimits{\vphantom{arg\,}min}_{a' \in \mathcal{A}} r(a', s')
    &\text{(by definition of $s$)}
  \\&= \operatornamewithlimits{\vphantom{arg\,}min}_{a' \in \mathcal{A}} \operatornamewithlimits{\vphantom{arg\,}max}_{s' \in \mathcal{S}} r(a', s')
    &\text{(by lemma 2)}
  \\&\geq \operatornamewithlimits{\vphantom{arg\,}min}_{a' \in \mathcal{A}} r(a', \sigma(a'))
    &\text{(by definition of max, min)}
  \\&= r(a, \sigma(a))
    &\text{(by definition of $a$)}
  \\&= \operatornamewithlimits{\vphantom{arg\,}max}_{s' \in \mathcal{S}} r(a, s')
    &\text{(by definition of $\sigma$)}
  \\&\geq r(a, s).
    &\text{(by definition of max)}
  \end{align*}$$ Since the first and final terms are equal, all of the
inequalities are equalities. The first and the last give us the two
parts of the minimax(2) definition, $$
    s \in \operatornamewithlimits{arg\,max}_{s'\in\mathcal{S}} r(a, s')
    \quad\text{and}\quad
    a \in \operatornamewithlimits{arg\,min}_{a'\in\mathcal{A}} r(a', s).
  \tag*{$\square$}
  $$

This proof neatly blends together the chains of relations from
propositions 2 and 4. For example, note the two uses of the definition
of max as in the proof of proposition 4 (one on the inside of a min
operator); and note the use of lemma 2 as in proposition 2. Moreover,
there is no obvious redundancy in the argument, since each assumption on
$a$, $s$, or $\sigma$ is used exactly once. Therefore, this proof seems
suitably direct.

Finally, we prove that minimax(2) implies minimax(3$\sigma$).

**Proposition 6:** *Let $\sigma: \mathcal{A}\to \mathcal{S}$ be any max
map. Let $a \in \mathcal{A}$ be minimax(2). Then $a$ is
minimax(3$\sigma$).*

*Proof.* Suppose $a$ is minimax(2). Then there exists
$s \in \mathcal{S}$ such that both
$s \in \operatornamewithlimits{arg\,max}_{s'\in\mathcal{S}} r(a, s')$
and
$a \in \operatornamewithlimits{arg\,min}_{a'\in\mathcal{A}} r(a', s)$.
It follows that $$\begin{align*}
    r(a, \sigma(a))
    &\leq \operatornamewithlimits{\vphantom{arg\,}max}_{s' \in \mathcal{S}} r(a, s')
    &\text{(by definition of max)}
  \\&= r(a, s)
    &\text{(by definition of $s$)}
  \\&= \operatornamewithlimits{\vphantom{arg\,}min}_{a' \in \mathcal{A}} r(a', s)
    &\text{(by definition of $a$)}
  \\&\leq \operatornamewithlimits{\vphantom{arg\,}max}_{s' \in \mathcal{S}} \operatornamewithlimits{\vphantom{arg\,}min}_{a' \in \mathcal{A}} r(a', s')
    &\text{(by definition of max)}
  \\&\leq \operatornamewithlimits{\vphantom{arg\,}min}_{a' \in \mathcal{A}} \operatornamewithlimits{\vphantom{arg\,}max}_{s' \in \mathcal{S}} r(a', s')
    &\text{(by lemma 1)}
  \\&= \operatornamewithlimits{\vphantom{arg\,}min}_{a' \in \mathcal{A}} r(a', \sigma(a')).
    &\text{(by definition of $\sigma$)}
  \end{align*}$$ This suffices to prove the minimax(3$\sigma$)
condition: $$
    a \in \operatornamewithlimits{arg\,min}_{a' \in \mathcal{A}} r(a', \sigma(a')).
    \tag*{$\square$}
  $$

Similarly, this proof is reminiscent of the proofs of propositions 1 and
3. For example, note the use of the max--min inequality. Once again, we
only use each definition once, so it seems suitably direct. We're also
taking the reversed route around the same cycle of terms that arose in
proposition 5.

## Conclusion

Thus, the new definition is equivalent to the old ones after all. As I
said, I think these proofs are pretty neat. Moreover, they're going to
help me define the thing we are actually interested in, which is an
approximate notion of minimax optimisation. Speaking of which, I had
better get back to work on that...

Update: For the approximate case, see [this sequel
note](approximinimax-three-ways).

[^1]: Karim Abdel Sadek noted that definition 3 is reminiscent of a game
    theoretic equilibrium concept from a sequential game, where one can
    consider strategies to be functions that a player would use to
    decide their particular action in any given part of the 'game tree.'

[^2]: Definition 3 also seems conceptually reminiscent of Skolemisation
    from first-order logic, whereby we transform a formula with an
    existential quantifier by introducing a function that maps each
    universally quantified variable to a particular constant, yielding
    an equisatisfiable formula, as in the example $$
    \forall x \exists y P(x, y) \rightsquigarrow \forall x P(x, f(x)).
      $$