0:00

Okay, so we've got some basic definitions and ideas behind us in terms of

Â understanding equilibria in network games.

Â And now we can look at a little more structure.

Â And what I want to do is, is, talk a little bit about when it is that, that

Â there's multiple different actions that can be sustained in a, a, given network.

Â So when is that it's possible that some people adopt a new technology and other

Â people don't? Or that some people are, are becoming

Â educated, other people are not, and so forth.

Â So when is it that we actually can sustain multiple actions, even when we've

Â got a lot of homogeneity in the society. Even when anybody has the same

Â preferences and so forth, we still end up with different people taking different

Â actions based on their position in the network, okay.

Â So this is just sort of an interesting question conceptually to understand when

Â this can happen. And, so lets take a look at it.

Â And what we're going to do is, is look at a paper by Steven Morris a cord, a simple

Â coordination game. And this is going to be a game where you

Â care only about the fraction of your neighbors taking a different action.

Â So you prefer to take action one if a fraction Q or more of your neighbors take

Â action one. So suppose that Q is a, a half, then if

Â you just want to match the majority of your friends.

Â So if the majority of your friends take action one, you want to do that.

Â If the majority of your friends take action zero, then you prefer to take

Â action zero. Okay?

Â So this is a game of, of strategic compliments.

Â And a very simple one where everybody just cares about the fraction.

Â So everybody's threshold is just a fraction of their degree.

Â It's the same fraction. But we could have Q be a half, it could

Â be two thirds, or maybe you need two thirds of your neighbors to take this

Â action before, you know, this new technology, before you're willing to

Â adopt it and so forth, okay? So a sim, a very simple coordination

Â game. And let me say a little bit about the

Â background of this game. the game where it's actually a half is

Â also what's known as the majority game. And this is a game which has been studied

Â quite a bit in the statistical physics literature.

Â And has some background in the, physics and, and, agent based, literatures.

Â And, you know, part of the reason is that, that, there's certain kinds of

Â particles. Where the particles might be sitting in

Â some sort of lattice structure. And the particles react to what other

Â particles are doing. So, if other particles end up in one

Â state, then they end up trying to match the state or they could end up going in

Â opposite directions, but in certain situations they'll flip into be in a

Â certain state if, if more of their the other, so as more of their neighboring

Â particles become excited, they become excited, for instance.

Â And depending on what that threshold is, then that ends up having a percolation so

Â that you can end up having this move through different kinds of of materials.

Â And so that's been an area of study in physics.

Â And this actually has a nice interesting relationship to these kinds of games on

Â networks, where an, a given node cares about what its, its neighbors are doing,

Â and would like to match actions to the neighbors.

Â And in this case, we have the simple Q which describes what's the fraction that,

Â have to take action one before I want to take action one, okay?

Â Okay. So let's, let's think about what

Â equilibria look like in this game, so we're going to look at pure strategy,

Â Nash equilibria in this type of game. And, let's let S be the subset.

Â So we've got these N agents, one through N, [NOISE] they are connected in some

Â network, right? So there's some network describing which

Â people are connected to which other ones, and so forth.

Â And what we want to do is we want to color them so that some of them take

Â action one. And we'll let s be the set of individuals

Â that take action one, okay? So what can we say about an equilibrium

Â in this game? Where S is the set of people who take

Â action one. Well, it's going to have to be that every

Â person in S has a fraction of at least Q of its neighbors in S.

Â Okay. So the only way that they're going to

Â want to take action at one, is if at least Q of their neighbors are in S.

Â Right, so, so that just follows directly out of the fact that you only want to

Â take action one here if at least q of your neighbors do.

Â And it has to be that everybody not in S, doesn't want to take action one.

Â So it has to be that everybody who's not in that set has to have a fraction of at

Â least one minus Q of their neighbors outside of S, so that fewer than Q of

Â their neighbors are in S. More than 1 minus Q of their neighbors

Â have to be outside, okay? So, for any, for, for, the set S to be

Â the group that take action one, for that to be an equilibrium, these two things

Â have to be true, okay? And basically that characterizes a set of

Â equilibria. So S is going to be in equilibrium, if, a

Â pure strategy equilibrium, if and only if this is true in this game.

Â All right? Okay.

Â So now a definition which is actually an interesting definition in terms of a

Â network what, what's known as cohesion, following Stephen Morris' definition.

Â and we'll say that a group S, some group of nodes S, is R cohesive.

Â Where R is going to be something R is going to be some number in zero to one.

Â So we've got some number in zero one. And we'll see that S is r-cohesive if

Â when we look at everybody in the set, right?

Â So look at all of the people in S. And look at what fraction of their

Â neighbors are in S. So here's how many neighbors they have,

Â here's how many of their neighbors are both neighbors and in S.

Â 7:16

Here's another set, let's call it S prime.

Â Both S and S prime are two thirds cohesive.

Â Okay, so S is two thirds cohesive, at least two thirds of this person's

Â neighbors are in the set. In fact all of their neighbors are in

Â this set. this individual has exactly two thirds of

Â their neighbors in the set. Right, so they have two neighbors in, one

Â neighbor out. So this person has two thirds of their

Â neighbors in S. Everybody else has a fraction.

Â This person has two thirds, these people have fraction one, one, one, so this set

Â is two thirds cohesive. it's also one half cohesive, right?

Â So it's at least one half cohesive. But in fact, the cohesiveness of this set

Â is two thirds. that's the maximal level at which we can

Â find that everybody has at least that fraction of their friends in the set.

Â And similarly if you look at this one this one also has two thirds.

Â Now if added say extra friendships here, these, these two people also had friends

Â here, then this one would become three quarters cohesive, right?

Â So depending on the network structure, different sets are going to have

Â different cohesiveness. But what's interesting here, is we get a

Â split in this network. Such that we've got two different sets of

Â individuals who each are having a good portion of their friends, their

Â friendships inside the set and fewer of their friendships outside the set.

Â So, when we divide this network here and here.

Â If we were playing a majority game where you just cared to match your, the, the

Â actions of your minor, your friends, we could have all these people play one

Â action, say these people all play zero. The majority of their friends are all

Â playing zero. And all these people play action one,

Â right? That's one possibility.

Â So now we have a situation where we can have different actions played on the same

Â network, partly because we have a split in this network, a segregation where each

Â of these groups is sufficiently cohesive. Okay, so equilibria where both strategies

Â are played. we go back to Morris' paper.

Â There exists a pure strategy equilibrium where both of the zero and one actions

Â are going to be played if and only if there's a group S, such that that group

Â is at least Q cohesive. And such that its complement is at least

Â one minus q cohesive, right? So it has to be that everybody in that

Â set has at least q of their neighbors. So, this group S is going to be the group

Â that plays action one. They want to play action one if and only

Â if at least q of their neighbors do. So that set has to be q cohesive.

Â Everybody has to have at least q of their neighbors in that set.

Â 10:14

The compliment of S, has to be the people playing z, action zero.

Â So none of them can have more than Q of their friends in, in the set.

Â So that means that they have to have at least one minus Q of their friends

Â outside. So this proposition just follows pretty

Â much directly from the definition of the game and it's a very simple, straight

Â forward calculation. But what it does, is it, it shows that

Â this, now we've got a, a notion of cohesiveness of groups inside a network

Â which is going to be very useful in identifying when you can sustain multiple

Â equalibria in a, in a game. Okay, so let's talk a little bit about

Â how this relates to homophily. So for instance is Q is equal to half and

Â players want to match the majority then two groups that have more self ties than

Â cross ties, is that's going to be su sufficient to sustain both actions and

Â equilibrium. So, when we're looking you know, at, at

Â games where we've got you know, people really caring about matching most of

Â their neighbors, we can get different actions played in different parts of the

Â network, if the groups are sufficiently splintered.

Â Now as Q rises, so you need a higher and higher fraction of your friends in the

Â set in order to, to want to play action one.

Â Then you're going to need more homophily, more of a, a stronger split in the, in

Â the structure. So you have to have some group, which is

Â really highly cohesive in order to sustain both actions.

Â So for instance, if we go back to what we saw in the ad health data set this is a

Â situation where we basically have a strong split between a group of nodes

Â over here and another group of nodes over here.

Â And so this would be a situation where you could imagine different behaviors.

Â In particular largely categorized by races being sustained here even if the,

Â the people started out identically but, except they paid attention to who their

Â friends were. Friends here tend to be correlated with

Â race and if they then wanted to match the behavior of the majority of their

Â friends, you could end up with a situation where they had very different

Â behaviors sustained by different groups within the same, network.

Â And so that's, what we get out of that theorem or proposition.

Â So, so here we've got, you know, so far we've looked at understanding equilibria,

Â strategic compliments, there's a lot that, that has nice structure to it, and

Â we can begin to understand things. It relates back to the network structure.

Â It begins to relate back to things like homophily in terms of when is it that we

Â can sustain multiple actions and so forth.

Â what we will begin to do next, we'll take a look at one quick application of this

Â and then we'll start looking at games with richer action spaces.

Â So, mostly what we're looking is sort of zero one games.

Â We'll look at some other games that have richer actions.

Â But before that we'll, we'll take a quick look at an application of this.

Â