10
$\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.

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

$\endgroup$
3
$\begingroup$

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

$\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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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