One of my favorite parables ever since childhood was that of the four blind men and the elephant, with each man announcing the local image evoked in his mind’s eye on touching a different part of the elephant. This parable has provided an interesting metaphor even for serious scientific matters, a well-known one being wave-particle duality in physics.
But when it comes to matching markets, the parable has taken an unusual twist, with the proverbial elephant undergoing a metamorphosis of its own! The “blind men’’ in this case are entire disciplines which can lay claim to the field of matching markets. Of course, the obvious one is economics – the founders of this field, namely Gale and Shapley, were mathematical economists and the 2012 Nobel Prize in Economics was awarded to Alvin Roth and Lloyd Shapley for work on these markets.
A key enabler was researchers in systems and networking. Their scientific revolutions of the Internet and mobile computing put matching markets on an exciting, new journey and their systems run these centralized markets on powerful computers.
The discipline of algorithm design has had an umbilical connection to matching markets: At the birth of this field lies the highly sophisticated Gale-Shapley stable matching algorithm (1962), whose pivotal game-theoretic property of incentive compatibility follows as a free gift from polynomial time solvability — it was established two decades after the discovery of the algorithm! Yet most researchers, including those in theoretical computer science, are not aware that algorithm design is also a legitimate claimant to this field. Indeed, the very “engine’’ that runs almost each one of these markets is a sophisticated algorithm chosen from the “gold mine’’ of matching theory! Besides stable matching, this includes maximum matching and online matching and their numerous variants.
Looking back at the huge expansion of matching markets over the last decade-and-a-half, one can see that all three disciplines were faced with numerous challenges: understanding the incentive structure of a new market; finding ways of dealing with terra-bytes of data, and choosing and delivering within milli-seconds the “right’’ ads to show with a user query; and designing an algorithm for the latest variant of online matching. And they all delivered!
The rich and diverse set of research talks given at the recent Simons program on matching markets is proof enough that the elephant is still evolving!
Interesting read! Great to know about the Simons program on matching markets.