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. The fraction everybody who's in S has at least a fraction r of their neighbors in S. So that means that the set R S is r-cohesive. Everybody in that set has at least R of their neighbors in the same set. Okay, so that gives us a,a definition, and then we'll, we'll say that the cohesiveness of a given set is just going to be the lowest fraction that you can find out of all the individuals in that set of their, how many of their neighbors are in that set. Okay? So this is, the cohesiveness is this, the, the minimum across s. This is also sort of the maximal r that you could have, and still satisfy this. Right? So it's the maximal r, such that the, that s is at least is, r-cohesive. Okay. So either way we've got a definition which says how cohesive a set is. So, how, what's the fraction of everybody's neighbors who are inside that set. So, here's an example of a network, and here's a set, s. 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. 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.
