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.

The Organization of Cities

Model Thinking

Meet the Instructors