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.

Â