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.