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.