Hi, in this set of lectures we're going to talk about something called Lyapunov
functions and what the Lyapunov functions are, is they're functions that really can
be thought of as mapping models into outcomes in the following way. So what we
can do, is we can take a model or take a system and we can ask ourselves, can I
come up with a Lyapunov function that describes that model or describes that
system. And if I can, then I know for sure that system goes to equilibrium. So what a
Lyapunov function is, is it's this tool, it's this incredibly powerful tool to help
us understand, at least for some systems, whether they go to equilibrium or not. Let
me explain what I mean a little bit more. Remember how we talked about, there's four
things a system can do. It can go equilibrium, it can cycle, it can be
random. Or it can be complex. Lyapunov functions, if we can construct them,
that's going to be one of the challenges. If we can come up with one, then we'll
know for sure that the system's going to go to equilibrium. If we can't construct
one, then maybe it goes to equilibrium, maybe it's random, maybe it's chaos, maybe
it's complex, we don't know. We can't really say anything. So the challenge here,
the really hard and fun part is coming up with Lyapunov functions. If you come up
with a Lyapunov function, then you know for sure, hey, this system's going to a
equilibrium. which is a nice thing to know. Not only that, we'll see in a minute that
you can see how fast it's going to equilibrium. So, how does it work? Here's
the ideal. Suppose you have a system and I've got something I care about here which
might be velocity on this axis. And suppose there's a minimal velocity which is zero,
which I'm representing by this big black region down here. Now, suppose that I say
the following property holds: I start with some positive velocity, and every period, if
the velocity changes it goes down. So it's gonna down to there and then it goes down to
there. Now it could be the velocity doesn't change, if the velocity doesn't
change then you're fixed, then you're in an equilibrium, but if the velocity does
change, it has to go down. Well if that's the case, if it changes it has to go down,
at some point it's going to hit this barrier down at the bottom, this zero
velocity point. And when it hits zero, it has to stop, so that's the idea. If
something, if it falls, if it moves, it has to fall. That's property one, it's got
to go down, if it moves it's got to fall, and there's a minimum, well those two
conditions are gonna mean that the system has to stop. With one little, we got to
pick up one little peculiar detail besides that, but that's basically the idea. If
the system is gonna move, it's got to fall and there's a min. So therefore at some
point, it's either gonna stop before the min, like it might fall, fall, fall and
then stop right here, or eventually it will get the thing at the bottom. That's
the idea. Now, how do economists do it? Economists do the opposite. They have
something where maybe this is happiness on this axis. And maybe people are making
trades. And you say, people trade, happiness goes up. So, I've got happiness
here. People trade, it goes up. People trade, it goes up. So any time people
trade, total happiness goes up, otherwise they wouldn't trade. So that means any
time the system moves, happiness is increasing. But, you've got this caveat
that there is a maximum happiness here, it can't go above this black bar. So what
does that mean, if anytime people trade it goes up. And at, and at some point, you're
gonna hit this bar, that means the process has to stop. And if it has to
stop, that means it's at an equilibrium, where there's no more trade.
Everybody's happy with what they've got. So there's these two in substance identical
ideas, right? One is from physics, that if things fall every period and there's a
min, the process has to stop. And then from economics, you have where things go
up every period, and there's a max. It has to stop. That's it, that's the theorem. I
know it sounds sort of frightening, right? Lyapunov, it sounds really scary, and I'm
sure when you looked at the syllabus, you thought, oh my gosh, Lyapunov functions!
This is gonna be hard. Maybe I'll skip this lecture. I thought about calling it
Dave functions, or Maria functions, because then it wouldn't sound so
frightening if I said, we're gonna study Maria functions, you know, so, ha, that's
probably gonna be pretty easy, or Dave functions. It's just that with these
Russian surnames, you sorta think, oh my goodness, this is frightening. It's not,
very, very easy. Here's the formal part. What we do is we say there's a Lyapunov
function if the following holds: First, I just have some function F, and
I'm gonna call this a Lyapunov function. And there's just three conditions. The
first one is, it has a maximum value. I'm gonna do the economist's version. In the
physics version, I'd say there's a minimum value. So there's a maximum value. Second
assumption, there is a k bigger than zero. So there's some number k bigger than zero,
such that, if x<u>t+1 isn't equal to x<u>t. So what that means is if-- F is</u></u>
gonna basically map the state now to x<u>t into x<u>t+1. If they're not equal,</u></u>
alright, so if the state in time t plus one is not equal to the time the state at time t
then F of x<u>t+1 is bigger than F of x<u>t+k. What does that mean in words,</u></u>
not in math? What it means is, if it increases, if it's not fixed, that the
point is not fixed, then it increases by at least k. Just by some fixed amount. It
doesn't always have to increase by exactly k, it can increase by more. But it's got
to be increased by at least k. If those things hold, so it's got a maximum, you're
always going to be increasing by at least some amount k, then at some point
the process has to stop. Because if it didn't stop, you would keep decreasing by k
and would go above our maximum. That's the theory. Now what does this assumption do?
What is this thing about, it's gotta be-- Before I just said, it has to be bigger; now I've got,
it's gotta be bigger by plus k. What's going on? Well this goes back to something
way back in philosophy called Zeno's paradox and Aristotle's treatment of this
is probably the one most of you learned in college, and that is: suppose I want to
leave this room, suppose I'm gonna leave this room right here and the first day I'm
standing right here. Here I am, da-ta-da, and the first day I go half way to the
door. Then before I get half, and then the next day go another half way. And then the
next day I go another half way, The next day another half way, The next day another
half way. I'd never actually leave the room. Well, if I don't assume, cause
what's happening here is I'm going up a half and then a quarter, and then an
eighth, and then a sixteenth. So if I made my steps smaller and smaller and smaller
and smaller and smaller and smaller and smaller, it could be that I continue to
increase, but I never actually get to the maximum. But if instead, I assume that
each step has to be at least 1/16. Well then after sixteen steps, I'm going to be
out of the room. So what Zeno's paradox is that you can basically keep making steps halfway, and
you'll never actually exit. And the paradox was that you could keep moving
towards the door but never actually get to the door. The way we get around that is, we
make this formal assumption that says there's some k such that, if you move, you
go up by at least k. So in this case I talked about it being one sixteenth, if
you go by, up by at least one sixteenth, then in sixteen steps you're out of the
room which, and, since you can't leave the room, that's a max, what's gonna happen is, the process has to
stop. So that's all there is to it. We often have function consistent is F, it's
got a maximum value. And then there's some, if it's the case that the process
moves over time, then in the next period, you've gone up by at least some amount k.
And since there's this max, you're going up by at least k each time. Eventually
you're gonna hit that max and the process has to stop. And there's a bonus we just
got as well, right? If each time I go up by 1/16th, then in sixteen steps, I'm
gonna have to stop. So you can also say how fast the process is going to stop, and
that's obviously not a very complicated calculation at all. Here's the tricky part
[laugh] about this, the hard part about this is constructing the function. So the
theory, the idea that there's a function, there's a max, we go up by k each time,
that's really straight forward. The really tricky part is going to be coming up with
a Lyapunov function, coming up with that function F. So what we're going to do in
this set of lectures is, we're gonna take some processes, things like arms
trading, trading within markets, people deciding where to shop, and we're gonna
show how, in some of these cases, it's really easy to construct Lyapunov
functions. In other cases, it's really hard to construct Lyapunov functions
and, I mean, we can't even construct Lyapunov functions. So we're just going
to explore how this framework, this Lyapunov function framework, can help us
make sense of some systems. Help us understand why some things become so
structured and so ordered so fast, and why other things still seem to be churning
around a little bit. So the outline of what we're going to do is, we're just going
to start out by first doing some simple examples, see how Lyapunov functions
work. Then we're going to move on and see some sort of interesting applications of
Lyapunov functions, maybe when they don't work. And then from there, we'll go on and
talk about processes that maybe we can't even decide whether Lyapunov
functions exist or not, some open problems of mathematics that involve trying to
figure out: does this thing go to an equilibrium or does thing continually
churn? And then we'll close it up by talking about how Lyapunov functions
differ from Markov processes. Remember, Markov processes also went to equilibrium.
We'll talk about how those equilibria are different from the equilibrium we're talking about
in these Lyapunov functions, and also how just the entire logic about how the system
goes to equilibrium is different in the two cases. Okay, so let's get started.
