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.