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) ?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
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

Improve this answer
$\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
    Commented 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$
    – Seyhmus Güngören
    Commented 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
    Commented 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.

Improve this answer
$\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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .