Microsoft Research Podcast - Ideas: Economics and computation with Nicole Immorlica

Episode Date: December 5, 2024

When Senior Principal Research Manager Nicole Immorlica discovered she could use math to make the world a better place for people, she was all in. She discusses working in computer science theory and economics, including studying the impact of algorithms and AI on markets. 

So honestly, when Generative AI came out, I had a bit of a moment, a crisis of confidence, so to speak, in the value of theory and my own work. And I decided to dive into a data-driven project, which was not my background at all. As a complete newbie, I was quite shocked by what I found, which is probably common knowledge among experts. data is very messy and very noisy. And it's very hard to get any signal out of it. Theory is an essential counterpart to any data-driven research. It provides a guiding light.

But even more importantly, theory allows us to illuminate things that have not even happened. So with models, we can hypothesize about possible futures and use that to shape what direction we take. You're listening to Ideas, a Microsoft Research podcast that dives deep into the world of technology research and the profound questions behind the code. I'm Gretchen Huizenga. In this series, we'll explore the technologies that are shaping our future and the big ideas

that propel them forward. My guest on this episode is Nicole Imorlica, a senior principal research manager at Microsoft Research New England, where she leads the economics and computation group. Considered by many to be an expert on social networks, matching markets, and mechanism design, Nicole has a long list of accomplishments and honors to her name and some pretty cool new research besides. Nicole Imorlica, I'm excited to get into all the things with you today.

Welcome to Ideas. Thank you. So before we get into specifics on the big ideas behind your work, let's find out a little bit about how and why you started doing it. Tell us your research origin story, and if there was one, what big idea or animating what-if inspired young Nicole and launched a career in theoretical economics and computation research? So I took a rather circuitous route to my current research path. In high school, I thought I actually wanted to study physics, specifically cosmology, because I was super curious about the origins and evolution of the universe.

In college, I realized on a day-to-day basis what I really enjoyed was the math underlying physics, in particular, proving theorems. So I changed my major to computer science, enjoyed was the math underlying physics, in particular, proving theorems. So I changed my major to computer science, which was the closest thing to math that seemed to have a promising career path. But when graduation came, I just wasn't ready to be a grown-up and enter the workforce. So I defaulted to graduate school, thinking I'd continue my studies in theoretical computer science. It was in graduate school where I found my passion for the intersection of CS theory and microeconomics. I was just really enthralled with this idea that I could use the math that I so love to understand society and to help shape it in ways that improve the world for everyone in it. I've yet to meet an accomplished researcher who didn't have at least one inspirational who behind the what.

So tell us about the influential people in your life. Who are your heroes, economic or otherwise? And how did their ideas inspire yours and even inform your career? Yeah, of course. So when I was a graduate student at MIT, you know, I was happily enjoying my math. And just on a whim, I decided to take a course along with a bunch of my other MIT graduate students at Harvard from Professor Al Roth. And this was a market design course. We didn't even really know what market design was. But in the context of that course, Al himself

and the course content just demonstrated to me the transformative power of algorithms and economics. So, I mean, you might have heard of Al. He eventually won a Nobel Prize in economics for his work using a famous matching algorithm to optimize markets for doctors and separately for kidney exchange programs. And I thought to myself, wow, this is such meaningful work. This is something that I want to do, something I can contribute to the world, something that my skill set is well adapted to. And so I just decided to move on with that. And I've never really looked back. It's so satisfying to do something that's both, I like both the means and I care very deeply about the end. Nicole, you mentioned you took a course from Al Roth. Did he become anything more to you than

that one inspirational teacher? Did you have any interaction with him? And were there any other professors, authors, or people that inspired you in the coursework and graduate studies side of things? I and many of the graduate students in my area have continued to work with him, speak to him at conferences, be influenced by him. So he's been there throughout my career for me. In terms of other inspirations, I've really admired throughout my career. This is maybe more structurally how different individuals operate their careers. So, for example, Jennifer Chase, who was the leader of the Microsoft Research Lab that I joined, and nowadays Sue Dumais, various other classic figures like Eva Tardos. these are incredibly strong, driven women that have a vision of research, which has been transformative in their individual fields, but also care very deeply about the community and the larger context than just themselves and creating spaces for people to really flourish. And I really admire that as well. Yeah, I've had both Sue and Jennifer on the show before, and they are amazing. Absolutely. Well, listen, Nicole, as an English major,

I was thrilled and a little surprised to hear that literature has influenced your work in economics. I did not have that on my bingo card. Tell us about your interactions with literature and how they broadened your vision of optimization and economic models. Oh, I read a lot, especially fiction, and I care very deeply about being a broad human being, like with a lot of different facets. And so I seek inspiration not just from my fellow economists and computer scientists, but also from artists and writers. One specific example would be Walt Whitman. So I took this poetry class as an MIT alumni, Walt Whitman. And we, in the context of that course, of course, read his famous poem, Song of Myself. And I remember one specific verse just really struck me where he writes,

do I contradict myself? Very well then, I contradict myself. I am large. I contain multitudes. And this just was so powerful because, you know, in traditional computer scientist, as an economist. And maybe we should actually try to think a little bit more seriously about these multiple identities in the context of our modeling. That just warms my English major heart. I'm glad. Oh my gosh. And it's so interesting because, yeah, we always think of sort of singular optimization.

And so it's like, how do we expand our horizon on that sort of optimization vision? So I love that. Well, you've received what I can only call a flurry of honors and awards last year. Most recently, you were named an ACM Fellow, ACM being Association for Computing Machinery, for those who don't know, which acknowledges people who bring, and I quote, transformative contributions to computing science and technology. Now your citation is for, and I quote again, contributions to economics and

computation, including market design auctions and social networks. That's a mouthful. But if we're talking about transformative contributions, how were things different before you brought your ideas to this field? And how are your contributions transformative or groundbreaking? Yeah, so it's actually a relatively new thing for computer scientists to study economics. And I was among the first cohort to do so seriously. So before our time, economists mostly focused on finding optimal solutions to the problems they posed without regard for the computational or informational requirements therein. But computer scientists have an extensive toolkit to manage such complexities. So, for example, in a paper on pricing, which is a classic economic problem,

how do we set up prices for goods in a store, my co-authors and I used the computer science notion of approximation to show that a very simple menu of prices generates almost optimal revenue for the seller. And prior to this work, economists only knew how to characterize optimal but infinitely large and thereby impractical menus of prices. So this is an example of the kind of work that I and other computer scientists do that can really transform economics. or SIGECOM recognizes influential papers published between 10 and 25 years ago that

significantly impacted research or applications in economics and computation. Now, you got this award for a paper you co-wrote in 2005 called Marriage, Honesty, and Stability. Clearly, I'm not an economist because I thought this was about how to avoid getting a divorce, but actually it's about a well-known and very difficult problem called the stable marriage problem. Tell us about this problem and the paper and why, as the award states, it stood the test of time. Sure.

You're not the only one to have misinterpreted the title. I remember I gave a talk once and someone came and when they left the talk, they said, I did not think that this was about math. But, you know, math, as I learned, is about life. And the stable marriage problem has, you know, an interpretation about marriage and divorce. how can we match market participants to one another such that no pair prefer each other to their assigned match? So to relate this to the somewhat outdated application of marriage markets, the market participants could be men and women. And the stable marriage problem asks if there's a set of marriages such that no pair of couples seeks a divorce in order to marry each other. And so, you know, that's not really a problem we solve in real life, but there's a lot of modern applications of this problem. For example, assigning medical students to hospitals for their residencies, or if you have children, many cities in the United States

and around the world use this stable marriage problem to think about the assignment of K-12 students to public schools. And so, in these applications, the stability property has been shown to contribute to the longevity of the market. And in the 1960s, David Gale and Lloyd Shapley proved via an algorithm, interestingly, that stable matches exist. Well, in fact, there can be exponentially many stable matches. And so this leads to a very important question for people that want to apply this theory to practice, which is which stable match should they select among the many ones that exist? And what algorithm should they use to

select it? So our work shows that under very natural conditions, namely that preference lists are short and sufficiently random, it doesn't matter. Most participants have a unique stable match. And so, you know, you can just design your market without worrying too much about what algorithm you use or which match you select, because for most people, it doesn't matter. And since our paper, many researchers have followed up on our work, studying conditions under which matchings are essentially unique and thereby influencing policy recommendations. So this work was clearly focused on the economics side of things like markets. So this seems to have wide application outside of economics. Is that accurate? Well, it depends how you define economics. So I would define,

I define economics as the problem. I mean, Al Roth, for example, wrote a book whose title was Who Gets What and Why. So economics is all about how do we allocate stuff? How do we allocate scarce resources? And many economic problems are not about spending money. It's about how do we create outcomes in the world? And so I would say all of these problem domains are economics. of honors, besides being named an ACM Fellow, and also this Test of Time Award, you were also named an Economic Theory Fellow by the Society for Advancement of Economic Theory, or SAET. And the primary qualification here was to have substantially or creatively advanced theoretical economics. So what were the big challenges you tackled and what big ideas did you contribute to advance economic theory? So as we've discussed, I and others with my background have done a lot to advance economic theory through the lens of computational thinking. We've introduced ideas

such as approximation, which we discussed earlier, or machine learning to economic models in proposing them as solution concepts. We've also used computer science tools to solve problems within these models. So two examples from my own work include randomized algorithm analysis and stochastic gradient descent. And importantly, we've introduced very relevant new settings to the field of economics. So, you know, I've worked hard on large scale auction design and associated auto bidding algorithms, for instance, which are a primary source of revenue for tech companies these days. I've thought a lot about how data enters into markets and how we should think about data in the context of market design.

And lately, I've spent a lot of time thinking about generative AI and its impact in the economy Magazine at the time, Chris Anderson. He wrote an article titled The End of Theory, which was provocative in itself. And he began by quoting the British statistician, George Box, who famously said, all models are wrong, but some are useful. And then he argued that in an era of massively abundant data, companies didn't have to settle for wrong models. And then he went even further and attacked the very idea of theory. And citing Google, he set out with every theory of human behavior from linguistics to sociology. Forget taxonomy, ontology, psychology. Who knows why people do what they do?

The point is they do it, and we can track and measure it with unprecedented fidelity. So, Nicole, from your perch 15 years later in the age of generative AI, what did Chris Anderson get right and what did he get wrong? So, honestly, when generative AI came out, I had a bit of a moment, a crisis of confidence, so to speak, in the value of theory in my own work. Really? value of theory in my own work. I decided to dive into a data-driven project, which was not my background at all. As a complete newbie, I was quite shocked by what I found, which is probably common knowledge among experts. Data is very messy and very noisy, and it's very hard to get any signal out of it. Theory is an essential counterpart to any data-driven research. It provides a guiding light. But even more importantly, theory allows us to illuminate things that have

not even happened. So with models, we can hypothesize about possible futures and use that to shape what direction we take. Relatedly, what I think that article got most wrong was the statement that correlation supersedes causation, which is actually how the article closes. This idea that causation is dead or dying. I think causation will never become irrelevant. Causation is what allows us to reason about counterfactuals. It's fundamentally irreplaceable. It's like, you know, data, you can only see data about things that happen. You can't see data about things that could happen, but haven't, or, you know, data, you can only see data about things that happen. You can't see data about things that could happen but haven't or, you know, about alternative futures. And that's what theory gives you. within a series featuring some of the work going on in the AI cognition and the economy initiative at Microsoft Research. And I just did an episode with Brendan Lussier and Mark Demerer on the micro

and macroeconomic impact of generative AI. And you were part of that project. But another fascinating project you're involved in right now looks at the impact of generative AI on what you call the content ecosystem. So what's the problem behind this research and what unique incentive challenges are content creators facing in light of large language and multimodal AI models? Yeah. So this is a project with Brendan as well, you interviewed previously, and also Najeeba Lee, an economist and ACE fellow at Penn State, and Meena Jagadisan, who was my intern from Microsoft Research from UC Berkeley. So when you think about content or really any consumption good, there's often a whole supply

chain that produces it. For music, for example, there's the composition of the song, the recording, the mixing, and finally the delivery to the consumer. And all of these steps involve multiple humans. So, for example, like I could ask a model, an AI model, to compose and play a song about my cat named Whiskey, and it would do a decent job of it, and it would tailor the song to my specific situation. But there are drawbacks as well. One thing many researchers fear is that AI needs human-generated content to train. And so if people start bypassing the supply chain and just using AI-generated content, there won't be any content for AI to train on, and AI will cease to improve.

Another thing that could be troubling is that there are economies of scale. So there is a non-trivial cost to producing music, even for AI. And if we share that cost among many listeners, it becomes more affordable. But if we each access the content ourselves, it's going to impose a large per song cost. And then finally, and this is, I think, most salient to most people, there's some kind of social benefit to having songs that everyone listens to. It provides a common ground for understanding. It's a pillar of our culture, right? And so if we bypass that, aren't we losing something?

So for all of these reasons, it becomes very important to understand the market conditions under which people will choose to bypass supply chains and the associated costs and benefits of this. What we show in this work, which is very much work in progress, is that when AI is very costly, neither producers nor consumers will use it. But as it gets cheaper, at first, it actually helps content producers that can leverage it to augment their own ability, creating higher quality content, more personalized content, more cheaply. But then as the AI gets super cheap, this bypassing behavior starts to emerge and the content creators are driven out of the market. Right. So what do we do about that?

Well, you know, you have to take a stance on whether that's even a good thing or a bad thing. Right. So it could be that we do nothing about it. We could also impose a sort of minimum wage on AI, if you like, to artificially inflate its costs. We could try to amplify the parts of the system that lead towards more human-generated content, like this sociability, the fact that we all are listening to the same stuff. We could try to make that more salient for people. But, you know, generally speaking, I'm not really in a place to take a stance on whether this is a good thing or a bad thing.

I think this is for policymakers. It feels like we're at an inflection point. I'm really interested to see what your research in this arena, the content ecosystem brings. You know, I'll mention too, recently I read a blog written by Joshua Bengio and Vincent Conitzer, and they acknowledged that the image that they used at the top had been created by an AI bot. And then they said they made a donation to an art museum to say, we're giving something back to the artistic community that we may have used. Where do you see this, you know, hashtag no LLM situation coming in this content ecosystem market. Yeah, that's a very interesting move on their part.

I know Vince quite well, actually. I'm not sure that artists of the sort of art museum nature suffer. So one of my favorite artists is Laurie Anderson. I don't know if you've seen her work at all, but she has a piece in the Mass MoCA right now, which is just brilliant, where she actually uses generative AI to create a sequence of images that creates an alternate story about her family history.

And it's just really, really cool. I'm more worried about people who are doing art vocationally. Yeah. And I think, and maybe you heard some of this from Mert and Brendan, like what's going to happen is that careers are going to shift and different vocations will become more salient. And we've seen this through every technological revolution. People shift their work towards the things that are uniquely human that we can provide. And if generating an image at the top of a blog is not one of them, you know, so be it. People will do something else.

Right, right, right. Yeah, I just, we're on the cusp and there's a lot of things that are going to happen in the next couple of years, maybe a couple months, who knows? Well, we hear a lot of dystopian fears, some of them we've just referred to, around AI and its impact on humanity. But those fears are often dismissed by tech optimists as what I might call unwishful thinking. So your research interests involve the design and use of socio-technical systems to, quote, explain, predict, and shape behavioral patterns in various online and offline systems, markets, and games. Now, I'm with you on the explain and predict, but when we get to shaping behavioral patterns, I wonder how we tease out the bad from the good. So in light of the power

of these sociotechnical systems, what could possibly go wrong, Nicole, if in fact you got everything right? Yeah, first I should clarify something. When I say I'm interested in shaping behavioral patterns, I don't mean that I want to impose particular behaviors on people, but rather that I want to design systems that expose to people relevant information and possible actions so that they have the power to shape their own behavior to achieve their own goals. And if we're able to do that and do it really well, then things can only really go wrong if you believe people aren't good at making themselves happy. I mean, there's certainly evidence of this, like the field of behavioral economics, to which I've contributed some, tries to understand how and when people make mistakes in their behavioral choices. And it proposes ways to help people mitigate these mistakes. But I caution us

from going too far in this direction, because at the end of the day, I believe people know things about themselves that no external authority can know. And you don't want to impose constraints that prevent people from acting on that information. Another issue here is, of course, externalities. It could be that my behavior makes me happy, but makes you unhappy. So another thing that can go wrong is that we, as designers of technology, fail to capture these underlying externalities. I mean, ideally, an economist would say, well, you should pay with your own happiness for any negative externality you impose on others. And the fields of market and mechanism design have identified very beautiful ways of making this happen automatically in simple settings, such as the famous Vickery auction. But getting this right

in the complex socio-technical systems of our day is quite a challenge. Okay, go back to that auction. What did you call it? The Vickery auction? Yeah, so Vickery was an economist, and he proposed an auction format that, so an auction is trying to find a way to allocate goods, let's say, to bidders such that the bidders that value the goods the most are the ones that win them. But of course, these bidders are imposing a negative externality on the people who lose, right? And so what Vickery showed is that a well-designed system of prices can compensate the losers exactly for the externality that is imposed on them. A very simple example of a Vickrey auction is if you're selling just one good, like a painting,

then what you should do, according to Vickrey, is solicit bids, give it to the highest bidder, and charge them the second highest price. And so that's going to have good outcomes for society i want to expand on a couple of thoughts here one is as you started out to answer this question you said well i'm not interested in shaping behaviors in terms of making you do what i want you to do but maybe someone else is what happens if it falls into the wrong hands? Yeah, I mean, there's definitely competing interests. Everybody has their own objectives. Sure, sure. I might be very fundamentally opposed to some of them,

but everybody's trying to optimize something. And there are competing optimization objectives. And so what's going to happen if people are leveraging this technology to optimize for themselves and thereby harming me a lot? Ideally, we'll have regulation to kind of cover that. I think what I'm more worried about is the idea that the technology itself might not be aligned with me, right? Like at the end of the day, there are companies that are producing this technology that I'm then using to achieve my objectives, but the company's objectives,

the creators of the technology might not be completely aligned with the person's objectives. And so I've looked a little bit in my research about how this potential misalignment might result in outcomes that are not all that great for either party. Wow. Is that stuff that's in the works? We have a few published papers on the area. I don't know if you want me to get into them. No, actually, what we'll probably do is put some in the show notes. We'll link people to those papers because I think that's an interesting topic. Listen, most research is incremental in nature, where the ideas are basically iterative steps on existing work. But sometimes there are out of the box ideas that feel like bigger swings

or even outrageous. And Microsoft is well known for making room for these. Have you had an idea that felt outrageous? Any idea that felt outrageous? Or is there anything that you might even consider outrageous now that you're currently working on or even thinking about? Yeah, well, I mean, this whole moment in history feels outrageous, honestly. It's like I'm kind of living in the sci-fi novels of my youth. So together with my economics and social science colleagues at Microsoft Research, one thing that we're really trying to think through is this outrageous idea of agentic AI, that is, every single individual

and business can have their own AI that acts like their own personal butler that knows them intimately and can take actions on their behalf. In such a world, what will become of the internet, social media platforms like Amazon, Spotify, Uber? On the one hand, maybe this is good because these individual agentic AIs can just bypass all of these kinds of intermediaries. For example, if I have a busy day of back-to-back meetings at work, my personal AI can notice that I have no time for lunch, contact the AI of some restaurant to order a sandwich for me, make sure that sandwich is tailored to my dietary needs and preferences, and then contact the AI of a delivery service to make sure that sandwich is sitting on my desk when I walk into my noon meeting, right?

And this is a huge disruption to how things currently work. It's shifting the power away from centralized platforms back to individuals and giving them the agency over their data and the power to leverage it to fulfill their needs. So those sort of big questions that we're thinking about right now is how will such decentralized markets work? How will they be monetized? Will it be a better world than the one we live in now? Or are we losing something? And if it is a better world, how can we get from here to there? And if it's a worse world, how can we steer the ship in the other direction? You know, like, right. I think these are all very important questions in this time.

Does this feel like, like it's imminent? I do think it's imminent. And I think, you know, in life, you can kind of decide whether to embrace the good or embrace the bad, see the glass is half full or half empty. And I am hoping that society will see the half full side of these amazing technologies and leverage them to do really great things in the world. Man, I would love to talk to you for another hour, but we have to close things up. To close this show, I want to do something new with you, a sort of lightning round of short questions with short answers that give us a little window into your life. So are you ready? Yep. Okay. First one, what are you reading right now for work?

Lots of papers of my students that are on the job market to help prepare recommendation letters. It's actually very inspiring to see the creativity of the younger generation. In terms of books, I'm reading The Idea Factory, which is about the creation of Bell Labs. Ooh, interesting. You might be interested in it. Actually, it talks about the value of theory and of understanding the fundamentals of a problem space and the sort of business value of that. So it's very intriguing.

Okay, second question. What are you reading for pleasure? The book on my nightstand right now is The Epic of Gilgamesh, the graphic novel version. I'm actually quite enthralled by graphic novels ever since I first encountered Mouse by Art Spiegelman in the 90s. But my favorite reading leans towards magic realism. So like Gabriel Garcia Marquez, Italo Calvino, Isabella Allende, and the like. I try to read nonfiction for pleasure too, but I generally find life is a bit too short for that genre. Well, and I made an assumption that what you were reading for work wasn't pleasurable. But moving on, question number three, what app

doesn't exist but should? Teleportation. Ooh, fascinating. What app exists but shouldn't? That's much harder for me. I think all apps within legal bounds should be allowed to exist and the free market should decide which ones survive. Should there be more regulation of apps? Perhaps, but more at the level of giving people tools to manage their consumption at their own discretion and not outlawing specific apps. That just feels too paternalistic to me. Interesting. Okay, next question.

What's one thing that used to be very important to you but isn't so much anymore? Freedom. So by that, I mean the freedom to do whatever I want, whenever I want, with whomever I want. This feeling that I could go anywhere at any time without any want, whenever I want, with whomever I want, this feeling that I could go anywhere at any time without any preparation, that I could be the Paul Erdos of the 21st century, traveling from city to city, living out of a suitcase, doing beautiful math just for the art of it. This feeling that I have no responsibilities, like I really bought into that in my 20s. And not so much now.

No. Okay, so what's one thing that wasn't very important to you but is now? Now, as Janice Joplin saying, freedom is just another word for nothing left to lose. And so now it's important to me to have things to lose, roots, family, friends, pets. I think this is really what gives my life meaning. Yeah. Having Janice Joplin cited in this podcast wasn't on my bingo card either, but that's great.

Well, finally, Nicole, I want to ask you this question. Based on something we talked about before, our audience doesn't know it, but I think it's funny. What do Nora Jones and oatmeal have in common for you? Yeah. So I use these in conversation as examples of comfort and nostalgia in the categories of music and food, because I think they're well-known examples. But for me personally, comfort is the Brahms cello sonata in E minor, which was in fact my high school cello performance piece. And nostalgia is spaghetti with homemade marinara sauce,

either my boyfriend's version or in my childhood, my Italian grandma's version. Van, poetry, art, cooking, music, who would have expected all of these to come into an economist, computer scientist podcast on the Microsoft Research Podcast? Nicole Amorlica, how fun to have you on the show. Thanks for joining us today on Ideas. Thank you.