From the Inside: Online and Matching-Based Market Design

by Sid Banerjee

...and then with sudden excitement...he had started to think. He had thought about ways to distinguish between better answers and worse answers to questions which had no right answer. He had seen a method which could do what the detective work of conventional algebra could not, in situations like the one the Plywood Trust described, and would trick impossibility into disclosing useful knowledge. The method depended on measuring each machine's output of one plywood in terms of all the other plywoods it could have made. But again, he had no sense of plywood as a scratchy concrete stuff. That had faded into nothing, leaving only the pure pattern of the situation, of all situations in which you had to choose one action over another action.

         From Red Plenty, by Francis Spufford (2010)

Red Plenty is a work of historical fiction by Francis Spufford, chronicling the birth and dissolution of the planned economy in the Soviet Union. In its opening chapter, the author imagines a moment in 1938 when the Russian mathematician Leonid Kantorovich first hits upon the idea of “designing a market” via linear programming (LP). While the modern theory of LP duality needed to wait another decade for a meeting between George Dantzig and John von Neumann, one can trace back to this moment the birth of three academic disciplines: theoretical computer science (TCS), operations research (OR), and modern microeconomics.

Despite this shared origin, in the years that have followed, the three fields have developed along parallel yet disjoint paths — focusing on different problems and objectives, developing different techniques, and evolving different vocabularies. But recent years have witnessed a remarkable convergence of the disciplines, spurred by the rise of modern online marketplaces that promise new proving grounds for the theory. The Simons Institute Fall 2019 program on Online and Matching-Based Market Design both acknowledged and accelerated this convergence. One imagines that Kantorovich would have heartily approved!

The basic market design problem can be summarized as follows: given a set of resources and a set of agents with different preferences for different bundles of these resources, how should one allocate the resources among the agents? This simple question, however, conceals a vast universe of possibilities. Uncovering the private utility of an agent requires reasoning about how agents behave under different market mechanisms — this is the core topic of microeconomics. Considering different sets of feasible allocations (for example, divisible versus indivisible resources) and different objectives leads to problems of vastly different computational natures — understanding these trade-offs lies at the heart of modern TCS. Going beyond simple models to more realistic markets requires reasoning about decision-making under stochastic uncertainty, temporal dynamics, and other practical constraints — these are the main concerns of the OR researcher. Finally, to translate research into practice in any real marketplace requires combining all these approaches.

The program’s three workshops reflected this theme of myriad domains drawing from a common theory wellspring. The invited speakers talked about a wide range of topics: online ad auctions and online review aggregators; ride-sharing and networked logistics; real estate markets and public housing allocation; school choice and food banks. The first workshop, on Matching and Objectives, helped provide a broad overview of different models and problems in matching markets. At just over six weeks in duration, Online and Matching-Based Market Design was a shorter-than-usual research program for the Simons Institute. Given this compressed format, the organizers eschewed the standard boot camp and instead invited researchers from a wide variety of academic disciplines and application domains to describe the state of the art and open problems in each area at the first workshop. The second workshop went deeper into the details of modern platform markets, with a collection of success stories of matching theory being applied in these markets. Finally, the third workshop focused on the links between market design and data science — and in particular on the role of information collection and revelation in influencing market outcomes.

The interaction among TCS, OR, and economics was central to all the events in the program. The overall organizing committee, as well as the organizers of each workshop, comprised a mix of researchers across the different disciplines, and each session had a mix of speakers from different backgrounds. The resulting effect was like a cubist painting, with different facets of the same topic stacked together but resolving into a more coherent theme when one stepped back and viewed them as a whole. The talks all drew on common theoretical foundations — everyone knew their Edmonds, Fulkerson, Gale, Scarf, Shapley, Walras (to name but a few names quoted regularly). However, each community has taken the field in very different directions, and most of the talks involved a dialogue between the speaker and the audience as everyone tried to understand each other’s objectives and techniques. We all had a lot to learn, and I, for one, learned a lot!

Two themes that emerged across the talks were how modern markets are driving the modern economy and, more importantly, how they are being driven by academic research. This was perhaps best expressed by Vijay Vazirani, who gave the inaugural lecture in a series dedicated to the other giant of matching theory, Dick Karp. In the space of an hour, Vijay gave a sweeping overview of three beautiful theoretical ideas in modern matching theory — stable matching, market equilibrium computation, and online matching — and highlighted the amazing role that algorithms have played in this story. His talk also highlighted the two great success stories of this theory — matching markets for schools and medical residencies, and the adwords auction — and provided a sneak peek into the role it will play in shaping future marketplaces. The lecture served as a good starting point before jumping into the many other talks in the program.

 

 

 

Related articles

Related stories

,