0:00

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.

Â 7:04

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.

Â 10:45

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.

Â 12:54

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.

Â 15:25

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.

Â