Ah…strategic action on network topologies. There is a wily problem. Tons of work has gone into the problem of strategic action on networks in the past 15 years, and I think it’s safe to say that the vast majority is either trivial or has proved too hard of a problem to say anything useful at all. This recent paper by Jeanne Hagenbach is a nice exception: it’s not all obvious, and it addresses an important question.
There is a fairly well-known experimental paper by Bonacich in the American Sociological Review from 1990 in which he examines how communications structure affects the centralizing of information. A group of N players attempt to gather N pieces of information (for example, a 10-digit string of numbers). They each start with one piece. A communication network is endowed on the group. Every period, each player can either share each piece of information they know with everyone they are connected to, or hide their information. When some person collects all the information, a prize is awarded to everybody, and the size of the prize decreases in the amount of time it took to gather the info. The person (or persons) who have all of the information in this last period are awarded a bonus, and if there are multiple solvers in the final period, the bonus is split among them. Assume throughout that the communications graph is undirected and connected.
Hagenbach formalizes this paper as a game, using SPNE instead of Nash as a solution concept in order to avoid the oft-seen problem of networks where “everybody do nothing” is an equilibrium. She proves the following. First, if the maximum game length is at least N-1 periods, then every SPNE involves information being aggregated. Second, in any game where a player i could potentially solve the puzzle first (i.e., the maximum length of shortest paths of player i to other players is less than the maximum time T the game lasts), there is an SPNE where she does win, and further she wins in the shortest possible amount of time. Third, for a group of communication networks that includes graphs like the tree and the complete graph, then every SPNE is solved by some player is no more than N-1 periods. Fourth, for other simple graph structures, there are SPNEs for which an arbitrary amount of time passes before some player solves the game.
The intuition for all of these results boils down to the following. Every complete graph involves at least two agents connected to each other who will potentially each hold every piece of information the opponent lacks. When this happens, we are in the normal Game of Chicken. Since the problem has a final period T and we are looking for SPNE, in the final period T the two players just play chicken with each other, and chicken has two pure strategy Nash equilibria: I go straight, you swerve, or you go straight and I swerve. Either way, one of us “swerves”/shares information, and the other player solves the puzzle. The second theorem just relies on the strategy where whichever player we want to solve the puzzle refuses to share ever; every other player can only win nonzero payoff by getting their information to her, and they want to do so as quickly as possible. The fourth result is pretty interesting as well. Consider a 1000 period game, with four players arranged in a square: A talks to B and D, B talks to A and C, C to B and D, and D to A and C. We can be in a situation where B needs what A has, and A needs what B has, but not be in a duel. Why? Because A may be able to get the information from C, and B the information he needs from D. Consider the following hypothesized SPNE, though: everyone hides until period 999, then everyone passes information on in 999 and 1000. In this SPNE, everyone solves the puzzle simultaneously in period 1000 and gets one-fourth of the bonus reward. If any player deviates and, say, shares information before period 999, then the other players all play an easily constructed strategy whereby the three of them solve the following period but the deviator does not. If the reward is big enough, then all the discounting we need to get to period 1000 will not be enough to make anyone want to deviate.
What does this all mean for social science? Essentially, if I want information to be shared and I have both team and individual bonuses, then no matter what individual and team bonuses I give, the information will be properly aggregated by strategic agents quite quickly if I make communication follow something like a hierarchy. Every (subgame perfect) equilibrium involves quick coordination. On the other hand, if the individual and team bonuses are not properly calibrated and communication involves cycles, it may take arbitrarily long to coordinate. I think a lot more could be done with these ideas applied to traditional team theory/multitasking.
One caveat: I am not a fan at all of modeling this game as having a terminal period. The assumption that the game ends after T periods is clearly driving the result, and I have some hunch that simply using a different equilibrium concept than SPNE and allowing an infinite horizon, you could solve for very similar results. If so, that would be much more satisfying. I always find it strange when hold-up problems or bargaining problems are modeled as having necessarily a firm “explosion date”. This avoids much of the great complexity of negotiation problems!
http://hal.archives-ouvertes.fr/docs/00/36/78/94/PDF/09011.pdf (2009 WP – final version with nice graphs in GEB 72 (2011). Hagenbach and a coauthor also have an interesting recent ReStud where they model something like Keynes’ beauty contest allowing cheap talk communication about the state among agents who have slight heterogeneity in preferences.
A Fine Theorem 
“Tons of work has gone into the problem of strategic action on networks in the past 15 years, and I think it’s safe to say that the vast majority is either trivial or has proved too hard of a problem to say anything useful at all. ” i am having a hard time accepting that you have read all, or even that you know all, about this topic. But you are a good blogger, since you are convinced of your work. Congratulations.
Of course, even Matt Jackson can’t have read *everything*. But it’s just well known in the networks literature that, for technical reasons, strategic action on networks is a problem we’ve come nowhere near “solving” adequately. Certainly *I* don’t claim to know how to crack any of the important open questions.