Learn how to model social and economic networks and their impact on human behavior. How do networks form, why do they exhibit certain patterns, and how does their structure impact diffusion, learning, and other behaviors? We will bring together models and techniques from economics, sociology, math, physics, statistics and computer science to answer these questions. The course begins with some empirical background on social and economic networks, and an overview of concepts used to describe and measure networks. Next, we will cover a set of models of how networks form, including random network models as well as strategic formation models, and some hybrids. We will then discuss a series of models of how networks impact behavior, including contagion, diffusion, learning, and peer influences. You can find a more detailed syllabus here: http://web.stanford.edu/~jacksonm/Networks-Online-Syllabus.pdf You can find a short introductory videao here: http://web.stanford.edu/~jacksonm/Intro_Networks.mp4
4.11: Dynamic Strategic Network Formation (Optional/Advanced 11:57)
Loading...
From the course by Stanford University
Social and Economic Networks: Models and Analysis
316 ratings
From the lesson
Strategic Network Formation
Game Theoretic Modeling of Network Formation, The Connections Model, The Conflict between Incentives and Efficiency, Dynamics, Directed Networks, Hybrid Models of Choice and Chance.
Meet the Instructors
Matthew O. JacksonProfessor
Economics
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.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
