Hello folks. And we're back again.

And I want to talk a little bit more about dynamics and network formation.

And in particular adding a little bit of noise to the dynamic process, and that

actually has some nice properties to it. So, let's have a peek so we're going to

talk about stochastic evolution of networks.

And we'll start with a concept which we called improving path.

And this comes out of, of work with I did with Alyson Watts, so it's Jackson and

Watts 2002. And the idea here is we've got this

sequence of adjacent networks. And just as, as in the process we talked

about just before. you could, you add a link if it benefits

both. at least one strictly.

Delete a link if either person benefits from its deletion.

But what we're going to do now in terms of, of looking at these paths is we're

going to noise them up a bit. So first let's just make sure that we've

got the concept of improving paths down. And the idea here is, we can look at say

a simple example. everybody disconnected has a value of

zero. So now what we're going to do is we're

going to have a diagram where we've got a bunch of different possible networks

there. And we're just going to keep track of

what the improving deviations would be. So from here you can think of, of adding

links. adding one link between any of the two

players. Then you can think of adding, you know,

another link so you got two links or going to the complete network.

And the payoffs here are telling us that players either get zero from the empty

network. a single link in isolation is not

worthwhile. You only get a value of minus one.

Once you form two links, then it's valuable and three links is the most

valuable. And what the arrows do here is represent

the changes that would be value improving for people.

So, if you were in a situation where you had one link, then you could benefit by

either severing that link and going to zero.

Or if the possibility of adding a new link arose, then you would want to add

either of the links that weren't there that would also be improving.

So, there'd be three different ways to get out of this.

They would all be improving. So, that's the notion of improvements.

And the arrows point here in the directions of improvements.

So the idea of improving paths is going to be that there are paths here in this

setting where everybody does better along each step.

So that improving path from this network to the complete network would be one that

passed through adding one link and then adding a second link.

So if we follow these arrows, we've got a series of path where each choice is an

improvement. And there's also improving paths leading

in this direction. So for many of these networks, you can

have an improving path leading down to the empty network.

So, in this situation there's actually two set of Pairwise Stable Networks.

And in fact, they're both Pairwise Nash Stable Networks.

So we've got the end points here, the empty and full and networks being stable.

And there's improving paths leading from different networks to one or the other of

these depending on which situation you're in.

Okay, so that's the concept of improving paths.

And what we're going to do now is, So we've got two Pairwise Nash Stable

Networks, these end points. Right?

Are both Pairwise Nash Stable and there's a question of, well, is one of them more

realistic as an outcome than the other? And in, in fact they're both strict

equilibriums, so if you were here, nobody would, would want to add a link.

It, it's strictly costly to them to do so.

and here obviously if you, anybody deleting a link is strictly costly.

So, just looking directly at these concepts and actually even adding

strictness isn't going to give us predictability.

so what we're going to do is add some trembles and errors to these improving

paths. So, we'll start at some network and with

equal probability look at any one of its links just like we did before.

We'll add that link if it's not present and both people want to add it.

We'll delete it if it's not there and, er, if it is there, and somebody benefits

from deleting it. but the key thing is we're going to

reverse the above decision with some probability epsilon.

So it'll be a probability epsilon greater than zero, that for whatever reason,

somebody makes a mistake. And when they want to add a link, they

don't or when they want to delete a link, they don't.

or a link that's beneficial gets deleted or a, a link that's not beneficial gets

added. Right?

So, so we're in a situation where some link is recognized.

People want to do one thing with it. Either keep it or get rid of it, or add,

it and the decision is reversed. Okay.

So whatever decision is made, it's reversed with some probability epsilon.

And we'll think of this as a small probability.

So there's some chance that people make errors but most of the time they'll make

the improving choice. Okay?

So, what this does is it adds these trembles and errors to improving paths.

and what this produces is now, this process is going to, as, as long as

there's errors, there's always a chance that you're going to keep moving around,

right? So, you're never going to stay anywhere

forever. And, you can get from any network to any

other network through a series of errors and improvements.

And so, this is a finite state. There's a finite set of possible networks

you could be in. it's irreducible, in the sense that from

anyone you can get to any other one, and it's aperiodic.

You could move in odd cycles, even cycles.

So this is a very nicely behaved Markov chain.

Ones that we know a lot about in terms of theory.

It's going to have a nice distribution over how much time you'll spend at each.

So, pro, given epsilon and we'll have an idea of how much time you would spend at

each network in this process over time. There's a steady state distribution which

gives us the long-run distribution of how much time you'll spend at each one of

these networks. So, lets have a look in more detail at

this process. So, what we've got, when we've noised up

our improvement paths, let's suppose we're here.

We're at the empty network. Well, now with probability one third, any

one of these links could be recognized. So, what's going to happen is, if we

recognize a link, they don't, it doesn't want to be added but with a probability

epsilon it would be added. So, there's a probability of one third

epsilon that you would end up recognizing this link and adding it by accident.

There's a probability one third epsilon that you would move here.

And a probability one third epsilon that you would move in this direction.

So, from a network with zero links there is a probability of epsilon that you go

from zero links to one link. And there's a probability of one minus

epsilon that you'd just stay there. Okay?

And, and so forth. If we're here with two, two, with three

links. Then there's a probability epsilon that

you go from three to two and the probability of one minus epsilon that you

go from three back to three. And so forth, okay.

And so from, from one of these networks there's a one third times one minus

epsilon chance that you go to the complete network.

There's a one third chance times epsilon you go and delete a link that you wanted.

one third chance times epsilon here and so forth.

So, for each one of these things we can figure out what's the probability that

you move from a network with zero links to one with one.

From one with one, to two, and so forth. So instead of keeping track of all of the

networks, let's just keep track of them in terms of how many links they have.

So zero links, one link, two links, three links.

And what's the probability that we move between those?

Okay. Well, you can, you can keep track of

that. What's the probability that you move

from, from any one to any other one. And we can go through, you know, the

probability that you went to one with zero to one with zero, with one, with

two, with three. So you can't move directly to two links.

if you have one link. there's a third of a chance any one of

the ones you recognize you could go back to to zero.

There's an epsilon chance you stay where you are.

there's a two third chance that you recognize one of the links that you

want to add and go to a two link network and so forth.

Alright, so we got a chance this matrix keeps track of what's the probability

that if you currently have zero, one, two, or three links that you transition

to a different state in the, in the next period.