Tim Roughgarden is professor in the Computer Science and Management Science and Engineering Departments at Stanford University. He is also a very active science communicator, hosting a popular algorithms course on the Coursera online learning platform. 

Among many recognitions, Tim has received the Gödel Prize for his research in computational game theory, a field that resides in the intersection of two disciplines: economics and computer science. We talk to Tim about one of the central insights of that work: the Prize of Anarchy, which quantifies the loss in efficiency of a system due to selfish behaviour of its agents.

We also look at applications of game-theoretic algorithms in the real world, when Tim explains the role that computer science played in designing the 2016 “incentive auction” used to by the US Federal Communications Commission (FCC) to buy and sell broadcast airwaves.

Welcome to yet another episode of Cast It.

This is our second episode where we are on the road.

We are recording at ALGO, the main European algorithms event, which in 2018 this year is in Helsinki, Finland hosted by Aalto University of Finland.

Tim is a professor at Stanford University in California in the US, and the winner of a gazillion prizes, including the Grace Hopper Award and the Goethe Prize.

So you're a professor of many things, actually.

You're not only a computer science professor, but there's a very long title on your job description.

Well, I consider myself first and foremost a computer scientist.

It is true that at Stanford I have a courtesy or 0 percent appointment in the management science and engineering department.

Yeah, so that there used to be an operations research department and industrial engineering department and they sort of merged and that's now called management science and engineering.

So they have a nice, really nice optimization group who I connect with.

And then I also connect a lot with the economists at Stanford, both in the econ department and also in the business school.

And I don't have any formal affiliation with them.

But I guess this is what we want to talk about today, the intersection between economics, which is an academic discipline, and computer science, which is another academic discipline.

And both of them have some effect on reality, even.

So game theory, I'm old enough to have been brought up in a computer science universe that was completely innocent of any game theory.

And that all changed in the, what, late 90s?

Well, you know, mid-90s or so was about the time the Internet started really exploding, taking over the world and becoming very commercialized

because there was computer science before the internet

There was believe it or not It was computer science before the internet But I think most computer scientists would say the field changed quite a bit with the advent of the internet And you know so to many people not just in theory, but across all branches of computer science, you saw a lot of research just changing a lot in the mid to late 90s for this reason.

And theoretical computer science was no different.

I think the community did a great job of responding to the new challenges that were coming up because of the advent of the internet.

And specifically, what you alluded to, this connection to game theory and economics, 1 thing that was really novel was that the computer science applications that we really cared about that were coming out at that time fundamentally really called out for game theoretic reasoning.

They really fundamentally involved the interaction of different competing parties.

So initially, we were thinking about things like internet service providers.

They're choosing how to route their traffic.

They're choosing how to do their peering agreements.

And it was clear that an internet service provider, they're kind of neither honest nor adversarial.

They're not going to just sort of play along with some protocol if it's not in their own best interest.

But they're also not going to bring the internet to a halt because they have such a vested interest in it going on.

I would say there are exceptions, but for the most part, working computer science prior to that, either you just had 1 entity, you were just building software for a single desktop and just did what you told it to.

Or if you had multiple parties, like say in distributed systems, you'd model people as either cooperative slash honest or adversarial, like in Byzantine fault tolerance or something like that.

Some of the nodes you would just assume obediently follow the protocol.

Other nodes you would assume are adversarial, but there's no notion of a utility function and different parties acting according to some utility function.

So before the internet, it's basically an engineering discipline or a math discipline where the thing you build is also the thing you analyze.

And then what happens with the Internet is that there are many different players with various incentives who not necessarily co-op...

Well maybe they have shared goals but they don't have the same, What was the word, utility function?

So the same result of being active in this environment?

So for example, you could imagine each internet service provider, they want the internet to survive.

But they also want to grab as much traffic from themselves.

They want to grab customers from the other internet service providers.

So they're simultaneously cooperating to make sure the internet routing works on the internet, but also competing for market share.

So that mixture of cooperation and competition didn't really have much of an analog in prior work in computer science.

But there was another discipline who had studied this for a generation at that time, I guess?

Well, so, I mean, you know, economics has been studying incentives and equilibria for a long time, since before the birth of computer science as an intellectual discipline, I would even say.

Which is really young, which is 70s or something.

But Stanford was the first department, wasn't it?

I'm not sure they were the first, but they were very early,

So John von Neumann, for example, was doing a lot of his foundational work in game theory in

Who incidentally also was 1 of the first people who built a computer.

So he's, in some sense, computer science and game theory have this shared heritage, in part, coming from.

If you want to reduce this to 1 guy, and you ignore Turing, then it's von Neumann.

certainly played a crucial role in 2 disciplines.

As you say, on the computer science side, Turing and others.

And even on the economic side, there were people like Borrell thinking about equilibria in poker games and so on beforehand.

But, you know, I think for most people, von Neumann's minimax theorem is really sort of a watershed event in the development of game theory.

That field really exploded a little bit later in

when von Neumann wrote his book with Oskar Morgenstern, Theory of Games and Economic Behaviour.

And at that point, really, you know, everybody knew that this was an important new field that required attention.

But computer science and game theory continued, innocent of each other, until the 90s.

So there's sort of this shared heritage and von Neumann being important in both.

But really, as the 20th century unfolded, they developed basically completely in parallel with very little communication.

There's some definitely forward-thinking visionaries.

Christos Papadimitriou would be an example.

More recently, in the 1980s, he was starting to look at connections between the 2 fields.

But for the most part, It's just been the last 20 years they've started talking to each other.

And I guess even before we continue that, we need to spell out what game theory is, because we are, in this show, epistemologically extremely vociferous, and there is another conversation I have with somebody in game studies, and that's something completely different.

That's a field of studies that studies computer games as narrative objects or as phenomena in literature.

And when you say game theory, you mean something completely different.

It's really thinking about what happens when you get different parties in a common strategic situation.

For example, a very early example would just be like a card game, a so-called zero-sum game, where either I win or you win.

So in game theory, you have to identify, first of all, who are the participants?

So in a card game, it might just be you and me.

You have to identify what are the strategies available to each of the participants.

So these could be, for example, different ways you could bet in Texas Hold'em or something like that.

And then you need a notion of payoffs, which says, given a choice of action by every participant, what is the payoff earned by every player?

Which in a card game could just be the amount of money that you win.

So that's sort of its origins from games of chance.

But increasingly, as the 20th century went on, people realized it might be interesting to think about real settings from this perspective, too.

Like 1 famous and very important example is known as the Prisoner's Dilemma.

There's 2 players, 2 criminals, or alleged criminals that have been charged with a crime.

They can either confess to the crime or not.

And the payoff structure is such that if both of the criminals deny that they did the crime, they're instead locked up on a sort of like charge.

So they each sort of say a one-year prison sentence.

If they, on the other hand, if 1 of them rats out his colleague, okay, so 1 of the person denies the crime, but the other person says, no, no, no, we did it, you got us.

Then the confessor as a witness is set free and serves no jail time.

But the other person, the person who denied the crime, gets convicted for a long jail sentence, say 5 years.

If they both confess, then let's say they both served 3 years of prison time.

Now, what do you think's going to happen?

So the question now, game theory asks, what's going to happen in the prisoner's dilemma?

But I mean, for the simplest analysis, you could reason as follows.

You could say, look, on the 1 hand, the prisoners collectively would be best off if they both denied the crime.

And that's less than they could get by any other combination of behaviors.

So it's in some sense collectively optimal for both prisoners to deny the crime.

However, it is not individually optimal for either 1.

If I'm 1 of the prisoners, I'm thinking, well, what are my options?

What are the 2 things my colleague could be doing?

If he denies, then if I confess, I get the love.

So either way, it's in your best interest to actually rat out your colleague.

So it's the notion of a dominant strategy in a game.

A strategy that's always in your best interest, that always maximizes your payoff independent of what the other person does.

In both cases of what the other person does.

In both cases of what the other person could do.

So that's the, Yeah, that's what dominant strategy means.

So I don't even have to worry about whether you're confessing or not.

Independent of whether you confess or don't confess, I'm always going to be

Which is counterintuitive, because If both prisoners were just zombies controlled by a third person that was able to determine what both of these zombie prisoners did, they would both be even better off.

And then the mystery is why can't they just get their act together and collectively perform exactly the strategy that would make the entire community, in this case, both prisoners better off.

So definitely, the story usually goes with the prisoners being separated in 2 different rooms.

So they can communicate in advance and plan out their strategy.

The idea is once the prisoners are in their separate room, and the jailers say, your colleague already told us what they're doing.

I've watched enough cratchos to know this is exactly what happens.

This is exactly what the police will do to you.

So this, I mean, I think this is a bit, and this is 1 thing game theory is really great for.

It's really almost like parables, which you can take with you and understand a large part of the world through them.

And the Prisoner's Dilemma is a great example.

It's just, you can look at a lot of problems that are out there in the world where fundamentally what's going on is this conflict between collective optimality and individual optimality.

And our normal tools from computer science, we just see all these actors as programs that I as a programmer have programmed are very poor at attacking these things.

The whole idea of, say, engineering of collectively optimizing various parts that work together simply breaks down in analyzing these scenarios where there are different incentives.

So the old school computer science approach might just be like, well, let's just program each of the 2 parties so that they do the right thing.

And then as long as there's no adversarial or no faulty machines, then you get a guarantee of collective optimality.

But that's not reality in a lot of applications.

There is this notion of sort of individual autonomy

OK, so games in the narrow sense as card games, board games, are covered by game theory.

But game theory also wants to model behavior of intelligent, independent agents that maximize various incentives.

So another really good example would be the tragedy of the commons, for example.

And so this again shows up in all kinds of places in the real world.

You can think, for example, about pollution, say.

So imagine you have sort of a bunch of factories.

Those are going to be the parties in the game, these factories.

And their strategy space is either they use a cheap technology that creates a lot of pollution, or they use an expensive technology that creates less pollution.

And each of them has to make this decision.

And in many cases, the payoffs are such that the incentive to pay for the expense of technology is not sufficient for the individual to actually do that.

So in other words, It could be that if some factory polluted less,

you took into account the benefits for everybody, it would far outweigh the cost to that factory.

But the factory is going to, in the absence of regulation or cultural norms or something, the factory will say, well, Yeah, but the benefits to me of using this expensive technology don't outweigh my costs for having this expensive technology.

So again, if you ask, what do you expect to have happen?

Again, it's this dominant strategy for every factory to use the cheap technology and pollute.

So you wind up with this worst case scenario where everybody's polluting as much as possible, and everyone's much worse off than they would be had they all agreed to buy the expensive technology.

So now you're sitting here as an American in 1 of the main Scandinavian welfare states where...

So this in the end is a question of politics in many, many respects.

How much regulation do we want and how much do we want individual agents in the market to just optimize their own welfare?

And so a key term you hear here is the idea of an externality.

And so an externality means it's some benefit or cost that's caused by your action that's borne by somebody else.

So in tragedy of the commons, there's what's called a negative externality, in that when I make my decision to build the cheap technology, there's a cost to society that is largely borne by everybody else.

And so what you learn in kind of introductory economics is when you have a market with externalities, that's somewhere you should consider regulation.

So you could imagine trying to have regulation that coaxes everybody into actually doing the collectively optimal strategy.

And just to spell out the Commons and the tragedy of the Commons, That's the large green pasture that everybody can put their cows or sheep out to graze on?

Yeah, I think originally it was a bovine example.

In the pollution context, I think the commons would just be air quality that we all breathe.

And the tragedy would be that that resource gets degraded because of this uninternalized externality.

Because none of the individual factories is individually incentivized to reduce the pollution.

So 1 way to think about it, So what would it mean for this externality to be internalized?

Well, suppose that I actually said, if you reduce your pollution, if you build the expensive technology.

So because the social value of your choice is so high, we will cover your cost, your investment in the expense of technology.

You'll have healthier people and less medical costs.

This will be the kind of decision you could imagine making in the face of tragedy of the commons.

Yeah, so these are obviously very, very important questions that are on everybody's minds right now, not even with climate change and whatnot.

And economics provides this model for reasoning about this.

And this is where you come in with your own thesis, right?

So both the prisoner's dilemma and tragedy of the commons, they all do show up everywhere.

Once you learn to think about the world in this way, you can recognize so many things out there.

It's really just being instantiations of a couple of these canonical examples.

So you look around in computer science, you see examples of the prisoner's dilemma.

So when I was a graduate student, first started thinking about this, I was looking at network routing.

That's what I was interested at the time in networks.

And then with the internet coming out, it was clear it was time to think about game theoretic behavior in networks.

And networks are good old-fashioned, not social networks, but networks actually, wires connecting computers.

I mean, the really old school interpretation of network would be a road network.

And This is the 1 that's still probably the easiest for most of us to understand.

So literally, you just have roads, median intersections.

Obviously, as a driver, at least in most cases, you can pick whatever route you want.

And there, again, can be a conflict between how good a route is for you and how good a route is for somebody else.

So why is it that if a single driver, choosing which route to drive on, how does it affect other people?

Well, if you think about it, on a given road, if there's some number of cars using it, every extra car, after a certain point, slows everybody down.

So you might prefer it for your own sake, because you'll get there faster to take some route.

But there might be 100 other people that are getting there slightly slower now that you've made that decision.

So that again is an example of an uninternalized externality.

So this is known as a congestion externality.

You cause congestion which makes it worse for other people but you don't factor that into your own individual decision.

You're just trying to get from point A to point B as quickly as you can.

It's still faster than taking the bus, I guess, which everybody could take.

So if you have a car and you're going to get there faster, and you're okay with the gas cost versus the bus fare,

You wouldn't not do it just because you make these other people's lives a little bit worse, typically, if you look at how drivers make decisions.

So this uninternalized externality, again, gives you the prisoner's dilemma all over again.

So there's a very actually nice example discussed by the economist A.C.

He only discussed it qualitatively, but still.

I mean, he makes all of the right points about congestion externalities.

So he says, imagine, and again, talking about these road networks.

So he says, imagine you just have point A and point B.

So you have a bunch of people leaving for work at roughly the same time, and then there's the place where the factory is.

See all IT UNIVERSITY OF COPENHAGEN transcripts on Youtube

TIM ROUGHGARDEN: THE PRICE OF ANARCHY