How to interpret max(min(expression))??

Question

I am reading this paper:

ai.stanford.edu/~ang/papers/icml04-apprentice.pdf

Step 2 of section 3 is to compute an expression of the form max(min(expr)). What does this mean?

I made a simple example of such an expression and am equally puzzled as to how to evaluate it:

$\max_{x \in (-3,5)} \min_{y \in \{-1,1\}} \frac{x-2}{y}$

EDIT: I changed the example problem (-1,1) -> {-1,1}.

Answer 1

Fix $x \in (-3,5)$. Then, solve the problem $f(x) = \min_{y \in (-1,1)} \frac{x-2}{y}$. Then, you have $f(x)$ defined on $(-3,5)$. Now solve $\max_{x \in (-3,5)} f(x)$.

There are various theorems on problems of the sort, known as minimax theorems (such as sion's minimax theorem, von neumann's minimax theorem, etc.)

Answer 2

First take the minimum of $\frac{x-2}{y}$ for $y\in (-1,1)$. Then that 'minimum' is in terms of $x$. Now take the maximum of that 'minimum' for $x\in (-3,5)$. But your example is little bit inappropriate because for instance $\frac{x-2}{y}$ is not defined at $y=0$. However, this is the procedure you have to use.