optimization
The certificate of optimality
It is the era when optimization must not only find an answer but prove it is the best. You have solved a linear program and claim a minimum — but how do you convince a skeptic without asking them to re-search the entire space? Construct the dual problem, whose feasible solutions each certify a bound on the primal, and prove strong duality: at the optimum the two meet exactly, so a dual solution is an unforgeable receipt of optimality. Then generalize to the conditions characterizing optimal points in constrained problems. Get it wrong and every optimization result is a claim taken on faith — instead, duality turns a hard search into a proof that nothing better exists, and hands you a second algorithm for free.
Who this problem belongs to
The two figures whose methods fit it best, out of 70 in contention.
Von Neumann's 1928 minimax theorem, the founding result of game theory, proves that in a zero-sum two-player game the maximizing and minimizing players' optimal values coincide, a structural result that is essentially the game-theoretic twin of linear programming duality: his own later work with Dantzig in the late 1940s made the connection between LP and matrix games explicit, showing that solving one is equivalent to solving the other. This gives him direct intellectual paternity over the deep mathematical fact this problem asks to be proven, that a dual solution can certify a primal optimum because the two values meet exactly. He did not himself formalize the specific LP duality theorem in Dantzig's terms, working instead from a game-theoretic angle that reaches the same destination, keeping him just shy of the full mark.
Dantzig, having invented the simplex method in 1947, worked directly with von Neumann shortly afterward, who suggested the duality connection to game theory that Dantzig then formalized into the linear programming duality theorem, showing that every LP has an associated dual problem whose feasible solutions bound the primal's optimal value, and that at optimality the two values coincide exactly. This is precisely the 'unforgeable receipt of optimality' the problem describes, discovered and formalized in Dantzig's own hands as a direct practical response to needing to certify solutions found by simplex without exhaustive search. He is not scored above von Neumann only because the founding minimax insight originated in game theory before Dantzig translated it into linear programming's specific language.
Fought here
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
70 figures are scored on this problem. Draw it in a battle to see where you land.