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. 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. So minus the 2 and minus 2, minus 1. All the rest of the links are, are not ones that are going to lead to the star. And so the chance that you even take this first step once you've formed one link towards forming a star. It's no more than 2n minus 4 over the number of links at that time which goes to zero at the rate 1 over n. So if you look at this it's, it looks like it's set the order of n over n squared. 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.
