Michael Kearns: Game Theory and Machine Learning

Speaking of markets, a lot of fascinating aspects of this world arise not from individual humans, but from the interaction of human beings. You've done a lot of work in game theory. First, can you say what is game theory and how does help us model and study.

Yeah, game theory, of course, let us give credit where it's due, comes from the economist first and foremost. But as I've mentioned before, computer scientists never hesitate to wander into other people's turf. And so there is now this 20 year old field called algorithmic game theory. But game theory first and foremost is a mathematical framework for reasoning about collective outcomes in systems of interacting individuals. So you need at least two people to get started in game theory. And many people are probably familiar with Prisoner's Dilemma as kind of a classic example of game theory and a classic example where everybody looking out for their own individual interests leads to a collective outcome that's kind of worse for everybody than what might be possible if they cooperated, for example. But cooperation is not an equilibrium in Prisoner's Dilemma. And so my work, and the field of algorithmic game theory more generally in these areas, kind of looks at settings in which the number of actors is potentially extraordinarily large and their incentives might be quite complicated and kind of hard to model directly, but you still want kind of algorithmic ways of kind of predicting what will happen or influencing what will happen in the design of platforms.

So what to you is the most beautiful idea that you've encountered in game theory?

There's a lot of them. I'm a big fan of the field. I mean, you know, I mean, technical answers to that of course would include Nash's work, just establishing that, you know, there, there's a competitive equilibrium under very, very general circumstances, which in many ways kind of put the field on a firm conceptual footing. Because if you don't have equilibria, it's kind of hard to ever reason about what might happen since, you know, there's just no stability.

So just the idea that stability can emerge when there's multiple or that, I.

Mean, not that it will necessarily emerge, just that it's possible. Right. It means like the existence of equilibrium doesn't mean that sort of natural iterative behavior will necessarily lead to it in the real world. Yeah, maybe answering slightly less personally than you asked the question. I think within the field of algorithmic game theory, perhaps the single most important kind of technical contribution that's been made is the realization between close connections between machine learning and game theory, and in particular between game theory and the branch of Machine learning that's known as no regret learning. And this sort of provides a very general framework in which a bunch of players interacting in a game or a system, each one kind of doing something that's in their self interest, will actually kind of reach an equilibrium and actually reach an equilibrium in a pretty rather short amount of steps.

So you kind of mentioned acting greedily can somehow end up pretty good for.

Everybody or pretty bad.

Or pretty bad. It will end up stable.

Yeah, right. And stability or equilibrium by itself is not necessarily either a good thing or a bad thing.

So what's the connection between machine learning and the ideas?

Well, I mean, I think we've kind of talked about these ideas already in kind of a non technical way, which is maybe the more interesting way of understanding them first, which is, you know, we, we have many systems, platforms and apps these days that work really hard to use our data and the data of everybody else on the platform to selfishly optimize on behalf of each user. Okay, so, you know, let me, let me give, I think the cleanest example, which is just driving apps, navigation apps like, you know, Google Maps and Waze, where, you know, miraculously compared to when I was growing up, at least, you know, the objective would be the same when you wanted to drive from point A to point B, spend the least time driving, not necessarily minimize the distance, but minimize the time. Right. And when I was growing up, like the only resources you had to do that were like maps in the car which literally just told you what roads were available. And then you might have like half hourly traffic reports just about the major freeways, but not about side roads. So you were pretty much on your own. And now we've got these apps, you pull it out and you say, I want to go from point A to point B. And in response kind of to what everybody else is doing, if you like what all the other players in this game are doing right now, here's the, you know, the route that minimizes your driving time. So it is really kind of computing a selfish best response for each of us in response to what all of the rest of us are doing at any given moment. And so I think it's quite fair to think of these apps as driving or nudging us all towards the competitive or Nash equilibrium of that game. Now you might ask, well, that sounds great. Why is that a bad thing? Well, it's known both in theory and with some limited studies from actual traffic data that all of us being in this competitive equilibrium might cause our collective driving time to be higher, maybe significantly higher than it would be under other solutions. And then you have to talk about what those other solutions might be and what the algorithms to implement them are which we do discuss in the kind of game theory chapter of the book but but similarly you know, on social media platforms or on Amazon, you know all these algorithms that are essentially trying to optimize our behalf they're driving us in a colloquial sense towards some kind of competitive equilibrium. And you know one of the most important lessons of game theory is that just because we're at equilibrium doesn't mean that there's not a solution in which some or maybe even all of us might be better off. And then the connection to machine learning of course is that in all these platforms I've mentioned the optimization that they're doing on our behalf is driven by machine learning like predicting where the traffic will be, predicting what products I'm going to like, predicting what would make me happy in my newsfeed. Sa.