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$
4
$\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$
  • $\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 '14 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 Jan 26 '14 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 '14 at 2:53
3
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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