The max flowmin cut theorem is one of the most famous theorems of discrete optimization, although it is very straightforward to prove using duality theory from linear programming. Are there any other examples of famous theorems that are also corollaries of LP duality, or duality of convex optimization? The Farkas lemma and the hyperplane separation theorem would be other candidates, although they look more like equivalent statements to me.
$\begingroup$
$\endgroup$
2

$\begingroup$ The existence of Nash equilibria for matrix games with probabilistic strategies came to my mind, but I don't think there is a famous theorem behind this. $\endgroup$– M. WinterCommented Jan 10, 2019 at 21:24

1$\begingroup$ mathoverflow.net/q/252206/12674 looks relevant. $\endgroup$– Thomas KalinowskiCommented Jan 11, 2019 at 2:04
Add a comment

3 Answers
$\begingroup$
$\endgroup$
To elaborate on M. Winter's comment: Von Neumann's minimax theorem for twoperson zerosum games can be thought of as a consequence of LP duality, although his first proof of the theorem did not make this connection explicit.
$\begingroup$
$\endgroup$
Kőnig's theorem and Hall's marriage theorem are famous and follow from LP duality (together with an integrality argument).
$\begingroup$
$\endgroup$
Bondareva–Shapley_theorem is quite famous in a game theory. In more modern terms, it unites the usual and dual description of the generalized permutohedron.