13
$\begingroup$

The max flow-min 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.

Improve this question
$\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. Winter
    Commented Jan 10, 2019 at 21:24
  • 1
    $\begingroup$ mathoverflow.net/q/252206/12674 looks relevant. $\endgroup$
    – Thomas Kalinowski
    Commented Jan 11, 2019 at 2:04

3 Answers 3

Reset to default
5
$\begingroup$

To elaborate on M. Winter's comment: Von Neumann's minimax theorem for two-person zero-sum games can be thought of as a consequence of LP duality, although his first proof of the theorem did not make this connection explicit.

Improve this answer
$\endgroup$
3
$\begingroup$

Kőnig's theorem and Hall's marriage theorem are famous and follow from LP duality (together with an integrality argument).

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

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