[Guest post by Sid Banerjee.]
Divergent Evolution: The formation of new species when populations experience different selective pressures.
While the canonical example is Darwin’s finches, it could apply as well to matching theorists! A notable feature of the first and second workshops at the Simons Institute program on Matching Markets was how researchers in Economics, Operations Research and TCS all share common antecedents (Fulkerson, Gale, Scarf, Shapley, Walras — to name but a few giants invoked regularly), and yet have taken the theory in diverse directions. The workshops helped create a healthy dialogue between the communities, as everyone tries to understand each other’s objectives and techniques.
A more notable aspect of matching theory in recent years has been its impact on the design of real-world marketplaces. Over the two workshops, a mix of speakers from academia and industry covered a host of markets, including payment routing, online advertising, kidney exchange, real-estate, public housing, ride-sharing, long-haul trucking, restaurant reviews, school choice, food-banks and many many others. A common theme that emerged was that online marketplaces, with the support of good algorithm and mechanism designers, are slowly taking over the economy.
And talking of giants of matching theory, another event held in parallel with the program was a celebration of the achievements and contributions of Dick Karp, with Vijay Vazirani giving the inaugural lecture of the Simons Institute Richard M. Karp Distinguished Lecture Series. Vijay’s talk touched on both the above themes, with a sweeping overview of three great threads in matching theory (stable matching, market equilibria, and online matching). He highlighted the critical role of algorithmic thinking in their development, and concluded with a tantalizing 40-year-old open problem connected to finding a polynomial-time algorithm for the Hylland-Zeckhauser market equilibrium. It is an excellent starting point for those interested in the program, or matching markets in general!
Leave a comment