# $\max_{y} \min_{x} f(x,y)$ as motif for exploring mathematics

It's been several years since my undergraduate math days, and I would like to spend a bit of time refreshing and then tackling a few things I never completely mastered.

Rather than proceeding topic by topic (e.g. analysis, algebra, topology, etc) I wanted to choose a motif to keep as a frame of reference -- that way, for example, when I return to diff. geom. I can ask questions about what that topic has to say about my particular motif and hopefully not get completely lost in all the abstraction.

I've chosen a particular motif, and was hoping people could comment on whether this motif seems general and interesting enough that the major branches and theorems of math might have something to conclude about this topic, and furthermore, I would be extremely grateful if people could suggest various little puzzles around this motif that would eventually tie in to the various deep theorems.

The motif I am interested in exploring is the relationship between $\displaystyle\max_{y} \min_{x} f(x,y)$ and $\displaystyle \min_{x} \max_{y} f(x,y)$

I like this motif because 1) it feels like a lot of interesting real word problems involve mins of maxes or vice versa, and 2) it just seems really easy to pose interesting questions about this topic. For example:

under what conditions of f does
$\displaystyle\max_{y} \min_{x} f(x,y) = \min_{x} \max_{y} f(x,y)$

Assuming $f \in C^{\infty}$ or $f$ is convex, etc, what kinds of bounds can we place on $\displaystyle\max_{y} \min_{x} f(x,y) - \min_{x} \max_{y} f(x,y)$ in some compact, convex, etc region $A$?

Thinking a f(x,y) as a discrete, lookup table (i.e. matrix) with random iid entries, what can we say about the probability distribution of $\displaystyle\max_{y} \min_{x} f(x,y) - \min_{x} \max_{y} f(x,y)$

The above questions are not meant to be deep issues for professionals, but more at the level of textbook exercises. Currently they feel mostly linked to analysis with maybe a small touch of topology, but my intuition feels like I could keep going and find things that would feel like algebra, certainly geometry, and so forth. What do people think? -- is there enough meat here, or is this motif too trivial in a way that I'm not really seeing (of course, I imagine there is a reasonable chance that the entire methodology will seem confusing -- my apologies)

• I interpret your expression as $\max_y(\min_x f(x,y))$. Am I wrong to do so? If that is the interpretation, then what would $\min_x f(x,y)$ mean? Each $x$-value provides you with a function of $y$. How are you comparing these functions to pick the minimal one? – alex.jordan Jan 26 '12 at 18:48
• hi -- your parenthesis are correct. but $min_x f(x,y)$ leaves you with a function in y e.g. $min_x x^2/2-xy = -y^2/2$. Then following with $max_y$ leaves you with an expression free of both x and y. Show for $f(x,y) = x^2/2-xy$, $max_y, min_x f(x,y) = 0$ but – lilinjn Jan 27 '12 at 1:43
• sorry -- stack exchange timed out my last comment -- it should have ended with: So for $f(x,y)=x^2/2−xy$, $\max_y \min_x f(x,y)=0$ – lilinjn Jan 27 '12 at 1:59
• It seems like you computed $\min_x(x^2/2-xy)$ by letting $x=y$. Does that mean that you are letting $x$ range over functions of $y$ rather than over real numbers? In any case, how will you generally compare two functions of $y$? Your example provides a choice $x=y$ that yields $-y^2/2$ which is always less than $f(y)^2/2-f(y)y$. But most similar expressions won't have any meaning. For example, $\min_x(xy)$ - what will that mean? – alex.jordan Jan 27 '12 at 6:12
• $min_x(xy) = -\infty$ for $y \neq 0$ and 0 for $y=0$, or if the domain was restricted to a square centered around $(0,0)$ with side length d, the $min_x (x y)$ would be $-d/2*abs(y)$ – lilinjn Jan 27 '12 at 13:44