Games on Networks - Outline¶
Basic Definitions
Examples
Strategic Complements / Substitutes
Equilibrium existence and structure
Equilibrium response to network structure
Complements/Substitutes¶
look at the payoff that a given individual of degree d gets from taking action 1 compared to action 0, let's think of starting with some number of neighbors m' taking it, and then increasing that number to m, $m \rightarrow m'$, as we increasing the number of friends taking this action, what ends up happending to this person's incentives to take it.
- strategic complements -- for all d, $m \ge m'$
- Increasing differences" $$u_d(1,m) - u_d(0,m) \ge u_d(1, m') - u_d(0, m')$$
the idea behind strategic complements is that we end up with a 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 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. So that's called increasing differences, this is strategic complements. There is a positive relationship between number of people that take the action and my incentives to take it.
- strategic substitutes -- for all d, $m \ge m'$
- Decreasing differences: $$u_d(1,m) - u_d(0,m) \le u_d(1, m') - u_d(0, m')$$
Strategic substitutes just reverse this, and effectively as more people take the action, as we move from $m' \rightarrow 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 realationships.
Externalities¶
Others' behaviors affect my utility/welfare
Others' behaviors affect my decisions, actions, consumptions, opinions...
- others' actions affect the relative payoffs to my behaviors
(Strategic) Complements/Substitutes¶
Complements: Choice to take an action by my friends increases my relative payoff to taking that action (e.g., friend learns to play a video game)
Substitues: Choice to take an action by my friends decreases my relative payoff to taking that action (e.g., roommate buys a stereo/fridge)
Examples¶
Complements
- education decisions : care about number of neighbors, access to jobs, etc. - invest if at least k neighbors do
- smoking & other behavior among teens, peers,...
- technology adoption - how many others are compatible...
- learn a language...
- cheating, doping
Substitutes
- information gathering: e.g., payoff of 1 if anyone in neighborhood is informed, cost to being informed (c<1)
- local public goods (shareable products...)
- competing firms (oligopoly with local markets)
- ...
Equilibrium¶
Nash equilibrium: Every player's action is optimal for that player given the actions of others
Often look for pure strategy equilibria
May require some mixing
Best shot¶
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 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.
Maximal independent set: each person who's actually taking the action(1) has no 1's in its neighborhood, each 0 has at least one 1. So maximal independent set, it corresponds exactly to the pure strategy equilibria of this best shot public goods.
Different distributions of utilities, and different total costs.
- 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. 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 (pic 1). This case, we get one person at the 1 minus c, and five people getting the value of 1 (pic 2). 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.
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, does one of the individuals on the outside here (left node in pic 1), does this individual want to change their action? Well, if they change to a 0 as well, they're going to 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 (the center of pic 2), 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.
Maximal Independent Set¶
Independent Set: a set S of nodes such that no two nodes in S are linked
Maximal: every node in N is either in S or linked to a nose in S
Useful Observation¶
Complements: there is a threshold t(d), such that i prefers 1 if $m_{N_i} > t(d)$ and 0 if $m_{N_i} < t(d)$
Substitutes: there is a threshold t(d) such that i prefers 1 if $m_{N_i} < t(d)$ and 0 if $m_{N_i} > t(d)$
Can be indifferent at te threshold
threshold is 2, same for all the agents here, so it's independent of their degree
Same network, here's 3 different equilibria
lattice structure to set of equilibria