Refinement of pairwise stability, an alternative way of modeling network formation, this is known as pairwise nash stability

Strategic Formation Models

  • Saw conflict between stability and efficiency
  • Can Transfers help?
  • Modeling Stability and Dynamics, etc
    • Refining pairwise stability
    • Dynamic processes
    • Forward looking behavior
  • Directed Networks
  • Fitting such models

Modeling Stability

  • Beyond Pairwise Stability - Allowing other deviations

    • multiple links by individuals
    • coordinated deviations
  • Existence questions

  • Dynamics

  • Stochastic Stability

  • Forward looking behavior

  • Directed Networks

Nash equilibrium

  • Myerson's announcement game
  • Players simutaneously announce their preferred set of neighbors $S_i$
  • g(S) = {ij : j in $S_i$ and i in $S_j$}

    • the network forms as a function of the profile, the full vector of all the announcements made by different individuals, are the links such that j was named by i and i was names by j, so this is consensual network formation, you form a relationship if and only if both people named each other.

Nash Stability

  • Nash stable, $u_i(g(S)) \ge u_i(g(S'_i, S_{-i}))$ for all i $S_i'$

    • $u_i(g(S))$ is a situation where the utility that a given individual get from the network that forms under the announcements that are there is at least as good as anything that could get by changing their announcements($u_i(g(S'_i, S_{-i}))$), so they might want to announce for instance that they can't add some new links, announcements that they didn't make and do better and they can delete some of the announcements they did make and do better.
  • So g is Nash stable if and only if no player wants to delete some set of his or her links

    • So Nash stability basically looks at a given network and says "Does anybody want to take some subset of links that are there and delete them?". So the set of all Nash equilibria of pure startegy Nash equilibria could be of this game are going to be equivalent to the networks where no player wants to deviate from the links that they have and delete some of them. But it doesn't ask about adding mutually.

Why is this Nash stable? This is sort of a coordination failure. Nobody manages to name anybody else and nobody thinks anybody is going to name it anybody else. So everybody, each Si is equal to the empty set. Nobody names anybody and now if nobody named me I can't form a link anyway so I might as well name the empty set. This is a Nash equilibrium. These two players are getting one. They don't want to deviate and the third player doesn't make any sense, they're happy. This is a Nash equilibrium, everybody's getting one, there's no better payoff they could get. This one is not and why isn't it? Well this person must be announcing. So if you call this player one, player one must be announcing player two. They could deviate and not announce player two and they would be better off because their pay off would go from minus one to one. So this one is the only one that's not finished.

If we look at the pairwise stable networks here. Well this one's not pairwise stable, right? So this is not pairwise stable for the same reason it wasn't Nash stable. This person can delete a link. This one is not pairwise stable because these two individuals would both strictly gain from adding a link so pairwise stability rules this one out whereas Nash stability did not. And that was part of the reason that we wanted pairwise stability because it eliminated this problem that we have with coordination failures leading to networks that really don't make a whole lot of sense in terms of if anybody really can communicate. They'd rather form the links that are giving them positive payoffs. This one's clearly going to be pairwise stable because it gives everybody a maximum payoff. There's no better thing they could do. What about this one? Is it pairwise stable? Well, if we think about deleting a link, nobody wants to delete a link, do any two players want to add a link? Well if they added a link, so if these two players added the link for instance, what would happen? They would go to payoff of minus one so indeed this one is pairwise stable. They wouldn't want to do that. And this one is pairwise stable. So what we end up with is a situation where we have three Nash stable networks and then two pairwise stable networks so the pairwise stable networks are picking a subset of what the Nash stable networks are. And so we could ask which ones are both pairwise stable and Nash stable. It will be these two and those we could call pairwise Nash stable networks. Well, here pairwise stability already was just picking a subset so there wasn't really any reason to look at Nash stability in addition to pairwise stability because it wasn't narrowing things at all. But more generally, if we look at pairwise Nash stability, so we ask for something to be both pairwise stable and Nash stable, we can end up in some cases with more of a refinement.

Pairwise Nash Stability

  • Both pairwise stable and Nash stable

  • Captures multiple link changes

  • Other variationis: e.g., allow addition of link plus deletion of others at same time, larger coalitions...)

So here's a situation where if everyone is separate they get zero as before. One link leads to payoff of one. Here this situation is one where two links together lead to minus two and three links together lead everyone to a payoff of minus one. So in this setting, when we look at the Nash stable networks, this is slightly different than our previous example. The only ones that are Nash stable are this one and this one. So we've got this one, we still get the problem of a coordination failure, we're getting the Nash stable here. This one is also Nash stable. This is not Nash stable anymore because now somebody could just sever both of their links and get a zero instead of a minus one so they would be better off. And this one's clearly not Nash stable because by severing both links and getting zero they'd be better off as well. So in this situation what we end up with is the only Nash stable networks are the two at the bottom. And when we look at pairwise stability we end up with this one being pairwise stable. Nobody wants to add or delete a link from here, that's clear. That's the maximum possible payoffs that people could get. But this one ends up being pairwise stable as well. And why is that? Well if anybody deleted one of their links, just severed one link, they would end up getting a minus two. So they would end up being at the end of a triangle, they would go to a minus two payoff. And so they don't want to sever a single link even though they could benefit from severing multiple links. So pairwise stability was only looking one link at a time and it didn't allow people to say "Oh look I'd be better off severing two links so Nash stability allows for multiple link changes but then has this coordination failure problem. Pairwise stability one looks one link at a time and so might miss some deviations where you could delete multiple links and be better off. But putting them together in this case we end up with a simple conclusion that seems to sort of be the right network in this setting to expect a form which is the one that's both pairwise stable. So nobody wants to add a link and nobody wants to delete multiple links. And that combination of pairwise Nash stability ends up being more selective than either of the two and in some senses is picking out a more sensible prediction in this particular example. So that's useful to have some refinements of pairwise stability alternative methods of modeling network formation and, you know, it captures these multiple linked changes. You could do all kinds of other variations, you could allow additions of links plus deletions of some links, you can allow larger coalitions. So there's a whole series of different ways in which you can embellish these definitions.