1 Introduction

Random network formation models have found widespread applicability in socio-economic and natural sciences in the past two decades. Notably, the preferential attachment model of Barabási and Albert (1999) is seen as a quasi-universal model of network formation in domains ranging from biology to sociology through computer science (see Barabási (2009), for a survey of applications). In economics, the “friend of friends” model of Jackson and Rogers (2007), extended by Bramoullé et al. (2012), forms the backbone of recent influential contributions in international trade (Chaney 2014), industrial dynamics (Luttmer 2011), or public economics (Mayer and Puller 2008). The unusual success, in economics, of such phenomenological models, is due to their ability to reproduce key empirical characteristics of socio-economic networks such as fat-tailed degree distribution, short average distance, large clustering coefficient and positive assortativity (see e.g. Jackson and Rogers (2007)).

Random network formation models however parly lack micro-foundations. There is a substantial game-theoretic literature on strategic network formation that offer a detailed representation of individuals’ incentives but it predicts the emergence of much simpler structures than these observed empirically. Among seminal contributions, the connection model in Jackson and Wolinsky (1996) puts forward as pairwise stable networks the star and the complete network. In the co-author model of Jackson and Wolinsky (1996), efficient networks consist of disjoint pairs and pairwise stable networks consist in fully intraconnected components. In the one-sided network formation model of Bala and Goyal (2000), equilibrium networks are either empty, complete, stars or wheels. Subsequent contributions analyze the emergence of more elaborate structures such as nested-split graph (König et al. 2014), bipartite networks (Bramoullé et al. 2004) or star-like structures with connections between peripheral nodes (Möhlmeier et al. 2016), but they remain much more regular than these observed empirically.

Against this background, this paper investigates whether strategic micro- foundations can be provided for random network formation models and in particular preferential attachment, i.e. the network formation process in which nodes sequentially enter the network and form links with existing nodes with a probability proportional to their degree. Namely, we investigate whether there exist strategic network formation models whose dynamics along an equilibrium path are observationally equivalent with preferential attachment. We consider a framework similar to that of Barabási and Albert (1999) and Jackson and Rogers (2007) where agents sequentially enter the network and form links with one of their predecessors. Yet, we consider agents are strategic and thus describe the process as an extensive game as in Acemoglu et al. (2011) . More precisely, we consider a game form in which a player chooses an action that induces a probability distribution on potential links and nature then picks a link following this probability distribution. Example of such processes are situations where a player invests some resources across different nodes in view of link creation and an actual link is formed with a probability that depends on the resources invested at each node.

In this setting two conditions appear necessary for players to adopt a behavior consistent with random network formation processes, i.e. to choose an action such that the resulting link is determined randomly rather than deterministically. First, players must have some imperfect information on the link created by their predecessors and/or the state of the network. Indeed, generating a randomized link can be efficient only if the actual realization of the link is not perfectly observed by the successors. Second, the actual choice of generating a randomized link implies some form of competition between a player and its successors: a player has incentives to reduce the information available to its successors only to the extent that their objectives are in opposition. In other words, competition is necessary for randomness to emerge endogenously in a game-theoretic setting. Alternative micro-foundations of preferential attachment would require some exogenous from of randomness, e.g as in D’souza et al. (2007) who assume that new nodes are “uniformly” distributed over the network when they enter.

We exhibit a class of game for which these conditions hold: games of sequential competition in which a player competes with his direct successor (and his predecessor) for the benefits induced by the socio-economic relationship they form with a third party in the network. In this setting, we consider that each player has a competitive advantage over his successor in their bilateral interactions. Therefore, a player seeks competition whereas his successor aims at avoiding it. Thus, a player has incentives to create a link to the same node as his successor but to avoid linking to the same node as his predecessor. These conflicting incentives force players to generate randomized links. Namely, we show that the focal equilibrium that emerges in this setting is one where players generate probability distributions with full support and target the whole network. More precisely, each node is reached with a probability inversely proportional to the linkage cost it induces on the players. Notably, if this cost is inversely proportional to the degree, equilibrium play induces a preferential attachment process. This result is at odds with standard explanations of the emergence of preferential attachment based on synergies (Barabási and Albert 1999). In our framework, preferential attachment is rather be tied to a congestion effect such that nodes with higher degree have lower payoff. This condition is necessary because in a competitive framework, a player is hedging the risk against his opponent by equalizing his expected payoff and thus put less weight on events with high returns.

Hence the paper provides a positive answer to the question whether there exists strategic network formation process that give rise to preferential attachment. However, we show that the result holds only for very specific type of utility functions. Namely, considering an extended class of games, we show that a necessary condition for preferential attachment to emerge at equilibrium is that the utility obtained by a player is inversely proportional to the degree of the node targeted by its predecessor. We put forward examples where these conditions are satisfied, e.g. specific forms of oligopolistic competition and perturbed versions of the co-author model. However, these restrictive conditions imply that the breadth of our results is limited and more broadly that preferential attachment might not be the outcome of strategic interactions, in general.

Despite being partly negative, these findings contribute to the literature on the microeconomic foundations of random network formation process, and more specifically preferential attachment. In particular, Jackson and Rogers (2007) emphasize that preferential attachment, and more general random network formation processes, can be rationalized by considering the utility derived from connections is random. Valverde et al. (2002) and D’souza et al. (2007) show that preferential attachment can emerge from the behavior of locally optimizing agents. We also contribute to the literature on farsighted network formation (see e.g. Dutta et al. 2005; Page et al. 2005; Herings et al. 2009 as well as the survey in Jackson (2005)) by developing a model of network formation as an extensive-form game. In this latter respect, our approach is connected to that of Aumann and Myerson (1988) although we consider unilateral link formation “player by player” rather than bilateral link formation “link by link”. We also put a very strong focus on the role of imperfections of information. Finally, our model relates to the literature on targeting and link formation in a fixed network (e.g. Kempe et al. 2003; Ballester et al. 2006; Grabisch et al. 2017). Yet, in our setting, the optimal strategy for players is to spread (probabilistically) their links over the network while, in the the targeting literature, optimal strategies generally focus on a key target or group of targets.

The remaining of the paper is organized as follows. Section 2 presents the general structure of our model of network formation. Section 3 provides an analysis of sequential competition games and characterizes the conditions under which random network formation processes emerge as equilibria of the game. Section 4 highlights the micro-economic applications of our model. Section 5 concludes. All the proofs are given in the appendix.

2 Network formation as an extensive game

2.1 The framework

Dynamic processes of network formation can be represented as extensive games in which players sequentially enter a network and form links with their predecessors. Alternative specifications of linkage actions, payoffs and information structures can generate a wide class of such games. In this paper, we investigate a subclass of these extensive games of network formation. We focus on the case where players form a single link when they enter the network, i.e. we consider the formation of trees. Informally, the game starts with a given tree \(g_0\) and T players arrive sequentially.

At the period in which he enters the network, each player takes a decision that induces a probability to link to existing nodes. We have in mind a framework where the player can not create directly a link but allocates his time/efforts/resources in order to influence which link will be created. Nature then draws randomly the realized link. We will assume that the allocation of resources of the player is observed but the realized link becomes observable only with a certain lag. Hence, the successors of a player might have imperfect information about the link he has formed. Furthermore, we shall assume that the set of actions is sufficiently large to generate any probability distribution and thus that the set of decisions of a player can be replaced by the set of probability distributions over nodes. In particular, every player has the possibility to choose a decision that induces a given link with certainty. Hence, in the following, we defined the strategy of a player as a distribution over nodes and assume that this distribution is observed. Although this last assumption is natural in our model, it differs from standard approaches in game theory. At the end of the game, players present in the network receive a payoff that depends on the actual history of network formation.

More formally, we focus on the set \(\mathcal {G}\) of finite trees. We denote by \(\mathcal {S}(g) \subset \mathcal {G}\) the set of possible successors of a tree \(g \in \mathcal {G},\) i.e. the trees that contain g as a subtree and have exactly one more node than g. We then consider as given a tree \(g_0\in \mathcal {G}\) with \(n_0\) nodes indexed by \(A_0=\{1,\ldots , n_0\}\) and focus on the successive additions of nodes to \(g_0.\) Namely, we denote by \(\mathcal {G}_{T}(g_0)=\{(g_i)_{i=0,\ldots ,T} \in \mathcal {G}^T \mid \forall t < T \ g_t \in \mathcal {S}(g_{t+1})\}\) the set of tree-histories that can be formed by the successive addition of T nodes to \(g_0.\) A game \(\Gamma (g_0,T,\tau ,\pi )\) is then defined by a 4-uple: \(g_0\) is the initial tree, T is the length of the game (and equivalently the number of players), \(\tau \) is the informational lag and \(\pi =(\pi _t)_{1\le t \le T}\) is the set of payoff functions where for each \(t=1,\ldots , T,\) \(\pi _t:\mathcal {G}_{T}(g_0) \rightarrow {\mathbb {R}}\) is a function of the tree-history. Each period of the game is decomposed into two stages and the game unfolds as follows.

  • At period 1, player 1 enters the network and chooses an action \(\alpha _1\) that induces a linkage probability over \(A_1=\{1,\ldots ,n_0-1\}.\) Then at period \(1'\), nature chooses \(m_1 \in A_1\) following \(\alpha _1.\) A new node \(n_1=n_0+1\) and a link \((m_1,n_1)\) are added to the graph. We denote by \(g_1\) the updated graph.

  • At period 2, player 2 enters the network and chooses an action \(\alpha _2\) that induces a linkage probability over \(A_2=\{1,\ldots ,n_0\}\). Then at period \(2'\), nature chooses \(m_2 \in A_2\) following \(\alpha _2\). A new node \(n_2=n_0+2\) and a link \((m_2,n_2)\) are added to the graph. We denote by \(g_2\) the updated graph.

  • More generally, for every period \(2\le t \le T,\) player t enters the network and chooses an action \(\alpha _t\) that induces a linkage probability over \(A_t=\{1,\ldots ,n_{t-2}\}.\) A new node \(n_t=n_0+t\) and a link \((m_t,n_t)\) are added to the graph. The updated graph is denoted by \(g_t\).

Remark 2.1

It is assumed that a player can not link to its direct predecessor and thus the action of player t induces a linkage probability over \(A_t=\{1,\ldots ,n_{t-2}\}.\)

For every \(t\ge 1\), a strategy of player t is a function from his observations to his action set. By assumption, player t has three types of information. First, player t knows the initial tree \(g_0\). Second, player t knows the actions, i.e. the probability distributions, chosen by every player until stage \(t-1.\) Finally, he knows all the choices of nature until stage \(t-1-\tau \). Notice that it implies that player t can compute the tree at stage \(t-1-\tau \) from the initial tree and the past choices of nature but that for later stages he only has a belief, i.e. a probability distribution, about the actual structure of the tree at stage t. This belief is uniquely defined by \(g_{0}\), the past choices of nature and the actions of players \(t-\tau \) to \(t-1\). Formally, a strategy for player t is a function from \(H_t= \Pi _{i=1}^{t-\tau -1} A_i \times \Pi _{j=1}^{t-1} \Delta (A_{j}) \) to \(\Delta (A_{t})\). We denote by \(\Sigma _{t,\tau }\) the corresponding set of strategies.

Given a strategy profile \((\phi _t)_{t= 1, \ldots , T}\), one can then define a probability distribution \({\mathbb {P}}_{g_0,\phi }\) on the set of histories of length T starting from \(g_0\) and the payoff of player t as the expectation of \(\pi _t\) under \({\mathbb {P}}_{g_0,\phi }\). This leads us to the following notion of Nash equilibrium.

Definition 2.2

Let \(\Gamma (g_0,T,\tau ,\pi )\) be a game. A profile of strategies \((\phi _t)_{1\le t \le T}\) is a Nash equilibrium if for every \(1\le t \le T\), and every strategy \(\psi _t \in \Sigma _{t,\tau },\) one has:

$$\begin{aligned} {\mathbb {E}}_{{\mathbb {P}}_{g_0,(\psi _t,\phi _{-t})}}(\pi _t) \le {\mathbb {E}}_{{\mathbb {P}}_{g_0,(\phi _t,\phi _{-t})}}(\pi _t) \end{aligned}$$

The sequential nature of action and information in the game further allows player t to form a belief \({\mathbb {P}}_{h_t,\alpha _t, \phi _{>t}}\) about the set of tree-history of length T based on the strategies of his successors \(\phi _{>t}\), of his action \(\alpha _t\) and of the history he observes \(h_t\), i.e. the observed actions \(\alpha _{<t}=(\alpha _1, \ldots ,\alpha _{t-1})\) and the realizations of the links observed with a \(\tau \) periods lag \(m_{<t-\tau }=(m_1,\ldots ,m_{t-\tau -1})\), This leads to a natural refinement of the notion of equilibrium in which each player play optimally conditionally on these beliefs. Namely, in the following, we shall focus on lagged subgame perfect equilibria

Definition 2.3

Let \(\Gamma (g_0,T,\tau ,\pi )\) be a game. A profile of strategies \((\phi _t)_{1\le t \le T}\) is a lagged subgame perfect equilibrium if for every \(1\le t \le T\) and every history \(h_t\in H_t\), we have

$$\begin{aligned} \forall \alpha '\in \Delta (A_t), \ {\mathbb {E}}_{{\mathbb {P}}_{h_t, \phi _t(h_t), \phi _{>t}}} \left( \pi _t \right) \ge {\mathbb {E}}_{{\mathbb {P}}_{h_t, \alpha ', \phi _{>t}}} \left( \pi _t \right) , \end{aligned}$$

Remark 2.4

The information structure is such that player t perfectly observes the state of the network in period \(t-\tau .\) He can then conditions his actions on the structure of the network in period \(t-\tau \) (and on the actions of other players between \(t-\tau \) and \(t-1\)). Accordingly, our framework naturally extends to settings where the player only observes certain network characteristics that determine the payoffs (e.g. the degree sequence).

Remark 2.5

In our setting, player t has perfect information on the actions of the preceding players but not on the choices of nature. Hence, the game is an extensive game with incomplete information. In this setting, the conventional solution concept is that of perfect Bayesian equilibrium, which assumes that players’ beliefs about the state of the game are consistent with players’ actions and Bayes updating on the equilibrium path. The notion of lagged subgame perfect equilibrium that we consider is more restrictive, as we constrain the beliefs, even off the equilibrium path, to be consistent with the observed history.

Another point of view is to change the timing of the game to delay the choice of nature, corresponding to the decision at stage t, until after stage \(t+\tau \). This resolves formally the incomplete information.

In the following, we shall also refer to an approximate notion of equilibria, that of lagged subgame perfect \(\varepsilon \)-equilibria, which is defined as follows.

Definition 2.6

Let \(\varepsilon >0\) and let \(\Gamma (g_0,T,\tau ,\pi )\) be a game. A profile of strategies \((\phi _t)_{1\le t \le T}\) is a lagged subgame perfect \(\varepsilon \)-equilibrium if for every \(1\le t \le T\) and every history \(h_t\in H_t\), we have

$$\begin{aligned} \forall \alpha '\in \Delta (A_t), \ {\mathbb {E}}_{{\mathbb {P}}_{h_t, \alpha ', \phi _{>t}}} \left( \pi _t \right) \le {\mathbb {E}}_{{\mathbb {P}}_{h_t, \phi _t(h_t), \phi _{>t}}} \left( \pi _t \right) +\varepsilon . \end{aligned}$$

In this setting, we aim to investigate the conditions under which strategic behavior can give rise to dynamics consistent with seminal random network formation models such as uniform and preferential attachment processes (Barabási and Albert 1999) or “friends of friends” models (Jackson and Rogers 2007; Bramoullé et al. 2012). In this perspective, it is useful to distinguish two categories of actions for a player in our game. On the one hand, a player can choose to allocate all his efforts to a given node such that the given link is created with probability 1., i.e. play deterministically. With a certain abuse of terminology, we will refer to these as pure actions and call “equilibrium with pure actions”, an equilibrium of the game in which all players choose pure actions along the equilibrium path. On the other hand, a player can choose to induce a probability distribution with non-trivial support. In this latter case, we shall say that the player chooses a probabilistic action and refer to the corresponding type of equilibrium as “equilibrium with probabilistic actions.”

One can then note that random network formation models can only be supported by equilibria with probabilistic actions. This raises the question as to which information and incentive structures can induce players to play probabilistic rather than pure actions. Two necessary conditions can be put forward in this respect. First, players must have some form of imperfect information. Indeed, in our setting where the payoff depends on the actions of future players, a probabilistic action is purposeful only if the actual realization of the action is not perfectly observed by the successors. Second, probabilistic actions require some form of competition between a player and its successors: a player has incentives to reduce the information available to its successors only to the extent that their objectives are in opposition. The remarks below provide a more formal statement of these considerations.

Remark 2.7

(Imperfect information) If there is no informational lag, i.e. if \(\tau =0,\) one can show by backward induction that the game \(\Gamma (g_0,T,\tau , \pi )\) necessarily has at least one subgame perfect equilibrium with pure actions. Indeed, as player T observes the realizations of all previous actions, he can choose a pure best response conditional on these realizations. This implies in particular that Player \(T-1\) has no incentives to randomize because everything goes as if player T would best-reply separately to each realization in the support of the probabilistic action that he would choose. Hence player \(T-1\) simply ought to choose the pure action that is a best reply to the action of his predecessors, taking as given the best-reply of player T. Iterating this reasoning by backward induction, one obtains a pure subgame perfect equilibrium. Note that this does not exclude strictly speaking the existence of equilibria with mixed strategies, as the player could be indifferent between different pure actions, but the player does not have real incentives to play a mixed action as a pure action with equivalent payoff is available.

Remark 2.8

(Competition) If the incentives of the players are perfectly aligned in the sense that there exists a tree-history \(\overline{g}\in \mathcal {G}_{T}(g_0)\) that is the unique global optimum for each player -i.e such that for every \(g \in \mathcal {G}_{T}(g_0) / \{\overline{g}\}\) and for every \(t=1,\ldots ,T\) \(\pi _t(\overline{g}) >\pi _t(g)\)- it is straightforward to show that there exists a unique subgame perfect equilibrium of the game and this equilibrium has pure actions corresponding to the history \(\overline{g}.\)

More broadly, it suffices that the incentives of the players are coordinated to ensure that there exists an equilibrium path with pure actions only. For example, if the delay is T and there exists a function \(\phi : \Pi _{i\in T} A_i \rightarrow {\mathbb {R}}\) such that for every sequence of pure actions \((m_t)_{t\in T}\in \Pi _{i\in T} A_i\),

$$\begin{aligned}&\forall a_i,b_i\in A_i, \ \pi _i(b_i,(m_t)_{t\in T-\{i\}})-\pi _i(a_i,(m_t)_{t\in T-\{i\}})\\&\quad =\phi (b_i,(m_t)_{t\in T-\{i\}})-\phi (a_i,(m_t)_{t\in T-\{i\}}), \end{aligned}$$

the basic game is then said to be potential and one knows (see Monderer and Shapley (1996)) that the normal-form game \(((A_t)_{t\in T},(\pi _t)_{t\in T})\) has at least one pure equilibrium given by the profile of actions that maximizes the potential function \(\phi \). If the delay is not T, we can obtain a pure lagged subgame perfect equilibrium by backward induction: given the decision of the previous players, each player maximizes the expectation of the potential function knowing the past actions and that the following player follows the same strategy.

2.2 A minimal example

Building on the previous remarks, we build a minimal example of a game that exhibits imperfect information and competition. We show that the simplest type of random network formation process, uniform attachment, emerges as a focal equilibrium of the game. This example anticipates important features of the more general class of games we introduce in the next section although the role of network effects is minimal.

We consider a game with a one-period informational lag and where the payoff of a player is only affected by the actions of its immediate predecessor and successor. The agent receives a fixed negative payoff if he links to the same node as his predecessor and a fixed positive payoff if he links to the same node as his successor. This implements a basic form of competition between agents. It corresponds to situations where players benefit from indirect linkages with their successors (as in the connection model of Jackson and Wolinsky (1996)) but face (congestion) costs related to indirect linkages with their predecessors (as in the co-author model of) Jackson and Wolinsky (1996)).

Up to normalization, we can assume that player t receives a payoff of 1 if player \(t+1\) links to the same node as he does and that he faces a cost, set equal to \(\lambda \in {\mathbb {R}}_+,\) if he links to the same node as player \(t-1.\) We shall also consider that if player t links to \(n_t-2\) (to whom player \(t-1\) could not link), he faces the average connection cost among other nodes, i.e \(\nicefrac {\lambda }{(n_t-3)},\) whereas player \(t-1\) receives a payoff of \(\frac{1}{n_t-3}\).

We consider such a game of length \(T \in {\mathbb {N}},\) \(\Gamma (g_0,T,1,\pi ).\) We can characterize equilibrium by backward induction as follows (the proof follows immediately from Theorem 3.6 in the next section).

  • Given the action of player \(T-1,\) \(s \in \Delta (A_{T-1}),\) the expected payoff of player T if he uses the action \(\alpha \in \Delta (A_{T})\) is:

    $$\begin{aligned} -\lambda \left[ \sum _{i=1}^{n_T-3} s_i \alpha _i + \dfrac{1}{n_T-3}\alpha _{n_T-2} \right] \end{aligned}$$
    (2.1)

    Given he has no successor, the objective of player T simply is to minimize his linkage cost and thus to choose the node that player \(T-1\) is less likely to have connected to. It is straightforward to check that:

    • if \(\min _{i \in A_{T-1}} s_i<\nicefrac {1}{n_T-3},\) any node, and thus any probabilistic action with support in \({\text {argmin}}_{i \in A_{T-1}} \ s_i\) is a best response for player T and his expected payoff is \(-\lambda \min _{i \in A_{T-1}} s_i,\)

    • if \(\min _{i \in A_{T-1}} s_i=\nicefrac {1}{n_T-3},\) then for all \( i=1\ldots , T-3,\) \(s_i=\nicefrac {1}{n_T-3}.\) Any node, and thus any probabilistic action of player T is a best response for player T and his expected payoff is \(-\nicefrac {\lambda }{n_T-3}.\)

    In the latter case, it is, in particular, an optimal action for player T to choose the uniform distribution. Notice that the induced payoff of Player \(T-1\) is in both case given by \(\min _{i \in A_{T-1}} s_i\).

  • Let us now compute the best reply of player \(T-1\) given the action of the other players. Since we consider one-lag subgame perfect equilibrium, we consider as given the best-response of player T. The expected payoff of player \(T-1\) if he uses the action \(\alpha \in \Delta (A_{T-1})\) given the action \(s \in \Delta (A_{T-2})\) of player \(T-2\) is given by:

    $$\begin{aligned} -\lambda \left[ \sum _{i=1}^{n_T-4} s_i \alpha _i + \dfrac{1}{n_T-4}\alpha _{n_T-3} \right] +\min _{i=1,\ldots , n_T-3} \alpha _i \end{aligned}$$
    (2.2)

    One can show (see Section 3) that if the linkage cost \(\lambda \) is not too high, the behavior of player \(T-1\) is completely determined by the objective to maximize the probability that his successor links to the same node as he does (i.e. the second term in Equation 2.2). Hence, independently of the action \(s \in \Delta (A_{T-2})\) of player \(T-2,\) the objective of player \(T-1\) is to maximize \(\min _{i \in A_{T-1}} s_i\). Therefore, he must choose the uniform distribution over \(A_{T-1}.\) He thus minimizes the information player T has about the link he has chosen.

  • If player \(T-1\) choses the uniform distribution independently of the choice of player \(T-2,\) player \(T-2\) shall focus only on minimizing his linkage cost and thus choose the node that player \(T-3\) is less likely to have connected to. In a nutshell, the problem of player \(T-2\) is identical to the problem faced by player T and thus admits the same solutions. Accordingly, the problem of player \(T-3\) is similar to the problem of player \(T-1\) and he ought to choose the uniform distribution.

  • More broadly, one can show by induction that along an equilibrium path, players in \(\{2,\ldots ,T\} \cap \{T-(2k+1), \ k \in {\mathbb {N}}\}\) ought to choose the uniform distribution and players in \(\{2,\ldots ,T\} \cap \{T-2k,\ k \in {\mathbb {N}}\}\) are indifferent between all possible actions (in particular they can choose the uniform distribution).

Overall, uniform attachment appears as the focal equilibrium of our game as it corresponds to strategies that induce an equilibrium independently of the length of the game. Indeed, uniform attachment is an equilibrium action for each player and the only equilibrium action for the penultimate player. This suggests that simple forms of competition and imperfect information do suffice to generate random network formation processes.

3 Sequential competition on networks

3.1 Sufficient conditions for the emergence of preferential attachment

Building on the above example, we focus, in the following, on network formation games in which the payoffs of players depend on the timing of link formation. Moreover, for sake of analytical tractability, we restrict attention to the subset of games where there is a one-period informational lag and the payoff of a player is only affected by the links formed by his immediate predecessor and successor. In this setting, a class of games giving rise to random network formation process can be characterized by the following feature: if two successive players link to the same node, the payoff from link formation is distorted to the benefit of the first player. In other words, we consider that two successive players who target the same node compete for some value related to that node. This value depends on the structure of the network and the position of the target node therein and is thus represented by a function \(f:\mathcal {G}\times A_T \rightarrow {\mathbb {R}}.\) Furthermore, a parameter \(\lambda \in {\mathbb {R}}\) measures the payoff distorsion between a player and his predecessor. Then, to define the resulting payoff function \(\pi _{f,\lambda },\) one must characterize the outcome of the interaction between player t and his successor. It is defined as follows for each \(t \le T-1.\)

  • If players t and \(t+1\) link to the same node, i.e. if the realizations \(m_t \in A_t\) and \(m_{t+1} \in A_{t+1}\) of their actions are such that \(m_t=m_{t+1}=i\) then both players compete in node i. Player t is the leader in this competition and receives a positive payoff \(f(\tilde{g}_{t-2},i)\) that depends on the connected node i and the commonly observed history of the network \(\tilde{g}_{t-2}.\) Player \(t+1\) is the follower in this competition and receives a negative payoff \(- \lambda f(\tilde{g}_{t-2},i)\) where \(\lambda >0.\)

  • If players t and \(t+1\) link to two different nodes (and \(t+1\) does not link to \(n_t-1,\) who is outside the set of potential connections of t), the players do not compete and we consider their payoffs are set to a benchmark of zero.

  • If player \(t+1\) links to node \(n_t-1\) (which is outside the set of potential connections of t), we consider he faces a cost equal to the harmonic meanFootnote 1 of costs in case of competition \(\lambda \overline{f}(\tilde{g}_{t-2})= \nicefrac {\lambda }{(\sum _{i \in A_{t}}\nicefrac {1}{f(\tilde{g}_{t-2},i)})}.\) Player t then receives \(\overline{f}(\tilde{g}_{t-2})\).

For \(t \in \{2,\ldots ,T-1\},\) the payoff of player t is then determined by summing the outcomes of the interactions with player \(t-1\) (where t is the successor) and with player \(t+1\) (where t is the predecessor). For player 1,  the payoff is completely determined by the outcome of the interaction with player 2 while for player T,  it is determined by the outcome of the interaction with player \(T-1.\) Figure 1 illustrates this payoff structure.

Fig. 1
figure 1

The payoffs generated by pairwise interaction for the payoff function \(\pi _{f,\lambda }\)

Full size image

One can first remark that in this setting, if \(\lambda <1,\) there is a social surplus if two successive players link to the same node. Accordingly, the socially efficient network is a star centeredon the node initially targeted by player 1. However, because of competition, individuals incentives are not aligned with social efficiency. Indeed, each player has an advantage in the competition with his successor and thus aims to attract him towards his target node. However, the successor is at a disadvantage if he enters the competition with his predecessor and thus has incentives to target a different node. This conflict of interests motivates the strategic usage of information by the players and the implementation of probabilistic actions, which eventually give rise to random network formation processes. The remaining of this section provides formal proof of this result by showing that \(\epsilon \)-equilibria of \(\Gamma (g_0,T,1, \pi _{f,\lambda })\) are observationally equivalent to random network formation processes, whose specific features depend on the choice of f.

This observational equivalence holds exactly, i.e. at a lagged subgame perfect equilibrium, for specific cases, e.g. the uniform payoff function introduced above. In the general case, it holds approximately, i.e. at a lagged subgame perfect \(\varepsilon \)-equilibrium that corresponds to an equilibrium of a perturbed game. The perturbed game, denoted by \(\Gamma (g_0,T,1,\pi '_{f,\lambda }),\) is identical to the original one \(\Gamma (g_0,T,1,\pi _{f,\lambda })\) but for the fact that when \(T-t\) is even and players t and \(t+1\) link to the same node, player t receives a payoff of \({f(\tilde{g}_{t-1},i)}\) (rather than \(f(\tilde{g}_{t-2},i)\) in the original game). Figure 2 illustrates the differences between the payoff in the original and the perturbed games.

These equivalence results also require the following technical condition on the normalization of f,  which is assumed to hold in the remaining of the paper.

Assumption 3.1

(Normalization) One has:

  1. 1.

    For every \(\tilde{g} \in \mathcal {G},\) \(0\le f(\tilde{g}) \le 1\)

  2. 2.

    For every tree \(\tilde{g} \in \mathcal {G},\) every admissible successor \(g \in \mathcal {S}(\tilde{g})\) of \(\tilde{g}\) and every node \(i \in \tilde{g},\) one has \(|\nicefrac{1}{f(g,i)}-\nicefrac{1}{f(\tilde{g},i)}|\le 1.\)

It implies in particular that for every tree \(\tilde{g} \in \mathcal {G},\) every admissible successor \(g \in \mathcal {S}(\tilde{g})\) of \(\tilde{g}\) and every node \(i \in \tilde{g},\) one has

$$\begin{aligned} \nicefrac {f(g,i)}{f(\tilde{g},i)} \le 2. \end{aligned}$$
Fig. 2
figure 2

The payoffs generated by pairwise interaction for the auxiliary payoff function \(\pi '_{f,\lambda }\)

Full size image

The lagged subgame perfect equilibria of the game \(\Gamma (g_0,T,1,\pi '_{f,\lambda })\) can then be characterized as follows.

  • The expected payoff of player T if he uses the action \(\alpha \in \Delta (A_{T-1})\) given the action \(s \in \Delta (A_{T-1})\) of player \(T-1\) and the history of the network up to the end of period \(T-2,\) \(\tilde{g}_{T-2}\) is given byFootnote 2:

    $$\begin{aligned} -\lambda \left[ \sum _{i=1}^{n_{T-3}} f(\tilde{g}_{T-3},i) s_i \alpha _i +{\bar{f}}(\tilde{g}_{T-3}) \alpha _{n_{T-2}} \right] . \end{aligned}$$
    (3.1)

    Given he has no successor, the objective of player T simply is to minimize his linkage cost, i.e. he wants to avoid competition with his predecessor. The problem is similar to the one faced by player T in the example (see Equation 2.1) and we can prove the following result:

Lemma 3.2

Given the tree \(\widetilde{g}_{T-3}\) and the action \(s \in \Delta (A_{T-1})\) of player \(T-1\), the set of best response for player T is determined as follow.

  1. 1.

    either \(\min _{i \in A_{t-1}} s_i f(\tilde{g}_{T-3},i)<\overline{f}(\tilde{g}_{T-3})\) and any probabilistic action with support in \({\text {argmin}}_{i \in A_{T-1}} \ s_i f(\tilde{g}_{T-3},i)\) is a best response.

  2. 2.

    or \(\min _{i \in A_{T-1}} s_i f(\tilde{g}_{T-3},i)=\overline{f}(\tilde{g}_{T-3})\) and any probabilistic action with support in \(A_{T}\) is a best response.

In particular, if the action \(n_T-2\) is a best-response then any action of player T is a best-response.

  • Taking as given the best response of player T,  the expected payoff of player \(T-1\) if he uses the action \(\alpha \in \Delta (A_{T-1})\), given the action \(s \in \Delta (A_{T-2})\) of player \(T-2,\) and the history of the network up to the end of period \(T-3,\) \(\tilde{g}_{T-3}\), is given by:

    $$\begin{aligned} -\lambda \left[ \sum _{i=1}^{n_{T-4}} s_i \alpha _i f(\tilde{g}_{T-4},i) + \overline{f}(\tilde{g}_{T-4}) \alpha _{n_{T-3}} \right] +\min _{i=1,\ldots , n_T-3} \alpha _i f(\tilde{g}_{T-3},i)\nonumber \\ \end{aligned}$$
    (3.2)

    Player \(T-1\) has two conflicting objectives. On the one hand, he has incentives to target a different node than player \(T-2\) and thus to choose a probability distribution whose support is the node that player \(T-2\) is less likely to have connected to, so as to avoid competition with player \(T-2\) with respect to whom he has a disadvantage (first part of Equation 3.2). On the other hand, he wants to maximize the probability of been connected to the same node as player T with whom he competes with the advantage of being the leader (second part of Equation 3.2). However, an important difference is that the cost faced because of the predecessor and the utility received from the successor now depend on the structure of the network. The player has to take into account this heterogeneity by trying to generate links less frequently on high payoff nodes to compensate the incentives of their successors to over-target these nodes. Now, if linking costs are low enough with respect to benefits, i.e. if \(\lambda \) is small, player \(T-2\) shall discard competition with his predecessor and focus on the competition with his successor. Thus, he shall play inversely proportionally to the payoff potential of each node. Namely:

Lemma 3.3

Let \(\lambda < \nicefrac {1}{3},\) and assume that every player plays a one-lag subgame perfect equilibrium. Then, independently of the action \(s \in \Delta (A_{T-2})\) played by player \(T-2\), the best-response of player \(T-1,\) \(\alpha ^* \in \Delta (A_{T-1})\) is to play a probability distribution inversely proportional to the node potential, that is \(\alpha ^*(\widetilde{g}_{T-3})=\mu ^{T-1}_{f}(\tilde{g}_{T-3})\) where

$$\begin{aligned} \mu ^{T-1}_{f}(\tilde{g}_{T-3}):=\left( \dfrac{\overline{f}(\tilde{g}_{T-3})}{f(\tilde{g}_{T-3},1)},\ldots ,\dfrac{\overline{f}(\tilde{g}_{T-3})}{f(\tilde{g}_{T-3},n_{T-3})} \right) \end{aligned}$$
(3.3)

This characterization of equilibrium actions can be extended by backward induction and we obtain the following result.

Lemma 3.4

Assume \(\lambda < \nicefrac {1}{3}\) and let \((\phi ^*)_t\) be a one-lag subgame perfect equilibrium then assuming that every player l after \(t+1\) follows \(\phi ^*_l\), we have

  1. 1.

    if player \(t \in U_T:={\mathbb {N}}^* \cap \{T-2k,\ k \in {\mathbb {N}}\}\) faces the predecessor action s at state \(\tilde{g}_{n_t-3}\), then one has

    1. (a)

      either \(\min _{i \in A_{t-1}} s_i f(\tilde{g}_{t-3},i)<\overline{f}(\tilde{g}_{t-3})\) and any probabilistic action with support in \({\text {argmin}}_{i \in A_{t-1}} \ s_i f(\tilde{g}_{t-3},i)\) is a best response.

    2. (b)

      or \(\min _{i \in A_{t-1}} s_i f(\tilde{g}_{t-3},i)=\overline{f}(\tilde{g}_{t-3})\) and any probabilistic action with support in \(A_{t}\) is a best response.

  2. 2.

    if player \(t \in V_T:{\mathbb {N}}^* \cap \{T-(2k+1), \ k \in {\mathbb {N}}\},\) then independently of the predecessor action \(s\in \Delta (A_{t-1}),\) the best response is to play \(\mu _f^{t}(\tilde{g}_{T-2}) \in \Delta (A_{t}).\)

Remark 3.5

The case of the first player is particular because he does not have a predecessor and thus is only competing with his successor. If stage 1 is at an odd distance of the last stage, then player 1 is constrained to play inversely proportionally to f like any other player in \(V_T\). If stage 1 is at an even distance of the last stage, then he can play any strategy since its successor is constrained to play inversely proportionally to f.

One then obtains the following characterization of one-lag subgame perfect equilibrium for the auxiliary game \(\Gamma (g_0,T,1, \pi '_{f,\lambda })\).

Theorem 3.6

If \(\lambda < \nicefrac {1}{3},\) for every \(g_0 \in G_0\) the following properties hold in the game \(\Gamma (g_0,T,1, \pi '_{f,\lambda })\).

  1. 1.

    There exists a one-lag subgame perfect equilibrium strategy profile \((\phi _{t}^*)_{t =2,\ldots , T}\) such that for all \(t \in \{2,\ldots , T\},\) \(\phi ^*_t(\tilde{g}_{t-2},\mu ^{t-1}_{f}(\tilde{g}_{t-3}))=\mu ^t_{f}(\tilde{g}_{t-2}).\) If T is even, it is true also for \(t=1\). The action profile along the equilibrium path then is \((\mu ^{1}_{f}(\tilde{g}_{-1}), \ldots , \mu ^{T}_{f}(\tilde{g}_{T-2}))\).

  2. 2.

    For every \(t \in {\mathbb {N}},\) every one-lag subgame perfect equilibrium strategy profile \((\phi ^{\#}_{i})_{i =1,\ldots , t+1}\) of the game of length \(t+1\) is such that for all \(\alpha _{t-1}\) and every realization \(\tilde{g}_{t-2}\) of trees, \(\phi ^{\#}_{t}(\tilde{g}_{t-2},\alpha _{t-1})= \mu ^{t}_{f}(\tilde{g}_{t-2}) \in \Delta (A_{t}).\)

One can then show that optimal strategies in the game \(\Gamma (g_0,T,1, \pi '_{f,\lambda })\) are approximately optimal in the original game \(\Gamma (g_0,T,1,\pi _{f,\lambda })\). More precisely, in the perturbed game, playing according to \(\mu _f\) renders both the successor and the predecessor of a player indifferent between all the nodes. In the unperturbed game, this strategy still renders indifferent the successor of a player but marginally distorts the incentives of his predecessor. It is thus only approximately optimal. Namely, one has the following corollary.

Theorem 3.7

Let \(\lambda < \nicefrac {1}{3}\). For every \(\varepsilon >0\), there exists \(n^*\in {\mathbb {N}}\) such that for every \(g_0 \in G_0\) with more than \(n^*\) nodes, the following properties hold in the game \(\Gamma (g_0,T,1, \pi _{f,\lambda })\).

  1. 1.

    There exists a \(\varepsilon \) one-lag subgame perfect equilibrium strategy profile \((\phi _{t}^*)_{t =2,\ldots , T}\) such that for all \(t \in \{2,\ldots , T\},\) \(\phi ^*_t(\tilde{g}_{t-2},\mu ^{t-1}_{f}(\tilde{g}_{t-3}))=\mu ^t_{f}(\tilde{g}_{t-2}).\) If T is even, it is true also for \(t=1\). The action profile along the equilibrium path then is \((\mu ^{1}_{f}(\tilde{g}_{-1}), \ldots , \mu ^{T}_{f}(\tilde{g}_{T-2}))\).

  2. 2.

    For every \(t \in {\mathbb {N}},\) every one-lag subgame perfect equilibrium strategy profile \((\phi ^{\#}_{i})_{i =1,\ldots , t+1}\) of the game of length \(t+1\) is such that for all \(\alpha _{t-1}\) and every realization \(\tilde{g}_{t-2}\) of trees, \(\phi ^{\#}_{t}(\tilde{g}_{t-2},\alpha _{t-1})= \mu ^{t}_{f}(\tilde{g}_{t-2}) \in \Delta (A_{t}).\)

Hence, if the initial network is sufficiently large, the optimal behavior of players is well-approximated by the equilibrium strategies of the game \(\Gamma (g_0,T,1, \pi '_{f,\lambda }).\)

Theorems 3.6 and 3.7 bring two main insights about the emergence of random network in the game \(\Gamma (g_0,T,1, \pi _{f,\lambda })\). First, the random network formation process corresponding to \(\mu _f,\) i.e where each node is targeted with a probability inversely proportional to its potential payoff, is an (approximate) equilibrium strategy. Second, playing according to \(\mu _f\) is the only optimal action for player t in the game of length \(t+1.\) Overall, \(\mu _f\) is an “uniform” best response in the sense that it induces an equilibrium independently of the length of the game and is the only strategy with this property. Therefore, the corresponding equilibrium can be consideredto be the focal equilibrium of the game. In this sense, our model of sequential competition provides micro-foundations for random network formation process.

A particularly noteworthy corollary of Theorem 3.6 concerns the case where the payoff potential of each node is inversely proportional to its degree. Then, preferential attachment emerges as the focal equilibrium of the game.

Corollary 3.8

Assume that for all \(T \in {\mathbb {N}},\) for all \(i \in A_t,\) and for all \(\tilde{g} \in \mathcal {H},\) \(f(\tilde{g},i)=\nicefrac {1}{d_i^{\tilde{g}}}\) where \(d^{\tilde{g}}\) is the degree sequence of the last graph in the history \(\tilde{g}.\) Then, the payoff function satisfies assumption 3.1 and the equilibrium strategy given by Theorem 3.6 is preferential attachment i.e. the profile of actions along an equilibrium path is such that for player t,  one has:

$$\begin{aligned} \mu ^{t}_{f}(\tilde{g}_{t-2}):= \left( \dfrac{\tilde{d}_{t-2,1}}{\sum _{j \in A_t} \tilde{d}_{t-2,j}},\ldots ,\dfrac{\tilde{d}_{t-2,t-2}}{\sum _{j \in A_t} \tilde{d}_{t-2,j}}) \in \Delta (A_{t}\right) \end{aligned}$$
(3.4)

where \(\tilde{d}_{t-2,j}\) denote the degree of node j in the graph \(\tilde{g}_{t-2}\) so that players target existing nodes proportionally to their degree.

Remark 3.9

The structure of interactions consideredabove is very specific as a player interacts only with his predecessor and successor. More complex interactions structures seem hardly tractable analytically in general. However, in principle, the model would yield similar results if extended in such a way that a set of player has a common competitive and informational relationship towards a successor. An extreme case where this assumption is satisfied is that where all players only observe and connect to the initial network. Then, if each player competes (bilaterally) with all his predecessors and all his successors, the arguments used in the proof of Lemma 3.4 could be applied provided the payoffs were normalized in such a way that players determine their behaviour only as a function of their successors. In such a setting, the incentives of players would be very similar to that in the above model and the arguments used in the proof of Lemma 3.4 and Theorem 3.6 could likely be extended.

3.2 Necessary conditions for the emergence of preferential attachment

Corollary 3.8 puts forward very specific conditions under which a network formation game admits an equilibrium that is observationally equivalent to preferential attachment. Besides the competitive interaction between a player and its predecessor, utility must be inversely proportional to the degree of the node targeted by the predecessor. In the following, we show that this latter condition can hardly be dispensed with: it is necessary for preferential attachment to emerge in an extended class of games.

Namely, we consider games where there is one period lag and the payoff of a player depends of the nodes chosen by its immediate predecessor and successor but where the precise relation between node characteristics and payoffs is left unspecified. More precisely, we consider games where given pure actions \((m_k)_{k \in T-\{t\}}\) of players other than t yielding a degree sequence \((d^{t-2}_k)_{k \in T-\{t\}})\) in period \(t-2\) (observed by player t), the payoff yielded to player t by the pure action \(a_t \in A_t\) is of the form:

$$\begin{aligned} \pi _t(a_t,(m_k)_{k \in T-\{t\}})&= f_t(d^{t-2}_{a_t},d^{t-2}_{m_{t-1}}) (1-\delta _{a_t,m_{t-1}}) + g_t(d^{t-2}_{a_t}) \delta _{a_t,m_{t-1}} \end{aligned}$$
(3.5)
$$\begin{aligned}& + h_t(d^{t-2}_{a_t},d^{t-2}_{m_{t+1}}) (1-\delta _{a_t,m_{t+1}}) + k_t(d^{t-2}_{a_t}) \delta _{a_t,m_{t+1}}, \end{aligned}$$
(3.6)

where \(\delta \) is the Kronecker symbol. Hence payoffs are determined by the degree sequence and the actions of consecutive agents. More precisely, \(f_t\) (resp. \(h_t\)) characterizes the payoff when player t and his predecessor (resp. successor) targets a different node and \(g_t\) (resp. \(k_t\)) characterizes the payoff when player t and his predecessor (resp. successor) targets the same node. In particular, player T,  who has no successor, is assumed to have a payoff function of the form:

$$\begin{aligned} \pi _T(a_T,(m_k)_{k <T})= f_T(d^{T-2}_{a_T},d^{T-2}_{m_{T-1}}) (1-\delta _{a_T,m_{T-1}}) + g_T(d^{T-2}_{a_T}) \delta _{a_T,m_{T-1}} \end{aligned}$$
(3.7)

Considering the degree sequence \((d^{T-2}_k)_{k <T}\) as given, and thus omitting the time superscript, the expected payoff of player T when he plays the pure action \(i \in A_T { \cap A_{T-1}}\) while player \(T-1\) plays the mixed action \(\lambda \in \Delta (A_{T-1} )\) is then given by

$$\begin{aligned} \xi _i:= \sum _{j \in A_{T-1}/\{i\} } f_T(d_i,d_j) \lambda _j +g_T(d_i)\lambda _i. \end{aligned}$$
(3.8)

In particular, if player \(T-1\) plays a preferential attachment strategy, one has \(\lambda _j:=\dfrac{d_j}{\overline{d}}\) with \(\overline{d}:= \sum _{j \in A_{T-1} } d_j\) and the expected payoff is given by

$$\begin{aligned} \xi _i:= \sum _{j \in A_{T-1}/\{i\} } f_T(d_i,d_j) \dfrac{d_j}{\overline{d}}+g_T(d_i) \dfrac{d_i}{\overline{d}} \end{aligned}$$
(3.9)

In this setting, a necessary condition for preferential attachment to be the best reply of player T is that for all \(i,k \in A_{T-1},\) one has \(\xi _i=\xi _k.\) If one further assumes payoffs are normalised so that \(\sum _{i \in A_{T-1}} \xi _i\) is constant with respect to the degree distribution \((d_j)_{j \in A_{T-1}}\) (as in our example above), one gets the following necessary condition for preferential attachment to be the best reply of player T and thus for preferential attachment to be a subgame perfect equilibrium.

Proposition 3.10

Consider a game such that the payoff function satisfies Equation 3.6, f and g are continuously differentiable and \(\sum _{i \in A_{T-1}} \xi _i\) is constant. Then preferential attachment is a subgame perfect equilibrium of the game only if there exists a function \(\phi : {\mathbb {R}}_+ \rightarrow {\mathbb {R}}\) and \(k \in {\mathbb {R}}\) such that:

  1. 1.

    \(f_T(d_i,d_j)=\dfrac{\phi (d_i)}{d_j}\)

  2. 2.

    \(g_T(d_i)= \dfrac{k -\sum _{j \in A_T/\{i\}} \phi (d_i)}{d_i}\)

Hence the conditions put forward in Corollary 3.8 are extended by Proposition 3.10 in the sense that a necessary condition for preferential attachment to be a subgame perfect equilibrium is that the payoff received by a player is inversely proportional to the degree of the node targeted by its predecessor. The main difference with the result in Corollary 3.8 is that the payoff when the player targets a different node than its predecessor is not necessarily zero. Competition does not occur only when the players target the same node but is extended to a setting where targeting different nodes can yield payoffs of different magnitude and signs, but remain inversely proportional to the degree of the node targeted by the predecessor. Nevertheless, this result implies that preferential attachment is likely to emerge from strategic network formation processes only in certain specific settings.

4 Microeconomic applications

Despite the limitations highlighted above, we describe in this section two toy models that give rise to payoff structures of the form \(\pi _{\lambda ,f}.\)

  • First, the “variable benefit model” corresponds to situations where the actions of the predecessor affect the benefits of link formation of a player but not its cost. Formally, it corresponds to a situation where, assuming the cost of link formation \(\alpha \) is such that \(\alpha > \lambda f(\tilde{g},i),\) the benefit of link formation equals its cost if the player links to a different node than his predecessor, while if the player links to the same node as his predecessor, he gets a benefit of \(\alpha - \lambda f(\tilde{g},i)\) and his predecessor gets a benefit of \(\alpha +f(\tilde{g},i).\) The variable benefit model applies for example to the formation of supply relationships in cases where the formation of these relationships is intertwined with Stackelberg competition. Indeed, consider links are supply relationships and \(f(\tilde{g},i)\) is an indicator of the potential market at node i,  given network \(\tilde{g}.\) Two successive players are thought to offer comparable products. Hence, if they link to the same node, they end up competing for the market potential. It is natural to consider that the first player is a Stackelberg leader in this case. Let us then consider a standard Stackelberg game with a linear price function of the form \(a-b(q_1+q_2)\) where \(q_1\) and \(q_2\) are the output of the leader and the follower respectively and production costs of the form \(c+dq\) where c is a fixed part and d a unit cost of production. Simple algebra shows that equilibrium profits for leader and follower are respectively given by \([\nicefrac {(a-d)^2}{8b}]-c\) and \([\nicefrac {(a-d)^2}{16b}]-c.\) This is consistent with the payoff in the variable benefit model as long as \(c=(1+2\lambda )f(\tilde{g},i)\) and \(\nicefrac {(a-d)^2}{16b}=(1+\lambda ) f(\tilde{g},i).\) That is the fixed part, \(c=(1+2\lambda )f(\tilde{g},i)\) corresponds to the linking cost and, the operating profit (net of fixed cost) of the first player, \(\nicefrac {(a-d)^2}{16b}=(1+\lambda ) f(\tilde{g},i),\) is double that of his successor. In this setting, Theorem 3.6 implies that the equilibrium of the game \(\Gamma (g_0,T,1, \pi _{f,\lambda })\) is observationally equivalent with a random network formation model in which the probability of connections is inversely proportional to market potential. In particular if the market potential at a node is thought to be inversely proportional to its degree, i.e. to its existing number of suppliers, then equilibrium actions are observationally equivalent with preferential attachment.

  • Second, the “variable cost model” corresponds to situations where the actions of the predecessor affects the costs of link formation for a player but not its benefit. Formally, this corresponds to a situation where, assuming the benefit of link formation \(\beta \) is such that \(\beta > f(\tilde{g},i),\) the cost of link formation equals its benefit if the player links to a different node than his predecessor, while if the player links to the same node as his predecessor, he pays a cost of \(\beta +\lambda f(\tilde{g},i)\) and his predecessor pays a cost of \(\beta -f(\tilde{g},i).\) For example, if \(\beta = (2+\lambda )f(\tilde{g},i)\) the “follower” pays twice the costs of the “leader”. The variable cost model yield a preferential attachment process in a framework similar to that of the co-author model of Jackson and Wolinsky (1996) but with costs of co-authorship that are increased for the latest co-author. More precisely, in the co-author model, the utility of player i given a network g is given by

    $$\begin{aligned} u_i(g)= & {} \sum _{\{j \mid \{i,j\} \in g\}} \dfrac{1}{d_i(g)} +\dfrac{1}{d_j(g)} + \dfrac{1}{d_i(g)d_j(g)} \nonumber \\= & {} 1+\left( 1+\dfrac{1}{d_i(g)} \right) \sum _{\{j \mid \{i,j\} \in g\}} \dfrac{1}{d_j(g)} \end{aligned}$$
    (4.1)

    where \(d_k(g)\) is the degree of node k in g and the utility of a link \(\{i,j\}\) is determined by the effort exerted by i,  \(\nicefrac {1}{d_i(g)},\) the effort exerted by j,  \(\nicefrac {1}{d_j(g)},\) and an interaction term \(\nicefrac {1}{d_i(g)d_j(g)}.\) Let us consider a model whithout the interaction term and where the incoming player pays the cost. As a consequence, players have always an incentive to accept incoming links. The incoming player, t,  forms a single link and thus has a benefit of \(1+\nicefrac {1}{d_j(\tilde{g})}\) when connecting to node j in network \(\tilde{g}.\) The payoff of player t then depends on the cost associated to the link, which depend on the behavior of the successor:

    • If the successor links to a different node, the cost is assumed to be equal to the benefit, \(1+\nicefrac {1}{d_j(\tilde{g})},\) and thus the payoff to player t is zero (up to a constant).

    • If the successor links to node j,  the cost is reduced to 1 for player t and increases to \(1+\nicefrac {(1+\lambda )}{d_j(\tilde{g})}\) for the successor. Thus, the payoff to player t is \(\nicefrac {1}{d_j(\tilde{g})}\) and that of his successor is \(\nicefrac {-\lambda }{d_j(\tilde{g})}\)

    In this setting, Theorem 3.6 implies that the focal equilibrium of the game \(\Gamma (g_0,T,1,\pi _{f,\lambda })\) is observationally equivalent to preferential attachment. The key assumption supporting this result is the differential cost paid by a player and his successor when they target the same node. This assumption can be justified by considering the trilateral relationship between the target node j,  player t and his successor \(t+1.\) Given t has just established a relationship with j,  \(t+1\) might have to make a more important effort to create an additional relationship. This higher “entry cost” can be linked to the complex process of integration in human groups (see e.g. Blau (1960); Moreland and Levine (1982); Collins (2014)). In this sense, the variable cost model relates strategic choices with respect to the costs of integration in social groups to the formation of social networks via a preferential attachment process (see e.g. Kunegis et al. (2013); De Blasio et al. (2007); Capocci et al. (2006)). This interpretation highlights a substantial difference with that of the co-author model of Jackson and Wolinsky (1996). In the co-author model, the formation of social relationships is perfectly symmetric. In our setting, it is one-sided. Indeed, although social relationships are bilateral, their formation is often one-sided in practice with a newcomer making a substantial effort to establish a relationship so as to enter a social group. More broadly, our results are at odds with standard explanations of the emergence of preferential attachment based on synergies Barabási and Albert (1999). In our framework, preferential attachment must rather be tied to a congestion effect such that nodes with higher degree have lower payoff. This condition is necessary because in a competitive framework, a player is hedging the risk against his opponent by equalizing his expected payoff and thus put less weight on events with high returns.

5 Conclusion

We propose to model the formation of socio-economic networks as an extensive game in which players sequentially enter the network and strategically form links with their predecessors. In this setting, we investigate the conditions under which random network formation processes such as preferential attachment can emerge as an equilibrium outcome of the game. Conceptually, two conditions are requiredfor players to have incentives to use mixed/probabilistic strategies rather than pure ones in this context. First, players must have imperfect information on the actions of their predecessors and/or on the state of the network. Indeed, a probabilistic strategy can be efficient only if the actual realization of the action is not perfectly observed by the successors. Second, the emergence of probabilistic strategies requires some form of competition between a player and its successors: a player has incentives to reduce the information available to its successors only to the extent that their objectives are in opposition.

We thus investigate a specific class of games of sequential competition in which a player competes with his predecessor and his successor for the benefits induced by a socio-economic relationship with a common party. We show that the focal equilibrium that emerges in this setting is one where players use probability distributions with full support and target the whole network with probabilities inversely proportionally to the utility of each node. Notably, when the utility of a node is inversely proportional to its degree, equilibrium play induces a preferential attachment process. Hence, our model of sequential competition provides a positive answer to the question of the existence of strategic foundations for preferential attachment. However, this observational equivalence holds only under very specific conditions on the payoffs and the structure of interactions. This suggests that preferential attachment can be explained by strategic considerations only in a limited number of situations. A broader question raised by our results is whether it is possible to characterize settings where socio-economic network formation is driven by strategic behavior and settings where it is driven by more boundedly rational forms of behavior.