[The following guest post was written by Vijay Vazirani.]
What the cutting locust left, the swarming locust has eaten. What the swarming locust left, the hopping locust has eaten, and what the hopping locust left, the destroying locust has eaten.
Joel 1:4
A few years ago, while attending a Dagstuhl program on Equilibrium Computation, I embarked on one of the traditional long hikes through the beautiful woods surrounding Schloss Dagstuhl and happened to be walking next to a senior member of the Operations Research community. In no time we got immersed in a lively discussion on the style of research going on in Algorithmic Game Theory. We both agreed that the progress made in a matter of a few years was nothing short of phenomenal. At this point, my colleague remarked that AGT was no exception and that when TCS researchers enter a new area, they go in with such energies and enthusiasm that in no time not only is all low hanging fruit gone but in fact the entire area is devoid of any reasonable open problems! “They attack the area like swarms of locusts devouring foliage in biblical lands, consuming not only fruit and leaves but even shrubs and twigs,” he added. “Yes, and only sh*t is left behind!” I chimed in.
As AGT is reaching that stage, with researchers yearning for new issues/problems for their students and their own research and grant proposals, there is a reprieve emerging on the horizon: a program at Simons on “Online and Matching-Based Market Design” in Fall 2019.
This is by no means a new area. In fact, the first such market, for matching medical residents to hospitals, dates back to 1920s, well before the classic — and by now Nobel Prize winning — work of Gale and Shapley on the stable matching problem, which provided the canonical algorithm for this market. In recent years, the advent of the Internet and the relocation of our most important activities to online platforms have led to an explosion of such marketplaces (for examples, see the Simons web page) and they have been occupying an ever-increasing fraction of our economy.
AGT, CS and Economics have already had a massive impact via these markets. My own experience comes from Google’s multi-billion dollar Adwords market in which sophisticated algorithmic ideas have also played a central role, e.g., see the Simons talk “Google’s AdWords Market: How Theory Influenced Practice“.
Clearly, the stakes are high. There is a real opportunity of extending the already existing highly inter-disciplinary theory in substantial ways and making an even bigger impact. Considering this and the enthusiasm of the researchers who have agreed to be participants in this program, Federico Echenique, Nicole Immorlica and I have launched the project of publishing a comprehensive volume of contributed chapters on this topic. More information on this will be coming soon.
Turing's Invisible Hand 