4
$\begingroup$

A minimax theorem is a theorem which states that under certain conditions on $\mathcal{X}$, $\mathcal{Y}$ and $f$: $$ \inf_{x \in \mathcal{X}}{\sup_{y \in \mathcal{Y}}{f(x,y)}} = \sup_{y \in \mathcal{Y}}{\inf_{x \in \mathcal{X}}{f(x,y)}}$$ All minimax theorems rely strongly on convexity: the sets $\mathcal{X}$ and $\mathcal{Y}$ are usually required to be convex subsets of vector spaces, and $f$ to be convex-concave.

My question is: of course one cannot expect much without some convexity, but is it possible to get rid of the convexity of the domain in any way?

For example, consider the simplest minimax problem: $\mathcal{X}$ is a subset of $\mathbb{R}^n$, $\mathcal{Y}$ a convex subset of $\mathbb{R}^n$ and $f(x,y) = \langle x,y \rangle$ is the usual scalar product.

Are there any minimax results in this setting (with of course additional assumptions on $\mathcal{X}$ or $\mathcal{Y}$, but $\mathcal{X}$ should not be assumed to be convex) ?

$\endgroup$

3 Answers 3

5
$\begingroup$

The weakest condition that I know is the quasi-convexity or quasi-concavity of the domain. Eventually the topology should accept a saddle point and without any convexity argument I am not sure if there exists a single point having this property. You might want to see for example:

the paper

$\endgroup$
3
  • $\begingroup$ I know what a quasi-convex function is, but I have never heard about quasi-convex sets. Can you explain what it is? $\endgroup$
    – Adrien
    Jan 26, 2014 at 2:08
  • $\begingroup$ I wrote it only as the set of quasi-convex functions without having further knowledge. However I came across with the following link.springer.com/chapter/10.1007/978-90-481-2785-6_6 $\endgroup$ Jan 26, 2014 at 2:31
  • $\begingroup$ I don't understand. You said "quasi convexity of the domain", so are you really speaking about the domain $\mathcal{X}$ (which is my question) or about the function $f$ (which is not really the point here) ? $\endgroup$
    – Adrien
    Jan 26, 2014 at 2:53
4
$\begingroup$

The situation were your objective $f(x,y)=x^T A y$ is bilinear corresponds to the case of zero-sum games (http://www.inf.ed.ac.uk/teaching/courses/agta/lec4.pdf). If you remove the convexity assumption in this framework, existence of equilibria is not guaranteed anymore. For instance, if you restrict your variables x, y to be integral then generally there is no equilibrium for the zero-sum game (and this is precisely the motivation for mixed strategies in Von Neumann's Theorem).

As in the previous answer, quasi-convexity and weaker forms of continuity (e.g., lower semicontinuity in the variables where the function is convex) still can guarantee existence. You can even remove compactness on one of the domains and still obtain it, but I don't think you can go much beyond that.

$\endgroup$
0
$\begingroup$

There are minimax theorems that replaces convexity by acyclicity and contractibility assumptions in:

McClendon, J. F. "Minimax theorems for ANRs." Proceedings of the American Mathematical Society 90.1 (1984): 149-154.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.