Okay, folks, so let's talk about a little more structure about games on networks and understanding how we can understand how the play in games relates to the structure of the payoffs and the structure of the network. And, what we're going to do is differentiate between what are known as strategic complements and strategic substitutes. And so let me just give you a little more detail on this. So we've gone through just basic definitions and some, a couple of examples, and now we're going to talk more explicitly about the difference between strategic complements and strategic substitutes, and that will allow us to talk a little bit more about how equilibrium behave in these games and how that relates to network structure. Okay, so, basic idea behind strategic complements is that these are kinds of behaviors that, as more of my friends take the action, I'm more likely to, it's a more attractive action to me. And strategic substitutes are as more of my friends take the action, it's a less attractive action for me to take. So, in particular, the way that this works is we look at, look at the payoff that a given individual of degree d gets from taking action 1 compared to action 0. And let's think of, of, starting with some number of neighbors m prime taking it, and then increasing that number to m. So, we go up from m to m prime. And we ask, as we increase the number of friends taking this action, what ends up happening to this person's incentives to take it. And the idea behind strategic complements is that we end up with a higher, weakly higher payoff on the left-hand side. So, it's become weakly more attractive for me to take this action than it did before. So the more friends who take it, as you increase the number of friends who take the action, then the payoff to taking the action compared to not taking the action has gone up. So the difference between taking the action and not taking it, it's more attractive than it was before. Okay? So that's called increasing differences this is strategic complements. There is a, a positive relationship between number of people that take the action and my incentives to take it. Strategic substitutes just reverse this, and effectively as more people take the action, as we move from m prime to m, it becomes less attractive to take the action. So this was the borrowing the book. As more of my friends have the book I can borrow it. It's easier for me to borrow it, it's less attractive for me to purchase it myself. more in other cases, if you know, more of my friends are learning a new language or were adopting a new technology, it could become more attractive for me to do that. So, in this case we have different complements, positive relationships, substitutes, negative relationships. And, you know, we can talk about strict, make these strict inequalities as opposed to weak inequalities, and then we can call, say that they're strict strategic complements, and strict strategic substitutes. Okay. So you know, obviously this is going to be a setting where there's externalities. And there's externalities because others' behaviors affect my utility or my welfare, my choices. So there's externalities present. And the, the, the ways in which people's decisions are being influenced depend on what other, actions, other people are taking. And in particular, what's important in this setting is not only that other people's actions affect my payoffs. But they affect my relative payoffs. Right? So, in order for it to affect my behavior. It has to affect the, the difference in, in utility I get from one action versus another. Otherwise it just could make me better off or worse off but doesn't effect what I want to do. Here what's going to be important in terms of the externalities in, in the game setting, is that it effects the relative payoff, so it can actually change how I want to behave. So when we think about complements and substitutes, there's these externalities present because it not only affects my pay offs, but it affects my relative payoffs. So more friends taking an action increases my relative payoff. So, more friends playing a particular video game, it makes it more attractive for me to play that video game. more of of my friends buying, you know my roommate buys a stereo or a fridge, or my roommate buys a book then I can borrow it. Those are going to be strategic substitutes. In terms of examples, examples of this abound, and that's why it's interesting to, to look at these things and to try and understand. How people are going to make decisions in situations where there's essentially a game on the network being played. So let's just start with some you know, basic examples. Education. So, whether or not a person goes to university, how, how much human capital they get, what kinds of courses they take. they'll care about the number of, of their friends who do it. So, you could care about it because you enjoy taking classes with your friends. that you know more about what classes are available if you have friends. That you get, learn more about what the payoffs are to becoming educated. That you have increased access to jobs. So the more people that you know that are well-educated and well-placed in society, the more attractive it becomes for you to become educated and, and to invest in your human capital. So education decisions are something that tend to be complements. Smoking and other behavior among teens, delinquent behavior, a whole series of things where there's sort of a peer influence. where the person feels more comfortable or more pressure to act in a certain way as the crowd grows. technology adoptions is another good example. So which technology you adopt, which you take up, the relative attractiveness of one versus another, depends on how many people are using that. Learning a language is another. Now let me, sort of emphasize one which I think is very interesting. cheating or doping are also things that tend to be strategic complements. So if you're in competition with a bunch of people, and they start you know, you're in a sport and people are taking performance enhancing drugs. Then the incentive for you to do so goes up. Because, if they are, then in order for you to compete you have to to, and so, the relative payoff of taking the drugs versus not can go up as more people take the drug. Now, this is sort of an important example, because actually, it points out the fact that you can still have strategic complements. The more people do something, the more you have an incentive to it. Even though it doesn't necessarily have to be true that the more people do it, the better off you are. Right? So having more people, take performance-enhancing drugs doesn't make it better for an athlete. They're not happier because that happened. But, it makes them more likely, or it gives them a higher relative payoff from doing it themselves. So, that could be a situation where you actually have negative externalities, but the externalities are such that the relative pay off from acting in one way versus another is going up as more people do it. So even though they're, they're causing harm, it's actually giving you more of an incentive to act in the same way. So strategic complements does not necessarily mean that the, the externalities are positive. It just means that the relative change in the attractiveness of a certain thing is positive as more people do it, okay? And that's a very important distinction. And one that you have to think about for a while to really wrap your head around. But it's an important distinction, okay? Substitutes, things like information gathering. So if, if one of my friends learns how to do something, maybe they can help me out, I don't have to spend time doing it myself. you know, local public goods, so shareable products, things like, you know, my, my friend buys the book, they buy a CD they download some music, and I can download it as well. there's also situations where the, this applies in competing markets. So, firms say competing in certain kinds of oligopolies the more that they're neighbors or their competitors actually act in a certain market, it might make them less likely to act in that market. So there, there can be certain situations of competition, which'll look like strategic substitutes. That depends very much on the setting, but that'll be another example that fits into this setting. So these are some basic examples. What's important to get, take away from this is that two things. One is that there's an enormous number of applications where people's decisions depend on what their friends are doing. Secondly, that a lot of these break into one of the two categories where incentives are either moving up, the more people who take the action the more one wants to do it, or down in the opposite direction. And so that means that there's a lot of structure on these games that we'll be able to take advantage of, in doing our analysis. Okay, so the next thing we'll talk about then is equilibrium existence and structure given that we have some definitions of strategic complements and substitutes in, in play. We'll look at those kinds of examples and understand what they look like. Okay, so the, the basic notion of equilibrium that we're going to use in, in understanding behavior, is the canonical solution in game theory, known as Nash Equilibrium after John Nash. and the idea here is that, it's, it's a very simple concept. so what we want to look for is a set of behaviors. So we, we want to say what is each person doing? And the Nash Equilibrium is a situation where each person's choice is the best that they could do given what all the other people are doing. So, if someone of my friends buys the book, I don't want to. If none of my friends buys the book, I do want to. Okay? So that's, the basic idea. if you want to learn a lot more about game theory, I've been teaching a, a game theory online course, with, Kevin Leyton-Brown and Yoav Shoham. you can find out a lot more about Nash Equilibrium there. For our purposes here, we just need some fairly simple ideas. And we're going to focus in on Nash Equilibria. we're going to focus in on situations where people don't randomize. So, generally we're going to look for what are known as pure strategy equilibria. So each person is just going to make a choice, they either buy the book or they don't. They're not going to be flipping coins over whether they buy the book. And then based on that we'll be able to make predictions of, of what is the outcome. Okay, so let's have a look at here's an example of a best shot public goods game. And in particular, this is a game, so here in this network, we have a situation where we have six different individuals. And we have equilibrium, pure strategy equilibria. Each person, remember the best shot public goods game. I want to buy the book if none of my friends do I don't want to buy the book if anyone does. So this would be a pure strategy [UNKNOWN] Nash Equilibrium. Each one of these people buys the book, the center doesn't, he free rides. Another equilibrium would be that the center buys the book and none of the neighbors do, they all kind of borrow it. And, in each one of those cases, nobody wants to change their action, right? So if we go back and we look at this case over here, we can ask, okay, does one of the individuals on the outside here, does this individual want to change their action? Well, if they change to a 0 as well, they're going to go, get a payoff of 0 so right now their payoff is 1 minus c, right, from the best shot public goods they're getting let's erase that, 1 minus c. And if they change to a 0 instead, they'll get a 0. They're better off staying at where they are. What about this individual, they're getting a payoff of 1. If they bought the book instead, they would get a payoff of 1 minus c. 1's greater than 1 minus c, they're better off sticking where they are. Okay? And so you can go through that as long as you have a neighbor buying the, the, the good, you're getting a payoff of 1, you don't want to change your action. If you don't have any neighbors buying the good, then you do want to buy it because you're getting 1 minus c, which is greater than 0. So they stick with it. This is a situation which is not an equilibrium. Right? This one's not an equilibrium because these two people both buying the good, one of them should stop and not buy the good. So, that's the equilibrium in the best shot public goods game. Interestingly enough this actually relates very closely to a nice concept from graph theory. which is known as a maximal independent set. So what's a maximal independent set? A maximal independent set, an independent set of nodes is going to be ones where you've got a set a nodes such that none of its neighbors are in the set. Okay, so here, what we've got is, we've got each person who's actually taking the action has no 1s in its neighborhood. So an independent set is going to be the set of people who are taking action 1. We want to find the ma, set which has all of those people such that none of their neighbors are in there. And, moreover, that any of the other nodes that we haven't got in this set, so here, this is a maximal independent set. All, we put all these people in their set. None of their neighbors are in it. And moreover, if we look at anybody who is not in the set, they have neighbors in the set already. Okay? This is also a maximal independent set. This person, if we put them in the set they don't have any neighbors in the set. Each one of these other individuals already has a neighbor in a set, so we couldn't add them to the set without having two connected people be in the set. This is not a maximal independent set, because each person already has a neighbor in the set. Okay, so maximal independent set, it corresponds exactly to the pure strategy equilibria of this best shot public goods. Now one thing that's sort of interesting about this is it leads to very different distributions of utilities and different outcomes for the society. Right? So if we look at this in this particular case well, what's going to happen here? Here we have five people expending the cost, c, so we get five people of 1 minus c, and one person at a value of 1. This case, we get one person at the 1 minus c, and five people getting the value of 1. So, from a society perspective, this is a lot less wasteful. Less cost is being expended here, unless you're the bookseller. so here, we're dealing with a situation where the overall welfare is better. So these can have very different distributions, even though they're both equilibria, even though they're both maximal independent sets of the graph. So these games can have different payoff consequences and multiple equilibria, in this setting. Okay, so maximal independent set again, a set of nodes such that no two nodes in the set are linked to each other. Its maximal in the sense that, what we're looking at in maximal independence sets, every node in n is either in s or already linked to a node in s, so you couldn't make s any bigger and still have it be independent. Okay, one other useful observation on games on networks, When we're looking at games of complements and games of substitutes, there's going to turn out to be thresholds, which are very useful. And, in particular, if we're dealing with a game of complements, there's going to be some threshold number, such that if more than that number of my neighbors take the action, then I prefer to take the action. And if fewer than that number of my neighbors take that action, then I prefer not to. Okay? So there's some number, depending possibly on my degree. So there's a number 3. That if at least 3 of my neighbors want to do it, I want to do it. If fewer than 3, then I don't want to do it. So directly from the definition of complements, we can translate that into a threshold. The threshold might differ by a degree. So, if I, if I really care about how, what's a fraction of neighbors, so let's say I want half my neighbors. Then if I have degree 10, the threshold's going to be 5. If I have degree 100, the threshold's going to be 50. So, it could be that this threshold is a fraction. It could be that it's an absolute number. So if it's playing bridge, maybe I just need three friends to play bridge before I want to do it. And it doesn't matter whether I have 10 friends or 50 friends or 100 friends. I'll still want to do it if at least three of my friends do. So, you can have different thresholds. The, the particulars of this are going to characterize what's special about that game. What is it about that game that's different from other games, that's going to be captured in the threshold. And then the network structure will give us exactly how that's going to play out in a particular setting. Substitutes, exactly the opposite, right? We're just going to reverse the inequality so there's a threshold such that if fewer of my friends take it then I want to take action 1, and if more than that threshold of my friends take it, I want to take action 0. Now it's possible for me to be exactly indifferent at the threshold,so depending on the game, you could have me be indifferent or you could have me care strictly one way or another at the threshold. that's sort of a minor, more minor detail. Okay, so let's have a look then at a game of complements. And here's a game where the threshold is 2. And so what we've done is we look at different examples. Same network. And here's three different equilibria, right? So threshold is 2 and the threshold's the same for all of the agents here, so it's independent of their degree. So, if at least two neighbors take the action, you want to take the action. Nobody taking the action, check that that's in equilibrium. Three people taking the action, these three taking the action. That's an equilibrium. Nobody else taking the action, nobody else has at least two neighbors doing it. All of these people taking the action. So these six people taking the action and nobody else taking it is also an equilibrium. Okay, there's three pure strategy equilibria. see if you can find a fourth, there should be a fourth one here. So look for the fourth equilibrium, that's, there's four pure strategy equilibria in this. And there's also what's known as a lattice structure of equilibria, so that's something we'll talk about in a little bit. But there's a nice, actual structure to this. It makes it easy to find equilibria in this particular game. So games with complements are going to be very well duh, vuh, behaved, there. So what we've done is we've defined strategic substitutes and complements. We've taken a look at some notions of equillibria, taken a look some examples and now we'll talk a little bit more in detail about the structure of these equillibria and so forth.
