Chen Avin
email: avin@cse.bgu.ac.il

Avi Cohen
email: avi.cohen@weizmann.ac.il

Pierre Fraigniaud
email: pierre.fraigniaud@irif.fr

Zvi Lotker

David Peleg
email: david.peleg@weizmann.ac.il

Preferential Attachment as a Unique Equilibrium

Keywords: Theory of computation → Social networks, Network formation, preferential attachment, network formation games, social networks, Young's lattice, random walks

This paper demonstrates that the Preferential Attachment rule naturally emerges in the context of evolutionary network formation, as the unique Nash equilibrium of a simple social network game. In this game, each node aims at maximizing its degree in the future, representing its social capital in the "society" formed by the nodes and their connections. This result provides additional formal support to the commonly used Preferential Attachment model, initially designed to capture the "rich get richer" aphorism. In the process of establishing our result, we expose new connections between Preferential Attachment, random walks, and Young's Lattice.

INTRODUCTION

The Preferential Attachment [START_REF] Albert | Statistical mechanics of complex networks[END_REF] model is definitely one of the most commonly used models for real life networks in general, and social networks in particular. The model is based on the Preferential Attachment rule, which dictates that an existing node in the network with degree k will receive a new link with probability k/Z where Z is a normalization constant. This model generates synthetic graphs with characteristics intriguingly similar to those of many existing networks. These characteristics include small diameter [START_REF] Bollobás | The diameter of a scale-free random graph[END_REF], a power-law degree sequence [START_REF] Bollobás | The degree sequence of a scale-free random graph process[END_REF][START_REF] Van | Random graphs and complex networks[END_REF], and correlation between neighbor degrees [START_REF] Paul | Organization of growing random networks[END_REF]. Yet, the reason why Preferential Attachment fits so well with observations is still widely open. Indeed, while

The wealth-based recommendation game. We model the network evolution as a network formation game, called the wealthbased recommendation (wbr) game, in which the goal of each node is to maximize its expected degree. The only choice each node makes occurs when it joins the network: it consists in choosing whom to ask for a recommendation. Specifically, we consider an evolutionary process in which nodes arrive one after the other. Initially, the network consists of a single node v 1 . The node v t , arriving at discrete time t > 1, proposes itself for connection to some existing node chosen at random. The choice is made on the basis of the actual social capital of each node present in the network, modeled as its current degree. That is, node v t chooses an index i ∈ {1, . . . , t -1} according to some probability distribution π t over the current degree sequence D = (d 1 , . . . , d t -1 ), d 1 ≥ d 2 ≥ • • • ≥ d t -1 , corresponding to the nodes of the actual network. Then v t contacts some node u of degree d, and asks for connection to u. The chosen node u, named the host, may either accept the connection, or delegate it to one of its neighbors. The motivation for this feature of the game is that, depending on some form of wealth of the current society formed by the actual network, hosts may be willing or reluctant to accept new connections (i.e., new contracts, new social, emotional or economical dependencies, etc.), since such connections induce risks. The wealth of the society at time t is captured by a parameter α t ∈ [0, 1], where the higher α t , the higher the wealth. The contacted host u accepts the connection proposed by v t with probability α t , or delegates it to one of its neighbors, with probability 1 -α t . This neighbor w is chosen uniformly at random among u's neighbors, and w accepts the connection.

An alternative perspective of this model is the following. Each new node v t meets its host u randomly according to π t when it enters the network. Then it starts to preform a simple random walk [START_REF] Lovász | Random walks on graphs: A survey[END_REF] with stopping probability α t > 0. The new node connects to the node where the walk stops. For the sake of simplifying the presentation, we do not enforce recursion and only consider a onestep recommendation or a one-step random walk.

Note that the network state at time 3 is always a chain of 3 nodes, since node v 2 has only a single strategy and the strategy of v 3 does not change the outcome. Uncertainty only starts at time t ≥ 4. Figures 1 and2 depict the possible scenarios of the network formation after 4 and 5 steps, respectively. Note that, in Figure 2, the two graphs G 11 and G 22 are isomorphic. We have distinguished the two cases on the figure because the two graphs arise from two different histories: in G 11 , the fifth node has connected to a leaf of the graph G 1 depicted in Figure 1, while in G 22 , the fifth node has connected to a leaf of the graph G 2 . Note that the connection of each node may be a direct connection to the contacted node (i.e., the host), or a delegated connection to a neighbor of the contacted nodes. The utility of a node is defined as its expected degree, measuring its social capital. Note that the choice to whom to propose connection when a node v t joins has no impact on the social capital of v t in the short term, because every new node has degree 1 regardless of the chosen node with whom the connection is established. The main consideration of players is the long term affect of their choice, in light of the current state of the network (captured by its degree sequence), and future players' strategies. Thus, the game captures some important psychological features of decision-making, where individuals must balance between the past, present, and future, and where the short and long term implications of a decision must be weighed. In particular, it is not known when the game will end, and nodes should plan their strategies to fit with long term scenarios. This is consistent with concepts like "best friends forever" (BFF) in social networks, and the terminology used in traditional wedding ceremonies: one does not know when the game will end, but one plans for the long term. In other words, unknown stoping time is the natural assumption, which is consistent with the fact that, sadly or luckily, one does not know when our life will end.

To sum up, our network formation game is characterized by the sequence ᾱ = (α t ) t ≥1 measuring the evolution of the wealth of the society along with time, and the ending time τ where the utilities are measured. Both ᾱ and τ are unknown to the players. They represent the natural uncertainty about the future, that decision making mechanisms have to cope with. The probability distribution π t over the degree sequences (d 1 , . . . , d t -1 ),

d 1 ≥ d 2 ≥ • • • ≥ d t -1 ,
defines the strategy of the t-th node joining the network. A strategy profile Π is defined as the collection of all strategies of the players, i.e., Π = (π t ) t ≥1 .

Our Results. We show that the Preferential Attachment strategy profile (defined formally later) is the unique Nash equilibrium of the game that is universal, i.e., it holds for all sequences ᾱ = (α t ) t ≥1 and all stoping times τ . The uniqueness property is the striking point: the uncertainty about the future behaviors of the players makes Preferential Attachment the only viable choice for establishing connections when joining the network. Any other strategy profile Π might be a Nash equilibrium for some pairs ( ᾱ, τ ), but there must exist some pair ( ᾱ ′ , τ ′ ) for which Π is not a Nash equilibrium. That is, in the game defined by the pair ( ᾱ ′ , τ ′ ), if there exists some player v t at time t, 4 < t ≤ τ , that decides to deviate from the Preferential Attachment strategy, then there exists at least one player v t ′ at time t ′ < t that gains (in expected degree) at time τ by deviating from the Preferential Attachment strategy.

It is worth discussing the impact of the amount of uncertainty about the future on the uniqueness of the Nash equilibrium. First, the unnatural assumption of a finite game, i.e., with ending time τ fixed a priori, and known to the players, would obviously result in many Nash equilibria, distinct from Preferential Attachment. In particular, the last player, v τ , could use any strategy, as this would have no impact on its utility, necessarily equal to 1 at the end of the game. On the other hand, the assumption that the wealth varies with time is not crucial to the existence of a unique universal Nash equilibrium. Indeed, even if the wealth of the society is constant over time, i.e., α t = α t ′ for all t, t ′ ≥ 1, Preferential Attachment would still be essentially the unique universal Nash equilibrium. More precisely, any universal Nash equilibrium under this assumption must satisfy that every player plays Preferential Attachment on all networks that are different from a star (i.e., an n-node tree with n -1 leaves). Hence, assuming α varies over time is not central for demonstrating the relevance of Preferential Attachment. What is crucial is that the players do not know the value of α (even if it is fixed over time). Nevertheless, our proofs do not require using the whole range [0, 1] of values for α, and having α taken from a finite set of at least two distinct values is sufficient for establishing Preferential Attachment as the unique universal Nash equilibrium. Assuming at least two values for α seems, however, necessary. Indeed, we show that if α is fixed a priori, say α = 1, and is known to the players, then there are many universal Nash equilibria. In fact, we characterize a sub-class of such universal Nash equilibria for α = 1, as an intermediate result toward demonstrating our main result.

Related Work. The Preferential Attachment (PA) model is a stochastic process used to randomly generate power-law degree distribution (a.k.a., scale-free) networks. It was originally proposed by Price [START_REF] De | A general theory of bibliometric and other cumulative advantage processes[END_REF] to study citation networks, and was popularized in Barabasi and Albert [START_REF] Albert | Statistical mechanics of complex networks[END_REF], who explained the structure of the World Wide Web using the PA rule. A few other examples of networks well captured by the PA rule include collaboration networks, the internet, interbank payment networks, airline networks, and protein-protein interaction networks [START_REF] Newman | Networks: an introduction[END_REF], among others. Hence, the PA model is a powerful tool for studying real-world networks in general, and social networks in particular, but it does not help fully explain the existence of the very property it aims at simulating, that is, the prevalence of social networks with a power law degree distribution. Some authors approach the problem of formally justifying PA. In particular, D'souza et al. [START_REF] Raissa | Emergence of tempered preferential attachment from optimization[END_REF] showed the emergence of preferential attachment from underlying optimization mechanisms. Our objective is to approach the problem from a simpler, and perhaps more natural game theoretical perspective. The same approach was suggested for future research by Jackson [START_REF] Matthew | The economics of social networks[END_REF]. Several network formation games have been defined. The one introduced by Fabrikant et al. [START_REF] Fabrikant | On a network creation game[END_REF] (see also [START_REF] Meirom | Network formation games with heterogeneous players and the internet structure[END_REF]) reaches an equilibrium on either the clique or the star graph, both of which rarely occur in large social networks. The PageRank game (see [START_REF] Avis | Verifying nash equilibria in pagerank games on undirected web graphs[END_REF][START_REF] Chen | On the alphasensitivity of nash equilibria in pagerank-based network reputation games[END_REF][START_REF] Hopcroft | Network reputation games[END_REF][START_REF] Kouroupas | The web graph as an equilibrium[END_REF]) better fits the social network setting. In this game, the players represent web pages, and each player forms directed links to other players, with the goal of maximizing his PageRank. In particular, equilibria of the PageRank game that are insensitive to the "jumping probability" of PageRank, and therefore are universal (in a similar sense to that defined in the current paper) were presented in [START_REF] Hopcroft | Network reputation games[END_REF]. Nevertheless, the PageRank game assumes that the number of players is fixed, and connections between individuals may evolve with time. Instead, we consider the formation of a possibly infinitely growing society, in which connections between individuals involve a permanent commitment.

We complete this section by noticing that another family of random models that generates scale scale-free networks is based on the copying mechanism [START_REF] Matthew | Meeting strangers and friends of friends: How random are social networks?[END_REF][START_REF] Kleinberg | The web as a graph: measurements, models, and methods[END_REF][START_REF] Pavel | Network growth by copying[END_REF][START_REF] Kumar | Stochastic models for the web graph[END_REF][START_REF] Vázquez | Growing network with local rules: Preferential attachment, clustering hierarchy, and degree correlations[END_REF]. In these models the process by which a new node selects its connections is similar to ours, but these models (as well as the original PA) are not gamebased.

FORMAL STATEMENT OF THE RESULTS

In this section we fully specify of the game presented in the introduction, and then formally state our main results.

The games wbr(ᾱ, τ )

To formalize our game, we define the network evolution as a network formation game called the wealth-based recommendation (wbr) game. The evolution of the network occurs at discrete times, with one event occurring at each time step. We start at time 1 with a single node denoted v 1 , and no edges. This graph is denoted by T (1) . At each time step t > 1, a new player v t arrives and adds a single edge from itself to an existing node v j in T (t -1) , and thus creates the graph T (t ) . Hence, at time t, the network T (t ) consists of a tree with t nodes (and t -1 edges). When the player v t arrives, it contacts an existing player v i and requests a host. When a host v i is contacted, it must recommend a neighbor for v t , which is determined as follows: with probability α t , the host recommends itself, and, with probability 1 -α t , it recommends one of its own neighbors uniformly at random. Subsequently, v t connects to the recommended node.

We now clarify the process for choosing the host. Let π t denote the strategy of v t , which dictates the distribution by which v t chooses its host, for every instance of the graph T (t -1) . For a node v i in a graph G, we denote by deg G (v i ) its degree (i.e., number of neighbors). The degree sequence DS(G) of an n-node graph G is the non-increasing sequence (d 1 , d 2 , . . . , d n ) of its node degrees. Let D (t ) be the set of all degree sequences of trees with t nodes. For every t ≥ 1, the strategy π t is a function

π t : N × D (t -1) → R.
That is, for every degree sequence D ∈ D (t -1) , and for every node v i of degree k in a tree T (t -1) with degree sequence D, the probability that v i is contacted at time t is π t (k, D). Note that, while the probability that a node is selected as a host at time t depends on the strategy π t , the probability that a node is recommended at time t (i.e., adopts a new neighbor), depends additionally on the edge set of the tree T (t -1) , and on the parameter α t . A strategy profile Π is the set of strategies for all players, Π = (π t ) t ≥1 . Definition 2.1. For a sequence ᾱ = (α t ) t ≥1 with α t ∈ [0, 1] for every t ≥ 1, and and a time τ > 1, let wbr( ᾱ, τ ) denote the wealthbased recommendation (wbr) game that is played with α t at round t = 1, . . . , τ , and which stops right after time τ .

For a given game wbr( ᾱ, τ ), let T (t ) (Π) be the random tree obtained at time t when strategy profile Π is used. Note that T (t ) (Π) is actually a node-labeled tree, where each node is labeled by its arrival time in the network. In the following, an n-node labeled tree is a tree with its node labeled by distinct integers in {1, . . . , n}. For every t-node labeled tree T , let

φ(T ) = Pr[T (t ) (Π) = T ] .
Definition 2.2. In the wbr game, the utility of v i at time t is defined as u

(t ) i (Π) = E[deg T (t ) (Π) (v i )] = T ∈T (t ) deg T (v i ) • φ(T ) ,
where T (t ) is the set of all t-node labeled trees.

A strategy profile Π is a Nash equilibrium for a game wbr( ᾱ, τ ) if no player v t can increase its utility by unilaterally changing its own strategy π t , and a strategy profile Π is a universal Nash equilibrium if it is a Nash equilibrium for wbr( ᾱ, t) for every finite time τ and every sequence ᾱ . More formally, for a game wbr( ᾱ, τ ), and t ∈ {1, . . . , τ }, let Π -t be the (τ -1)-dimensional vector of strategies played by all players different from t, and let (π ′ t , Π -t ) denote the strategy profile in which v t plays the strategy π t and all other players play according to the vector Π -t . Definition 2.3. A strategy profile Π = (π t ) t ≥1 is a universal Nash equilibrium for the wbr game if, for every game wbr( ᾱ, τ ), and every strategy profile

Π ′ = (π ′ t ) t ≥1 , we have u (τ ) t (π t , Π -t ) ≥ u (τ ) t (π ′ t , Π -t )
for every player t = 1, . . . , τ .

Formal statements

Let us denote by pa the preferential attachment strategy, that is, pa is the individual node strategy by which, given a degree sequence

D = (d 1 , . . . , d n ), a node of degree k ∈ D is contacted with probability pa(k, D) = k n j=1 d j .
Note that, in the wbr game, the graph at time t after the insertion of the t-th node is a tree T (t ) with t nodes. So, regardless of the history of the game, for any t > 1,

pa(k, D) = pa(k) = k 2(t -1)
.

Definition 2.4. The preferential attachment profile, denoted Π pa , is the strategy profile where players v t play arbitrarily for t ≤ 4, and players v t play according to pa for t ≥ 5.

Note that, for every strategy profile, the second player has no choice, and the choice of the third player is irrelevant (as any choice yields the same network). The assumption that the fourth player plays arbitrarily in Π pa is a minor artifact due to technical reasons which are popping up in the proofs. The following result shows that pa is a natural strategy to play.

Theorem 2.5. The preferential attachment profile Π pa is a universal Nash equilibrium for the wbr Game.

The following theorem is the main result in this paper. It shows that, in fact, for rational players, there is no alternative to play pa. Theorem 2.6. For any strategy profile Π Π pa , Π is not a universal Nash equilibrium for the wbr Game.

The time-invariant wbr game is the variant of the wbr game where the wealth parameter α does not evolve with time. The following result shows that, apart from pathological scenarios, Preferential Attachment remains essentially the only strategy to be played by rational players. Theorem 2.7. If a strategy profile Π is a universal Nash equilibrium for the time-invariant wbr game, then each player plays pa on every graph that is not a star, and if player t plays pa on the star S t -1 then all subsequent players t ′ > t play pa on all graphs. Moreover,

• if π t (t -2, DS(S t -1 )) > 1 2 then, with probability 1, the players take alternate choices: player t -1 chooses a leaf in the star, player t -2 chooses the center, player t -3 chooses a leaf, etc.;

• if π t (t -2, DS(S t -1 )) < 1
2 then, with probability 1, the players take alternate choices, where player t -1 starts with choosing the star center.

The static wbr game is the variant of the time-invariant wbr game where the wealth parameter equals 1. To characterize universal Nash equilibria for the static wbr game, we define the following concept. A strategy π t is degree-k consistent if, for every degree-k node, the probability of selecting that node is independent of the degree sequence. A strategy π t is degree consistent if it is degree-k consistent for every k ∈ N. Note that pa is a degree consistent strategy. A strategy profile Π = (π t ) t ≥1 is degree consistent if π t is degree consistent for every t ≥ 1. The following result shows that the universal Nash equilibria for the static wbr game are essentially degree consistent. Theorem 2.8. Let Π be a universal Nash equilibrium for the static wbr game. If the strategy π t ′ is degree consistent for every t ′ ∈ {1, 2, ..., t -1}, and π t ′ (k) > 0 for every k ∈ {1, . . . , t -1}, then π t is a degree consistent strategy. In particular, if every player t ′ ∈ {1, 2, ..., t -1} played pa, then π t is a degree consistent strategy.

It is important to note that pa is not the only degree consistent strategy. Actually, Lemma 4.15 describes an interesting family of degree consistent strategies, which consists of pa as well as the uniform distribution (i.e., connecting each host with probability 1/(t -1)), among other distributions.

The rest of the paper is dedicated to proving these theorems. Due to lack of space, some proofs are deferred to the full version.

PREFERENTIAL ATTACHMENT IS A UNIVERSAL NASH EQUILIBRIUM

We now show that the preferential attachment (PA) profile is universal. We do this by showing an intimate connection between the wbr( ᾱ, τ ) game and the simple random walk on a graphs. First recall a well known result about the stationary distribution of the simple random walk with self-loops (e.g., see Levin et al. [START_REF] Asher | Markov chains and mixing times[END_REF] §1.5).

For any undirected graph G = (V , E) with n nodes and m edges the stationary distribution of the simple random walk with self-loop probability α, for any 0

< α < 1, is π (v) = deg G (v)
2m . The interesting observation here is that the stationary distribution for the actual tree T at time t is the same as the pa strategy for T , namely, for every node v ∈ T , π (v) = pa(deg T (v), DS(T )). We can now use this observation to show that for any wealth, the probability that a new arriving node connects to any given existing node is equal to the probability of choosing that node as a host if the node plays according to pa. Lemma 3.1. Suppose that the preferential attachment profile is being used in wbr( ᾱ, τ ), and let us consider a node u joining the network T at time t ≥ 4. For every sequence ᾱ = (α t ) t ≥1 , we have

Pr[u connects to v | T ] = pa(deg T (v), DS(T )) = deg T (v) 2(t -2) .
Proof. The proof follows from the fact that the process by which u decides to which node it connects in our wbr( ᾱ, τ ) game, is identical to a one step simple random walk with self-loop probability α t and starting the walk from the distribution π t . By definition, if π t is the stationary distribution of T then the probability to choose v as a host is equal to the probability to connect to v (after one step of the random walk). The proof concludes by recalling that pa is the stationary distribution for T .

We can now prove Theorem 2.5.

Proof of Theorem 2.5. Suppose that the preferential attachment profile Π pa is being used, and assume towards contradiction that there exists a sequence ᾱ and some player v t for t ≥ 4 who could increase his utility by deviating from the strategy pa to a strategy π ′ t pa. Let d (s) t denote the random variable indicating the degree of player v t at time s. Then d (t ) t = 1 and, by Lemma 3.1, for every s > t the following recurrence holds:

d (s) t =        d (s-1) t + 1 with probability d (s -1) t 2(s-2) ; d (s-1) t otherwise.
This recurrence is independent of the strategy π ′ t of player v t and of the sequence ᾱ , in contradiction to the assumption. It follows that Π pa is a universal Nash equilibrium.

We now turn to prove the main technical result of the paper, namely, that Preferential Attachment is the unique Nash Equilibrium. We first explain and prove the case of five players, and then extend the result to the general case using what we call game event operators and relying on an interesting connection to Young's Lattice [START_REF] Sagan | The symmetric group: representations, combinatorial algorithms, and symmetric functions[END_REF].

Preliminaries

We make use of the following three simple lemmas. Lemma 4.3. Let T be a tree with the degree sequence (d 1 , ..., d n ), and let v i be a node in T such that d i > 1. Then a tree T ′ may be constructed with the same degree sequence as T where v i has a neighbor of degree 1.

The First Six Steps

Let Π = (π i ) i ≥1 be a strategy profile, where π i is the individual strategy of the i th player, denoted by v i . The strategies π 1 , π 2 , and π 3 are trivial since π 1 consists, by definition, in creating one node, while the second and third players invariably face degree distributions (0) and (1, 1), respectively. That is, π 2 is the unique strategy of contacting the unique degree-0 node, and π 3 is the strategy of contacting a degree-1 node (both with probability 1). After the third player has played, the graph consists of the 3-node path P 3 , so player v 4 can be facing only one kind of degree sequence, namely 211 (we omit parenthesis and commas for clarity). Still, player v 4 has infinitely many strategies. More specifically, the strategy of v 4 can be described by just one parameter p ∈ [0, 1], namely, the probability with which it contacts a degree-1 node. After player v 4 has played, the resulting tree can be of two forms only, denoted hereafter by G 1 and G 2 , where G 1 is the 4-node star S 4 and G 2 is the 4-node path P 4 , with respective degree sequences DS(G 1 ) = 3111 and DS(G 2 ) = 2211. These graphs are depicted in Figure 1.

It follows that the strategy π 5 may be described by just two parameters: the probabilities of connecting to a leaf in S 4 and in P 4 . After player 5 has played, the resulting tree can be of three forms only, the 5-node star S 5 , the 5-node path P 5 , and the unique tree T 5 with degree sequence 32111 (see Figure 2). For the sake of the analysis, we distinguish two different states corresponding to T 5 , depicted as G 11 and G 22 in Figure 2. Indeed, G 11 and G 12 in Figure 2 result from v 5 playing on G 1 in Figure 1, while G 21 and G 22 result from player v 5 playing on G 2 .

The strategy π 6 is played on one of three graphs: S 5 (= G 12 ), P 5 (= G 21 ) and T 5 (= G 11 = G 22 ), and may thus be described by four parameters: one parameter for each of the graphs S 5 and P 5 , and two parameters for the tree T 5 (since it contains three distinct degrees). After player v 6 has played, the resulting tree can take several forms, which we consider in the full version of the paper.

In Section 4.5 we collapse the evolution of the game further to consider only degree distributions. This new structure discards knowledge of the topology of the graph, and the history of the game, but is easier to generalize and has several advantages, to be discussed later.

Proof of Theorem 2.6 for Five Players

The strategies π 1 , π 2 , and π 3 are unique, as discussed earlier. The strategy of v 4 can be described by just one parameter p ∈ [0, 1], where π 4 (1) = p and π 4 (2) = 1 -2p (note that pa corresponds to p = 1 4 ). According to our definition of the preferential attachment profile, player v 4 is free to use any of the strategies available to it. Theorem 2.6 claims that, in particular, v 5 , must play the pa strategy in order to ensure a universal Nash equilibrium. This is shown by the next lemma. Lemma 4.4. Let Π = (π i ) i ≥1 be a strategy profile. If π 5 pa, then Π is not a universal Nash equilibrium. Moreover, if π 5 pa, then Π is not even a Nash equilibrium for all wbr( ᾱ, 5) game (i.e., even if the games stop after time 5).

Proof. To prove the lemma we show that if π 5 pa, then for every π 4 , there exists a wealth parameter α 5 such that π 4 is not the optimal strategy for v 4 . After v 4 has played, the resulting tree can be of two forms only, denoted earlier by G 1 and G 2 , corresponding to the 4-node star S 4 and the 4-node path P 4 (depicted in Fig. 1), with respective degree sequences DS(G 1 ) = 3111 and DS(G 2 ) = 2211. By the way S 4 and P 4 emerge from S 3 we have

φ(S 4 ) = 2p(1 -α 4 ) + (1 -2p)α 4 ; φ(P 4 ) = 2pα 4 + (1 -2p)(1 -α 4 ) .
The strategy of v 5 can be described by just two parameters r, s ∈ [0, 1], where π 5 (1, S 4 ) = r and π 5 (1, P 4 ) = s. Note that pa corresponds to r = 1 6 and s = 1 6 . After v 5 has played, the resulting tree can be of three forms only, the 5-node star S 5 , the 5-node path P 5 , and the unique tree T 5 with degree sequence DS(T 5 ) = 32111 (see Figure 2). Note that in accordance with our general notation, and for the sake of the analysis, we distinguish two different states corresponding to T 5 , depicted as G 11 and G 22 in Figure 2. We have

           φ(G 11 ) = φ(S 4 ) • [3rα 5 + (1 -3r )(1 -α 5 )] ; φ(G 12 ) = φ(S 4 ) • [3r (1 -α 5 ) + (1 -3r )α 5 ] ; φ(G 21 ) = φ(P 4 ) • [2sα 5 + 1 2 (1 -2s)(1 -α 5 )] ; φ(G 22 ) = φ(P 4 ) • [2s(1 -α 5 ) + 1 2 (1 -2s)(1 + α 5 )] .
By Definition 2.2, the utility u

(5)
4 (Π) of player v 4 at time 5 in strategy Π satisfies:

u (5) 4 (Π) = i, j ∈ {1,2} φ(G i j ) E[deg G i j (v 4 )] = 4 3 φ(G 11 ) + φ(G 12 ) + 3 2 φ(G 21 ) + φ(G 22 ) = 1 + 1 3 φ(G 11 ) + 1 2 φ(G 21 ).
This utility is a linear function of p, that we write as u

(5)

4 (Π) = A+Bp, where A = 1+ 1 3 α 4 3rα 5 +(1-3r )(1-α 5 ) + 1 2 (1-α 4 ) 2sα 5 + 1 2 (1-2s)(1-α 5 )
and Assume that s 1 6 , and write s = 1 6 + δ with δ ∈ [-1 6 , 5 6 ]. Let α = α 4 = α 5 = 1 2 + ϵ where |ϵ | > 0 is arbitrarily small. Then we have B = δϵ + O(ϵ 2 ). Therefore, if δ 0, choosing α > 1 2 or α < 1 2 yields the best response of player v 4 to be p = 0 or p = 1 2 depending on the sign of B, which is essentially governed by the sign of δϵ. Therefore, to be a universal Nash equilibrium, the strategy profile Π must be such that s = 1 6 . Hence, we now assume that s = 1 6 . Under the assumption that s = 1 6 , writing r = 1 6 + δ with δ ∈ [-1 6 , 5 6 ] yields B = -2δ (1-2α 4 )(1-2α 5 ). Therefore, if δ 0, by choosing α 4 and α 5 both larger than 1 2 , or one larger than 1 2 and the other small than 1 2 , one can change the sign of B, yielding the best response of player v 4 to be p = 0 or p = 1 2 depending on whether B < 0 or B > 0, respectively. Therefore, to be a universal Nash equilibrium, the strategy Π must be such that s = 1 6 and r = 1 6 . That is, player v 5 must play pa.

B = 2 3 (1-2α 4 ) 3rα 5 +(1-3r )(1-α 5 ) +(2α 4 -1) 2sα 5 + 1 2 (1-2s)(1-α 5 ) .
Remark. It would be tempting to use Lemma 4.4 as the basis for an induction on the arrival time t in order to establish Theorem 2.6. However, this is not as simple as it may seem at a first glance. Indeed, it turns out that the fact that player v t does not play pa may benefit not to player v t -1 but to some other earlier player v t ′ for t ′ < t -1. In particular, there is an example in which the fact that v 6 does not play pa benefits to v 4 but not to v 5 . Establishing Theorem 2.6 requires more sophisticated tools, which are presented in the next two sub-sections.

Game Event Operators

The aim of this section and the next one is to concisely represent a full sequence of the game. Each player has a single turn in which it takes a simple action: choosing the degree of its host in the current graph. For any tree T of size n, let T ⊕k be a random tree of size n +1 uniformly distributed over all trees obtained from T by adding a leaf to some node of degree k in T . Let D = (d 1 , d 2 , . . . , d n ) be a degree sequence of size n. Let k be a degree in D, and let i be the minimal index such that d i = k. We denote by D ⊕ k the degree sequence of size n + 1 obtained by increasing d i to d i + 1, and adding 1 at the end of the sequence D. That is,

D ⊕ k = (d 1 , d 2 , . . . , d i-1 , k + 1, d i+1 , . . . , d n , 1). ∅ 1 Figure 4: Young's Lattice.
We have DS(T ⊕ k) = DS(T ) ⊕ k. Additionally, by Lemma 4.2, if D is a degree sequence of a tree then D ⊕ k is a degree sequence of a tree, for every k ocurring in D. Similarly, T ⊖ k is a random tree of size n -1 obtained by selecting a random node u of degree k, selecting a random neighbor v of u. Then delete the edge (u, v), select a random leaf w from the tree of u, delete it and connect v to the parent of w. Let D = (d 1 , d 2 , . . . , d n ) be a degree sequence of size n, let k > 1 be a value occurring in D, and let i be the maximal index such that d i = k. D ⊖ k denotes the degree sequence of size n -1 obtained by decreasing d i to d i -1, and by removing

d n = 1 from D. That is, D ⊖ k = (d 1 , d 2 , . . . , d i-1 , k -1, d i+1 , . . . , d n-1 ).
By Lemma 4.3, if D is a degree sequence of a tree then D ⊖ k is well defined for every degree k in D.

Lemma 4.5. The operations ⊕k and ⊖(k +1) are inverse operations on degree sequences. Namely, let D and D ′ be degree sequences of size n and n + 1, respectively. n) be degree sequences of the same size, and let and, for every D ′ D in S ′ it holds that D ′ > D. Two degree sequences D 1 D 2 of size n are called a covering pair if there exists a degree sequence that is covered by both. Similarly, D 1 and D 2 are called a covered pair if there exists a degree sequence that covers both.

D ′ = D ⊕ k ⇐⇒ D = D ′ ⊖ (k + 1). We say that D ∈ D (n+1) covers D ′ ∈ D (n) , denoted by D ≻ D ′ , if D = D ′ ⊕ k for some degree k in D ′ . We say D ∈ D (n) dominates D ′ ∈ D (k) , denoted by D > D ′ , if n > k and for every 1 ≤ i ≤ k, d i ≥ d ′ i . Let D 1 , D 2 ∈ D (
S = {D ′ | D ′ < D 1 , D 2 }. We say D is the meet of D 1 and D 2 , denoted by D = D 1 ∧ D 2 , if D ∈ S, and, for every D ′ D in S, it holds that D ′ < D. Similarly, let S ′ = {D ′ | D ′ > D 1 , D 2 }. We say D is the join of D 1 and D 2 , denoted by D = D 1 ∨ D 2 , if D ∈ S,

The Degree Sequence Lattice

The game events defined in Section 4.4 describe a lattice structure of degree sequences as in Figure 3. Note that this lattice is a less detailed version of the evolution described in Section 4.2, disregarding the topology of the graph, as well as the history of the game. This collapsed version allows us to visualize the game evolution in terms of the operators ⊖ and ⊕. Moreover, if α i = 1 for all i > 0, then a path in the degree sequence lattice uniquely defines the evolution of the game, including the chosen hosts.

The lattice of degree sequences is equivalent to a poset called Young's lattice (see Figure 4). We will start with a few definitions (taken from Sagan [START_REF] Sagan | The symmetric group: representations, combinatorial algorithms, and symmetric functions[END_REF]) necessary to explain this equivalence.

A partition of n, denoted λ ⊢ n, is a non-increasing sequence of non-negative integers λ = (λ 1 , λ 2 , . . . , λ ℓ ) where ℓ i=1 λ i = n.

c ∈ A such that c ≤ a, c ≤ b and if d ≤ a, d ≤ b, then d ≤ c. (1)
The meet of a and b, if it exists, is denoted by a ∧ b. The least upper bound, or join, of a and b is defined by reversing all the inequalities in Eq. ( 1) and is written a ∨ b. A poset where every pair of elements has a meet and a join is called a lattice.

(2, 2, 1, 1) -→ (3, 1, 1, 1) -→ (4, 3, 2, 1, 1, 1, 1, 1) -→
By Lemma 4.2, D is a partition of 2n -2, and thus the sequence

d 1 -1, d 2 -1, . . . , d n -1 sums up to n -2.
Moreover, by the same lemma, every possible partition of n -2 can be similarly mapped to a degree sequence of a tree of size n. Now let D ′ be a degree sequence of size n + 1 such that D ′ ≻ D. The Young diagram that matches D ′ covers the Young diagram that matches D. Therefore, the lattice of degree sequences illustrated in Figure 3 is equivalent to Young's lattice.

The equivalence between the two lattices implies the following lemma, since a corresponding lemma holds for Young's lattice (see Prop. 5.1.3 in [START_REF] Sagan | The symmetric group: representations, combinatorial algorithms, and symmetric functions[END_REF]). Moreover, the following subsection was mostly inspired by analogous results on Young's lattice. Lemma 4.9. Let D 1 D 2 be degree sequences of size n. Then D 1 and D 2 are a covering pair if and only if they are a covered pair. Explicitly, there exists a degree sequence that is covered by both D 1 and D 2 if and only if there exists a degree sequence that covers both D 1 and D 2 .

Nash Equilibria of the Static wbr game

In this section, we assume that the wealth α t is 1 at all steps of the game (i.e., the game is static: each node connects to the host it contacts). The result obtained in this section will provide us with the tools we need for the proof of Theorem 2.6. Moreover, characterizing the Nash equilibria of this simpler variant of the game is interesting in itself, and establish Theorem 2.8.

For a given strategy profile Π, a degree sequence D is called reachable if there exists a sequence of player actions with nonzero probability of occurring such that

D = D (1) ⊕ k 1 ⊕ k 2 ⊕ . . . ⊕ k n
where D (1) = (0) is the degree sequence of the initial graph T (1) , containing one isolated node. (Recall that Lemma 4.1 states that every tree is reachable when the pa strategy profile is used).

There may be Nash equilibrium for the static wbr game that are not degree consistent. For example, consider a strategy profile Π such that π i (1, D) = 0 for every degree sequence D and every i ≥ 4. Namely, the players never choose to connect to a leaf. Then Π is not degree consistent, yet it is a Nash equilibrium for the static wbr game. As another example, let P n denote the path of length n. The path P n is the only graph with the degree sequence (2, 2, . . . , 2, 1, 1), so with a slight abuse of notation, we denote the degree sequence of P n as P n as well. If π i (1, P i-1 ) = 1/2 and π i (1, D) = 0 for all D P i-1 then Π is a Nash equilibrium for the static wbr game.

Our next goal is to establish a sufficient condition for a strategy profile that is a Nash equilibrium for the static wbr game to be degree consistent. The following lemma will be used later, and contributes to establish part of the statement on Theorem 2.8. Lemma 4.10. Let Π be a Nash equilibrium for the static wbr game, where π i = pa for all i ∈ {1, . . . , t -1}. Then the strategy π t is degree consistent.

In order to prove Lemma 4.10 we will need several helping lemmas. Let Γ n be a graph with the set of vertices V (Γ n ) = D (n) , the set of degree sequences of size n trees, and the set of edges Proof. By induction on n. For n = 4, V (Γ 4 ) = {(2211), (3111)}, and both degree sequences cover (211), so there is an edge between them. Suppose the statement holds for n = k, and consider n = k +1.

E(Γ n ) = {(D 1 , D 2 ) | D
Let λ, µ ∈ D (k +1) . Let λ ′ ∈ D (k) be a degree sequence such that λ ′ ≺ λ, and let µ ′ ∈ D (k) be a degree sequence such that µ ′ ≺ µ. By the induction hypothesis there exists a path between λ ′ and µ ′ in Γ k . Let that path be λ ′ = λ ′ 0 , λ ′ 1 , . . . , λ ′ ℓ = µ ′ . For every i = 0, . . . , ℓ -1, the degree sequences λ ′ i and λ ′ i+1 have an edge between them in Γ k , hence they are a covering pair. Therefore, by Lemma 4.9 they are also a covered pair, so they are covered by a degree sequence in D (k +1) , which we call λ i , for i = 0, . . . , ℓ -1. Now for every i = 0, . . . , ℓ -1, the elements λ i and λ i+1 both cover the element λ ′ i+1 , hence they are a covering pair, and thus have an edge between them. Moreover, λ and λ 0 both cover λ ′ (and possibly λ = λ 0 ), and λ l -1 and µ both cover µ ′ . Therefore there exists a path between λ and µ in Γ n . Lemma 4.12. Let Π be a Nash equilibrium for the static wbr game where π i = pa for all i ∈ {1, . . . , t -1}. Then the strategy π t is a degree-1 consistent strategy.

Proof. Consider a covering pair D 1 , D 2 ∈ D (t -1) . They both cover some degree sequence D ′ ∈ D (t -2) . By definition, there exist some

k 1 ∈ D 1 and k 2 ∈ D 2 such that D 1 ⊖ k 1 = D 2 ⊖ k 2 = D ′ .
The player v t -1 may deterministically choose between creating D 1 and D 2 when it sees the degree sequence D ′ . Hence, if π t (1, D 1 ) > π t (1, D 2 ) then the player v t -1 would gain by deviating from pa to take the action D ′ ⊕ (k 1 -1) with probability one, contradicting the assumption that Π is a Nash equilibrium for the static wbr game. Moreover, because the players v 1 , . . . , v t -2 all play pa, by Lemma 4.1, every D ′ ∈ D (t -2) is reachable at time t -2. So it must hold that for every D 1 , D 2 ∈ E(Γ t -1 ),

π t (1, D 1 ) = π t (1, D 2 ). (2)
Now let us consider any two degree sequences λ, µ ∈ D (t -1) , which are not necessarily neighbors in Γ t -1 . The graph Γ t -1 is connected by Lemma 4.11, so there exists a path in Γ t -1 from λ to µ. Let the path be λ = λ 0 , λ 1 , . . . , λ ℓ = µ. By Equation ( 2), π t (1, λ i ) = π t (1, λ i+1 ) for every i = 0, . . . , ℓ -1. Therefore, π t (1, λ) = π t (1, µ) for every two degree sequences λ and µ in D (t -1) . In other words, π t is a degree-1 consistent strategy. Lemma 4.13. Let Π be a strategy profile in which π i = pa for all i ∈ {1, . . . , t -1} and π t is a degree-d consistent strategy, for d = 1, . . . , k. Then none of the players v t -1 , v t -2 , . . . , v t -k can change their utility by unilaterally deviating from Π.

Remark. Conversely, provided the assumptions of the lemma above hold, and provided that π t is not degree-(k + 1) consistent, then the player v t -k-1 can profit by deviating from the pa strategy as we show in the next lemma. Lemma 4.14. Let Π be a Nash equilibrium for the static wbr game where π i = pa for all i ∈ {1, . . . , t -1}. Then the strategy π t is a degree-k consistent strategy, for every k ∈ {1, 2, . . . , t -4}.

Proof. We the lemma by induction on k. The statement is true for k = 1 by Lemma 4.12, so assume it holds for k ≤ ℓ, and consider k = ℓ + 1. By the induction hypothesis, the strategy π t is degree 1, . . . , ℓ consistent. Thus, by Lemma 4.13, the players v t -1 , v t -2 , . . . , v t -ℓ have no reason to deviate from pa. Let I = tℓ -1, and define the event

E = {players v t -1 , v t -2 , . . . , v t -ℓ all connected to the node v I } .
If E does not occur, then player v I has degree at most ℓ in T (t -1) and thus v I cannot affect its own utility (since π t is degree 1, . . . , ℓ consistent). Furthermore, the probability of event E is constant. Namely,

Pr[E] = ℓ j=1 pa t -ℓ-1+j (j) = ℓ j=1 j 2(t -ℓ -3 + j)
.

It is left for player v I to consider only the cases in which its degree is ℓ+1 in the graph T (t -1) . That is, for every degree sequence D ∈ D (I -1) that may occur at the beginning of player v I 's turn, and for every degree k ∈ D that v I selects in its turn, v I should consider the possibility that all subsequent players connect to it. This scenario would generate the following degree sequence:

D ⊕ k ⊕ 1 ⊕ 2 ⊕ • • • ⊕ ℓ .
Let f : D (I ) → {D ∈ D (t -1) | (ℓ + 1) ∈ D} be the following function:

f (D) = D ⊕ 1 ⊕ 2 ⊕ • • • ⊕ ℓ .
Hence in the above scenario, for degree k ∈ D chosen by player v I in its turn, the resulting degree sequence is f (D) ⊕ k = f (D ⊕ k). Now for any two distinct degrees k 1 , k 2 ∈ D that I considers to select in its turn, I should consider the following degree sequences in D (t -1) :

D 1 = f (D ⊕ k 1 ) and D 2 = f (D ⊕ k 2 ) . If π t (ℓ + 1, D 1 ) > π t (ℓ + 1, D 2 )
, then the player v I can improve its utility by deviating from pa to select the action D ⊕ k 1 whenever the pa strategy prescribes the action D ⊕ k 2 . Thus, Π is a Nash equilibrium for the static wbr game only if

π t (ℓ + 1, D 1 ) = π t (ℓ + 1, D 2 ). (3)
Accordingly, Eq. ( 3) translates to:

π t (ℓ + 1, f (D ⊕ k 1 )) = π t (ℓ + 1, f (D ⊕ k 2 ))
for every D ∈ D (I -1) , and every k 1 , k 2 ∈ D. Equivalently, we may say that for every edge (D 1 , D 2 ) in the graph Γ I ,

π t (ℓ + 1, f (D 1 )) = π t (ℓ + 1, f (D 2 )) (4)
By Lemma 4.11, the graph Γ I is connected. Therefore, as in the proof of Lemma 4.12, Eq. ( 4) must hold for every two degree sequences D 1 and D 2 in the graph Γ I . In other words, π t is a degree-(ℓ + 1) consistent strategy over all degree sequences in the range of the function f . So if we show that f is onto {D ∈ D (t -1) | (ℓ + 1) ∈ D}, we are done. Thus, let D ∈ D (t -1) be a degree sequence that contains a node of degree ℓ + 1. We define the function д : {D ∈ D (t -1) | (ℓ + 1) ∈ D} → D (I ) as follows:

д(D) = D ⊖ (ℓ + 1) ⊖ ℓ ⊖ • • • ⊖ 2.
We observe that the function д is well defined. For every degree sequence D in {D ∈ D (t -1) | (ℓ + 1) ∈ D}: the degree sequence D ⊖ (ℓ + 1) contains a node of degree ℓ, the degree sequence D ⊖ (ℓ + 1) ⊖ ℓ contains a node of degree ℓ -1, the degree sequence D ⊖ (ℓ + 1) ⊖ ℓ ⊖ (ℓ -1) contains a node of degree ℓ -2, etc. By applying Lemma 4.5 repeatedly, we get that for every

D in {D ∈ D (t -1) | (ℓ + 1) ∈ D} f (д(D)) = D ⊖ (ℓ + 1) ⊖ ℓ ⊖ • • • ⊖ 3 ⊖ 2 ⊕ 1 ⊕ 2 ⊕ • • • ⊕ ℓ = D ⊖ (ℓ + 1) ⊖ ℓ ⊖ • • • ⊖ 4 ⊖ 3 ⊕ 2 ⊕ 3 ⊕ • • • ⊕ ℓ = • • • = D ⊖ (ℓ + 1) ⊕ ℓ = D .
It follows that the function f is onto {D ∈ D (t -1) | (ℓ+1) ∈ D}, and thus Eq. (4) implies that π t is a degree ℓ + 1 consistent strategy.

Proof of Lemma 4.10. By Lemma 4.14 the strategy π t is a degreek consistent strategy, for every k ∈ {1, 2, . . . , t -4}. Degrees larger than t -2 are impossible because, at the beginning of step t, the graph contains exactly t -2 edges, so it is left to consider the degrees t -2 and t -3. The issue is that the only nodes that can be of degree t -2 or t -3 at time t -1 are nodes 1, 2 and 3, which have no meaningful choice in the game and thus have no effect on Nash equilibria. However, every possible strategy π ′ t at time t is degree-(t -2) and degree-(t -3) consistent. Because for D ∈ D (t -1) , it holds that t -2 ∈ D only if D is the degree sequence of the star graph, and t -3 ∈ D only if D = (t -3, 2, 1, . . . , 1). Since both of those degrees occur in only one degree sequence, there is no way for the strategy π ′ t to select nodes of those degrees with probabilities that are inconsistent over different degree sequences.

To establish the first part of the statement of Theorem 2.8, notice that the proof for Lemma 4.10 applies in this case as well. The assumption that every player up to t plays pa implied two properties of the strategy profile that were needed in the proof of the theorem. The first property is that π i is degree consistent for every i ∈ {1, . . . , t -1}, and the second property is that every degree sequence in t -1 i=1 D (i) is reachable. The first property applies here by definition. The second property applies since every possible action at steps 1, . . . , t -1 has a positive probability of occurring.

Proof of Theorem 2.6

We need one last preliminary result. Lemma 4.15. If π n is a degree consistent strategy, then n (1), the probability of contacting a leaf, determines the value of π n (k) for all k > 1. Moreover, if π n (1) = 1 2(n-2) then π n = pa.

Proof. Let π n (1) = x (note that necessarily x ≤ 1/(n -2)). We may calculate the probability of contacting a node of degree 2 by considering the path graph P n-1 . Contact probabilities must sum up to 1 in each graph, so π n (2) = (1 -2x)/(n -3). For every k = 3, . . . , n -2 we may calculate the probability of contacting a node of degree k by considering a graph with the degree sequence (k, 2 n-k -2 , 1 k ) to get:

π n (k) = 1 -(n -k -2) • 1 -2x n -3 -k • x . (5)
One can verify that for every degree sequence D = (d 1 , . . . , d n-1 ) in D (n-1) , π n defines a probability distribution over the nodes.

The second part of the lemma follows by direct calculation of π n (k) for every k when x = 1 2(n-2) .

Proof of Theorem 2.6. Let Π be a strategy profile. We show that if Π is not the preferential attachment profile, then Π is not a universal Nash equilibrium. Let n be the first player that does not play according to pa. From Lemma 4.4 if n = 5 we are done so assume n > 5 and so player v n-1 must play pa.

Let the graph at player v n-1 's turn be P n-2 , the path of length n -2. Note that the graph P n-2 is reachable by Lemma 4.1. Let π ′ n-1 be the strategy in which v n-1 selects a node of degree 1 with probability one, and let π ′′ n-1 be the strategy in which v n-1 selects a node of degree 2 with probability one. Let us denote by T n-1 the graph of n -1 nodes with degree sequence (3, 2, . . . , 2, 1, 1, 1), which results from v n-1 connecting to a node of degree 2 in P n-2 . Let α n-1 = 1, then the strategies π ′ n-1 and π ′′ n-1 result in the graphs P n-1 and T n-1 , respectively.

Since we assumed player v n-1 plays a mixed strategy and Π is a Nash equilibrium for every α n-1 , it follows that u

Plugging Equation ( 5) into Equation ( 6) yields

π n (1) = 1 2(n -2)
,

and thus the strategy π n must equal pa by Lemma 4.15, so we reach a contradiction. This completes the proof of Theorem 2.6.

CONCLUSION

This paper is, up to our knowledge, the first paper providing formal game-theoretic analytical arguments giving hints of why preferential attachment inherently pops up in the context of social networks. In short, there is no alternative: one must play preferential attachment for maximizing our social capital. This holds for a natural game capturing essential aspects of how connections between individuals are created in some realistic contexts. This work can be extended in many ways. First, one may ask what if the recommendation proceeds recursively, that is, the node recommended by the host may in turn recommend one of its neighbors with certain probability, and so on. Actually, the same argument as the one developed in this paper shows that PA remains a universal Nash equilibrium in this case too. A more challenging extension of this work is when each new node connects to m > 1 existing nodes. The resulting networks are not trees anymore, and extending our results to this framework appears to be non trivial. Finally, extensions where, in addition to node-events, edge-events could also occur, creating new connections between already existing nodes, or where the players have more knowledge about the actual structure than just its degree sequence, are challenging research directions which are definitely worth being investigated.

G 1 = S 4 G 2 = P 4 4 Figure 1 :

 42441 Figure 1: The two possible states after the first four players have played, with the possible positions of the fourth node.

Figure 2 :

 2 Figure 2: The four possible states after the first five players have played, with the possible positions of the fourth and fifth nodes.

Lemma 4 . 1 .

 41 Every tree T of size n has some positive probability of occurring after n steps of the wbr game with the preferential attachment profile. Lemma 4.2. A tree T of size n with degree sequence (d 1 , . . . , d n ) exists if and only if n i=1 d i = 2(n -1).

1 Figure 3 :

 13 Figure 3: The lattice of degree sequences connected by ⊕ events.

Definition 4 . 6 (

 46 [START_REF] Sagan | The symmetric group: representations, combinatorial algorithms, and symmetric functions[END_REF], p. 54). Suppose λ = (λ 1 , λ 2 , . . . , λ ℓ ) ⊢ n. The Young diagram of λ is an array of n boxes having ℓ left-justified rows with row i containing λ i boxes for 1 ≤ i ≤ ℓ.As an example, theYoung diagram of λ = (5, 3, 2, 2) is . Definition 4.7 ([23], p. 192). Let (A, ≤) be a partially ordered set. Then a, b ∈ A have a greatest lower bound, or meet, if there is

Definition 4 . 8 (

 48 [START_REF] Sagan | The symmetric group: representations, combinatorial algorithms, and symmetric functions[END_REF], p. 192). The Young lattice is the poset of all integer partitions ordered by inclusion of their Young diagrams.Consider a degree sequence D = (d 1 , d 2 , . . . , d n ) ∈ D(n) . Let us map D to the Young diagram with d 1 -1 boxes in the first row, d 2 -1 boxes in the second row, etc. For example:

  1 and D 2 are a covering pair} . Lemma 4.11. The graph Γ n is connected for all n.

2 ( 1 - 3 ( 1 -

 2131 (n) n-1 (π ′ n-1 , Π -(n-1) ) = u (n) n-1 (π ′′ n-1 , Π -(n-1) ) ,By Lemma 4.10, π n is a degree consistent strategy, so we may rewrite this equation as1 + α n π n (1) + 1 α n )π n (2) = 1 + α n π n (1) + 1 α n )π n (3) ,In turn this yields (for α n 1

ACKNOWLEDGMENTS

The authors would like to thank the anonymous referees for their valuable comments and helpful suggestions.

Pierre Fraigniaud received additional support from ANR under project DESCARTES -Grant No: ANR-16-CE40-0023 (http://www. agence-nationale-recherche.fr/Projet-ANR-16-CE40-0023), and from Inria under Project GANG (https://www.inria.fr/equipes/gang).

Zvi Lotker received additional support from LabEx Sciences Mathématiques de Paris (SMP). This work was partially done when he was visiting IRIF, CNRS and University Paris Diderot, under the framework of CNRS LIA FILOFOCS.