Grant: Discovery Grants Program - Individual

Markets are institutions that facilitate the exchange of goods and services via binding contracts; they thus run according to rules. Sometimes these rules arise organically. This can work well when buyers and sellers have little trouble finding each other, when it's not very important who does the buying and selling, and when the market produces simple contracts (e.g., “I'll sell you this can of Coke for $2”). Otherwise, it can be harder for markets to determine effective rules (e.g., to produce contracts like “I'll rent you my spare room tomorrow for $60, but you have to be quiet after 11 PM”). ******When effective markets do not arise organically, rules can instead be crafted explicitly, an idea championed by the fields of market design and mechanism design (recognized by Nobel prizes in 2012 and 2007 respectively). The goal is to prove that a market achieves desirable outcomes (e.g., matching up buyers and sellers who gain the most by trading) under the constraints imposed by a problem and under reasonable assumptions about the behaviour of participants. These assumptions are typically game theoretic: roughly, that participants are fully informed about how a market works and act “rationally” within it to best serve their interests. This is a powerful approach; it has yielded both elegant, general theory and deeply impactful applications as varied as search-engine keyword auctions and kidney exchanges. It has also had a profound impact on artificial intelligence, providing practical, theoretically grounded techniques for addressing longstanding challenges like information fusion and task allocation in multiagent systems.******This approach has a critical flaw, which is more egregious in 2016 than it was when the field's foundations were being laid in the mid-1900s. This flaw is that market design is almost entirely an analytic (i.e., mathematical) exercise: once one has committed to a game theoretic model of the world, there is little room left for responsiveness to real-world observations. In contrast, computer science is currently undergoing a data science revolution: we now think of computer systems not as static artefacts, but as evolving services that remember user interactions and adapt to them. It is becoming a truism that the more data one has about user interactions with a system (a self-driving car; a speech recognition system; a search engine) the better it should work.******The proposed research will help market design to become part of this paradigm shift, enabling markets to draw jointly on actual interactions with users and on game theoretic analysis. More specifically, it will develop data-sensitive techniques for modeling human behavior in markets, building heuristic clearing algorithms, and analyzing adaptive mechanisms. The result will be market designs that can be optimized to different settings and that can adapt after being deployed, just like other modern computer systems.