posted by Rakesh Vohra, 17 November 2015
Herbert Scarf, one of the towering figures of the field, passed away on November 15th, 2015. Like John Nash and Harold Kuhn he was a member of that cohort that was to revolutionize Economics and Operations Research. Scarf himself left a lasting mark in Economic Theory, Mathematical Programming, Operations Research and Game Theory. In many ways he was ahead of his time in working on problems at the intersection of Game Theory and Algorithms.
Scarf’s interest in algorithms was long standing. The title of his magnum opus: `The Computation of Economic Equilibria’ said as much. His interest in the problem of indivisibilities led to a sequence of papers in integer programming that introduced the notion of neighborhood systems. This anticipated the use of Groebner basis in integer programming.
The lemma that bears his name, has, in the last decade found many applications in combinatorics and computer science. That lemma showed that balancedness was a sufficient condition for non-emptiness of the core of a NTU game. It has received renewed attention as a powerful tool for proving a host of combinatorial results. In fact, it has been used recently to establish stability properties of a stylized version of the border gateway protocol (BGP). The BGP is the dominant interdomain routing protocol used to exchange routing information on the internet today.
He departs leaving us richer than we were before.