Why is max min less than min max?

I couldn’t find a simple proof of this supposedly simple fact after searching online for quite some time. It took me more time than I expected to finally convince myself, hence it seems worthwhile noting the proof.

Statement: Given a function f(x,y)

f: R \times R \longmapsto R

And given subsets S_x and S_y of R

\displaystyle\max_{\substack{x \in S_x}} \min_{\substack{y \in S_y}} f(x,y) \leq \min_{\substack{y \in S_y}} \max_{\substack{x \in S_x}} f(x,y)

Proof: Let

\displaystyle g(x) = \min_{\substack{y \in S_y}} f(x,y)

Thus, for any x, g(x) is the minimum value of f(x,y) over all values of y \in S_y. Also let g_y(x) be the value of y that is associated with that minimum value of f(x,y). Note there can be multiple such values in which case we can pick any one of them, e.g., the smallest.

\displaystyle g_y(x) = argmin_{\substack{y \in S_y}} f(x,y)

This means

\displaystyle \min_{\substack{y \in S_y}} f(x,y) = f(x, g_y(x))

Similarly, define h(x) and h_x(y) to be the maximum value of f(x,y) over all x \in S_x and the value of x that gives that maximum value.

\displaystyle h(y) = \max_{\substack{x \in S_x}} f(x,y)

\displaystyle h_x(y) = argmax_{\substack{x \in S_x}} f(x,y)

This means

\displaystyle \max_{\substack{x \in S_x}} f(x,y) = f(h_x(y), y)

Claim 1: \forall y f(x, g_y(x)) \leq f(x,y)

This follows from the fact that

\displaystyle \min_{\substack{y \in S_y}} f(x,y) = f(x, g_y(x))

Claim 2: \forall x f(x, y) \leq f(h_x(y),y)

Again, this follows from the fact that

\displaystyle \max_{\substack{x \in S_x}} f(x,y) = f(h_x(y), y)

Claim 3: \forall x \forall y f(x, g_y(x)) \leq f(h_x(y),y)

Given any x and y, by claim 1

f(x, g_y(x)) \leq f(x,y)

And by claim 2

f(x, y) \leq f(h_x(y),y)

Thus, by claim 3

\displaystyle\max_{\substack{x \in S_x}} f(x, g_y(x)) \leq \min_{\substack{y \in S_y}} f(h_x(y),y)

The picture below is purely for illustration and might help visualize the proof of claim 3.

min-max

Advertisements

Hello world!

Welcome to WordPress.com. After you read this, you should delete and write your own post, with a new title above. Or hit Add New on the left (of the admin dashboard) to start a fresh post.

Here are some suggestions for your first post.

  1. You can find new ideas for what to blog about by reading the Daily Post.
  2. Add PressThis to your browser. It creates a new blog post for you about any interesting  page you read on the web.
  3. Make some changes to this page, and then hit preview on the right. You can always preview any post or edit it before you share it to the world.