Jeanne Hagenbach
email: hagenbach@univ-paris1.fr

F Bloch

N Houy

J-C Vergnaud

Centralizing Information in Networks *

Keywords: Social network, social dilemma, dynamic network game, strategic communication. JEL Classification : D83 , C72, L22

In the dynamic game we consider, players are the members of a fixed network.

Everyone is initially endowed with an information item that he is the only player to hold. Players are offered a finite number of periods to centralize the initially dispersed items in the hands of any one member of the network. In every period, each agent strategically chooses whether or not to transmit the items he holds to his neighbors in the network. The sooner all the items are gathered by any individual, the better it is for the group of players as a whole. Besides, the agent who first centralizes all the items is offered an additional reward that he keeps for himself. In this framework where information transmission is strategic and physically restricted, we provide a necessary and sufficient condition for a group to pool information items in every equilibrium. This condition is independent of the network structure. The architecture of links however affects the time needed before items are centralized in equilibrium. This paper provides theoretical support to Bonacich (1990)'s experimental results. Résumé : Dans le jeu dynamique que nous considérons, les joueurs sont les membres d'un réseau donné. Chacun est initialement doté d'une information qu'il est seul à détenir. Les joueurs disposent d'un nombre fini de périodes pour centraliser ces informations initialement dispersées dans les mains d'un membre quelconque du réseau. A chaque période, chaque agent choisit stratégiquement de transmettre ou non les éléments qu'il détient à ses voisins dans le réseau. Plus les éléments sont rapidement rassemblés par un individu, meilleure est la situation pour le groupe de joueurs dans son ensemble. De plus, l'agent qui parvient le premier à centraliser tous les éléments reçoit une récompense additionnelle qu'il garde pour lui. Dans ce cadre où la transmission d'informations est stratégique ainsi que physiquement contrainte, nous donnons une condition nécessaire et suffisante à la centralisation des éléments par le groupe dans tous les équilibres. Cette condition est indépendante de la structure du réseau. En revanche, l'architecture des liens affecte le temps nécessaire à cette centralisation à l'équilibre. Ce papier fournit un soutien théorique aux résultats expérimentaux de Bonacich (1990).

1 Introduction [START_REF] Bonacich | Communication Dilemmas in Social Networks : An Experimental Study[END_REF] reports an experiment in which sucess of a given group depends on an effective flow of information among the members of this group. Precisely, subjects were initially given nonoverlapping subsets of letters from a quotation that the group of participants had to identify. Only once an individual identified the quote and independently of who did so, the group received a Collective Reward, equally shared between its members. This collective reward was reduced by a penalty that increased with the time needed to reach the common goal. To gather letters, subjects were offered several communication rounds, each being an opportunity for agents to transmit their letters along given communication links. Indeed, participants were arranged in a fixed network, whose links were the only possible channels letters could flow through. In addition to be physically restricted by the architecture of the communication links, the transmission of letters had a strategic aspect. Indeed, the participant who first identified the quotation in the name of the whole group was offered an Additional Reward that he kept for himself. Therefore, individuals had a collective interest to share their letters as well as an individual motivation to hoard them while waiting for other players' ones to arrive. Bonacich's experiment was run for different network structures and whether a subject communicated extensively or withheld letters appeared to depend on its network position. At a global level, Bonacich's experimental results support the following hypothesis : the outcome of the experimental game is affected by the architecture of the network players belong to. The present work proposes a model in which this hypothesis can be made precise and given theoretical support.

Bonacich's experiment is representative of a large class of situations in which the problem of communication between information holders arises, communication being physically restricted as well as limited by strategic retention of information. In organizations, the nature of a team's decision is often such that it requires the aggregation of some privately held pieces of information. 1 In this paper, we consider that the team's collective task is to put together all the information items that are initially dispersed. As teams often exist as a part of larger organizations, they seldom have the freedom to make adjustments of the stated patterns of communication used to pool information. We therefore examine the transmission of items along the links of a fixed communication structure. 2 We further consider that the agent who first centralizes information in the interest of his team individually benefits from this achievement. For instance, such an additional gain can take the form of a monetary reward, a promotion or gratitude form other members.

In this framework, we investigate how the fixed communication network affects the group's ability to centralize information items in equilibrium. We address the question of whether it may be 1 For instance, in [START_REF] Jehiel | Information Aggregation and Communication in Organizations[END_REF], an organization is in charge of a decision and each operating unit of the firm holds a partial and crucial information on the decision to be taken. In this work, communication is not strategic but works through the formation of groups of agents at different levels : employees directly communicate within their group before representatives of each group pool information in some groups of representatives and so on. The author characterizes the optimal communication structure assuming that information transmission within a group fails with a probability that solely depends on the group size.

2 A view of a firm's internal organization as a communication network can be found in [START_REF] Bolton | The Firm as a Communication Network[END_REF] or [START_REF] Radner | The Organization of Decentralized Information Processing[END_REF].

that among several communication patterns, all physically adequate for the successful completion of the common task, one results in a significantly "better" equilibrium outcome than an other. As there is not a unique definition of what "better" means in this context, we examine the effect of the network structure on the group performance in two ways. First, the performance of a team is evaluated regarding whether there is failure or success in pooling information in equilibrium. Next, and if success is ensured, we examine the impact of the structure on the time the group needs to succeed in equilibrium. If communication within the given network had no strategic aspect, the smaller the distance between a team member and every other member would be, the sooner the collective goal of items centralization could be reached. 3 In such a case, communication networks could be ranked regarding this distance only.

Formally, we analyze games in which n players are arranged in a network g and have T periods of play to put together n dispersed items. Each agent is initially given a unique item that he is the only player to hold and items are assumed obsolete after date T . In every period of this dynamic game, each player strategically chooses either to Hide or to Pass On to his neighbors in the network the items that he holds at that time. The game is of perfect information as actions are perfectly observed in every period. Two networks g and g ′ are compared with respect to the equilibrium outcomes of the two games played in g and g ′ . Our analysis yields two main insights. First, we provide a necessary and sufficient condition for a group to centralize items at some position in the network in every (subgame perfect) equilibrium. Interestingly, this condition is independent of the network structure. Precisely, we show that a group of n players never fails to pool information in equilibrium if and only if the number of periods offered to do so is at least equal to n -1, no matter the network players are arranged in. Next, we claim that network structure affects the time needed for the n items to be gathered in equilibrium. Even in the case in which every player Passes On his items to all his neighbors in every period, every player needs a minimal number of periods to win that depends on his position. This minimal number of periods physically required corresponds to a graph-theoretical measure called a player's eccentricity. We prove that there always exists an equilibrium in which the game ends at the earliest date physically possible for the group. This date is given by the minimal eccentricity in the network, called its radius. Finally, we show that, for two particular networks, namely separable and complete ones, there exists an upper bound on the duration before success in equilibrium.

The game we analyze is a Network Game in the sense that non-cooperative players are the members of an exogenous network. It contributes to the economic literature studying games played on social networks extensively surveyed in [START_REF] Goyal | Connections : An Introduction to the Economics of Networks[END_REF] and [START_REF] Jackson | Social and Economic Networks[END_REF]. [START_REF] Galeotti | Network Games[END_REF] present a very general framework for static network games. The authors assume that a player's payoff depends on his own action as well as on the actions taken by his direct neighbors in the graph. The same assumption is made in computer sciences models of Graphical Games introduced by [START_REF] Kearns | Graphical Models for Game Theory[END_REF]. Graphical games literature focuses on finding algorithms to compute equilibria in one-stage games played on large-scale networks. In the present work, the game played by network members is dynamic. Players' payoffs directly depend on the actions taken by every member of the network in every period of play and on the order of these actions. Indeed, in the game we build, information is pooled not only if every player transmits the items he holds, but also if it happens in a particular order that depends on the network structure. To understand this idea, consider the following network g line :

1 2 3

To get the three dispersed information items privately held by every player at the beginning of the game, player 1 not only needs players 2 and 3 to Pass On but he also needs player 3 to Pass On before player 2 does so. In the network g line , player 2 is an intermediary for the transmission of information from agent 3 to 1.

The paper is organized as follows. In the next section, we present the model. The necessary and sufficient condition to ensure information centralization in every equilibrium is provided in Section III. Results on possible sets of winners in equilibrium are presented in Section IV. The focus of Section V is on the time needed to pool information items in equilibrium. Section VI concludes. Proofs are mainly relegated to the Appendix.

The Model

Set-Up

Players, Actions and Network : The set of agents is N = {1, . . . , n}. Agents are arranged in a connected network4 represented by a graph g, with ij ∈ g if player i is linked to player j. We assume that communication links are undirected so that ij ∈ g implies ji ∈ g, meaning that information can flow in both ways. For a given network g, the geodesic distance d ij (g) between agents i and j is the length of the shortest path between them. Let N i (g) be i's neighborhood in g : N i (g) = { j ∈ N \{i} : ij ∈ g}. We denote g\{i} the subnetwork of g with the set of agents N \{i} and all links between these agents which exist in g.

The game is played over discrete time periods t = 0, ..., T with a finite deadline T ≥ 1. At each date t ≥ 1, every player i chooses an action a t i from the set A = {P, H} : a t i = P means that player i Passes On all the information items he holds at time t to every agents in his neighborhood N i (g) and a t i = H means that player i Hides all his information items to every player. The way pieces of information are transmitted is exposed in more detail below.

An action profile at time t is a vector a t = (a t i ) i∈N ∈ A n . A history h t of the game at time t is the observed past sequence of profiles of actions (a 1 , ..., a t-1 ), which is an element of the set of histories at date t denoted H t = (A n ) t-1 . At date t, every player perfectly observes the history h t .

Information Items : We assume that there are n different information items, numbered from 1 to n. Initially, every player is given a unique item, which he is the only player to hold. Player i is given the item numbered i. The state of players' information at date t is given by a matrix V t ∈ {0, 1} n×n with the component v t ij of V t equal to 1 if player i holds the item j at date t and 0 otherwise. Initially, the matrix of players' information is the identity matrix : V 0 = Id n .

The state of players' information evolves as players Pass On or Hide. We assume that, once received, an item is never lost, even if Passed On later in the game. Formally, for every i, j ∈ N , the component v t ij evolves in the following way :

v t ij = M ax {k∈N i (g):a t k =P } {v t-1 ij , v t-1 kj }. (1)
Payoffs, Winners and Losers : The payoff structure has common features with the one considered in Bonacich's experimental study. If there is no player who manages to gather the n items before the deadline T is reached, then players earn nothing. On the contrary, if there is at least one player who centralizes the n items in the time offered to do so, then all the players are rewarded. In this case, we denote τ the first period in which the n items are held by an agent. The game ends up at τ . At this date, a Collective Reward of value n is equally shared between all the players. Besides, the players who have managed to pool information items, called the winners, receive an Additional Reward of value R > 0. In case there are several winners, the Additional Reward is equally shared between them. Players who have not centralized the items are called the losers. Payoffs are discounted according to some common discount factor δ ∈ (0, 1].

For a given g, each final history h T +1 uniquely defines a sequence of matrices representing players' information (V 0 , V 1 , ..., V T ). Denote ι n the vector with n components equal to 1. The present value of player i's payoff is given by :

u i (V 0 ...V T ) =                0 if V T j = ι n , ∀ j ∈ N, δ t-1 if V t i = ι n and ∃ j = i, j ∈ N : V t j = ι n and ∀ k ∈ N , V t-1 k = ι n , δ t-1 (1 + R l ) if V t i = ι n and ∀ k ∈ N , V t-1 k = ι n , with l = #{k ∈ N : V t k = ι n }.
A game involving players in the set N arranged in a network g and lasting T periods is denoted Γ(N, g, T ).

Strategies : We restrict our attention to pure strategies. A pure strategy of player i is a profile s i = (s 1 i , ..., s T i ) with s t i : H t → A for every t = 0, . . . , T . A strategy profile is denoted s = (s i ) i∈N .

Example :

As an example, consider the one-shot duel Γ({1, 2}, g, 1) where g is the complete network. Initially, players' states of information V 0 is Id 2 . Since N 1 (g) = N 2 (g) = N , if player i Passes On the item he holds initially to player j = i, then v 1 ji = v 1 ii = 1. It is easy to get the matrix of utilities of Γ({1, 2}, g, 1) which is the well known Chicken Game :

P H P 1 + R 2 , 1 + R 2 1, 1 + R H 1 + R, 1 0, 0
The one-shot duel has two Nash Equilibria in pure strategies : (a 1 , a 2 ) = (P, H) and (a ′ 1 , a ′ 2 ) = (H, P ). Note that every equilibrium outcome is such that the game ends with a winner.

Equilibrium Concept

The game Γ(N, g, T ) has a multiplicity of Nash Equilibria (NE) and we do not attempt to provide a complete characterization of these. To narrow down the set of NE, the solution concept we use is the Subgame Perfect Nash Equilibrium (SPNE). 5 Since we investigate the way information is pooled in a decentralized way by the members of a fixed network, we find it reasonable to assume that players do not commit themselves to the dates at which they plan to Pass On. Incorporating subgame perfection therefore makes sense. In the sequel, for every game Γ(N, g, T ), the set of (SP)NE is denoted S (SP )N E .

The way subgame perfection eliminates non-credible threats in the game we propose appears in the following example. Consider Γ({1, 2, 3}, g line , 2) with g line the three-player network presented in the Introduction. The strategy profile that consists in "every player Hiding in every period, whatever the history", is a NE. Indeed, as long as two players out of three Hide in every period, every player receives 0, whatever his strategy. Next, consider the subgame of Γ({1, 2, 3}, g line , 2) that starts at time t = 2 after player 1 has Passed On at date t = 1 while players 2 and 3 have Hidden. In this subgame, if player 3 Passes On instead of Hiding, he receives δ instead of 0 as player 2 finally holds the three information items. It follows that "players 2 and 3 Hiding in the second period of play, whatever the history" is not credible.

Graphical Objects

We define some graph-theoretical concepts that are used in the sequel. First, a classical measure of centrality in graphs is the eccentricity : Definition 1 Player i's eccentricity in the network g, denoted e i (g), is the distance from agent i to the agent furthest away from him : e i (g) =max j∈N {d ij (g)}.

In the game Γ(N, g, T ), player i's eccentricity is equal to the minimal number of periods required for player i to centralize the n items when every player Passes On in every period. Given a network g, the minimal eccentricity is called the radius r(g) and the maximal eccentricity is called the diameter d(g). Obviously, a player i cannot win in a game Γ(N, g, T ) that lasts strictly less than e i (g) periods. We define the following set :

Definition 2 In a game Γ(N, g, T ), the set of potential winners is given by W (g, T ) = { i ∈ N : e i (g) ≤ T }.
Games of interest are games Γ(n, g, T ) such that W (g, T ) = ∅ or equivalently such that T ≥ r(g) and we restrict our attention to such games in the present work. Note that every player can potentially win, i.e. W (g, T ) = N , iff T ≥ d(g).

Definition 3 In a connected graph g, an agent i is exterior (respectively interior ) if g\{i} is connected (respectively disconnected).

In other words, an exterior agent can be dropped from a connected graph with the resulting subnetwork still being connected. On the contrary, an interior agent is crucial in maintaining the connectedness of a network. By definition, an agent who is interior in g is on every path between at least one pair of agents in g.

A complete network, denoted g complete , is a particular architecture in which every agent is linked to every other one, i.e. N i (g) = N \{i} for every i ∈ N . As it implies that a link exists between every pair of distinct agents, every agent is exterior in g complete . A tree network, denoted g tree , is such that there is a unique path between every pair of distinct agents. It follows that there is at least one interior agent in every tree involving n ≥ 3 players. Note that a connected network involving n = 2 players is particular in that it is both a complete and a tree network. More generally, the following theorem deals with the existence of exterior agents in connected networks :

Theorem 1 [ [START_REF] Kelly | On the Transpose Connectivity of Graphs[END_REF]] In a connected network with n ≥ 2 agents, there are at least two exterior agents.

Finally, a particular type of network structure is defined with respect to the existence of an interior agent :

Definition 4 A connected network in which there exists at least one interior agent is separable. A connected network in which every agent is exterior is nonseparable.

A separable network can be disconnected by removing one agent. Tree networks involving more than three players are separable whereas complete networks are not.

To illustrate the previous definitions, we consider the following network g kite which is neither complete nor a tree :

1 2 3 4 e 1 = 2 e 2 = 1 e 3 = 2 e 4 = 2
Players' eccentricities appear near players' labels. We have r(g kite ) = 1 and d(g kite ) = 2. The sets of potential winners are W (g kite , 1) = {2} and W (g kite , T ) = N for every T ≥ 2. The network g kite is separable with player 2 being interior whereas players 1, 3 and 4 are exterior.

Success or Failure in Equilibrium

Our objective is to compare network structures with respect to their efficiency in encouraging information centralization when its transmission is strategic. Note that if information transmission were not strategic but were automatic in every period, network structures could be trivially ranked as r(g) would be the number of periods required to centralize the n dispersed items in a network g.

The first measure of group performance that we consider is the achievement of the collective goal in every equilibrium. For every game Γ(N, g, T ), the set of strategy profiles S is split into two disjoint subsets. Let S W ⊆ S be the set of strategy profiles such that the game Γ(N, g, T ) ends with at least one winner, or equivalently, such that the collective goal is reached at a time t ≤ T . Let S L = S\S W be the set of strategy profiles such that the game ends with no winner, or equivalently, such that players have failed to centralize information at some position in the network before the deadline is reached.

Recall that if a game ends with at least a winner, every player earns a strictly positive payoff whereas if the game ends with no winner, every player earns 0. It follows that failure in performing the collective task is an outcome that is Pareto dominated by any outcome in which success is ensured.

The following Proposition, which is instrumental to prove our general result, states that every NE of a dynamic duel Γ({1, 2}, g, T ) yields at least one winner:

Proposition 1 In the dynamic duel Γ({1, 2}, g, T ), S N E ⊆ S W .
Proof : For a duel to end up with a winner, it is sufficient to have one of the two players Pass On before the deadline is reached. Therefore, when players are offered T ≥ 1 periods of play, both players loosing cannot be an equilibrium outcome since every player can unilaterally prevent such an outcome.

The next proposition provides a necessary and sufficient condition for success to be ensured in every SPNE outcome of Γ(N, g, T ) :

Proposition 2 S SP N E ⊆ S W if and only if the game Γ(N, g, T ) is such that T ≥ n -1.
That is, every equilibrium yields at least one winner if and only if the game lasts sufficiently many periods. On the contrary, if the deadline is T ≤ n -2, there exists equilibria that lead to failure in the collective task. Note however that, in such cases, there may also be equilibrium outcomes such that there is a winner.

Interestingly, the condition T ≥ n -1 is independent of the structure of the connected network g and, in particular, depends neither on its radius nor on its diameter. Given a deadline T and a fixed number of players n, all communication networks are therefore equally efficient with respect to the efficiency criterion considered in this section, namely the achievement of the collective goal in every equilibrium. Precisely, a complete network happens to be as efficient as any connected structure that minimizes the number of links such as tree networks do. In settings in which building communication links is costly but neither the identity of the winner nor the time needed to succeed matters, a tree network can be chosen rather than any other structure.

The proof of the fact that T ≥ n -1 is a sufficient condition to get S SP N E ⊆ S W is done by induction and is quite constructive. To see how Proposition 1 is used, consider the one-shot game Γ({1, 2, 3}, g line , 1). In this game, if two or more players Hide, the game ends with no winner and this is a NE since no player can unilaterally prevent this outcome. Proposition 2 says that, adding a period to Γ({1, 2, 3}, g line , 1) is sufficient to rule out such an equilibrium. This is due to the fact that, in Γ({1, 2, 3}, g line , 2), player 1 or player 3 have the ability to unilaterally make the game evolve into a duel between the two other players that would last at least one period. This happens to be a general feature of exterior agents whose existence relies on Theorem 1. More precisely, if an exterior player, say player 1, Passes On at date t = 1 while the other players Hide (which means they behave in the worst way regarding items centralization), then the subgame that starts at time t = 2 is strategically equivalent to the one-shot duel : players 2 and 3 are directly linked to each other and each player is holding some items that, if transmitted, make the other player win immediately. This is represented as Situation A in Figure 1. 6 Next, as stated in Proposition 1, once a duel is reached, every equilibrium yields at least a winner. The same reasoning can be applied to the game Γ({1, 2, 3}, g complete , 2) as it is illustrated by Situation B on the following Figure. From the previous paragraph, we have that every equilibrium outcome of Γ({1, 2, 3}, g, 2) is such that there is a winner. Next, one can get the same result for games Γ({1, 2, 3, 4}, g, 3) by noticing that there always exists an exterior agent in g who can, by Passing on at time t = 1, make the subgame that starts at time t = 2 be such that the other three players are in a situation strategically equivalent either to Γ({1, 2, 3}, g line , 2) or to Γ({1, 2, 3}, g complete , 2). This inductive reasoning enables to state that the minimal number of periods sufficient to get a winner in every equilibrium of Γ(N, g, T ) is (n -1). It corresponds to the minimal number of links necessary to connect n players. It is also the number of periods required to reduce the game to a duel through successive items transmissions by exterior agents who are then "dropped" from the network.

The last section stressed the special role played by exterior players. We next show that, for some particular networks, there is at least one exterior agent who loses in every equilibrium. More generally, in this section, we examine the impact that network architectures have on the set of agents who may manage to centralize information items. Even in the case in which all the players had the opportunity to do so because they were offered a number of periods greater than every eccentricity, the structure prevents some players from winning together in equilibrium.

Proposition 3 If the game Γ(N, g, T ) is such that the network g is separable, then every strategy profile s ∈ S W is such that there exists at least one exterior agent who loses.

Proposition 3 states that it cannot be that all the members of a separable network win together. Taking a look at the separable network g kite presented in section 2.3, one can easily get an intuition of why it is so. Assume that exterior players 1, 3 and 4 win together at time t. To get such an outcome, player 1 must hold, at date t, the items initially held by players 3 and 4 and vice versa. In g kite , player 2 is the intermediary for information transmission between player 1 and players 3 and 4. It follows that players 1, 3 and 4 winning together at time t implies that player 2 already held the four items at a date t ′ ≤ t -1, which contradicts the initial assumption.

As stated in definition 2, given an architecture g and a deadline T , a set W (g, T ) of potential winners is defined. In particular, a game Γ(N, g, T ) can be such that every player in W (g, T ) is interior. Since a connected structure involves at least one exterior agent, this directly implies that every strategy profile s ∈ S W is such that there exists at least one exterior agent who loses. Note that this is not the object of the previous Proposition. Indeed, Proposition 3 states that if g is separable, then all the players cannot win together and this, even in the case in which they all potentially could. Proposition 3 imposes no restriction on the set W (g, T ).

While the previous proposition relies on the graphical properties of separability, the following result is established for equilibrium strategy profiles. Precisely, we prove the uniqueness of the winner in equilibrium for two particular network structures. The following statement, as Proposition 3, is independent of W (g, T ).

Proposition 4 If the game Γ(N, g, T ) is such that the network g is either complete or a tree, then every strategy profile s ∈ S SP N E ∩ S W is such that the winner is unique.

Next, using Proposition 2, the following result is directly deduced from Propositions 3 and 4 : separability or completeness and a sufficiently large number of periods are sufficient to get at least one exterior agent losing in every equilibrium.

Corollary 1 Let Γ(N, g, T ) be such that T ≥ n-1. In this game, if the network g is either separable or complete, then every strategy profile s ∈ S SP N E is such that there exists at least one exterior agent who loses.

On the contrary, we now present an example in which all the members of a nonseparable and incomplete network win together in equilibrium. In the circle examined, every player is exterior. Consider the game Γ({1, 2, 3, 4}, g circle , 2) with g circle a four-players circle. We start by analyzing the subgame that would result from a first period in which every player Passes On. The informational situation of such a subgame is illustrated by Situation C on Figure 2. In Situation C, if every player Passes On, the game ends with four winners. At date t = 2, by Hiding while the other players Pass On, no player can prevent the other three players from winning. Consequently, starting from Situation C, "every player Passing On" is a NE that yields four simultaneous winners.

Next, we analyze the subgame that would result from a first period of play in which one player, say 1, Hides and the other three players Pass On. Situation D on Figure 2 shows the resulting informational situation. In Situation D, if player 1 Passes On while the other three players Hide, the game ends up with players 2 and 4 receiving δ(1 + R

2 ) whereas players 1 and 3 earn δ. At date t = 2, by Hiding instead of Passing On, player 1 makes the game end with no winner. Given Situation D, player 3's action has no impact on the outcome of the game. Finally, if player 2 or 4 deviates from Hiding, it makes three players win (1, 2 and 4) instead of two (2 and 4). Therefore, starting from Situation D, "player 1 Passing On while the other players Hide" is a NE that yields two simultaneous winners, players 2 and 4.

Finally, comparing Situations C and D, player 1 has no interest in deviating from Passing On in the first period when the other three players Pass On. The same is true for every player as their positions are symmetric. We conclude that there exists an equilibrium action profile such that every player Passes On in the two periods of play yielding four winners at time t = 2.

What makes nonseparable and incomplete networks different from other structures is that they exhibit at least two paths linking any pair of agents. Therefore every information item can flow at least two distinct ways to go from the initial holder to any agent. As a result, for every agent, it can happen that, by Hiding, he is unable to stop some items' transmission because they are transmitted along the other possible path. It follows that a subgame can start in which there does not exist a single player who is able to prevent all the players from winning together, which never happens in situations analyzed in Corollary 1. Among equilibria that yield success, aggregate payoffs are lower when information is centralized at time t than at any earlier date t ′ < t.7 This section focuses on the time needed for the group of players to succeed in equilibrium. From a global point of view, the minimal duration before success in equilibrium gives the best equilibrium outcome and, once success is ensured in every equilibrium, maximal duration before success gives the worst equilibrium outcome.

Minimal Duration

In a game Γ(N, g, T ), duration before success has a lower bound that depends on the architecture of the network g and corresponds to the radius r(g). The first question we ask is therefore whether the end of the game at time t = r(g) is a SPNE outcome. The next proposition states that it is the case meaning that, with respect to the best equilibrium outcomes, networks can be ranked according to their radiuses.

Proposition 5 For every player i ∈ N such that e i (g) = r(g), there exists a SP N E such that player i is the unique winner at time t = r(g).

Complete networks are particular in that every member's eccentricity is equal to the radius r(g) = 1. Interestingly, the previous proposition applied to games Γ(N, g complete , T ) corresponds to a well-known result of the war of attrition literature. In g complete , an information item which is Passed On is immediately held by every player. As a consequence, a member of a complete network is the unique winner if and only if he is the last player to Pass On. In other words, as soon as (n -1) players have "conceded", the game ends with the player who has not conceded yet holding the n items and winning. To that extent, the game Γ(N, g complete , T ) can be viewed as a war of attrition of complete information in which n symmetric players compete for one prize in discrete and finite time. As in the war of attrition, every player strictly prefers to win than to lose but prefers to lose sooner than later.

In [START_REF] Kornhauser | Reputation and Patience in the 'War of Attrition[END_REF], a concession game with complete information is played in discrete time by two players 1 and 2 with different discount factors. The authors show that "there is an infinity of SPNE outcomes : one of these outcomes is for player 1 to concede immediately, another is for player 1 to wait and for player 2 to concede immediately". Proposition 5 corresponds to the straightforward generalization of the previous statement to n players competing for one prize. [START_REF] Bilodeau | Toilet cleaning and department chairing : Volunteering a public service[END_REF] present a n players continuous-time war of attrition in finite horizon with n players competing for (n -1) prizes. The authors state that "for every individual, there is a SPNE outcome in which only that individual concedes immediately". On the contrary, since we study a case in which n players compete for one prize, we show that, for every individual, there is a SPNE outcome in which all the individuals except that one concede immediately. If g = g complete , n players compete for one prize but the order in which (n-1) players concede is crucial and dependent on the network structure.

Maximal Duration

Among games in which success is ensured in every equilibrium, we further pay attention to the maximal duration of the game in equilibrium. For every game Γ(N, g, T ), the set of strategy profiles S W is split into two disjoint subsets. Let S end≤n-1 ⊂ S W be the set of strategy profiles such that the game ends with at least a winner at a date t ≤ n -1. Let S end≥n = S W \S end≤n-1 be the set of strategy profiles such that the game ends with at least a winner at a date t ≥ n.

The following proposition states that every equilibrium of a dynamic duel Γ({1, 2}, g, T ) is such that the game ends up in the first period of play :

Proposition 6 In the dynamic duel Γ({1, 2}, g, T ), S SP N E ⊆ S end≤1 .

Proof: As mentioned in the proof of Proposition 1, a single period of time is sufficient for every agent to make a duel end. In addition, Proposition 4 states that the winner is unique in every equilibrium of Γ({1, 2}, g, T ). It follows that an equilibrium strategy profile cannot be such that the game lasts strictly more than one period as the loser would have a profitable deviation to a strategy that makes him lose in the first period of play.

Next, we focus on games involving three players.

Proposition 7 Let Γ({1, 2, 3}, g, T ) be such that T ≥ 2. In this game, S SP N E ⊆ S end≤2 .

Proof: As illustrated on Figure 1, as soon as an exterior player Passes On in Γ({1, 2, 3}, g, T ), say at t, the subgame starting at t + 1 is a duel between the two other players. Proposition 6 states that, in equilibrium, dynamic duels always end in one-shot. It implies that every s ∈ S SP N E such that Γ({1, 2, 3}, g, T ) ends at t is such that there is no exterior agent who Passed On at a date t ′ < t -1. In addition, from Corollary 1, we have that every s ∈ S SP N E is such that there is an exterior agent who loses. If such an agent loses at a date t ≥ 3, he has a strictly profitable deviation that consists in Passing on at t = 1 to lose at date t = 2. We conclude that S SP N E ∩ S end≥3 = ∅.

In a three-player game lasting at least two periods, Proposition 7 states that every equilibrium yielding a winner does so in either one or two shots. This result relies on the fact that, in equilibrium, every duel lasts one period and on the fact that every player who is exterior in a three-player network can make the game change into a duel. Recall that we assume that every player strictly prefers to lose sooner than later but we do not exclude that an agent may prefer to be a winner (even among many) at date T than to lose earlier. It follows that Corollary 1 is required to find an exterior player who loses in equilibrium and therefore has a strict incentive to reduce the game to a duel, in which he still loses but more rapidly. More generally, we have : Proposition 8 Let Γ(N, g, T ) be such that T ≥ n -1. In this game, if the network g is either separable or complete, then S SP N E ⊆ S end≤n-1 .

In a game Γ(N, g, T ) with T ≥ n -1, there are equilibrium outcomes such that there is a winner at a date t ≤ n -1. What Proposition 8 shows is that this is true for every equilibrium if either separability or completeness of g is ensured. As mentioned before, Proposition 7 relies on Proposition 6. Similarly, Proposition 8 is established by induction, assuming that it is true for n players to prove it for n + 1. An additional complexity to this inductive reasoning comes from the fact that networks matter in Proposition 8 but the two examined structures are particular : to remove an exterior agent with all its links from a complete network leaves the subnetwork complete and to remove an exterior agent from a separable graph leaves the subnetwork separable.

Conclusion

In the dynamic game we propose, the members of a fixed network face a social dilemma in the sense that they have a collective interest to share information items by transmitting them via communication links as well as an individual interest to withhold them. We show that, a group of n players centralizes all the initially dispersed items in every subgame perfect equilibrium, if and only if the game lasts sufficiently many periods, precisely more than n-1 periods. It follows that whether or not the collective task is performed in every equilibrium is independent of the network structure, as long as it is physically adequate for the successful completion of this task which means that the network is connected. On the contrary, the architecture of communication links affects the time needed before information items are pooled in equilibrium. For every network, the minimal time needed in equilibrium is given by the radius of the network. For complete and separable graphs, once sucess is ensured in equilibrium, n -1 corresponds to the maximal number of periods required for items centralization.

Information items that are considered in this paper are not private information in the usual sense of incomplete information games. For instance, one could imagine that the items transmitted by players are some keys that have to be centralized by the agents for them to open a box. Note that it would then be as if each player Passed On copies of the keys he possessed. To answer the question about the structure that is the most appropriate for the pooling of these keys, we introduce graphical notions and results from graph theory that are used in some areas of operations research.8 For instance, a building block of our analysis is a graphical result stating that, in every connected network, there exists at least two exterior agents. Since such agents can be dropped from a network without disconnecting the resulting subnetwork, proofs can be done by induction within networks.

Even if [START_REF] Bonacich | Communication Dilemmas in Social Networks : An Experimental Study[END_REF]'s experimental results stated that the outcome of social dilemmas is affected by the network structure, his study rather examined the influence of an agent's position on his individual behavior. For instance, it seemed that agents with peripheral positions behaved more cooperatively than central agents. In the present work, for agents who are not in the set of potential winners because they are peripheral in the sense that their eccentricities are too large, Passing On in every period of play is a weakly dominating strategy. That is, the effective chances of victory determined by physical network positions clearly affect one's communication behavior. such that, for every i ∈ N and every t ≤ T , we have (A) : for each item j ∈ N , ṽ′t ij ≥ v t ij .9 Next, since s′ ∈ S′ L , there exists for every i ∈ N an item k ∈ N ′ such that ṽ′T ik = 0. Given that items n and (n + 1) are transmitted together in Γ(N ′ , g ′ , T ) as ṽ′0 n n+1 = 1, we get that s′ ∈ S′ L implies that there exists for every i ∈ N an item k ∈ N such that ṽ′T ik = 0. Using (A), we have that s′ ∈ S′ L implies s ∈ S L . Finally, if s′ ∈ S′ SP N E , the profile of continuation strategy s′ |h ′t is a NE of the subgame Γ(N ′ , g ′ , T )|h ′t for every h ′t ∈ H ′t . Since s′ is such that, for every i ∈ N , player i's action in every period is independent of player (n + 1)'s past actions and player (n + 1)'s actions are independent of the history, we directly get: if s′ |h ′t is a NE of Γ(N ′ , g ′ , T )|h ′t , then s|h t is a NE of Γ(N, g, T )|h t with h ′t and h t describing the same action profile for every i ∈ N and every date t ≤ T . It follows that s′ ∈ S′ SP N E implies s ∈ S SP N E which completes the proof.

Proof of Lemma 1 : From Proposition 1, Lemma 1 is true for n = 2. We assume that Lemma 1 is true for n agents and prove that it stays true for n + 1 agents: if the game

Γ(N ′ , g ′ , T + 1) is such that T + 1 ≥ n, then S ′ SP N E ∩ S ′ L = ∅. First, in Γ(N ′ , g ′ , T + 1), we consider a strategy profile s ′ ∈ S ′
SP N E such that a ′1 n+1 = P and we show that T + 1 ≥ n implies s ′ ∈ S ′ W . By definition of SPNE, the profile of continuation strategy

(s ′ i |h ′2 ) i∈N ′ is a SPNE of the subgame Γ(N ′ , g ′ , T + 1)|h ′2 with h ′2 = ((a ′1 i ) i∈N , P
). This subgame is equivalent to the augmented modified game Γ(N ′ , g ′ , T ). More precisely, games Γ(N ′ , g ′ , T + 1)|h ′2 and Γ(N ′ , g ′ , T ) have the same set of players N ′ , the same network g ′ , the same number of periods of play T and the same matrix of players' information : at the beginning of Γ(N ′ , g ′ , T + 1)|h ′2 the matrix V ′1 is such that, for every i ∈ N ′ , we have v ′1

ii = 1 and such that v ′1 n n+1 = 1 since n ∈ N n+1 (g ′ ) and a ′1 n+1 = P . By assumption, if Γ(N, g, T ) is such that T ≥ n -1, then S SP N E ⊆ S W . Given Γ(N ′ , g ′ , T ), we can find a game Γ(N, g, T ) to get a pair and then deduce from Lemma 2 that

S′ SP N E ⊆ S′ W . Therefore, (s ′ i |h ′2 ) i∈N ′ ∈ S′ SP N E implies (s ′ i |h ′2 ) i∈N ′ ∈ S′ W which implies that s ′ = (s ′1 i (h ′1 ), s ′ i |h ′2 ) i∈N ′ ∈ S ′ W . Next, in Γ(N ′ , g ′ , T + 1), we consider a strategy profile s ′ ∈ S ′
SP N E such that a ′1 n+1 = H and we show that T + 1 ≥ n implies s ′ ∈ S L . By definition of SPNE, the profile of continuation strategy

(s ′ i |h ′2 ) i∈N ′ is a SPNE of Γ(N ′ , g ′ , T + 1)|h ′2 with h ′2 = ((a ′1 i ) i∈N , H).
As shown in the previous paragraph, if T ≥ n -1, then every SPNE played in a subgame Γ(N ′ , g ′ , T + 1)|h ′2 that starts after an history h ′2 = ((a ′1 i ) i∈N , P ) is such that the game Γ(N ′ , g ′ , T + 1) ends up with a winner. Therefore, if we assume that s ′ ∈ S ′ L , then T ≥ n -1 implies that player (n + 1) has an interest in deviating from s ′ n+1 such that a ′1 n+1 = H to a strategy s ′′ n+1 such that a ′′1 n+1 = P . This profitable deviation in the first period of play contradicts

s ′ ∈ S ′ SP N E which is why s ′ ∈ S ′ L . Proof is completed by noting that every s ′ ∈ S ′ SP N E is either such that a ′1 n+1 = H or such that a ′1 n+1 = P . 7.1.2 Proposition 2 : Necessary Condition Lemma 3 If the game Γ(N, g, T ) is such that T ≤ n -2, then S SP N E ∩ S L = ∅.
We prove Lemma 3 for complete networks only and use the the following lemma to get it for every connected network.

Lemma 4 If S SP N E ∩ S L = ∅ in Γ(N, g complete , T ), then S SP N E ∩ S L = ∅ in Γ(N, g, T ).
Proof : In Γ(N, g complete , T ), consider a strategy profile s c ∈ S L . Next, in Γ(N, g, T ), consider a strategy profile s such that s and s c describe the same action profiles for every i ∈ N and every t ≤ T , in Γ(N, g complete , T ) and Γ(N, g, T ) respectively. It is easy to show that if s c ∈ S L , then s ∈ S L since N i (g) ⊆ N i (g complete ) = N \{i} for every i ∈ N . Equivalently, we get that if s ∈ S W , then s c ∈ S W . It follows that if there exists a player i who has a strictly profitable deviation from a profile s ∈ S L for an history h t in Γ(N, g, T ), then the same deviation from s c ∈ S L is strictly profitable in Γ(N, g complete , T ). We conclude that if the strategy profile s ∈ S L is not in S SP N E , then the strategy profile

s c ∈ S L is not in S SP N E . Lemma 5 If the game Γ(N, g complete , T ) is such that T ≤ n -2, then S SP N E ∩ S L = ∅.
Proof : We show that if T ≤ n -2, then there exists a strategy profile s ∈ S SP N E ∩ S L . For every

h t , denote K(h t ) the set {i ∈ N : ∀j ∈ N \{i}, v t-1 ji = 0} and let k(h t ) = |K(h t )|. Players in K(h t ) have Hidden in every period t ′ ∈ [1, t -1].
Note that as soon as an history h t is such that K(h t ) is a singleton, say K(h t ) = {l}, the game ends at t with player l being the unique winner. Consider the profile s such that, for every i ∈ N , we have : -

s t i (h t ) = H if i ∈ K(h t ) -s t i (h t ) = H if i ∈ K(h t ) and T -t + 1 ≤ k(h t ) -2 -s t i (h t ) = H if i ∈ K(h t ) and T -t + 1 > k(h t ) -2 and i = M in j∈K(h t ) j -s t i (h t ) = P if i ∈ K(h t ) and T -t + 1 > k(h t ) -2 and i = M in j∈K(h t ) j. First, let's show s ∈ S L . Since for every i, j ∈ N , i = j, v 0 ij = 0, we have that K(h 1 ) = N and k(h 1 ) = n. If T -1 + 1 ≤ n -2, then, following s, V 1 remains equal to Id n . Repeating the reasoning directly establishes s ∈ S L .
Next, let's show s ∈ S SP N E by showing that s satisfies the one-stage deviation principle. We distinguish two kinds of histories h t and check that, conditional on h t reached, no player i ∈ N has an strict interest in unilaterally deviating from the continuation strategy s i |h t at date t and conforming to s i |h t thereafter10 .

First, consider a subgame Γ(N, g complete , T )|h t with h t such that Tt + 1 > k(h t ) -2. Let l = M in j∈K(h t ) j. Following (s i |h t ) i∈N , the action profile (a t i ) i∈N is such that (a) for every i ∈ K(h t ), a t i = H, (b) for every i ∈ K(h t )\{l}, a t i = P and (c) a t l = H. Therefore, we get K(h t+1 ) = {l} 11 . As a consequence, following (s i |h t ) i∈N in Γ(N, g complete , T )|h t , the game Γ(N, g complete , T ) ends at t with l being the unique winner. Obviously, player l has no interest in unilaterally deviating from s l |h t at time t. In addition, in g complete , the action of every i ∈ K(h t ) has no effect in Γ(N, g complete , T )|h t12 , so there is no strict interest in deviating from s i |h t at t. Finally, consider a deviation of a player j ∈ K(h t )\{l}. A strategy s ′ j |h t that agrees with s j |h t except at date t consists in Hiding at t instead of Passing On. If period t = T , then player j has no interest in such a deviation as the game would end at T with no winner instead of ending at T with player l winning. If period t < T , then at time t + 1 after player j's deviation, we have K(h t+1 ) = {j, l} and k(h t+1 ) = 2 which implies that k(h t+1 ) -2 = 0. Since t < T , we have Tt = T -(t + 1) + 1 > 0 = k(h t+1 ) -2. As a consequence, following (s i |h t ) i∈N in the subgame that starts at t + 1 after player j's deviation, every agent i = j Hides and player j Passes On. It follows that player l is still the unique winner but at time t + 1 instead of t : if player j deviates, he then receives δ t instead of δ t-1 . Conditional on h t reached, we conclude that no player i ∈ N has a strict interest in unilaterally deviating from s i |h t at time t only.

Finally, consider a subgame Γ(N, g complete , T )|h t with h t such that Tt + 1 ≤ k(h t ) -2. Following (s i |h t ) i∈N , the action profile (a t i ) i∈N is such that, for every i ∈ N ,

a t i = H. Therefore, we get k(h t+1 ) = k(h t ). Since T -t + 1 ≤ k(h t ) -2, we have T -(t + 1) + 1 ≤ k(h t+1
). As a consequence, following (s i |h t ) i∈N in Γ(N, g complete , T )|h t , we have that for every i ∈ N , a t+1 i = H yiedling k(h t+2 ) = k(h t+1 ). The same reasoning applies for every t ′ ∈ [t + 2, T ] meaning that following (s i |h t ) i∈N , the game Γ(N, g complete , T )|h t ends at T with no winner. As mentioned in the previous paragraph, in Γ(N, g complete , T )|h t , players i ∈ K(h t ) have no strict interest in deviating from s i |h t at t. For a player i ∈ K(h t ), a strategy s ′ i |h t that agrees with s i |h t except at date t consists in Passing On at t instead of Hiding. If a player i Passes On at time t, we get k(

h t+1 ) = k(h t ) -1. Since h t is such that T -t + 1 ≤ k(h t ) -2, we have that T -(t + 1) + 1 ≤ k(h t ) -1 -2 = k(h t+1 ) -2.
Therefore, following (s i |h t ) i∈N in the subgame of Γ(N, g complete , T )|h t starting at t + 1 after history h t+1 , we get for every i ∈ N , a t+1 i = H. Repeating the reasoning, we get for every i ∈ N , a t+2 i = H and so until date T . Conditional on h t reached, we conclude that no player i ∈ N has a strict interest in deviating from s i |h t at time t only.

Proof of Lemma 3 : Directly from Lemmas 5 and 4.

Proof of Proposition 2 : Directly from Lemmas 1 and 3.

Equilibrium Sets of Winners

Proof of Proposition 3: Every s ∈ S W is either such that all the winners are interior agents13 or such that there is at least one exterior agent who wins. We show that if g is separable, then every s ∈ S W such that there is at least one exterior agent who wins is also such that there is at least one exterior agent who loses. We prove that if g is separable, then there exists a pair of exterior players who cannot win together.

By definition (chapter 3 in Tutte ( 2001)), if g is separable, then there exists a pair (g 1 , g 2 ) of connected subnetworks of g such that g 1 ∪ g 2 = g and g 1 ∩ g 2 is an interior agent of g, say k. Letting N 1 be the agents in g 1 and N 2 the agents in g 2 , we get N 1 ∪ N 2 = N and N 1 ∩ N 2 = {k}. From Theorem 1, there exists at least one agent in N 1 \{k} who is exterior in g 1 , say i, and at least one agent in N 2 \{k} who is exterior in g 2 , say j. It follows from the fact that g 1 \{i} is connected that (g 1 \{i}) ∪ g 2 = g 1 ∪ g 2 \{i} = g\{i} is connected14 meaning that i is exterior in g. The same is true for agent j. We show that i and j cannot win together at a date t ≤ T .

Assume that i and j win together at t meaning that, at t, player i has every item l ∈ N 2 and player j has every item l ∈ N 1 . Since k is on every path between i and j, every item l ∈ N 2 was held by k at least one period before it was held by i and every item l ∈ N 1 was held by k at least one period before it was held by j. Since N 1 ∪ N 2 = N , there was a period t ′ ≤ t -1 in which k held the n items. This contradicts the fact that i and j win together at t.

Proof of Proposition 4 : Split into the two following lemmas.

Lemma 6 In Γ(N, g complete , T ), every s ∈ S SP N E ∩ S W is such that the winner is unique.

Proof : First, we show that every s ∈ S W is either such that the winner is unique or such that there are n winners. Consider a strategy profile s ∈ S W such that the game ends with strictly more than one winner, say players i and j win together at t. Since i wins at t, i holds every item l ∈ N \{i} at that date. Since the network is complete, every agent k ∈ N also holds every item l ∈ N \{i} at t. Applying the same reasoning to j, we get that players i and j both winning at t implies n players winning at that date.

Next, we consider a strategy profile s ∈ S W such that there are n winners at t and show that s ∈ S SP N E . If n players win at t, every i ∈ N has Passed On at least at one date t ′ ≤ t. Nevertheless, since the n players have not won at t -1, at least two agents, say i and j, had not Passed On yet at time t -1 but both Pass On at t15 . Given that i Passes On at t, j has a strict interest in deviating from Passing On so that he can be the only winner at t. Lemma 7 In Γ(N, g tree , T ), every s ∈ S SP N E ∩ S W is such that the winner is unique.

Proof : We show that there does not exist a strategy profile s ∈ S SP N E ∩ S W such that a pair of players, say i and j, win together at t. The proof has three parts depending on the way i and j are linked. Recall that a tree network is such that there is a unique path between any pair of distinct agents.

1st Part : Assume that ij ∈ g tree . Let a player k be on the unique path between i and j. Since g tree is separable, one can find a pair (g 1 , g 2 ) of connected subnetworks such that g 1 ∪ g 2 = g and g 1 ∩ g 2 is the interior agent k. Using the same reasoning as in the proof of Lemma 3 with i ∈ N 1 \{k} and j ∈ N 2 \{k} 16 , we get that there does not exist a strategy profile s ∈ S W such that i and j win together at t. 2nd Part : Assume that n = 2 and ij ∈ g tree . The tree network involving 2 players is complete. From Lemma 6, every s ∈ S W ∩ S SP N E is such that the winner is unique.

3rd Part : Assume that n ≥ 3 and ij ∈ g tree . Consider a strategy profile s ∈ S W ∩ S SP N E such that i and j win together at t. In a tree with n ≥ 3 players, two connected agents are either two interior agents or one is interior and the other is exterior. Assume agent i is interior. It follows that there exists a pair (g 1 , g 2 ) of connected subnetworks such that g 1 ∪ g 2 = g and g 1 ∩ g 2 is agent i. Let N 1 be agents in g 1 and N 2 agents in g 2 and assume that j ∈ N 2 \{i}. Since players i and j do not win at t -1, they both lack at least one item at that date. Let's show that every item that agent i lacks at t -1 is held by j at that time and vice versa. We first focus on items that player j ∈ N 2 \{i} lacks at t -1 :

First case : j lacks an item k ∈ N 1 . As i is on every path between j ∈ N 2 and k ∈ N 1 , the item k must be held by i at t -1 for j to hold it at t.

Second case : j lacks an item k ∈ N 2 \{i} and j is on the unique path between k and i. Since j is on every path between k and i, if j lacks the item k at t -1, it cannot reach i at time t. This contradicts the fact that i and j win together at t.

Third case : j lacks an item k ∈ N 2 \{i} and j is not on the unique path between k and i. First, we show that network g being a tree implies that i is on the unique path between players j and k17 . We assume it is not and show that this contradicts the fact that j is not on the unique path between i and k : if i is not on the unique path between j ∈ N 2 \{i} and k ∈ N 2 \{i}, then the unique path between j and k exists within the subnetwork g 2 and therefore passes trough a player l ∈ N 2 \{i}18 . Since ji ∈ g tree and j is linked to k through l, then j is on the path between i and k. Since this path is unique by definition of a tree, j is on the unique path between k and i. We conclude that i is on the unique path between k and j. Therefore, the item k must be held by i at t -1 for j to hold it at t.

From the previous cases, we get that i and j winning at t implies that items that j lacks at time t -1 are held by i at that time. Using a symmetric reasoning19 , we get that items that i lacks at t -1 are held by j at that time. Therefore, the only way i and j can both win at t is that they both Pass On at t. If they both Pass On, each of them wins δ t-1 (1 + R

2 ). If one of the two Passes On, the other earns δ t-1 (1 + R) by Hiding. A strategy profile s ∈ S W such that two players win together at t is not in S SP N E .

Equilibrium Duration before Success

Minimal Duration

Let W (g, T )|h t denote the set of potential winners in Γ(N, g, T )|h t . Given h t , the state of players' information is such that players in W (g, T )|h t can hold the n items at a date t ≤ T when every player Passes On in every period of play in [t, T ].

Lemma 8 Consider an history h t of Γ(N, g, T ) such that there exists a player i ∈ W (g, T )|h t who has Hidden in every period t ′ ∈ [1, t -1]. There exists a continuation strategy profile s|h t that is a NE of Γ(N, g, T )|h t and such that player i is the unique winner of Γ(N, g, T ).

Proof : Let s|h t be such that i Hides in every period of play whatever the history and such that every j = i Passes On in every period of play whatever the history. Following s|h t , i is the unique winner of Γ(N, g, T ). It is straightforward to check that no player i ∈ N has a strict interest in unilaterally deviating from s|h t . . Proof of Proposition 5 : Pick a player i ∈ N such that e i (g) = r(g) and let r(g) = r. Consider a strategy profile s ∈ S that results in a final history h r+1 = (a 1 , . . . , a r ) such that, for every date t ≤ r, a t i = H and, for every j = i, a t j = P . Following s, player i wins at t = r. Let's prove that s ∈ S SP N E by showing that s satisfies the one-stage deviation principle. We consider three types of histories h t : First, consider an history h t = (a 1 , . . . , a t-1 ) with t -1 ≤ r that describes the same actions as h r+1 for every i ∈ N and every date t ′ ≤ t -1. Conditional on h t reached, player i has no strict interest in unilaterally deviating from s i |h t as being the unique winner at date r is player i's best possible outcome. Next, consider a player j = i who unilaterally deviates from s j |h t at t and the resulting history h t+1 . Sticking to s i |h t , player i Hides at t meaning that h t+1 is such that i has never Passed On in t ′ ∈ [1, t]. Player j's deviation at t consists in Hiding instead of Passing On, which can have two distinct effects on W (g, t)|h t+1 :

In case i ∈ W (g, T )|h t+1 , it follows from Lemma 8 that s can be constructed so that s|h t+1 is a NE of Γ(N, g, T )|h t+1 such that i is still the unique winner at a date t ≥ r. Player j has therefore no strict interest in deviating from s j |h t at t.

In case i ∈ W (g, T )|h t+1 , player i is excluded from potential winners of Γ(N, g, T )|h t+1 by the fact that player j Hides at t. If this single deviation from s prevents i from winning, it must be that d ij (g) > Tt, with (Tt) the number of remaining periods of play after date t. Conditional on h t+1 reached, player i has never Passed On in t ′ ∈ [1, t]. It follows from d ij (g) > Tt that j cannot hold the item i at a date t ∈ [t + 1, T ]. Therefore, player j cannot win. Since player i is the player with the smallest eccentricity, there is no other player k = i, j who can win at a date t < r. Player j has therefore no strict interest in deviating from s j |h t at time t.

Next, an history h t = (a 1 , . . . , a t-1 ) with t -1 ≥ r + 1 that describes the same actions as h r+1 for every i ∈ N and every t ′ ∈ [1, r] is never reached as Γ(n, g, T ) ends at date r. Finally, for any other history h t , s can be constructed so that s|h t is a NE of Γ(N, g, T )|h t .

Maximal Duration

Proof of Proposition 8 is by induction. As in section 7.1.1, we fix n and consider games Γ(N, g, T ), augmented games Γ(N ′ , g ′ , T ), and modified augmented games Γ(N ′ , g ′ , T ).

Let two games Γ(N, g, T ) and Γ(N ′ , g ′ , T ) form a complete pair (respectively a separable pair ) if the two connected networks g and g ′ are such that g = g ′ \{n + 1} with g and g ′ two complete networks (respectively two separable networks). Given either Γ(N, g, T ) with g complete or Γ(N ′ , g ′ , T ) with g ′ complete, one can always construct a complete pair. Indeed, a complete g ′ is built from a complete g by linking agent (n + 1) to every agent in g. Since g ′ is complete, agent (n + 1) is exterior in g ′ . A complete g is built from a complete g ′ by removing agent (n + 1) and all its links. Given either Γ(N, g, T ) with g separable or Γ(N ′ , g ′ , T ) with g ′ separable, one can always construct a separable pair. Indeed, a separable g ′ is built from a separable g by linking agent (n + 1) only to agent n20 . Since agent (n + 1) has a unique neighbor in g ′ , he is exterior in g ′ . A separable g is built from a separable g ′ by removing the exterior agent (n + 1) and all its links21 . The sets of strategy profiles such that the games Γ(N ′ , g ′ , T ) and Γ(N ′ , g ′ , T ) end up with a winner at a date t ≤ n (at date t ≥ n + 1, resp.) are denoted S ′ end≤n and S′ end≤n respectively (S end≥n+1 and S′ end≥n+1 , resp.). To prove Proposition 8, we use:

Lemma 9 For every complete or separable pair of games Γ(N, g, T ) and Γ(N ′ , g ′ , T ), we have: if S SP N E ⊆ S ≤n-1 , then S′ SP N E ⊆ S′ end≤n ′ -1 .

Proof : Similar to Lemma 2.

Proof of Proposition 8 : From Proposition 6, Proposition 8 is true for n = 2. From Proposition 7, Proposition 8 is true for n = 3. We assume that Proposition 8 is true for n agents and we prove that it stays true for n + 1 agents : we let Γ(N ′ , g ′ , T + 1) be such that T + 1 ≥ n. If g ′ is either separable or complete, then S ′ SP N E ⊆ S ′ end≤n . From Corollary 1, we have that if g ′ is either separable or complete, every s ′ ∈ S ′ SP N E is such that there is one exterior agent in g ′ who loses. First, in Γ(N ′ , g ′ , T + 1), we consider a strategy profile s ′ ∈ S ′

SP N E such that player (n + 1) loses and such that a ′1 n+1 = P . By definition of SPNE, the profile of continuation strategy (s ′ i |h ′2 ) i∈N ′ is a SPNE of the subgame Γ(N ′ , g ′ , T + 1)|h ′2 with h ′2 = ((a ′1 i ) i∈N , P ). This subgame is equivalent to the augmented modified game Γ(N ′ , g ′ , T ) in the same sense as in the proof of Lemma 1. By assumption, if g is separable or complete, then S SP N E ⊆ S end≤n-1 . Given Γ(N ′ , g ′ , T ), we can find a game Γ(N, g, T ) to get a complete or separable pair and then deduce from lemma 9 that S′ SP N E ⊆ S′ end≤n-1 . Therefore, (s

′ i |h ′2 ) i∈N ′ ∈ S′ SP N E implies (s ′ i |h ′2 ) i∈N ′ ∈ S′ end≤n-1 which implies s ′ = ((s ′1 i (h ′1 )), (s ′ i |h ′2 )) i∈N ′ ∈ S ′ end≤n .
Next, in Γ(N ′ , g ′ , T + 1), we consider a strategy profile s ′ ∈ S ′

SP N E such that player (n + 1) loses and such that a ′1 n+1 = H. By definition of SPNE, the profile of continuation strategy (s ′ i |h ′2 ) i∈N ′ is a SPNE of Γ(N ′ , g ′ , T + 1)|h ′2 with h ′2 = ((a ′1 i ) i∈N , H). As shown in the previous paragraph, if g is separable or complete, then every SPNE played in a subgame Γ(N ′ , g ′ , T + 1)|h ′2 that starts after an history h ′2 = ((a ′1 i ) i∈N , P ) is such that the game Γ(N ′ , g ′ , T + 1) ends up with a winner different from player (n + 1) at a time t ≤ n. Therefore, if we assume that s ′ ∈ S ′ end≥n+1 , then the separability or completeness of g ′ implies that player (n + 1) has an interest in deviating from s ′ n+1 such that a ′1 n+1 = H to a strategy s ′′ n+1 such that a ′′1 n+1 = P . Such a deviation would not make player (n + 1) win but make him loose at t ≤ n instead of t ≥ n + 1. This profitable deviation in the first period of play contradicts s ′ ∈ S ′

SP N E which is why s ′ ∈ S ′ end≥n+1 . Proof is completed by noting that every s ′ ∈ S ′ SP N E is either such that a ′1 n+1 = H or such that a ′1 n+1 = P .

Figure 1 :

 1 Figure 1: Informational situations once player 1 has Passed On and players 2 and 3 have Hidden.

Figure 2 :

 2 Figure 2: Two informational situations at the end of time t = 1.

Document de Travail du Centre d'Economie de laSorbonne -2009.11

Ignoring strategic aspects, the impact of the communication structure on group performance is the object of a vaste literature in social psychology mainly based on[START_REF] Bavelas | Communication Patterns in Task-Oriented Groups[END_REF] and[START_REF] Leavitt | Some Effects of Certain Communication Patterns on Group Performance[END_REF].

Document de Travail du Centre d'Economie de laSorbonne -2009.11

A network is connected if there exists a path between any pair of distinct agents. A path is a sequence of agents for which every agent is linked to the next agent in the sequence.

Document de Travail du Centre d'Economie de laSorbonne -2009.11

Each finite game Γ(N, g, T ) contains subgames that are uniquely defined by each history h t and denoted Γ(N, g, T )|h t . The strategy profile s ∈ S is a SPNE if, for every h t ∈ H t , the continuation strategy profile denoted s|h t is a NE of Γ(N, g, T )|h t . 7 Document de Travail du Centre d'Economie de laSorbonne -2009.11

On Figure1, players' labels correspond to numbers written above the line. Every player i's informational situation is represented by three boxes numbered 1,2 and 3 and situated near player i : box numbered j near player i is filled in black if player i holds the item j and is empty otherwise. 10 Document de Travail du Centre d'Economie de laSorbonne -2009.11

Indeed, if a game ends up with at least a winner at time t ≤ T , then the aggregate payoffs are equal to δ t-1 (n+R).

For instance, see[START_REF] Buckley | Facility Location Problems[END_REF] in which the eccentricity measure is used to define and find the center of a tree network. More generally, see network location theory that addresses the question of the optimal location of a single-point facility in a graph.

Note that we have ṽ′t ij ≥ v t ij and not ṽ′t ij = v t ij because we do not exclude that the initial matrix Ṽ ′0 of players' information in Γ(N ′ , g ′ , T ) is such that there exists a pair of players i, j ∈ N , i = j such that ṽ′0 ij = 1 whereas this is excluded for the initial matrix of players' information V 0 = Idn of Γ(N, g, T ).

See one-stage deviation principle for finite horizon games inFudenberg and Tirole (1991)[pp 108-110].

If a player i ∈ K(h t ) Passes On at time t, then i ∈ K(h t+1 ) since g is complete meaning that Ni(g complete ) = N \{i} for every i ∈ N .

This is due to the fact that, in g complete , a Passed On item immediately reaches every player.

Using Theorem 1, it is obvious that if all the winners are interior agents, there is at least one exterior agent who loses.19Document de Travail du Centre d'Economie de laSorbonne -2009.11

The union of two connected networks is a connected network (Chapter 1 in[START_REF] Tutte | Graph Theory[END_REF]).

If there is a unique i who has not Passed On yet at time t -1, then player i is the unique winner at time t -1.

The difference is that i is not necessarily exterior in g1 and j is not necessarily exterior in g2.20Document de Travail du Centre d'Economie de laSorbonne -2009.11

Note that this cannot be deduced from g's decomposition into g1 and g2 as k and j both belong to N2.

Note that, by definition of the split of the network g into networks g1 and g2, the unique path between j and k cannot go through an agent l in N1\{i} without going through player i since i is on every path between players from the sets N1\{i} and N2\{i}.

When focusing on items that player i ∈ N1\{j} lacks at t -1, we also distinguish three cases. The case in which i lacks an item k ∈ N1\{i} is similar to the previous Second case. The case in which i lacks an item k ∈ N2\{i} and j is on the unique path between k and i is similar to the previous First case. The case in which i lacks an item k ∈ N2\{i} and j is not on the unique path between k and i is similar to the previous Third case.

An interior agent in g is still interior in g ′ .

An interior agent in g ′ is still interior in g.

Focusing on such individual effects is left for further research.

Appendix

For every proposition presented in a previous section, the proof is given in a subsection of the Appendix entitled as the section. We denote Γ(N, g, T )|h t the subgame of Γ(N, g, T ) that starts at time t ≤ T after history h t . Player i's continuation strategy after history h t is denoted s i |h t .

7.1 Success or Failure in Equilibrium

Proof of Lemma 1 is by induction: assume it is true for n players and show it stays true for n + 1. To do so, fix n and consider three kinds of games. First, games Γ(N, g, T ) with |N | = n. Next, augmented games Γ(N ′ , g ′ , T ) with |N ′ | = n + 1. Without loss of generality, let player (n + 1) be in N n (g ′ ) and be exterior in g ′ . Finally, augmented modified games Γ(N ′ , g ′ , T ) that differ from augmented games only in that the initial matrix of information Ṽ ′0 = Id n+1 is such that, for every i ∈ N ′ , we have ṽ′0

ii = 1 and such that ṽ′0 n n+1 = 1 meaning that player n initially holds the item (n + 1).

Let two games Γ(N, g, T ) and Γ(N ′ , g ′ , T ) form a pair if the two connected networks g and g ′ are such that g = g ′ \{n + 1}. Given either Γ(N, g, T ) or Γ(N ′ , g ′ , T ) only, one can always construct a pair. Indeed, a connected g ′ is built from a connected g by linking agent (n + 1) only to agent n. Since agent (n + 1) has a unique neighbor in g ′ , he is exterior in g ′ . A connected g is built from a connected g ′ by removing the exterior agent (n + 1) and all its links.

The sets of (SP)NE of games Γ(N ′ , g ′ , T ) and Γ(N ′ , g ′ , T ) are denoted S ′ (SP )N E and S′

respectively. The sets of strategy profiles such that games Γ(N ′ , g ′ , T ) and Γ(N ′ , g ′ , T ) end with a winner (no winner, resp.) are denoted S ′ W and S′ W respectively (S ′ L and S′ L , resp.). Before proving Lemma 1, we show: Lemma 2 For every pair of games Γ(N, g, T ) and Γ(N ′ , g ′ , T ), we have: if

Proof : Take a pair of games Γ(N, g, T ) and Γ(N ′ , g ′ , T ). We show that if there exists a strategy profile s′ in S′ SP N E ∩ S′ L , then there exists a strategy profile s in S SP N E ∩ S L . In Γ(N ′ , g ′ , T ), consider a profile s′ ∈ S′ such that player (n + 1) Hides in every period whatever the history and such that, for every player i ∈ N , player i's action at time t is independent of player (n + 1)'s actions at dates t ′ ∈ [1, t -1]. Next, in Γ(N, g, T ), consider a profile s ∈ S such that s and s′ describe, for every player i ∈ N and every date t ≤ T , the same action profile in games Γ(N, g, T ) and Γ(N ′ , g ′ , T ) respectively.

Considering the process of items' transmission given by (1), it is easy to show that the sequences (V 0 , ...V T ) and ( Ṽ ′0 , ..., Ṽ ′T ) determined by s and s′ in Γ(N, g, T ) and Γ(N ′ , g ′ , T ) respectively are