0:01

Hello there. So we're going to talk now a little bit

about dynamic strategic network formation.

So add some dynamics to the process instead of just a static look at what's

stable. And looking at these dynamic processes we

can think of, of you know adding dynamics for different reasons.

you know again as I sort of mentioned earlier in the course we don't

necessarily want to just add enriched models because that adds realism.

That's not a good reason to enrich your model because it complicates the model

and we want things to be as simple as possible.

So we only want to add it if it's going to give us something that we didn't

get before. And here in particular what it's going to

do is, is begin to give us some predictions of which networks might form

when there might be multiple ones which are stable.

And you know, another possibility is that by doing this you could begin to capture

forward looking behaviour. Where people were sort of asking, well if

I do this, then what's going to happen further down the line.

We're going to start by just really focussing in on this fact that it's going

to refine static, models. And there's three different approaches to

deal with dynamics. We can think of dynamics where they are

myopic and error-prone and, and nature's just marching along.

And we're thinking about an evolution of a system or we can think of very forward

looking calculating types. And we're going to look at a fairly

myopic version of a model right now, but a fairly simple one.

So the idea here is that we're going to look at a dynamic process where people

can form links over time. And, even if there are multiple pairwise

stable networks and some of them happen to be efficient, we might not reach

those. And this process we'll look at was first

proposed by Allison Watson in 2001 and the process is really the simplest one

you can think of in terms of adding a dynamic.

Nature just finds a link, uniformly at random picks a link, and then it, it's,

then that link is added if adding that link to the current network would benefit

both individuals involved. At least one of them strictly benefiting,

and if the link is already in the network.

Then it will be deleted if it would, if deleting it would help either of those

individuals involved. So, it's basically like the pairwise

stability concept but instead we're just going to look a link at a time.

So, we start at some network randomly pick a link and then if it's already

there, we think about deleting it. If it's not there we think about adding

and then, just continue randomly picking links and, and so forth.

So now we've got a nice dynamic process, it's going to march along and then we can

ask where will it, where, where will it end.

So, first thing we can say is that any resting point, so if, if, if this process

ever stops at some network and never moves from that network.

It must be that whichever links are recognized nobody wants to add a new one

and nobody wants to delete an existing one.

Therefore it must be pairwise stable. So this process is going to identify

pairwise stable networks. It's going to come to rest at pairwise

stable networks. And so the proposition that Allison Watts

showed is an interesting one. Where, let's suppose we consider the

connections model, where c is less than delta, so it actually makes sense just to

form individual links to people you're not connected with.

But c is bigger than delta minus delta squared.

So, it stars are going to be efficient networks and a star would be pairwise

stable. So, if you actually had the center of a

star, where this sort of low to medium cost range where stars are going to be

efficient, and pairwise stable. And a point that she made is that if we

look at this dynamic process as end grows the probability that this process

actually stops at a star goes to a zero. So, even though a star would be one of

the pairwise stable networks, the chance that a process of fairly of natural.

Dynamic process is actually going to reach one of those efficient networks is

going to zero. So most likely you're going to end up

with an inefficient network. And, and let me just go through the basic

ideas here and then we can go through a short proof of this.

So the ideas of, are fairly straight forward.

So let's imagine we started at an empty network and we just start building in

these things up. So, we started an empty network and you

know, two people are, are identified. And they can form a link let's call them

one and two so that the first two people who have a chance to form a link.

Well, we're in a situation where c is less than delta, so they're going to form

that link, it's beneficial. Now another person comes along, we

recognize another link, now there's different possibilities in this, in this

setting. one is that, that somehow the link

involves two individuals other than one and two.

And those people would want to form that link if, if we happened to find three and

four they'd want to form a link because that link's not theirs and they're myopic

they think this is good, it's beneficial. They would form that link.

Already, we're on a on a path that's not going to lead to a star.

and question is we have to be careful to find out if that three, four ever be

deleted and maybe they'd form a new link to one and so forth.

But at this point the the we're on a bad tragectory we could also think of a

situation instead. Where maybe, some individuals recognized

along with the link to one or two. Okay.

So we do happen. So we do happen to, to go on a good

trajectory towards the star. And once that happens then as new links

come in, it's quite possible that the new links being recognized are not directly

to either one or two, but to somebody else.

In which case you know, we can end up having things move out in ways that are

not going to lead to a star. Okay, so the, the, the fact that people

are biopic and not necessarily thinking, oh we have to get to a star, that's the

best thing for us. Instead adding links when they're

valuable means that this thing could arise in a way that's going to look very

different from the star. And, the, you know, we would have to have

basically an order where the ordering of the links that are recognized would have

to just happen to be exactly in a configuration of a star for a star to

arise. And a that these are the links that are

recognized and not any other ones before we get to finishing it is going to zero.

So that's the basic idea behind this proposition of balance and watts.

6:54

So, you know, to be a little bit more explicit about the proof, one key

observation is in this cost range, once you have a link, you'll always have at

least one, okay. So given that c is less than delta.

It makes sense to have a connection to somebody that you don't have any other

connections with. You would never sever a link which

completely disconnects from, you, from somebody, even indirectly.

because links are, are net benefits. And so nobody would ever sever a link

that would lead a node to be isolated, okay?

So once a node is connected into the network.

They're always going to be connected into the network.

Okay, so that's the first observation. and then, so let's suppose that we act,

you know, somehow manage to reach a star. relabel, let's label the nodes as one,

whatever the node, the center was, and two through n are, are labeled at the

last date at which they connected their link to one.

Okay, so we ended up with the star formation.

So n is the last person who added a link to person one.

Okay. the observation here is that n, this last

person to connect it, couldn't have been somehow connected somewhere else in the

network already, when it attached to one. Because, n, one would have already a

distance of two. So for instance if we've got 1, 2, 1, 3,

1, 4, etc. And we go through and this is person n,

who is connected. When they formed this link, this last

link, it couldn't have been that they were already connected to somebody else

in the network. Otherwise they never would have formed

that link because they already would have been at a distance of at most two.

And we've got the it's not in one's interest to to shorten that path given

that the cost exceeds delta minus delta squared.

So it's not in person one's interest to shorten that link.

So this tells us that n couldn't have been connected to anyone before

connecting to one, okay? And if you go through you can do the

induction into the same reasoning for 'n' minus '1' etc.

Basically each link had to be formed to one directly so it has to be that the

only way this could have happened is that you had to form a star directly.

And then you just have to show that the recognizing the links to form a star, the

chance of that happens is going to be vanishing.

So you gotta form a star directly. So if ij is the first link identified,

the next one must involve either i or j, to get a star.

Right? So if, if, if this is the first link

that's recognized, then the next link that's recognized can't be some other

link. It's got to be one that goes to i or j.

Well ,there is each of these people has n minus two people they are not connected

to. So there's two times n minus two possible

links that connect to either i or j. And the, all the rest of the links.

10:39

it's looking like something one over n. It's probability is vanishing and very

tiny. So the chance that your actually form a

star is going to 0. In fact if you go through and think about

the, the probabilities that each one has to be recognized in order, the chance you

form a star when you look at all the ordering is actually even much smaller

than this. And, and it goes to 0 at a very rapid

rate. So the chance that you are hitting a

star, is, is tiny. Okay, so this was a very simple, natural

dynamic process. It finds pairwise stable networks if they

exist, and even is pairwise stable networks are efficient, if some of them

are efficient, it doesn't necessarily find them.

So what this does is tell us that when we're looking at these things, there

might be many possible resting points. it, it might not be that nature just

because something is efficient needs society to find that.

So we do want to be careful about what we think the formation process is, in order

to make predictions about what might be the outcomes.

Okay. So the next thing we'll do is take a look

at enriching these models a little bit further.

We can even add noise to these and that will give us higher predictive power in

terms of of which things we might end up at when there's multiple stable networks.