People of ACM - Nicole Immorlica

July 2, 2019

The Microsoft Research New England Lab, which includes 30 full-time researchers and postdocs, has a strong research focus on economics and computer science (EConCS). Why is EconCS so important to the future of industry?

EconCS is the fundamental core of any tech industry—econ because it predicts how humans (or businesses or countries) may interact in a marketplace, and CS because computing increasingly forms the basis of those interactions. At Microsoft, the tools of EconCS provide guidance to product teams designing everything from the advertisement auctions that monetize Bing to the Azure cloud pricing schemes, to marketing games on Xbox—all groups I’ve interacted with. Our various product teams seek advice about how changes to their pricing or product targeting algorithms will impact sales and adoption. We answer these questions by forming mathematical models of customer behavior based on the assumption that rational agents act to maximize their own benefit, and then design algorithms that optimize Microsoft’s objectives subject to these behavior assumptions.

More broadly, EconCS can inform the deep issues of our time that impact not just industry, but our entire social structure. These issues include questions about data, ethics, and identity. The data individuals generate as they navigate their lives has incredible economic value. It fuels much of the machine learning systems we hear so much about these days. In exploring incentives, those in our field ask questions such as, “How can we reward individuals for the data they produce, and how does this impact what data they reveal?” Relatedly, the ways we use this data can have extreme implications for privacy and fairness, the latter of which particularly interests me. Naïve uses of data can systematically discriminate against certain minority groups, even, or perhaps especially so, if policy makers try to combat this with blanket restrictions on data use. Finally, identity is the fundamental unit we use to interact with one-another, but we increasingly rely on centralized agencies to grant and verify our identities. This is driven, in part, by our global-sized societies and online presence. But research shows we are, nonetheless, quite connected. Famously, any two people can be reached within 6 hops in the world social network. Intriguing questions arise including “Can we leverage what we know about our friends to create a global decentralized identity scheme based on asking and answering questions about each other in this world social network?”

In your 2013 paper “Incentives in Large Random Two-Sided Markets,” which you co-authored with Mohammad Mahdian, you explored the matching paradigm in two-sided markets, such as the National Residency Matching Program (NRMP), which matches medical students to hospitals. What was a key insight from this paper that may be applied to other research in algorithmic game theory?

Centralized labor markets, use the famous Gale-Shapley stable marriage algorithm to match workers to firms. The match produced by this algorithm is stable in the sense that no worker/firm pair prefer each other to their assigned matches. Despite this appealing property of the output, famous results show that the algorithm suffers from an input problem: one side of the market has incentives to try and manipulate their stated preferences in order to improve their match. In extreme cases, such manipulations can improve the match of a participant from a least preferred to a most preferred option.

But markets aren’t arbitrary mathematical objects. They exhibit a lot of structure. They also tend to be large,. And there’s often a lot of random perturbations in agent preferences. Furthermore, for centralized labor markets like the NRMP, one side of the market tends to have very short preferences. Medical residents, for instance, apply to 10-12 hospitals despite there being tens of thousands of openings. Our work showed that under these conditions the stable matching mechanism used by these markets incentivizes truthful reporting of preferences. Since its initial publication in the ACM Symposium on Discrete Algorithms (SODA) in 2005, this work spawned a long line of literature in the market design community identifying and quantifying large market conditions under which standard mechanisms perform well. In corporate settings, these works provide a convincing argument for batching sales (e.g., of online advertisements) to create a large market condition, and then introducing small perturbations to smooth the market.

What was the central idea of your 2018 plenary talk at the International Joint Conference on Artificial Intelligence (IJCAI), "Maximizing the Social Good: Markets without Money"?

To create a truly sustainable world, we need to generate ample resources and allocate them appropriately. In traditional economics, these goals are achieved using money; by charging people appropriately, we can guarantee they value the resources they receive more than anyone else. However, in many settings of social significance, monetary transactions are infeasible, be it due to ethical considerations or technological constraints. In this talk, I discussed alternatives to money, including risk, social status, and scarcity, and showed how to use these tools to achieve socially-optimal outcomes. Risk helps determine a person's value for a resource: the more someone is willing to risk for something, the more they value it. Using this insight, my co-authors and I propose an algorithm to find a good assignment of students in school choice programs. Social status helps motivate people to contribute to a public project. Using this insight, my co-authors and I design badges to maximize contributions to user-generated content websites. Scarcity forces people to evaluate trade-offs, allowing algorithms to infer the relative strength of their preference for different options. Using this insight, my co-authors and I design voting schemes that select the most highly-valued alternative.

As the incoming Chair of SIGecom, how would you like to see the group grow?

The SIGecom community is my academic family, and I am passionate about helping it grow. One particularly unique aspect of this SIG is its interdisciplinarity. Our community consists of computer scientists from disparate fields like theory, AI and ML. Recently, we have experienced increasing participation from other fields as well. Empirical and theoretical economists have long been a part of our community, and traditionally co-chair our flagship conference, EC, along with a computer scientist. For the past three or four ECs, a core group of young economists has made EC one of their annual commitments. One of them—Scott Duke Kominers, an economics professor at Harvard Business School—is an incoming Vice Chair of SIGecom. We also have seen an influx of researchers from the operations research community.

I chaired EC this year, and my co-chair, Ramesh Johari, is a professor in the Management Science and Engineering Department at Stanford University as well as Area Co-Editor of the Revenue Management and Market Analytics Area for the journal Operations Research. Together, he and I worked to strengthen participation of researchers from economics and operations research in EC. We added a track, Applied Modeling, to the existing conference tracks (AI, Empirics, and Theory) which we felt would appeal to that research community. To celebrate this horizontal differentiation, we introduced new track awards recognizing best papers in each of these conference tracks. We also solicited contributors to influential economics journals to participate in the new EC forward-to-journal option. We reached out to journals including Games and Economic Behavior, Journal of Economic Theory, Management Science, Mathematics of Operations Research, and Operations Research. These efforts paid off: the EC conference had a 40% increase in submissions and an even larger increase in attendance, and the diversity of researchers was reflected in the diverse program. In my role as SIGecom Chair, I hope to institutionalize some of the structures that foster interdisciplinarity in EC. My first effort will be to create an ACM-recognized award structure that recognizes papers in each track.

I also want to make sure the SIG highlights the real-world impact of our community. The SIG, originally named the ACM Special Interest Group on eCommerce, has a history of real-world impact on ad auctions and other ecommerce platforms. We recently changed our name to the ACM Special Interest Group on Economics and Computation to emphasize our expanding theoretical and applied interests. Our members are now foundational in designing markets from ridesharing to cryptocurrencies to school choice and kidney exchange. The Applied Modeling track at EC gives these projects a voice within the community. I would like to find platforms, such as Communications of the ACM, to help broadcast this success to the public.