Hi! So we're talking about Lyapunov processes. Lyapunov processes gives

us one technique, one tool for possibly determining whether or not the system goes

to equilibrium, so it can tell us for sure the system's gonna go to equilibrium. But

sort of lingering out there is this question of well, can we always tell?

Maybe not using Lyapunov functions, But if we have a system, can we say for

sure, hey, does this go to equilibrium or does it not go to equilibrium? Well,

that's the question that we're going to take up in this lecture. Does the system

go to equilibrium or does it not, or can we even tell? Well, and that's, that's a

good question. So what we're going to do is we're going to do this in two ways.

We're going to do this in sort of a fun way with some examples and then we'll do

something a little bit deeper. We'll see, in fact, that why some processes are very

hard to figure out. So here's the fun example and this is called "chairs and

offices", and this actually comes from an experience that one of my former students

had. So the student had learned about Lyapunov functions in class, and she's

working for some firm. And this firm's moving to new offices. And they've also

got a whole bunch of new office furniture, and they're trying to decide, how do we allocate

the furniture and how do we allocate the offices? So I'm gonna just put furniture

in this one category "chairs", and all the offices in a separate category which I

call "offices". So allocate the chairs: My students said, well, here's a really great

idea. Let's just give each person a chair, just randomly assign each person a chair.

We can all hold our chairs, cause these chairs are different. And then, people can

just trade. Each person can trade their chair with someone else if they want to.

And this will be great, and then the process will stop and we'll be done. And her boss said,

you know that seems [laugh] kind of crazy, because we could be trading chairs all

day. And she said no, no, we're not going to trade chairs all day because there's a

Lyapunov function. Let the Lyapunov function be how happy people are with

their chairs. And this is just a simple exchange market. I'm going to only trade

with someone else if I'm happier and if they're happier. And so that means

happiness is going to go up. Now there's a maximum happiness which would be if

everybody had their preferred chair. Now of course, not everybody would get their

preferred chair, but there's still definitely a maximum. So if you assume

even some small cost of trading, you know, if it takes time and everything else,

you've got to push the chairs around, that means happiness is going to go up with each

trade. There's a maximum happiness. Process stops. So the boss says, that's a

brilliant idea. So we can do that, we can allocate the chairs that way. Well then

the boss says, hey, that's such a great idea. We can also do it. You can also do

it for offices. We can just randomly assign people offices, and then let people

trade. And my student said, that's a terrible idea. [laugh] The boss said, wait

a minute. Why is that a terrible idea? It was your idea for the chairs, but now it's

a bad idea for the offices. What's going on there? The student says, look, office

is different because there's externalities. It's like the North Korea/

Iraq example. So, suppose you mix your boxes, and here's, you know, me right here,

and now there's someone, let's suppose there's someone who wears a hat and this

person likes to play really loud music. Well when this person and maybe that

person wants to be next to this person over here, who's really happy and always

whistling. So there's the whistler over here and the loud music person, well the

loud music person moves into this center office because the center office, the

center cubicle because they want to be near the whistler. So there sitting near

the whistler. And they're happy, but now I'm sitting next to this person who plays loud

music. So I then, decide to, I would want to move. So I'm gonna move over here,

let's say. But maybe when I move over here, maybe I'm someone that, frequently

gets out of my cubicle and wanders around, 'cause I like to walk around when

I think, 'cause I do do that. Well, this person who's sitting here, she may not

like that at all. She may not like people who get up and wander around, 'cause that

disturbs her. So when I move here, she may wanna move someplace else. So when you

think about allocating offices, I may move someplace to be happier, but that may

make other people less happy. In fact, we saw that a little bit in the Schelling

model. Right? One person moving can cause other people to move. In the Schelling

model, the process eventually stopped. In the office case, depending on the nature

of the externalities, maybe it'll stop, maybe it won't stop. So my student

could say, here's, well we don't know for the office. This may be undecidable. In

order to know whether or not the office relocation thing will stop, we're gonna

need to know a lot about how people feel about other people and how much they care

about who their office is next to. So that leads to the deep question: When can you

decide? And can you always decide? And that's a hard question. The answer is it

depends on the problem. So in some cases you can figure out some other way to show

or prove that the process goes to equilibrium. Or in some cases you can come

up with a really sophisticated Lyapunov function to show the system goes to

equilibrium. But other problems, even what seems like incredibly simple

problems, it turns out they're very hard to solve. So let me take just a simple

instance of this. Can we know that a process stops? This is the question. Let

me take just an incredible simple instance of this to show you just how complicated

even simple processes can be. This is something called the Collatz problem.

The Collatz problem works as follows. I call it "HOTPO", half or three plus one. So

the idea is that you pick a number: if it's an even number, divide it in half. If

it's an odd number, multiply it by three and add one, and you stop, the process

stops if you ever reach one. So pick a number. It's even: divide by two. If it's

odd: multiply by three and add one. So it's going to be going down every time you

divide. It's going to be going up every time you multiply it by three. And you

stop if the process ever reaches the number one. I could ask: Does this process ever

stop? Let's do some examples to see how this works. So let's suppose we start with

five. Five's odd, so I'm gonna take three times five plus one, so that's sixteen.

Then I divide--that's even--so I divide by two, that's eight. That's even: I divide

by two, that's four. That's even: I divide by two, that's two. That's even: I divide

by two, that's one, process stops. Let's take seven; that's odd, so I multiply by

three, three times seven plus one, so it's 21, that's 22. That's even, so divide by

two, that's eleven. That's odd, so we multiply by three and add one, that's 34.

And I divide by two, that's seventeen, that's even. And it's odd, so I multiply

by three. And add one, that's 52. Even, so I divide by two. Even, divide by two,

that's thirteen. Odd, I multiply by three and add one, that's 40. That's even,

twenty. Even, ten. Even, five. And once I get to five, I know, look, sixteen, eight,

four, two, one. Process stops. So I start with five, I get to one pretty quickly.

When I start at seven, I get to one but it takes a long time. Why don't I start with

27, start with a bigger number. Well, you see, whoa, this process seems to take an

incredibly long time, it's no longer a really simple process. Turns out that

this is a very hard problem. In fact, the mathematician Paul Erdős, he's one of

the great number theorists ever, said, "mathematics is not yet

ripe for such problems". In other words, mathematics as a subject hasn't matured

enough to be able to solve this. We can put a man on the moon, but we can't solve

the Collatz problem, sort of amazing. Just to give you a sense of how

complicated this is, here's a graph of from Carnegie Mellon of all the

numbers up to 2000 on this axis. And this is how many periods it takes them to

stop in the Collatz problem. So, what you see is, you see, wow, there's a lot of

structure in here. There seems to be one set of numbers that sort of goes like this,

and then another set of numbers that sort of has this pattern, but it seems really

interesting and hard to figure out. Well, that's why we don't know. Because it's so

interesting and hard to figure out, we can't tell whether the Collatz problem

stops, and we probably can't tell where the office problem stops. But we can tell

whether the chair problem stops. That's what's so interesting. So when you think

about a model, when you think about a process like the Lyapunov process,

right? Lyapunov functions. What you've got is, you can say, hey, there some

cases like the case of chairs, a pure exchange market, this thing works great. And we can just

can say, boom, it's gonna stop, we're fine. There's other things like the office

process, that unless you know a lot about the nature of the externalities, you can't

tell. It could be, oh yeah this thing's gonna go right to equilibrium. Or it could

be that, whoa it's gonna churn a long time. Like the number 27 did, alright where it

just goes and goes and goes and goes and goes when we put in the Collatz process or

HOTPO process. Okay thanks.