Sunday, October 13, 2019

Matching markets @ Simons Institute are multi-disciplinary

Two recent blog posts at the algorithmic game theory blog Turing's Invisible Hand remark on the multi-disciplinary nature of modern matching theory and market design, which involves economics, computer science, operations research and mathematics...


Matching Markets @ Simons: Driven by Theory, Driving the Economy by robertkleinberg

"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 routingonline advertisingkidney exchangereal-estatepublic housingride-sharinglong-haul truckingrestaurant reviewsschool choicefood-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

Blind Folks and the Evolving Elephant – by Vijay Vazirani

"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."

No comments: