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.
