Antoine Mandel
email: antoine.mandel@univ-paris1.fr

Xavier Venel
email: xavier.venel@univ-paris1.fr.

Sequential competition and the strategic origins of preferential attachment

Keywords: Socio-economic networks, endogenous network formation, game theory JEL codes: SC71, D85

There exists a wide gap between the predictions of strategic models of network formation and empirical observations of the characteristics of socio-economic networks. Empirical observations underline a complex structure characterized by fat-tailed degree distribution, short average distance, large clustering coefficient and positive assortativity. Game theoretic models offer a detailed representation of individuals' incentives but they predict the emergence of much simpler structures than these observed empirically. Random network formation processes, such as preferential attachment, provide a much better fit to empirical observations but generally lack micro-foundations. In order to bridge this gap, we propose to model network formation as extensive games and investigate under which conditions equilibria of these games are observationally equivalent with random network formation process. In particular, we introduce a class of games in which players compete with their predecessors and their successors for the utility induced by the links they form with another node in the network. Such sequential competition games can represent a number of strategic economic interactions such as oligopolistic competition in supply networks or diffusion of influence in opinion networks. We show that the focal equilibrium that emerge in this setting is one where players use probability distributions with full support and target the whole network with probabilities inversely proportional, 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.

Comments 2 Introduction

There exists a wide gap between the predictions of strategic models of network formation and empirical observations of the characteristics of socio-economic networks. Empirical observations underline a complex structure characterized by fat-tailed degree distribution, short average distance, large clustering coefficient and positive assortativity (see e.g. [START_REF] Jackson | Meeting strangers and friends of friends: How random are social networks?[END_REF]. Game theoretic models offer a detailed representation of individuals' incentives but they predict the emergence of much simpler structures than these observed empirically.

Against this background, 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 [START_REF] Barabási | Emergence of scaling in random networks[END_REF] is seen as a quasi-universal model of network formation in domains ranging from biology to sociology through computer science (see [START_REF] Barabási | Scale-free networks: a decade and beyond[END_REF], for a survey of applications). In economics, the "friend of friends" model of [START_REF] Jackson | Meeting strangers and friends of friends: How random are social networks?[END_REF], which can be seen as an extension of preferential attachment, forms the backbone of recent influential contributions in international trade [START_REF] Chaney | The network structure of international trade[END_REF], industrial dynamics [START_REF] Luttmer | On the mechanics of firm growth[END_REF], or public economics [START_REF] Mayer | The old boy (and girl) network: Social network formation on university campuses[END_REF]. The unusual success, in economics, of such phenomenological models is likely due to their empirical superiority over game-theoretic models. However, they lack micro-foundations. We aim to bridge this gap by putting forward a class of game-theoretic models whose dynamics along an equilibrium path are observationally equivalent with random network formation processes and thus provide micro-foundations for the emergence of network structures consistent with empirical observation.

We represent network formation as an extensive game in which players sequentially enter the network and form links with one of their predecessor. We consider a game form that partly departs from the conventional one as we consider players choose probability distributions as actions and nature then takes an action following these probability distributions. In this setting two conditions appear necessary for players to actually play probabilistically at equilibrium and thus adopt a behavior consistent with random network formation processes. First, players must have imperfect information on the actions of their predecessors and/or on the state of the network. Indeed, a mixed action can be efficient only if the actual realization of the action is not perfectly observed by the successors. Second, the emergence of mixed actions 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.

A salient class of games satisfying these conditions are games of sequential competition in which a player competes with his direct successor (and accordingly with his predecessor) for the benefits induced by the socio-economic relationship they form with a third party in the network. Such games can represent a number of situations where competition is intertwined with network formation such as oligopolistic competition in supply networks or diffusion of influence in opinion networks. We further consider that a player has a competitive advantage over his successor in these bilateral interactions. Therefore, a player seeks competition when his successor aims at avoiding it. Thus, a player has incentives to 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 adopt fully probabilisitic (mixed) strategies. Namely, we show that the focal equilibrium that emerges in our setting is one where players use probability distributions with full support and target the whole network. More precisely, each node is targeted with a probability inversely proportional to the utility it can yield. Notably, if the utility potential of each node is inversely proportional to its degree, as in the co-author model of [START_REF] Jackson | A strategic model of social and economic networks[END_REF], equilibrium play induces a preferential attachment process. Hence, sequential competition provides micro-foundations for the emergence of preferential attachment in the formation of socio-economic networks: preferential attachment appears as the strategic behavior of agents who use mixed strategies in order to benefit from the first-mover advantage in a competition for the benefits of socio-economic links.

Hence when competition and network formation are intertwined, the optimal strategy for players is to spread (probabilistically) their links over the network. This is in strong contrast with the conclusions of the literature on targeting and link formation in a fixed network (e.g. [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF][START_REF] Ballester | Who's who in networks. wanted: The key player[END_REF][START_REF] Grabisch | Strategic influence in social networks[END_REF] where optimal strategies generally focus on a key target or group of targets. This contrast highlights that the interplay between network formation and competition is fundamental in the emergence of preferential attachment.

The literature on the micro-economic foundations of random network formation process, and more specifically preferential attachment, is sparse. The most closely related contributions to ours are [START_REF] Valverde | Scale-free networks from optimal design[END_REF][START_REF] Borgs | Emergence of tempered preferential attachment from optimization[END_REF]. They investigate the emergence of preferential attachement from the behavior of locally optimizing agents. However, our paper is, to our knowledge, the first one to identify potential strategic origins for preferential attachment. We also contribute to the literature on farsighted network formation (see e.g. [START_REF] Dutta | Farsighted network formation[END_REF][START_REF] Page | Networks and farsighted stability[END_REF][START_REF] Herings | Farsightedly stable networks[END_REF] as well as the survey in [START_REF] Jackson | A survey of network formation models: stability and efficiency[END_REF]) by developing a model of network formation as an extensive-form game. In this latter respect, our approach is connected to this of [START_REF] Aumann | Endogenous formation of links between players and coalitions: an application of the shapley value[END_REF] 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.

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 preferential attachment emerges as an equilibrium outcome of the game. Section 4 concludes. All the proofs are given in the appendix.

3 Network formation as an extensive game

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 in succession. At the period in which he enters the network, each player chooses a probability distribution (a mixed action) on how to link to the current tree and then nature draws randomly a realized link. We assume that the realized link becomes observable only with a certain lag so that the successors of a player might have imperfect information about the link he has actually formed. 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, for every l ≥ 1, we denote by G l the set of trees with l nodes and by G = ∪ l≥1 G l the set of all finite trees. Given a tree g 0 ∈ G, we denote by G(g 0 ) the set of trees in G that contains g 0 as a subtree and have one more node than g 0 . Further, we denote by

G T (g 0 ) = {(g i ) i=0,••• ,T ∈ T i=1 G ni | ∀t < T g t ∈ G(g t+1 )}
the set of tree-histories that can be formed by the successive addition of T nodes to g 0 .

A game Γ(g 0 , T, τ, π) 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), τ is the informational lag and π = (π t ) 1≤t≤T is the set of payoff functions where for each t = 1, • • • T, π t : G T (g 0 ) → 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 and chooses a linkage probability α 1 over A 1 = {1, • • • , n 0 -1}. Then at period 1 , nature chooses m 1 ∈ A 1 following α 1 . A new node n 1 = n 0 + 1 and a link (m 1 , n 1 ) is added to the graph. We denote by g 1 the updated graph.

• At period 2, player 2 enters and chooses a linkage probability α 2 in A 2 = {1, • • • , n 0 }. Then at period 2 , nature chooses m 2 ∈ A 2 following α 2 . A new node n 2 = n 0 + 2 and a link (m 2 , n 2 ) is added to the graph. We denote by g 2 the updated graph.

• More generally, for every period 2 ≤ t ≤ T , player t enters and chooses a probability α t in A t = {1, • • • , n t-2 } (we assume that there is a one period lag before n t-1 , i.e. player t -1, can receive a link). Then at period t , nature chooses m t ∈ A t following α t . A new node n t = n 0 + t and a link (m t , n t ) is added to the graph. The updated graph is denoted by g t .

For every t ≥ 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 before stage t -1 (included). Finally, he knows all the choices of nature until stage t -1 -τ . Notice that it implies that player t can compute the tree at stage t -1 -τ from the initial tree and the past choices of nature but that for latter 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 3 Documents de travail du Centre d'Economie de la Sorbonne -2018.35 players t -τ tot -1. Formally, a strategy for player t is a function from

H t = Π t-τ -1 i=1 A i × Π t-1 j=1 ∆(A j ) to ∆(A t ).
We denote by Σ t,τ the corresponding set of strategies.

Given a strategy profile (φ t ) t=1,••• ,T , one can then define a probability distribution P g0,φ on the set of histories of length T starting from g 0 and the payoff of player t as the expectation of π t under P g0,φ . This leads us to the following notion of Nash equilibrium. Definition 3.1 Let Γ(g 0 , T, τ, π) be a game. A profile of strategies (φ t ) 1≤t≤T is a Nash equilibrium if for every 1 ≤ t ≤ T , and for every strategy ψ t ∈ Σ t,τ , one has:

E P g 0 ,(φ t ,φ -t ) (π t ) ≥ E P g 0 ,(ψ t ,φ -t ) (π t )
The sequential nature of action and of information in the game further allows player t to form a belief P ht,αt,φ>t about the set of tree-history of length T on the basis of the strategies of his successors φ >t , of his own action α t and of the history he observes h t , i.e. the observed actions α <t = (α 1 , • • • , α t-1 ) and the realizations of these actions observed with a τ periods lag m <t-τ = (m 1 , ...., m t-τ -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 that are defined as follows.

Definition 3.2 Let Γ(g 0 , T, τ, π) be a game. A profile of strategies (φ t ) 1≤t≤T is a lagged subgame perfect equilibrium if for every 1 ≤ t ≤ T and for every history h t ∈ H t , we have

∀α ∈ ∆(A t ), E P h t ,φ t (h t ),φ >t (π t ) ≥ E P h t ,α ,φ >t (π t ) ,
Remark 3.3 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 we consider is more restrictive as we constrain the beliefs, even off the equilibrium path, to be consistent with the observed history.

In fact, our notion of equilibrium is linked to the conventional notion of subgame perfect equilibrium for the game with perfect information where the link (n t , m t ) is created at time t + τ instead of t. This new game can be shown to be equivalent to our extensive game (see the proof in the appendix).

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 [START_REF] Barabási | Emergence of scaling in random networks[END_REF] or "friends of friends" models à la [START_REF] Jackson | Meeting strangers and friends of friends: How random are social networks?[END_REF]. In this perspective, it is useful to disinguish two categories of actions for a player in our game. On the one hand, a player can choose to play deterministically, i.e. choose to link to a given node with probability 1. 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 a probability distribution with nontrivial support. In this latter case, we shall say that the player chooses a mixed action and refer to the corresponding type of equilibrium as "equilibrium with mixed actions."

One can then note that random network formation models can only be supported by equilibria with mixed actions. This raises the question as to which information and incentive structures can induce players to play mixed rather than pure actions. Two necessary conditions can be put forward à priori 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 mixed action is purposeful only if the actual realization of the action is not perfectly observed by the successors. Second, mixed 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 3.4 (Imperfect information) If there is no informational lag, i.e. if τ = 0, the game Γ(g 0 , T, τ, π) necessarily has at least one equilibrium with pure actions. Indeed, one can solve the game by backward induction. The last player clearly has a pure best response that may depends on the actions of all the previous players. It implies in particular that Player T -1 has no incentives to randomize since Player T learns his action in any case, he can therefore chose a pure Best-reply to the predecessor. The same reasoning for every player yields a pure subgame perfect equilibrium. Moreover, up to an arbitrary small modification of payoff functions that removes any indifference between pure actions at any stage of the game, the game only has equilibria with pure actions.

Remark 3.5 (Competition) If the incentives of the players are perfectly aligned in the sense that there exists a tree-history g ∈ G T (g 0 ) that is a global optimum for each player -i.e such that for every g ∈ G T (g 0 )/{g} and for every t = 1, • • • , T π t (g) > π t (g)-then there exists a unique equilibrium of the game and this equilibrium has pure actions corresponding to the history g.

More broadly, it suffices that the incentives of the players be coordinated to ensure that there exists an equilibrium path with pure actions only. Namely, if the game is potential, i.e if there exists a function φ : Π i∈T A i → R such that for every sequence of pure actions (m t ) t∈T ,

∀a i , b i ∈ A i , π i (b i , (m t ) t∈T -{i} ) -π i (a i , (m t ) t∈T -{i} ) = φ(b i , (m t ) t∈T -{i} ) -φ(a i , (m t ) t∈T -{i} ),
one knows (see [START_REF] Monderer | Potential games[END_REF] that the normal-form game ((A t ) t∈T , (π t ) t∈T ) has at least one pure equilibrium given by the profile of actions that maximizes the potential function φ. In our dynamical setting, we obtain a pure lagged subgame perfect equilibrium by backward induction: each player maximizes the expectation of the potential function knowing his information and that other players also follow this equilibrium. By selecting each time a pure action, we construct an equilibrium that generates an equilibrium path with only pure actions.

A basic example

We conclude this section by introducing a basic example of a game that exhibits imperfect information and some form of competition. We show that uniform attachment emerges as the focal equilibrium. This example anticipates important features of the class of games we introduce in the next section although it is extremely stylized and the role of network effects is limited to a minimum.

Namely, 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 [START_REF] Jackson | A strategic model of social and economic networks[END_REF]) but face (congestion) costs related to indirect linkages with their predecessors (as in the co-author model of [START_REF] Jackson | A strategic model of social and economic networks[END_REF]. 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 λ ∈ 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 λ /(nt-3) whereas player t -1 receives a payoff of 1 nt-3 . We consider such a game of length T ∈ N, Γ(g 0 , T, π, 1). We can characterize equilibrium by backward induction as follows (the proof follows immediately from the general results of the next section).

• Given the action of player T -1, s ∈ ∆(A T -1 ), the expected payoff of player T if he uses the action α ∈ ∆(A T ) is:

-λ[

n T -3 i=1 s i α i + 1 n T -3 α n T -2 ] (3.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 -

If min i∈A T -1 s i = 1 /n T -3, then for all i = 1 • • • T -3, s i = 1 /n T -3.
Any node, and thus any mixed strategy of player T is then a best response for player T and his expected payoff is

-λ /n T -3.
In the latter case, it is in particular an optimal action for player T to play uniformly at random. Notice that the induced payoff of Player T -1 is in both case given by min i∈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 are looking at 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 α ∈ ∆(A T -1 ) given the action s ∈ ∆(A T -2 ) of player T -2 is given by:

-

λ n T -4 i=1 s i α i + 1 n T -4 α n T -3 + min i=1,•••n T -3 α i (3.2)
One can show (see section 4) that if the linkage cost λ is not too high, the behavior of player T -1 is completely determined by the objective to maximize the probebility that his successor links to the same node as he does (i.e. the second term in equation 3. 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 of imperfect information do suffice to generate random network formation processes.

Sequential competition on networks

Generalizing the example introduced above, one can define a class of games where the network formation process is governed by a sequence of intertwined competitive games between a player and his successors (as well as his predecessors). Namely, we consider that two successive players who target the same existing node compete for some value related to that node. In general, this value depends on the structure of the network and the position of the target node therein. The leading player has an advantage in this competition and thus aims to attract his successors towards his target node. Conversely, the followers has a disadvantage if he enters this competition and thus incentives to target a different node. This conflict of interests motivates the strategic usage of information by the players and the implementation of mixed actions, which eventually give raise to random network formation processes. As emphasized below, this framework captures a number of socio-economic interactions in which an incumbent has incentives to attract new nodes in his area of the network in order to increase his centrality whereas outsiders face a trade-off between fostering their own centrality and falling into the dependency of their predecessor. 6 Documents de travail du Centre d'Economie de la Sorbonne -2018.35 For the sake of analytical tractability, we restrict attention in the following to the case where there is a one period informational lag and competition is only between a player and his immediate predecessor and successor. Formally, we consider the game such that at every period 1 ≤ t ≤ T :

• If players t and t + 1 link to the same node, i.e. if the realizations m t ∈ A t and m t+1 ∈ A t+1 of their probabilistic 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 (g t-2 , i) that depends on the connected node i and the commonly observed history of the network gt-2 . Player t + 1 is the follower in this competition and receives a negative payoff -λf (g t-2 , i) where λ > 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 mean1 of costs in case of competition λf (g t-2 ) = λ /( i∈A t 1 /f(g t-2 ,i)). Player t then receives f (g t-2 ).

Notice that the first player has only a payoff from its successor. We shall impose a technical assumption on the normalization of f in the remaining of the paper:

Assumption 4.1 (Normalization) One has:

1. For every g ∈ G, f (g) ≤ 1

2. For every tree g ∈ G, every admissible successor g ∈ G of g and every node i ∈ g, one has

f (g,i) /f(g,i) ≤ 2.
Independently of the normalization, this model of network formation through sequential competition can capture a number of situations in which network formation is intertwined with competition between players.

• First, formation of social relationships. If one considers that when two players successively link to the same node the benefit of the relationship mostly accrue to the first player while the cost is shared between players, then the first player might reap a benefit and the second face a proportional cost. In such a setting, f (g, i) measures the benefit obtained by linking to agent i given the network g.

• Second, formation of influence relationships (as in [START_REF] Bimpikis | Competitive targeted advertising over networks[END_REF][START_REF] Grabisch | Strategic influence in social networks[END_REF]. Consider two successive players that have opposite opinions and aim at forming relationships with existing agents in order to influence their opinion. If the agent that speaks first has a stronger influence than the one that speaks second and both players link to the same agent the first player has a relative advantage and the second player faces a relative cost with respect to the situation where both players link to a different agent. In such as setting, f (g, i) measures the importance of the opinion of agent i given the network history g

• Third, oligopolistic competition in networks (see [START_REF] Bimpikis | Cournot competition in networked markets[END_REF], for a recent contribution from this perspective). Consider links are supply relationships and that f (g, i) is an indicator of the potential market at node i, given the history of the economy summarized by 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 Stackleberg leader in this case. Assume a linear price 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 cost and d the unit cost of production. Then, simple algebra shows that equilibrium profits for leader and follower are respectively given by [ (a-d) 2 /8b] -c and [ (a-d) 2 /16b] -c. This is consistent with our networked game as long as c = (1 + 2λ)f (g, i) and (a-d) 2 /16b = (1 + λ)f (g, i). That is fixed cost of production are given by (1 + 2λ)f (g, i), the operating profit (net of fixed cost) of the first player is double this of his successor and λ represents the share of the fixed cost not covered for the successor. In other words, the fixed cost of forming a link (1 + λ)f (g, i) is the same for both players while the benefits of forming the link for the first player are double these of his successor.

We shall denote by π f,λ the payoff function induced by f and λ. As for the example of subsection 3.2, one-lag subgame perfect equilibrium of the game Γ(g 0 , T, π f,λ , 1) can be determined by backward induction as follows.

• The expected payoff of player T if he uses the strategy α ∈ ∆(A T -1 ) given the action s ∈ ∆(A T -1 ) of player T -1 and the history of the network up to the end of period T -2, gT -2 (in fact the payoff of player T only depends on the history gT -3 up to period T -3 because he competes only with his predecessor who has access to nodes up to n T -3 ) is given by:

-

λ n T -3 i=1 f (g T -3 , i)s i α i + f (g T -3 )α n T -2 . (4.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 this of player T in the example (see Equation 3.1) and we can prove the following result:

Lemma 4.2 Given the tree g T -3 and the action s ∈ ∆(A T -1 ) of player T -1, the set of best response for player T is determined as follow.

either min

i∈At-1 s i f (g T -3 , i) < f (g T -3
) and any mixed action with support in argmin i∈A T -1 s i f (g T -3 , i) is a best response.

or min

i∈A T -1 s i f (g T -3 , i) = f (g T -3
) and any mixed 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 strategy α ∈ ∆(A T -1 ), given the mixed action s ∈ ∆(A T -2 ) of player T -2, and the history of the network up to the end of period T -3, gT -3 , is given by:

-

λ n T -4 i=1 s i α i f (g T -4 , i) + f (g T -4 )α n T -3 + min i=1,•••n T -3 α i f (g T -3 , i) (4.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 the node that player T -2 is less likely to have connected to in order to avoid competition with player T -2 with respect to whom he has a disadvantage (first part of Equation 4.2). On the other hand, he wants to maximize the probability of choosing the same node as player T with whom he competes with the advantage of being the leader (second part of Equation 4.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 playing less frequently on high payoff nodes in order 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 λ 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 4.3 Let λ < 1 /3, and assume that every player plays a one-lag subgame perfect equilibrium. Then, independently of the action s ∈ ∆(A T -2 ) played by player T -2, the best-response of player

T -1, α * ∈ ∆(A T -1
) is to play a probability distribution proportional to the node potential, that is

α * ( g T -3 ) = µ T -1 f (g T -3 ) where µ T -1 f (g T -3 ) := f (g T -3 ) f (g T -3 , 1) , • • • , f (g T -3 ) f (g T -3 , n T -3 ) (4.3)
This characterization of equilibrium actions can be extended by backward induction and we obtain the following result.

Lemma 4.4 Let (φ * ) t be a one-lag subgame perfect equilibrium then assuming that every player l after t + 1 follows φ * l , we have 1. if player t ∈ U T := N * ∩ {T -2k, k ∈ N} faces the predecessor action s at state gnt-3 , then one has (a) either min i∈At-1 s i f (g t-3 , i) < f (g t-3 ) and any mixed action with support in argmin i∈At-

1 s i f (g t-3 , i) is a best response. (b) or min i∈At-1 s i f (g t-3 , i) = f (g t-3
) and any mixed action with support in A t is a best response.

if player

t ∈ V T : N * ∩ {T -(2k + 1), k ∈ N}, then independently of the predecessor action s ∈ ∆(A t-1 ), the best-response is to play µ t f (g T -2 ) ∈ ∆(A t ).
One thus obtains the following characterization of one-lag subgame perfect equilibrium.

Theorem 4.5 If λ < 1 /3, for every g 0 ∈ G 0 the following properties hold in the game Γ(g 0 , T, π f,λ , 1).

1. There exists a one-lag subgame perfect equilibrium strategy profile

(φ * t ) t=2,••• ,T such that for all t ∈ {2, • • • T }, φ * t (g t-2 , µ t-1 f (g t-3 )) = µ t f (g t-2
). Moreover if T is even, it is true also for t = 1. The action profile along the equilibrium path then is (µ

1 f (g -1 ), • • • , µ T f (g T -2 )).
2. For every t ∈ N, every one-lag subgame perfect equilibrium strategy profile (φ # i ) i=1,•••t+1 of the game of length t + 1 is such that for all α t-1 and every realization gt-2 of trees, φ # t (g t-2 , α t-1 ) = µ t f (g t-2 ) ∈ ∆(A t ).

Theorem 4.5 brings two main insights about the emergence of random network in the game Γ(g 0 , T, π f,λ , 1). First, the random network formation process corresponding to µ f , i.e where each node is targeted with a probability inversely proportional to its potential payoff , is an equilibrium of the game. Second, playing according to µ f is the only optimal action for player t in the game of length t + 1. Overall, µ f is an uniform best-response as it induces an equilibrium independently of the length of the game and moreover is the only strategy with this property. Therefore, the corresponding equilibrium can be considered to be the focal equilibrium of the game. Thus our model of sequential competition provides micro-foundations for random network formation process.

Remark 4.6 Notice that the case of the first stage is a little particular. Indeed following our assumption, the first player is only in competition with its successor. If stage 1 is at an odd distance of the last stage, then player 1 is constrained to play 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 proportionnally to f and he is therefore indifferent.

A particularly noteworthy corollary of Theorem 4.5 is when the payoff potential of each node is inversely proportional to its degree, that is for all T ∈ N, for all i ∈ A t , and for all g ∈ H, f (g, i) = 1 /d g i where d g is the degree sequence of the last graph in the history g. Indeed, in this setting, the focal equilibrium strategy, in the sense of Theorem 4.5, is preferential attachment à la [START_REF] Barabási | Emergence of scaling in random networks[END_REF]: players target existing nodes proportionally to their degree. There are two particular noteworthy cases where the payoff function does satisfy this specification:

• In "pure" models of network formation, it is the key property of the co-author model introduced in [START_REF] Jackson | A strategic model of social and economic networks[END_REF].

• In models of strategic influence (see e.g. [START_REF] Jackson | Social and economic networks[END_REF], it is a conventional assumption to consider that the influence exerted by an agent on another is inversely proportional to the actual number of influencers, i.e. to the degree.

In this range of settings in which the payoff function is inversely proportional to the degree, sequential competition provides micro-foundations for the emergence of preferential attachment in the formation of socio-economic networks. From this perspective, preferential attachment appears as the strategic behavior of agents who use mixed strategies in order to benefit from the first-mover advantage in a competition for the benefits of socio-economic links.

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 equilibrium outcome of the game. Conceptually, two conditions are required for 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 mixed strategy can be efficient only if the actual realization of the action is not perfectly observed by the successors. Second, the emergence of mixed 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. Such games can represent a number of strategic economic interactions such as oligopolistic competition in supply networks or diffusion of influence in opinion networks. We show that the focal equilibrium that emerge 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, as in the co-author model of [START_REF] Jackson | A strategic model of social and economic networks[END_REF], equilibrium play induces a preferential attachment process. Hence, our model of sequential competition provides micro-foundations for the emergence of preferential attachment in the formation of socio-economic networks and starts bridging a long lasting gap between game-theoretic models and empirical observations of the dynamics of network formation.

Appendix

Proof of Remark 3.3. We introduce the game Γ , which is decomposed into T periods. The first τ periods are composed of one stage. The periods between τ + 1 and T are composed of two stages whereas the last period T is composed of τ + 1 stages.

• From period 1 to period τ , player t enters and chooses a linkage probability α t in

A t = {1, • • • , n t -2}
and a new node n t = n 0 + t is added to the graph.

• From period τ + 1 to T , player t enters and chooses a linkage probability α

t in A t = {1, • • • , n t -2}
and a new node n t = n 0 + t is added to the graph. Then at the second stage of period t, nature chooses m t-τ ∈ A t-τ following α t-τ and a new link (m t-τ , n t-τ ) is added to the graph. We denote by g t-τ the induced graph on {1, ..., n t-τ }.

• Finally at stage T , player T enters and chooses a linkage probability α m l-τ ∈ A l-τ following α l-τ and a new link (m l-τ , n l-τ ) is added to the graph. We denote by g l-τ the induced graph on {1, ..., n l-τ }.

T in A T = {1, • • • , n T -2} and
The games Γ and Γ have the same set of strategies and the same payoffs functions and therefore are equivalent. Moreover, a profile of strategy is a lagged subgame perfect equilibrium of Γ if and only if it is a subgame perfect equilibrium of Γ .

Proof of Lemma 4.2.

The expected payoff of player T if he uses the strategy α ∈ ∆(A T -1 ) given the action s ∈ ∆(A T -1 ) of player T -1 and the history of the network up to the end of period T -2, gT -2 (in fact the payoff of player T only depends on the history gT -3 up to period T -3 because he only competes with his predecessor ) is given by:

-λ n T -3 i=1 f (g T -3 , i)s i α i + f (g T -3 )α n T -2 . (6.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. We can distinguish two cases depending on where the minimum cost is reached: on link to node before n T -3 or on n T -2.

• if min i∈A T -1 s i f (g T -3 , i) < f (g T -3
), any node, and thus any mixed strategy in

argmin i∈A T -1 s i f (g T -3 , i)
is a best response for player T and his expected payoff is -λ

min i∈A T -1 s i f (g T -3 , i). • If min i∈A T -1 s i f (g T -3 , i) ≥ f (g T -3 ), then one has for all i = 1, • • • , T -3, p i ≥ f (g T -3 ) /f(gt-3,i) and thus, as f (•) is the harmonic mean of the f (•, i), for every i ∈ {1, • • • , T -3}, s i = f (g T -3 ) /f(g T -3 ,i).
Any node, and thus any mixed strategy in A T -1 is then a best response for player T and his expected payoff is -λf

(g T -3 ) = -λ min i∈A T -1 s i f (g T -3 , i).
Proof of Lemma 4.3. Let us consider player T -1. We denote by s the action of its predecessor and by α the action played by player T -1. One consider the auxiliary linear program for k = 1, • • • , n T -3:

P k :=            max -λ n T -4 i=1 f (g T -4 , i)s i α i + f (g T -4 )α n T -3 + α k f (g T -3 , k) s.t n T -3 i=1 α i = 1 ∀i ∈ A T -1 , α i ≥ 0 ∀i ∈ A T -1 , α k f (g T -3 , k) ≤ α i f (g T -3 , i) (6.2)
Letting then on the one hand γ

k := f (g T -3 , k) -λf (g T -4 , k)s k , γ n T -3 := -λf (g T -4 ) and for i = k, n T -3 , γ i := -λf (g T -4 , i)s i and on the other hand φ i = f (g T -3 , i) one has: P k :=            max n T -3 i=1 γ i α i s.t n T -3 i=1 α i = 1 ∀i ∈ N n-2 , α i ≥ 0 ∀i ∈ A T -1 , α k φ k ≤ α i φ i (6.3)
Let us denote I * = argmax i =k γ i and γ I * = max i =k γ i . A solution α of P k must be such that for all 11 Documents de travail du Centre d'Economie de la Sorbonne -2018.35 i ∈ I * , α i = α k φ k/φ i and such that α k is a solution of:

         max 1 - i ∈I * φ(k) φ(i) α k γ I * + i ∈I * γ i φ(k) φ(i) α k s.t 0 ≤ α k ≤ 1 i∈A T -1 φ k φ i
This is a one-dimensional problem. Its solutions must satisfy either

α k = 0 or α k = 1 /( i∈A T -1 φ k/φ i ).
Then, one has:

• If α k = 0, any probability distribution with support in I * is a solution to P k and the value is γ I * := -λ min f (g T -4 ), min i =k f (g T -4 , i)s i .

• If α k > 0, one must have for all i ∈ A T -1 , α i = φ k/φ i , that is to say α i = f (g T -3 ,k) /f(g T -3 ,i)α k .

Thus the solution must be inversely proportional to the f (g T -3 , i). Hence, one has:

α * = µ T -1 f (g -3 ) := f (g T -3 ) f (g T -3 , 1) , • • • , f (g T -3 ) f (g T -3 , n T -3 ) where f (g T -3 ) = 1 i∈At 1 f (g t-2 , i) .
Accordingly, the value in that case is:

i∈A T -1 α * i γ i = f (g T -3 )   1 -λf (g T -4 ) -λ i∈A T -2 f (g T -4 , i) f (g T -3 , i) s i  
Now, the best-response of player T -1 corresponds to the solutions of the problems P k that have the largest value. In this respect, it is clear that under Assumption 4.1, one has f (g T -4 ) ≤ 1 and

i∈A T -2 f (g T -4 , i) f (g T -3 , i) s i ≤ 2 so that f (g T -3 )   1 -λf (g T -4 ) -λ i∈A T -2 f (g T -4 , i) f (g T -3 , i) s i   ≥ f (g T -3
) (1 -3λ) (6.4) Hence for λ < 1 /3, one has for all (p, gT -3 , gT -4 ) ∈ ∆(A T -2 ) × H × H :

f (g T -3 )   1 -λf (g T -4 ) -λ i∈A T -2 f (g T -4 , i) f (g T -3 , i) s i   ≥ f (g T -3 ) (1 -3λ) > 0 ≥ -λ min f (g T -4 ), min i =k f (g T -4 , i)s i . (6.5) Hence, µ T -1 f (g T -3
) is the solution of all the P k and the best-response of player T -1 is to play mixed proportionally to f independently of the action of its predecessor.

Proof of Lemma 4.4.

The property has been proven for player T in Lemma 4.2 and T -1 in Lemma 4.3. Then, an immediate backward induction shows that:

• The expected payoff of a player t ∈ U T := N * ∩ {T -2k, k ∈ N} using a strategy α ∈ ∆(A t ) given the predecessor action s ∈ ∆(A t-1 ) is of the form:

-λ nt-3 i=1 f (g t-3 , i)s i α i + f (g t-3 )α nt-2 + κ t (6.6) where κ t is constant. Indeed, player t + 1 ∈ V T is following a one-lag subgame perfect equilibrium hence plays independently of the action α by induction assumption. The best-reply of player t is then determined similarly to this of player T :

if min i∈At-1 s i f (g t-3 , i) < f (g t-3 ), any node, and thus any mixed strategy in

argmin i∈A T -1 s i f (g t-3 , i)
is a best response for player T and his expected payoff is -λ min i∈A T -1 s i f (g T -3 , i).

-If min i∈A T -1 s i f (g t-3 , i) ≥ f (g t-3 ), one then has for all i = 1, • • • , t-3, s i ≥ f (gt-3) /f(gt-3,i) and thus, as f (•) is the harmonic mean of the f (•, i), for every i ∈ {1, • • • , t-3}, s i = f (gt-3) /f(gt-3,i).

Any node, and thus any mixed strategy in A t is then a best response for player t and his expected payoff is -λf (g t-3 ).

• The expected payoff of a player t ∈ V T := N * ∩ {T -(2k + 1), k ∈ N}, using a strategy α ∈ ∆(A t ) given the predecessor action s ∈ ∆(A t-1 ) is of the form:

-λ[ nt-2 i=1 s i α i f (g 3 , i) + f (g 3 )α nt-2 ] + min i=1,•••nt-2 α i f (g 2 , i) (6.7)
Indeed, player t + 1 ∈ U T is following a one-lag subgame perfect equilibrium hence play independently of the future so as to minimize the payoff of player t. Using Lemma 4.3, it is clear that the best-response of player t is to play mixed proportionally to f independently of the action of its predecessor: hence to play µ t-1 f (g t-2 ).

proof of Theorem 4.5.

The theorem is an immediate consequence of Lemma 4.4. We define the strategy of player t as a function of gt-2 the graph at stage t -2 and s t-1 the action of player t -1. The first one can be computed from g 0 and the sequence of choices of the nature. The second one is directly observed by player t. Then φ * (g t-2 ) = µ T -1 f (g t-2 ), form a one-lag subgame perfect equilibrium. The second statement is a reformulation of the second part of Lemma 4.4.

  2). Hence, independently of the action s ∈ ∆(A T -2 ) of player T -2, player T -1 must play uniformly at random over A T -1 in order to minimize the information player T has about the link he has chosen.• If player T -1 plays uniformly at random 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 play uniformly at random.• More broadly, one can show by induction that along an equilibrium path, players in {2, ..., T } ∩ {T -(2k + 1), k ∈ N} ought to play uniformly at random and players in {2, ..., T } ∩ {T -2k, k ∈ N} are indifferent between all possible actions (in particular they can play uniformly at random).

  a new node n T = n 0 + T is added to the graph. Then, for every T -τ ≤ l ≤ T , nature chooses 10 Documents de travail du Centre d'Economie de la Sorbonne -2018.35

  if min i∈A T -1 s i < 1 /n T -3, any node, and thus any mixed strategy in argmin i∈A T -1 s i is a best response for player T and his expected payoff is -λ min i∈A T -1 s i .

T -1 is less likely to have connected to. It is straightforward to check that: 5 Documents de travail du Centre d'Economie de la Sorbonne -2018.35 -

Documents de travail du Centre d'Economie de laSorbonne -2018.35

The harmonic mean is used to let the (deterministic) cost faced when linking to node nt -1 be commensurate with the expected cost faced when connecting to a player in At.

Venel acknowledges the support of Agence nationale de la recherche via grant CIGNE ANR-15-CE38-0007-01. Mandel acknowledges the support of the ITN program Exside 1 Documents de travail du Centre d'Economie de la Sorbonne -2018.35 Documents de travail du Centre d'Economie de la Sorbonne -2018.35