Vying for Dominance: An Experiment in Dynamic NetworkFormationNate NelighNovember 15, 2017AbstractCentrality in a network is highly valuable. This paper investigates the idea that the timing ofentry into the network is a crucial determinant of a node's nal centrality. We propose a modelof strategic network growth which makes novel predictions about the forward-looking behaviors ofplayers. In particular, the model predicts that agents entering the network at speci c times will"vie for dominance"; that is, they will make more connections than is myopically optimal in hopesof receiving additional connections from future players and thereby becoming dominant.Theoccurrence of these opportunities varies non-monotonically with the parameters of the game. In alaboratory experiment, we nd that players do exhibit vying for dominance behavior, but do notalways do so at the predicted critical times. We nd that a model of heterogeneous risk aversionbest ts the observed deviations from initial predictions. Timing determines whether players havethe opportunity to become dominant, but individual characteristics determine whether playersexploit that opportunity.1IntroductionNetwork structures play a vital role in determining the behavior of many economic systems.1Thismakes it important to understand how networks form and, in particular, how some nodes end up ascentral (i.e. how a node ends up being close to many other nodes). In many settings, being close toother nodes is pro table it means having more information, more opportunities for exchange, or more2power but why are some nodes ( rms, individuals, politicians) more central than others?We hypothesize that thetiming of entry into a networkplays a critical role in determining whichnodes are the most central in the eventual network. It is common wisdom in the technology industrythat startup timing, that is when a new rm joins the market, is critical to eventual success. In general,3it is neither the rst rm to enter an industry nor the last that ends up being the most successful.Itis not just fundamental di erences between nodes or equilibrium selection that determines whether anode becomes well connected; when the node joins the network can also have a large impact.The following example illustrates how the order of entry may impact which nodes become central.Figure 1 shows the formation of a network where connections represent compatibilities between piecesof animation software.At the start the network contained Photoshop and Poser, which were notconnected. Maya entered the network and connected to both of the existing softwares. Later, additionalanimation softwares joined the network, and they all connected to Maya. By 2017, Maya has becomethe dominant rm in the animation software market, with more compatibilities than any other softwarein the network.One possible hypothesis is that Maya became dominant in the network because it joined at a criticaltime. By connecting to both Photoshop and Poser, Maya became central, meaning that subsequent1 Fortheoretical evidence see: Corominas-Bosch (2004); Kranton and Minehart (2001); Allouch (2015); Apt et al.(2016); McCubbins and Weller (2012); Carpenter et al. (2012).For reviews of the empirical evidence see: Bala andGoyal (2000); Jackson (2003); Jackson and Wolinsky (1996); Carrillo and Gaduh (2012). For experimental evidence see:Charness et al. (2007); Charness et al. (2014); Kittel and Luhan (2013); McCubbins and Weller (2012); Kos eld (2003).2 TheoreticalEvidence: Kranton and Minehart (2001); Blume et al. (2009); Apt et al. (2016); Chen and Teng (2016)Empirical Evidence: Pollack et al. (2015); Sarigöl et al. (2014); Powell et al. (1996); Rossi et al. (2015)3 SeeLilien and Yoon (1990).1

Figure 1: The formation of a network of compatibilities in animation software starting at the top leftand going clock-wise.players wanted to connect to it. Earlier players could not achieve high enough centrality to dominatethe network because there were not enough players to connect to. For later players it was too expensiveto challenge Maya's position of dominance.In order to better understand how opportunities to vie for dominance arise in this type of system,we construct a dynamic model of network formation with forward looking strategic agents.In themodel, players form a network by joining one at a time. As they join, players unilaterally decide which4existing nodes to connect with. Centrality is bene cial, but connections are costly.Having a dynamic model of this type is essential in exploring the impact of entry timing on centrality, because entry timing is an inherently dynamic feature: players make decision taking into accounttheir expectation of future moves. According to our hypothesis, Maya is willing to sustain the cost ofconnecting to both Photoshop and Poser, because it expects that this action will generate connectionsfrom other softwares in the future. As we discuss in Section 1.1, previous models of network formationhave either ignored dynamics entirely, had agents who are not strategic and forward looking, or areconstructed in such a way that equilibrium depends only on static features of the network.In Section 3 we discuss the basic features of the model.When the cost of connections is highrelative to the bene ts of centrality, the minimally connected network is e cient, and players will formthe minimally connected network in equilibrium. When the reverse is true, the maximally connectednetwork is e cient and players will form the maximally connected network.However, we nd apotentially large intermediate parameter region where players form non-degenerate networks, andbehavior can be strategically rich. Two intuitively plausible moves that occur in many equilibria are amyopicaction orDe nition:vying for dominance.Amyopicmove is a move which would be optimal if the game ended immediatelyafter that move. In the games we discuss in this paper, this means making one connection to one ofthe most central (or4 Seedominant ) nodes.Neligh (2017) for more detail on the theory and an exploration of what happens when we relax some of theseassumptions.2

De nition: Vying for dominanceis a move causing the player to become one of the dominantnodes immediately after his move.Solving the unconstrained version of the game can be di cult for large networks. We focus on twoapproaches which simplify the game so that equilibrium behavior can be exhaustively characterized aseither vying for dominance or taking a myopic action.5One approach summarized here, and covered in more depth in Neligh (2017) involves restrictingthe game so that each player must connect to one of the most central nodes. Surprisingly, this simple,plausible restriction is powerful enough to limit the set of possible networks and thus keep the gamesolvable. In this game we nd that vying for dominance happens periodically; the time between vyingmoves increasing exponentially as the game progresses in response to the increasing cost of vying.This result highlights a general property: players who vie for dominance do so because they expectconnections from future players taking myopic actions. As the network becomes larger, and vying fordominance increasingly costly, more myopic players are needed to justify the investment made by eachnew vying player. The timing between vying moves must therefore increase.In this paper we focus on a scenario that is both theoretically tractable and easily amenable toexperimental testing: we restrict the maximal size of the network by limiting the number of nodes.If the network is small enough, then the only equilibrium moves are myopic or vying for dominance.This restriction, is natural for our study, since it would be impractical to study much larger networkin an experimental laboratory.We begin by solving a game with ve players, the setting used in the lab. Player 5's move is simple;he should play a myopic move. The interesting behavior is that of the intermediate players, 3 and 4.Their incentives to vie for dominance naturally depend on the cost of connections, essentially creatingfour parameter regions. Player 4 can pro tably vie for dominance in the two lower cost regions but notin the higher two. The logic is not trivial, however: a player's incentives depend also on the number ofcompeting central nodes they face when they enter the network and, crucially, on their expectation offuture nodes' behavior. There is a parameter region where Player 4 will not vie for dominance if thereare too many competing central nodes. Player 3 wants Player 4 to vie, however, so he chooses notto vie in that cost region when he otherwise might have. This leads to an interesting non-monotonicrelationship between the cost of connections and vying behavior for Player 3.Section 4 describes the experiment we used to test the model of the ve-node game. We ran twotreatments with di erent costs for connections, corresponding to the second lowest and the secondhighest of the parameter regions previously mentioned. Using our solution to the ve-node game, wepredict that in the low cost treatment Player 3 should choose a myopic move and Player 4 should viefor dominance, and in the high cost treatment we should see the reverse.In Section 5 we present the data, and compare it to the predictions of the model. In general, mostplayers either vied for dominance or chose myopic moves as predicted. However, players often did notalways vie for dominance at the predicted critical times.Broadly speaking, the model does betterin predicting the play for later movers. The prediction that player 5 always plays myopically is wellsupported.For player 4, the comparative statics were right, but the levels were sometimes wrong.Player 4 is predicted to vie most often when costs are low, and when Player 3 did not vie, and thisis the case in our data. However, Player 4s only vied 22% of the time in that scenario, far di erentfrom the 100% predicted by the theory. For Player 3 even the comparative static was wrong: Player3s were found to vie more when costs were low.Overall, players vied for dominance less often than expected, but when they did vie, they did somore often in conditions where the average gain from vying was higher. One possible explanation forthe di erence from the equilibrium prediction is that players have some aversion to vying for dominancewhich could be overcome with high enough payo s. Because vying is a risky option relative to playingmyopically, risk aversion is a natural candidate.In Section 6 we explore the possibility that riskaversion is in uencing subjects' choices. We elicit risk preferences and nd that they have signi cantpower in predicting when players vie for dominance. On the basis of this nding we develop a versionof the model with heterogeneous risk preferences. We nd that this model does a good job of matchingthe aggregate moments in the data.5 Withsome caveats regarding the exact de nition of myopic in the case of the rst approach. See Neligh (2017) formore details.3

Our conclusion then is that timing does play a strong role in whether nodes have the opportunityto become central However, whether nodes (individuals, managers, rms) are able to exploit theopportunity that the right timing gives them depends on individual characteristics as well.1.1 Literature: Theory and Experiments on Network FormationBefore we present the model, we review the literature concerning theories and experiments on networksand network formation.Previous models of network formation are not well suited to studying the role of vying for dominanceand entry timing in determining network structure. These models generally attribute node centrality6to either luckof node entry.or some combination of fundamentals and equilibrium selection7rather than the timingFor example, because any pairwise stable network can be a solution in Jackson andWolinsky (1996), whether node is central depends only on whether there exists a pairwise stablenetwork where that node is central (fundamentals) and whether that pairwise stable network happensto be the one that is chosen (equilibrium selection). Existing models of network formation usually lackat least one of the critical elements for exploring the impact of entry timing on centrality: either theagents are not forward looking, the nodes do not enter the network sequentially, or the set of solutionsdepends only on static features of the network.The earliest models of network formation, such as the preferential attachment model of Yule (1925)and the small world model of Erdös and Rényi (1960) did not include any optimizing agents or strategicbehavior.Network formation models were introduced to economics by Jackson and Wolinsky (1996) and theirmodel of cooperative network formation.In this model, a network is stable if no two unconnectedplayers want to form a connection, and no player who is party to a connection wishes to break thatconnection. This network formation process is called cooperative, because two players must agree ona connection for it to persist. This model has no dynamic aspect.Bala and Goyal (2000) propose a similar stability based network formation model, but they allowedplayers to generate connections unilaterally.As such, their model is referred to as non-cooperativenetwork formation. Bala and Goyal (2000) also introduces dynamics to their models, but as in many8dynamic models of network formation players were not strategically forward looking.Players areassumed to best respond to the strategies of players from the previous period. In a similar vein, themodel of Watts (2001) assumes that players myopically update their connections, and in the model ofKim and Jo (2009) connections only provide an immediate bene t.There are several papers that do include dynamics as well as forward looking strategic agents. Inmany of these models, payo s or game structures are chosen such that the set of possible outcomes depends on some static feature of the network. For example Currarini and Morelli (2000) and Mutuswamiand Winter (2002) both nd that only e cient networks can be supported in equilibria of their game.Song and van der Schaar (2015) nd that the dynamic network formation process can converge toany network which satis es a static individual rationality constraint requiring that each player makea payo of at least zero. These papers either lack strong history dependence or use specialized payo functions which simplify strategic considerations.While dynamics do not drop out of the network formation model of Aumann and Myerson (1988),the payo function used guarantees that only complete connected components can form.In otherwords, all nodes in a group must be connected to all other nodes in that group. Only the numberof nodes in a particular group matters, because only one structure is possible for a given group size.This allows the network formation model to be reduced to a more standard model of dynamic coalitionformation where players are picking their groups.The model of Chowdhury (2008) is one of the most similar to our own.Both models includesequential link formation and forward-looking strategic agents. In addition, there is the possibility inChowdhury (2008) for early movers to make myopically sub-optimal moves in hopes of gaining futureconnections, which can be thought of as loosely similar to the vying for dominance behavior of our6 Kim and Jo (2009)7 Watts (2001); Currarini and Morelli (2000);8 Watts (2001) and Kim and Jo (2009)Jackson and Wolinsky (1996); Bala and Goyal (2000)4

model. However, Chowdhury (2008) assumes that each node can only sponsor one connection, andthus rules out by assumption the possibility of competing for centrality by making multiple connectionsthat is the center of the present paper.Our experiment is designed with a more de ned temporal structure than previous network formation9experiments.It is this rigid time structure that allows us to carefully study how entry order and moveorder relate to the eventual centrality of nodes.To our knowledge, there is only one other paper in the economics literature which has examinednetwork growth in with a similar structure. Celen and Hyndman (2006) have players form small threeperson networks using a fairly similar sequential process to the one used in this experiment. In theirexperiment, new players can pay to gain information about the state of the world from older nodes.The informational ows form a directed network.Our experiment di ers from Celen and Hyndman (2006) in that players care about the behaviorof later nodes and the network is larger, which makes the space of possible behavior much richer. InCelen and Hyndman (2006), the behavior of future players is irrelevant. Players are instead concernedwith inferring the behavior of previous players. As such, we need to conduct a new experiment to testthe vying for dominance prediction of Neligh (2017) and to examine the importance of entry timingin determining node centrality.Several experiments have found that network structure can have large impacts on behavior. Exper10imentalists have studied the impact of network structure on trading games,12and group decision making games.11public goods games,A good review of older experiments examining the role of networkstructure in determining economic outcomes can be found in Kos eld (2003).Experiments have been conducted testing various network formation models. In examining thesestudies, we nd two consistent important ndings which are potentially relevant to our own experiment.First, is the competition for centrality.Players want to be central, because it is often bene cial tobe so in many experimental setups. As such, there are often several players all attempting to becomecentral in these experiments. Second, is the role of heterogeneity. Player di erences, whether inherentor exogenously given, have a large impact on the behavior of players in network formation games.Kearns et al. (2012), van Leeuwen et al. (2013), and Goeree et al. (2007) all nd evidence thatcompetition for centrality plays a role in determining whether and how players converge to a stablesolution.In all experiments, players were slow in converging to stable networks, at least in partbecause multiple players consistently tried to become the most central in the network. Players can beheterogeneous in how much they compete for centrality. Kearns et al. (2012) found a very bimodaldistribution of connections made. Players either made a lot of connections or very few. In Section 6 weexamine how heterogeneity in players can in uence the competition for centrality in our experiment.Competition for centrality is a very important feature of our model as well. Players vie for dominance by making multiple connections in hopes of being highly central and receiving many connectionsas the game progresses. However, while this competition for centrality has been a confounding factorin previous studies, it is a direct prediction in our model.As such, it will allow us to discuss thephenomenon with more rigor and detail than in previous studies.2The GameWe now present the general concept of the network formation model. There is a set of players, eachone represented by a node. New players/nodes join the network one at a time. As players join thenetwork, they choose which existing nodes to connect to. They must connect to at least one existingnode. Once the last player has joined the network and made their choice the game ends, and playersreceive points based on the number of connections they made and their position in the nal network.Centrality is bene cial but making connections is costly.9 Carrilloand Gaduh (2012); Bernasconi and Galizzi (2005); Carrillo and Gaduh (2012); Kearns et al. (2012); vanLeeuwen et al. (2013)10 Charness et al. (2007)11 Charness et al. (2014); Carpenter et al. (2012)12 Kittel and Luhan (2013);McCubbins and Weller(2012)5

j x(G)We now present the model formally. There is a set of players represented by nodes indexed{1, ., J}.Networks are represented asG {n(G); x(G)}is a set of edges represents by pairs of nodes.t {1, 2, .J}.wheren(G)is a set of nodes, andThe networks are also indexed by time asGtwhereNote that there is one time period for every player/node, so indices are largelyG1 {1; }.Gt 1 , to a distributioninterchangeable. The game begins with the initial network containing only Node 1A strategy for playerjmaps every possible network state they can face,over sets of connections. Each set of connectionsbetween NodetAfter playerand existing nodes intGt 1 .htPlayermust be non-empty and contain only connectionstis choosing which existing nodes to connect to.makes their move, the network evolves according to the following rule:Gt Gt 1 {t; ht }In other words, the new network is created by adding a node representing the new player and allof the connections made by that player to the existing network.The game concludes after PlayerJmakes his choice, generating the nal networkGJ .Once the game has concluded, each player gets a payo according to the following utility function.ui (hi , GJ ) Y C hi Bζi (GJ , δ)Y IRis a constant base payo .the set of connectionsB IR hi . C IR C hi (1)is the cost of connections by individualis the constant cost of connections.Bζi (GJ , δ)iwho purchasedis the bene t fromPζ(GJ , δ) j6 i δ dij (GJ ) 1 is a standard measure ofdij (GJ ) 1closeness centrality. Decomposing, δ (0, 1) is a geometric discount factor. dij (Gt ) isj6 i δthe minimum distance between Node i and Node j in edges under network Gt . The minus one in theexponent adjusts the term such that we do not have to normalize B and C with respect to δ a constant multiplier, andPThis type of payo function is common in the network formation literature. It is very similar to thepayo function used in Watts (2001) and Jackson and Wolinsky (1996).13This type of network payo is most relevant for systems in which some bene cial opportunity or information lands at a randomnode and then disseminates throughout the network with value decaying over time. It can, however,be applied as a useful approximation in any system where more central nodes gain more bene ts, asthis measure of centrality is highly correlated with other measures of centrality, especially in networks14with low diameter.2.1 SolutionsWe take Subgame Perfect Equilibria (SPE) as our solution concept of choice, because it capturesthe idea of fully forwards looking strategic agents.A SPE is de ned in the standard manner, as astrategy pro le in which players only choose moves after a given action history which are optimal for thesubgame resulting from that action history. Existence is guaranteed by the fact that we are consideringa nite game of perfect information.The solution to the game is not always unique.Because thisis a nite game of perfect information, multiplicity of equilibria derives from the manner in whichplayers resolve indi erences. As such it is useful to address the way players resolve indi erences in asystematic manner.De nition.Tie-Breaking Rule: a tie-breaking rule refers to some rule by which players resolveindi erences in the construction of a SPE.A player's tie-breaking rule can be thought of as a mapping from action histories to strict orderingsover moves. Whichever strict ordering is drawn after a given action history is used to transform thecurrent actor's weak preference ordering on moves into a strict one (thereby determining that player'smove).Note that the indi erences in this game are due to structural symmetries and similarities13 Their payo function is has Y 0 and B δ ,14 For an examination of correlation in measuresbut otherwise is identical.of centrality in real world networks, see Valente et al. (2008)6

inherent in network formation and are not related to o path behavior.As such the indi erencescannot be easily dealt with using equilibrium re nements or payo perturbations.15Note that because indi erence resolution is the only source of multiplicity in this game, a solutionto the game can be fully characterized by the set of parameters and the tie-breaking rules employedby all players.3Results3.1 E ciency ResultsWe rst explore the structure of the e cient network. This depends on the parameters of the problemCCB . When B (1 δ) most of the outcomes are not Pareto ranked, but wecan productively consider whether networks are e cient in the following sense.and in particular the ratioDe nition:We say an outcome networkGJis e cient if it generates the highest possible sumof utilities of all feasible outcome networks for given parameters.This is equivalent to the stronge ciency of Jackson and Wolinsky (1996).The following proposition characterizes e cient networks for several parameter regions.Proposition 1: IfCB 2(1 δ),then the e cient network is the complete network. IfCB 2(1 δ),then the e cient network is the star network (on Node 1 or Node 2) IfCB 2(1 δ),then all feasible networks which contain stars are e cientFor proofs, see Neligh (2017).This result is similar to that of Jackson and Wolinsky (1996) with a few key di erences. First, theempty network is never e cient, because it is never feasible in this game. Second, the threshold belowwhich the complete network is e cient in Jackson and Wolinsky (1996) isC/B 1 δ .This di erencecomes from the fact that, in our model, the cost of each connection is only paid once by the playerwho makes it. In the cooperative game, the connection is costly to both parties. As such connectionsmust be twice as costly in our game before they become socially ine cient.Note that, while the sequential nature of the game does impose limits on the set of feasible networks,it does not impose strong limits on the structure of the networks other than connectedness. Given anyconnected network of un-indexed nodes, we can nd a sequence of actions which generates a networkof that same shape.3.2 Subgame Perfect EquilibriaHaving established e ciency, we now examine the types of networks that can form in di erent parameter regions.Proposition 2:CB game. If CB (1 δ), then the complete network is no longer a possible outcome of any SPE at all. Tosee this consider the move of Player J . If15 In(1 δ)then the complete network is the unique network which can form in SPE's of theIfC1 δ J 3B (J 1) 1 δ , then the star networks centered on Node 1 and Node 2 are the onlynetworks which can be formed in SPE's of the game.face, tie-breaking rules behave much like small move dependent bonus payment perturbations which are drawnrandomly from a distribution which depends on the move history of the game, assuming that the payments are smallenough never to change the relationship of two moves between which the player is not indi erent.7

Figure 2: Visualization of parameter regions of interest. Threshold locations imply lowδ . f (J, δ) δ δ J 3.1 δFor proofs, see Neligh (2017).As in Jackson and Wolinsky (1996), whenC 1 δonly outcome of subgame perfect equilibria, and whenend, however.the complete network forms as the possibleC 1 δ.That is where the similaritiesThe ability of earlier moves to a ect the incentives of later players means that thepotential bene ts of additional connections are much higher than in a one shot model; recall the vyingfor dominance discussed in the introduction.As such, we cannot guarantee a minimally connectednetwork unless costs are relatively very high.C1 δ J 3B (J 1) 1 δ , is increasing in J , sothe condition is more restrictive in large networks. Intuitively, this means that it is easier to generateAlso, note that the right hand side of the condition,non-star networks when the number of players is large and when the geometric discount factor is large.Proposition SPE 2 is tight as long asCBδ J 2andδδis small in a weaker sense than for Proposition SPE 1. Ifis su ciently small such that there exist a SPE of the game parameterized by16CB andwhich does not always generate a star network.3.3 Summary of ResultsThese results are intuitive and are generally quite robust to small changes in the assumptions of the17model.These results also provide a basis for some of the more novel results such as those discussedin Section3.5 and tested in the experiment. The results of the previous sections are summarized inFigure 2.There are parameter regions where the star network and complete network are formed as the uniqueSPE outcome and regions where they e cient. There are also regions where both networks are e cient.In addition, there is an interesting region, where we cannot guarantee either the star or the completenetwork. In the yellow region, the complete network cannot form. The star network can form, butit is not guaranteed to be a solution, and it is never the unique SPE outcome as long asδis small.Instead, we often see more complex strategic behaviors in the yellow region, like vying for dominance.The above results are comparable to those found in Jackson and Wolinsky (1996) and Watts (2001)with several major di erences. First, the fact that we are using non-cooperative network formationshifts the e ciency threshold, Since the region where the complete network is guaranteed does notshift, this change allows for the possibility of ine cient under-connection.Second, the nature of the non-degenerate networks that can form is very di erent.The stablenetworks in Jackson and Wolinsky (1996) are always locally e cient in the sense that changing themby adding or removing one connection will decrease the overall sum of payo s generated by the network.Ine ciency in their model is driven by the di erence between global and local optimum. In our model,on the other hand, local optimality is not guaranteed. Ine ciency is instead driven by the existenceof positive and negative externalities. The positive externalities are easy to see, because players arebene ting from connections th

By connecting to both Photoshop and Poser, Maya became central, meaning that subsequent 1 orF theoretical evidence see: Corominas-Bosch (2004); Kranton and Minehart (2001); Allouch (2015); Apt et al. (2016); McCubbins and ellerW (2012); Carpenter et al. (2