0:00

Hi, welcome back. Remember we're talking about Lyapunov functions.

Â Lyapunov functions are really this simple thing. We have two ways of

Â explaining them. First was the physics way, where there's the minimum value and you've

Â got a process where, if it changes its value, moves down every period. So, if

Â it's moving down, down, down, down, eventually it's going to stop. It's going

Â to hit the floor. It could stop before the floor, but it's gotta stop because of the

Â floor. Where in economics, we often talk about systems where there is a max. And

Â so, every period, if the process moves, it's value's going up and since there's a

Â ceiling here, the process has to stop there. So, Lyapunov functions give us

Â a way to say for sure that a particular system's going to equilibrium. Now, that's

Â if we can construct one. If we can't construct one, then we don't know. Maybe

Â it goes to equilibrium, maybe it doesn't. What we're gonna do in this lecture is

Â remind ourselves of what Lyapunov functions are, and then take an example,

Â take the famous example of a puzzle that's out there, and show how this very, very

Â simple framework helps us make sense of that puzzle. Before we get to the puzzle,

Â though, I first wanna just remind ourselves of what a Lyapunov function is.

Â A Lyapunov function is a function F that has a minimum value, we're in the minimum

Â case here. And then there's another assumption that it satisfies. If the process moves,

Â it's not in an equilibrium, then the value of F falls by some amount k, some amount at

Â least k. So what you've got is a process that's got a minimum value and if it's

Â moving, it's not in an equilibrium, then it has to fall by at least k. What that's

Â gonna mean is that eventually you're either gonna stop or you're gonna hit the

Â floor. So what that means is, you're going to get in equilibrium. Here's the puzzle:

Â Go to any major city, and this is a picture of Stockholm that you see to my right. And

Â what you see is amazing order. Restaurants have the right number of people in 'em,

Â so do coffee shops. There's not huge lines behind dry cleaners. There's traffic, but

Â it's typically not incredibly backed up. And the interesting thing is: there's

Â no central planner. It's like the city self-organizes in some way, so that there's

Â the right number of people at the right places. We're not all bunched up in

Â particular places, and there's not places that are completely vacant. It's almost as

Â if there was a central planner telling people where to go. But we know there

Â isn't. So how is it that cities have this amazing structure, that when you go to the

Â grocery store, they've got the right groceries for you, there's the right

Â number of workers? When you hop on the train the lines aren't incredibly long,

Â when you go the grocery store, when you go to the dry cleaners, it's not incredibly

Â crowded nor is it particularly empty? What-- what enables the city to

Â self-organize in the way that it does to be so darn efficient? That's the puzzle. And what

Â we're going to see is that Lyapunov functions can give us some inkling as to

Â why even huge cities can self-organize in interesting ways. So here's the idea.

Â Suppose that you've got five things you've gotta do during the week. You've gotta go

Â to the cleaners, the grocery, the deli, the bookstore and the fish market. So

Â these are five things you have to do at some point during the week. You always

Â gotta go get fish and books, and get your groceries. So, this sort of stuff. And you

Â can choose which day to go. So, here's how to think of it. There's five days

Â during the week, assuming you take the weekends off and you just read your book

Â and have some fish, wearing your nice clean shirt. So, there's five days, Monday

Â through Friday. And each day, you have to decide during your lunch hour, where to

Â go. We can assume, maybe Monday you go to the dry cleaners. Right? Tuesday, the grocery

Â store. Wednesdays the deli, Thursdays the book store, Friday the fish market.

Â This would be just a route that you would take during the week, and somebody else

Â might take a different route. What we wanna see is, by people choosing these

Â routes, whether or not the system is gonna organize in such a way that you don't get

Â huge crowds in particular locations. We'll see how we can map a Lyapunov function

Â onto this process. So here's the idea: Suppose you've got five people and each

Â one of these people chooses some random order in which to visit these different

Â locations. So listen, everybody else is just like you. Everybody else has to go to

Â the cleaners, the grocery store, the deli, the bookstore and the fish market, and

Â they also pick one day a week to go to these things. So each person has chosen

Â their route. This may be your route. This may be my route. This may be somebody

Â else's route. Everybody's got their own route. What we'd like to do is not go to

Â some place that's really crowded, because if it's really crowded then we've got to

Â wait in line and it may take our whole lunch hour and don't have time for lunch.

Â So, the rule is you're just going to want to sort of avoid crowded places. And

Â what we're going to see is, if people follow that rule, then we can pull the

Â Lyapunov function on the process, and show that it's going to go to an

Â equilibrium, and go to a pretty darn good equilibrium. So here's the idea. We're

Â gonna assume the following behavior: that people want to avoid crowds. So, I pick a

Â route, and if it turns out that I notice, "boy, when I go to the cleaners on Monday

Â it's incredibly crowded", I switch that with another location, so that Monday I go

Â to a place that's less crowded. So I'm just gonna switch the time I visit the dry

Â cleaner's and the time I visit the fish market in order to bump into fewer people.

Â That's the rule. And then we're going to see if that's the rule, that this process

Â is actually going to self-organize into something that makes a lot of sense. So

Â again, here's the idea. Everybody's choosing these routes. And let's look,

Â let's look at this person here, this first person. The very first day they're going

Â to the cleaner's, but notice there's three other people at the cleaner's. So that

Â means that there's four people at the cleaner's. What they'd like to do is, not

Â have four people telling us we have to wait in line. So what they might think of is,

Â "if I go to the fish market here, there's no one going to the fish market on the

Â first day. So if I switch the fish market with the cleaner's, then Monday I won't see

Â anybody at the fish market, and Friday I won't see anybody at the cleaner's". So this

Â first person realizes, "if I just switch these two, then I'm gonna run into fewer

Â people". That's the idea. That's the behavior that we're going to assume people

Â follow. What we want to show is, we can put a Lyapunov function on this process and

Â show that this system is going to keep going down, and eventually has to

Â stop. Because there's a min. So what's the Lyapunov function? Remember, I said this

Â is the hard part, and it's hard. So the first thing that I think of is, well,

Â maybe it's just the total number of people at each location. Well, let's try

Â that. So, how many people go to the cleaner's? Well, five people go to the

Â cleaner's. How many people go to the deli? Five people go to the deli. And what you

Â realize is, five people go to every location. So that's not gonna

Â work. Right? Because even if I switched my route, there's still five people going to

Â the cleaner's, and five people going to the deli, and five people going to the fish

Â market. So, this first attempt of total number of people at each location: not

Â gonna work. So let's try something else. Here's another attempt, let's have it be the total

Â number of people that each person meets. So, how many people do I meet in a given week?

Â And now let's look at our example. So we start out here. We look at this person, and right here

Â [inaudible] on the first day, they meet three people. On the second day, they meet

Â no one, he meets no one. On the third day, meets two people. On the last, fourth day,

Â on Thursday two people, and on Friday one person. So that's 5, 7, 8. So this person

Â meets eight people. We'll now suppose they switch, and go to the fish market on Monday and

Â go to the cleaner's on Friday. So this person switches to be less crowded. Well, now

Â on Monday they meet no one. On Tuesday they meet no one. On Wednesday they meet

Â two people. On Thursday they meet two people, and on Friday they meet no one, for

Â a total of four people. Now remember, before, they met eight. So by switching

Â those two, they reduced the number of people they meet from eight to four. We

Â gotta look carefully because there's also four other people, what about those four

Â other people? Could their numbers have changed? Well they did, right, because

Â these four people, these people that we see here, before were meeting this person,

Â and now they're not. So in addition to this person running into four fewer

Â people, the four people they were meeting also run into four fewer people. So the

Â total reduction in the number of people that meet each other is eight. It's gonna

Â be four times two which is eight. Because each person that person one doesn't meet, also

Â doesn't meet person one. So it's a total of eight fewer meetings. So this is gonna

Â be a Lyapunov function. If peoples' rule is, "switch so that I meet fewer

Â people", then when somebody switches, they meet fewer people, fewer people meet them.

Â So the total number of people who meet each other, falls. Now let's ask, is this

Â a Lyapunov function? Well, what are the conditions? The first is, does it have a

Â minimum value? Sure: zero. If nobody meets anybody, then that's the best you could do.

Â So yes, there's a minimum value, it's just zero. Second, if it's the case that

Â somebody changes their route, does it mean that the total number of people that people meet

Â falls? And the answer again there is, yes. Because if I move, I'm moving so I meet

Â fewer people. It also means that fewer people meet me. Which means that the

Â number of people met has to fall. So, if anybody moves, the number of people met has

Â to fall. Remember, it also has to fall at least by some amount k. Well this

Â situation is easy. That k is easy. Because I'm meeting at least one fewer person. And

Â if I'm meeting one fewer person, that person is also not meeting me, so

Â k is going to be equal 2. If I'm meeting one fewer person, then there's one

Â fewer person meeting me, so at least two people have lowered the number of people

Â they meet. So I've got a function with a minimum of zero; it goes down by two each

Â period; so, therefore the process has to stop. So if I take a route

Â selection process like this and people are switching, what you're eventually gonna get

Â is, you're gonna get that everybody meets no one, because you can keep switching. So

Â we're going to keep switching, until you will get an efficient ordering of people,

Â so that nobody's running into anyone else. Now to prove that you actually, this

Â thing only stops at zero, takes a little bit more work, so we won't do that. But

Â what's going to happen is you're going down by two each period, and it just keeps

Â going down, down, down, down, down until eventually nobody's meeting anybody. This

Â gives us an understanding, it's not a full explanation, because there's some

Â intuition, as to why, when we go to a city, it's so organized: because people are

Â trying to avoid crowds. If everybody is trying to avoid crowds, then what happens

Â is, you get a relatively efficient distribution of people across activities,

Â and restaurants, and shops, and museums, and things like that. So, the whole city

Â seems to be organized, as if by a central planner, when in fact it's self-organizing

Â because the fact that people are trying to avoid running into too many people and

Â what you end up getting then is a reasonably smoothly running city, without

Â some massive central planning, without us giving signals like, "it's okay, you can

Â now go to the caf?, Scott". You don't have to tell me that, because people are going

Â to develop routines of when they go to particular locations, in order to avoid

Â those crowds. This is pretty cool, I think. What have we got now? [laugh] A very

Â simple model, right? Simple model is, there's a min, if the process moves, it

Â goes down by some amount each time, therefore the process has to stop. We use

Â that model to say, let's think about how a city organizes itself. How is it that

Â people in a city choose where to go, and how does it seem to be so efficient? And

Â what we see is that peoples' manoeuvering within the city is probably somewhat to

Â avoid crowds, to go to places you like but not wait in huge lines. So in doing that,

Â you're always reducing the number of people that you meet. Let me be just a

Â little bit critical of this for a moment. This was an extreme simplification,

Â because this model says, the city's gonna go to an equilibrium with everybody

Â choosing the exact same routes. Now in fact, a city's more of an open system.

Â There's tourists coming in, there's all sorts of, you know, people being born and

Â people dying and new businesses starting and all sorts of things. So, that's gonna

Â keep a city churning and somewhat complex. But within that process, there's

Â all sorts of people who develop regular routines of places that they go. And those

Â regular routines move that Lyapunov function down, down, down, in terms of the

Â number of people that one of each of us runs into, and allows the system, even

Â though the influx maintains some complexity, to be relatively efficient.

Â It's sort of, keep down the number of crowds that people run into. So the model

Â doesn't fully explain the city, but what it does is gives us the insight into how the

Â city's able to organize itself in such a way that there's never too many people at

Â the barber shop, and never too many people at the cleaner's, and always some people at

Â that caf?. It's never completely empty. Alright. Thank you.

Â