Mohamed Belhaj
email: mbelhaj@ec-marseille.fr

Sebastian Bervoets
email: sebastian.bervoets@univ-amu.fr

Frédéric Deroïan
email: frederic.deroian@univ-amu.fr.

Network Design under Local Complementarities *

Keywords: Network, Linear Interaction, Bonacich Centralities, Strategic Complementarity, Nested Split Graphs. JEL: C72, D85

We consider agents playing a linear network game with strategic complementarities. We analyse the problem of a policy maker who can change the structure of the network in order to increase the aggregate efforts of the individuals and/or the sum of their utilities, given that the number of links of the network has to remain fixed. We identify some link reallocations that guarantee an improvement of aggregate efforts and/or aggregate utilities. With this comparative statics exercise, we then prove that the networks maximising both aggregate outcomes (efforts and utilities) belong to the class of Nested-Split Graphs.

Introduction

In games played on networks, individuals' level of action as well as the utility they derive from this action directly depend on the structure of the network. In such a context, a natural question then arises, as to know how a policy maker can impact on aggregate outcomes (actions and/or utilities) by affecting the structure of the network. In this paper, we consider games with three main ingredients. First, the interactions between individuals are local, as agents only interact with their neighbours. Second, actions are strategic complements, so more action by others is assumed to make action more attractive for an individual. Third, best-replies are assumed to be linear in neighbours' actions 1 . Given the actions played by agents on the network, we focus on two related issues. First, we analyse how a policy maker can improve on an existing network by reallocating some of its links. This can be thought of as a comparative static exercise on networks with a fixed number of links. Second, we examine which networks should be built up by a policy maker maximising either aggregate actions (the network will be said to be optimal) or the sum of utilities (the network will be said to be efficient), under the constraint that the total number of links on the network is bounded from above. This limitation can come, for instance, from a limited budget constraint.

Answers to the two questions we address provide useful insights on several issues. First, designing a network, by either building it up or by modifying it when it already exists, appears to be a natural public policy tool. Although many studies document that peer effects should be accounted for in the design of public policies, there is no existing analysis providing the details of precise linking arrangements that should be made. Our aim is to provide such an analysis. Second, the identification of efficient network architectures serves as a natural benchmark to the evaluation of the level of organisational inefficiency of observed networks. Understanding how far a network is from optimality or efficiency is an important issue. Third, this analysis brings some insights on the mechanisms through which complementarities can be exploited by a social planner. In particular we will show that what leads to improvements in the network is the accumulation of links around some subset of agents, and we will illustrate how this accumulation process can be implemented in different ways. Last, we believe that our analysis puts forward some technical advances that can be useful to the social network theory.

The linear interaction setting has been widely used in the growing network literature because it offers an appropriate approximation of a wide range of social and economic phenomena, such as education decisions, crime, technology adoption, R & D races etc. In addition, a by-know well-known Nash-Bonacich linkage has been identified in this setting [START_REF] Ballester | Who's who in networks. Wanted: the key player[END_REF], a linkage that we will use to tackle the issue of network design. For that purpose, we focus on levels of interaction that guarantee that equilibrium efforts (resp. utilities) are well-defined and given by the Bonacich centralities (resp. the square of the Bonacich centralities) of the agents on the network. The Bonacich centrality measure is a discounted sum2 of every possible path of any length in the network. Therefore, comparing aggregate outcomes in two different networks is a serious challenge, because it implies the comparison of an infinite number of path. This gives rise to non-trivial trade-offs, where a network can dominate another network on some given path length while being dominated on another given path length.

We start our analysis by addressing the first question of modifying an existing network. We try to find a reallocation of links that systematically guarantees an increase of aggregate efforts and aggregate utilities. Although computing the net effects of reallocating links is tedious, because of the complicated trade-offs mentioned above, we identify a specific reallocation for which the net effects can be summarised into a tractable formula. We call it a single-switch (S-switch). It is such that an agent deletes a link and re-creates it with another agent exerting a higher effort than the initial neighbour. As we illustrate in our exposition, the impact of a single-switch on aggregate efforts is ambiguous. Indeed, if the direct effect of the single link reallocation intuitively goes in the appropriate direction, it can be overwhelmed by feedback effects. However, we show that it guarantees a systematic increase of aggregate efforts, whatever the initial network and for any admissible level of interaction. To prove our statement, we first notice that the matrix which serves to compute the Bonacich centralities is an inverse M-matrix. We then use recent advances in the theory of M-matrices in order to sign the net effects of the single-switch. In particular, we use some powerful properties on the sign of some of the principal minors of M-matrices.

The single-switch previously identified does not guarantee an increase of aggregate utilities. We exhibit a 25 players example such that aggregate utilities decrease after a singleswitch. This is due to the quadratic properties of utilities which force us to account for the distribution of the agents' effort levels. Fortunately, we identify another type of reallocation which guarantees a systematic increase in both aggregate efforts and aggregate utilities. This reallocation involves potentially more than three players, and many links, we call it a neighbourhood-switch (N-switch). This reallocation is again local: every neighbour of an agent with low centrality deletes his link to this agent and re-creates it to another agent with higher centrality. The proof of this result relies on a Simultaneous Best-Response Algorithm (SBRA).

From a public policy perspective, a natural question arises, as to know whether these reallocations can be decentralised. We show that in an S-switch, the agent involved in the replacement of the link often ends up being worse off. So unless there are complex transfers taking place on the network, S-switches cannot be decentralised. On the contrary, an N-switch insures that every agent is better off, except for the one whose links have been deleted. No transfers need to be made, but the policy maker should necessarily encourage a complex coordination between agents.

Both results, with single and multiple-switches, allow us to answer the second question of building up a network. Indeed, these results imply that both the optimal and the efficient networks have to be Nested-Split Graphs (NSG). These graphs have been long studied in mathematics (see for instance Madahev and Peled (1995) for an overview), but have only recently been identified in economics (to the best of our knowledge, [START_REF] König | A dynamic model of network formation with strategic interactions[END_REF] is the only other contribution in economics on NSG). A NSG is a hierarchical structure such that the neighbourhood of an agent with low centrality is a subset of the neighbourhood of another agent with higher centrality (neighbourhoods are nested). This property imposes a lot of structure on the possible set of optimal or efficient networks. The nested structure results from the accumulation of links around a subset of very central agents 3 . This accumulation principle makes NSG naturally desirable when maximising aggregate outcomes, in a context of complementarities in efforts.

We check that optimal and efficient networks still belong to the class of NSG under several variations of the model. In particular, if we allow for heterogeneous individual characteristics, if the social planner weighs individuals differently, or if he restricts to the subclass of connected networks, we show that the class of NSG still contains the best networks. We also explore the introduction of non linear interactions. We find that if best-responses are convex with moderate slope, then the best networks are still NSG, while they might not be in that class if best-responses are concave.

Even though the class of NSG is very small compared to the total number of graphs4 , we would like to push the analysis further and identify the unique optimal and efficient network structures. This is a difficult exercise, mainly for two reasons. First, once we are in the class of NSG, any link reallocation implies that a highly central agent looses a link at the benefit of a less central agent. In this case, the direct effects are negative and even though the indirect effects may be positive, the sign of net effects depends both on the interaction level and on the specific organisation of every agent in the network. This makes the analysis intractable. Second, many NSG can only be improved by a multiple reallocation of links. This reinforces the difficulty of the first problem.

Still, we provide some results for specific values of interaction levels. For interaction levels close to the maximal admissible value 5 , we show that the optimal network is the network with the highest largest eigenvalue (also called the index of the network). The problem of finding the network with maximal index, among all networks with a fixed number of links, has been solved by [START_REF] Rowlinson | On the maximal index of graphs with a prescribed number of edges[END_REF]. As a corollary of Rowlinson's result, the optimal network is also the efficient network, and it is given by a unique architecture named the Quasi-Complete network. This architecture is built by accumulating links around a subset of agents, so as to create the biggest possible complete component. This implies that in optimal and efficient networks, many agents are isolated.

For interaction levels close to zero, we show that the optimal and the efficient network are given by the graph maximising the sum of the square of the degrees of the network. It turns out that the problem of finding, among all networks with a fixed number of links, the network with maximal sum of squares of degrees, has a long tradition in mathematics. This problem has been solved very recently in graph theory by [START_REF] Abrego | Sum of Squares of Degrees in a Graph[END_REF], who show that only six architectures can maximize this quantity. Using these results and discriminating between these possible networks, we conclude that only two architectures can be optimal and efficient, depending on the number of links in the network. For low link density, the best organization is given by the Quasi-star network structure. This architecture is built by forming a star network, in which a central agent is involved in as many links as possible. If some links are left to be attributed, a second central agent is formed, and so on. On the contrary, when link density is high, the best organization is given by the Quasi-complete network.

For general levels of interaction, we resort to numerical simulations. We observe that the Quasi-Star and the Quasi-Complete networks are very often the dominant structures, but this is not always true. Counter examples are, however, quite sophisticated. The issue of finding the optimal or efficient architecture, as a function of the interaction level and link density, stays an open issue.

Related literature. Since the seminal contributions of [START_REF] Jackson | A strategic model of social and economic networks[END_REF] and [START_REF] Bala | A noncooperative model of network formation[END_REF], the issue of finding efficient networks has been analysed in the context of network formation games. The questions we address in this paper are different in two essential respects. First, in the strategic network formation games, individuals derive some utility from their connections. The strategy space is the set of possible links an individual can form. In the setting we analyse, individuals do not derive utility from their connections, rather their derive utility from their actions and those of their neighbours. Therefore the connections matter, not because they shape utilities but because they shape actions. Second, we do not ask whether links are sustainable or not, we assume that they are given and can only be modified by the policy maker. Hence it is a problem of network design we are focusing on, and not a problem of network stability, contrary to the aforementioned papers.

Next, in the recent developments of social network theory, some papers have focused on models with linear interactions on endogenous networks, on which agents choose an action from which they derive utility. In [START_REF] Goyal | R&D networks[END_REF], the authors analyse interfirm collaboration in R & D activity. They restrict their attention to regular networks (i.e. such that every firm has the same number k of neighbours) and derive the number k which maximises social welfare. In Cabralès et al. (2011), the authors do not consider nominal networks, but a general socialising level which is chosen by individuals at the same time as productive investments. They show that two Nash equilibria coexist which can be Pareto ranked, and that the efficient socialisation level should be somewhere in between the two Nash equilibria. Finally, in [START_REF] Galeotti | The law of the few[END_REF], the authors focus on games where actions are strategic substitutes and provide an analysis of efficient networks. They show that either the star network or the empty network are efficient. Our contribution differs from these papers in several aspects. First, we consider networks in which the identity of the neighbours matter, and we do not restrict to regular networks. We also focus on games with strategic complements. Second, we impose the constraint that the number of links in the network should be fixed, which radically changes the analysis. And third, we provide a full-fledged comparative static analysis.

A problem similar to ours has been recently introduced in [START_REF] Corbo | A study of Nash equilibrium in contribution games for peer-to-peer networks[END_REF]. In that paper the authors analyse the same game as we do and also look for optimal and efficient networks. They restrict their attention to connected graphs and show that, when the level of interaction tends to its upper bound, and when the number of links is equal to n -1, the star is the unique connected network maximizing both aggregate efforts and utilities. Our paper actually takes the analysis further, because we do not impose any restriction on the number of links we just assume it is fixed), we do not restrict to connected graphs, and we examine every possible level of interaction.

Our results shed light on the class of Nested-Split Graphs. Two other close papers also focus on NSG. First, Konig et al. (2012) investigate R&D collaborations in a model with spillovers along network lines. They show that the efficient network structure depends on the marginal cost of collaborations, and in particular, the efficient network is asymmetric and has a nested structure when cost is high. Further, [START_REF] König | A dynamic model of network formation with strategic interactions[END_REF] explore in details the topological properties of NSG, which they find to be stable graphs of a dynamic, noncooperative network formation game in which the individuals have the same utility functions as in this paper. Our paper analyses network design issues instead of strategic incentives to link formation and we show that NSG also have desirable properties from this perspective. As a by-product, we illustrate how the results they obtain are tied to the specific link formation protocol they consider.

Last, there is a large literature examining the design of optimal communication structures in teams and organizations, where the objective is the efficiency of information transmission. Building on [START_REF] Marshak | The Economic Theory of Teams[END_REF], an extensive literature analyses the optimal inner structure of an organization. Sah and Stiglitz (1987) compare two different organizational structures, polyarchies and hierarchies, and their respective benefits in reducing errors during the processing of information. [START_REF] Radner | The Organization of Decentralized Information Processing[END_REF], [START_REF] Bolton | The Firm as a Communication Network[END_REF] and [START_REF] Garicano | Hierarchies and the organization of knowledge in production[END_REF] further stress the importance of hierarchical structures in to decreasing the costs of processing information. In this tradition, the closest paper to ours is Calvó-Armengol and Marti (2008), who explore information aggregation and communication in a team context. They compare the performance of networks with fixed number of links (the four player, four links kite and wheel ). Recently, Renou and Tomala (2012) study a mechanism design model where the players and the designer are nodes in a communication network and the objective is to get information from the players to the designer. They show how some properties on the connectedness of the (directed) network relate to the implementability of incentive compatible social choice functions. Although in their spirit these papers share common features with this one, our model is not concerned with information transmission and the network does not represent a communication channel. Rather, networks in our setting represent a channel for peer effects. Further, we assume complete information. And again, we provide a detailed comparative statics exercise which cannot be found in these papers.

The rest of the paper is organized as follows. Section 2 introduces the model and the formal questions we address. Next we analyse in section 3 the problem of modifying an existing network. We identify the S-switch as a systematic reallocation that guarantees an increase in aggregated efforts, and the N-switch that also guarantees an increase in aggregated utilities.

In section 4 we address the problem of building an entire network with a given number of links. We show that the optimal and efficient networks belong to the class of Nested-Split Graphs and we push the analysis further by trying to identify the unique best architecture. We present results for low and high levels of interactions, and we conclude the section by some numerical simulations which show that the problem in the general case is far from trivial. We discuss in section 5 the robustness of our results to two assumptions: we first examine the additional constraint of connectedness (no agent should be isolated), second we relax linearity of best-responses. Section 6 concludes. All proofs and figures can be found in the Appendix.

The model

We consider a fixed and finite set of agents N = {1, 2, • • • , n} who interact on a network and choose some action or effort. For instance, agents may represent firms engaged in R&D innovation or students in a friendship network at school. An agent's payoff is determined both by his action and by the action of the agents he is linked to.

The Network

A network is a collection of binary relationships, represented by an adjacency matrix G = [g ij ] where g ij = 1 when there is a link between agents i and j, and g ij = 0 otherwise. We restrict our attention to undirected networks, i.e. g ij = g ji , and assume that g ii = 0. By abuse of notation, G will alternatively stand for the network or its adjacency matrix. When g ij = 1 (resp. g ij = 0) we will say ij ∈ G (resp. ij / ∈ G). A network G with an additional link ij (resp. with deletion of link ij) will be denoted G + ij (resp. G -ij). We let deg(i, G) denote the number of neighbours of agent i in the network G. A component is defined as a set of individuals such that there is a path between every pair of individuals belonging to the component and there is no path between individuals inside the component and individuals outside the component. A component is said to be non trivial if it contains strictly more than one agent. Let G(l) denote the set of all networks with l links (0 ≤ l ≤ n(n-1)

2

). Finally denote by µ(G) the largest eigenvalue (or the index) of the adjacency matrix G.

Payoffs, equilibrium and the planner's objective

Individual i chooses some action x i ∈ R + which measures for instance the effort he invests into education or his contribution to R&D activities. Let X ∈ R n + be the profile of individual efforts and x -i denotes the actions of all agents other than i. We consider a standard linear quadratic utility function with local synergies as in [START_REF] Ballester | Who's who in networks. Wanted: the key player[END_REF]. It is formed of an idiosyncratic component resulting from own effort and a local interaction term which reflects strategic complementarities.

u i (x i , x -i ) = a i x i - 1 2 x 2 i + δ n j=1 g ij x i x j
where δ > 0 measures the intensity of interactions between agents and a i > 0 measures agent i's private return to effort. The interaction term can be interpreted as affecting either the cost of or the return to effort. We assume a i = 1 in the remainder (we discuss in section 5 how our results generalise to heterogeneous a i 's).

In such games with fixed N and G, a (pure) Nash equilibrium X * satisfies the following first order conditions:

(I -δG)X * = 1

Because interactions are strategic complements and best-responses are linear, too high intensity of interactions would induce infinite efforts. In order to guarantee that Nash equilibrium efforts are finite on the network G, we assume that δµ(G) < 1 6 . Then the inverse matrix M = (I -δG) -1 is non-negative and the linear system admits a unique solution. It is by know well-known that this solution coincides with the Bonacich centralities of individuals (Bonacich, 1987), i.e.

X * = B(G, δ) = +∞ k=0 δ k G k 1
Individual i's Bonacich centrality can be interpreted as the weighted sum of paths of any length starting from agent i in the network G:

b i (G, δ) = +∞ k=0 δ k P k (i, G)
where P k (i, G) is the number of paths of length k, including loops, starting from agent i.

The aggregate effort in such a game is given by the sum of all Bonacich centralities while aggregate utilities are given by the sum of the squares of all Bonacich centralities.

Remark 1. Although we focus on this standard game for simplicity, linear first-order conditions such as in condition (1) can come from various utility functions. For instance linear benefits and convex costs, decreasing with local interactions, would lead to condition [START_REF] Abrego | Sum of Squares of Degrees in a Graph[END_REF]. So does a Cobb-Douglas payoff function. In the particular game we present here, utilities at equilibrium are given by the square of equilibrium efforts. This is not true for other utility functions.

We consider two related problems: First, we analyse the problem of a planner who wants to modify an existing network by reallocating some of its links in order to increase either aggregate efforts or aggregate utilities. Second, we investigate the problem of a planner who wants to build a network given a fixed number of links, with the maximisation of aggregate outcomes in mind 7 .

Of course, because equilibrium efforts depend on weighted sums of paths of different lengths in a network, comparing two networks in terms of their equilibrium reveals a difficult exercise. Indeed, when changing only one link of a network G, an infinite number of paths between potentially every pair of individuals are modified. Net effects of network perturbations must keep track of all these modifications.

Interaction levels and some network architectures

We restrict our attention to interaction levels such that existence is guaranteed for every network in G(l). Define µ max (l) as the largest index among all networks with l links and define accordingly δ max (l) = 1/µ max (l). Admissible interaction intensities are all δ in [0, δ max (l)[. Before turning to the analysis, we define the class of Nested Split Graphs (NSG), as well as two specific members of this class, which will play a prominent role. NSG were first introduced in graph theory by [START_REF] Chvatal | Aggregation of inequalities in integer programming[END_REF] as threshold graphs. They propose several equivalent definitions, among which the following:

Definition 1 (Nested Split Graph). A graph G is called a nested split graph if [ij ∈ G and deg(k, G) ≥ deg(j, G)] =⇒ ik ∈ G
This definition is not standard in the graph theory literature, but it is, in our context, the simplest to use. NSG can be described as networks in which individuals' neighbourhoods are nested one into the other. In particular, individuals can be partitioned into k classes, such that:

1-two individuals in the same class have the same degree 2-individuals in class i are linked to every individual in classes 1 to k -i + 1 Out of many interesting properties (see for instance [START_REF] König | A dynamic model of network formation with strategic interactions[END_REF] for an extensive analysis of the properties of NSG), we stress the four following. First, any NSG has at most one non trivial component, which is of diameter two. Individuals who are not in the component are isolated. Second, individuals are ordered by degrees. Class 1 individuals have degree n C -1 (where n C is the size of the non trivial component) and as the class number increases, degree decreases. Third, the set of agents belonging to the first E[ k+1 2 ] classes form a complete subgraph (also called a clique). Last, the Bonacich centrality ranking of individuals is aligned with the degree ranking. Figure 1 presents a NSG with 10 agents and 5 classes (doted circles represent classes).

We define two specific members of the class of NSG which are of special interest for our analysis. Let K p denote a complete subgraph with p agents.

Definition 2 (Quasi-complete graph). A graph G ∈ G(l) is called a Quasi-complete graph, noted QC(l), if it contains K p with p(p-1) 2 ≤ l < p(p+1)

2

, and the remaining l -p(p-1) 2 links are set between one other individual and agents in K p .

In a Quasi-complete graph there is either a unique class of agents when l = p(p-1)

2

, or three. Figure 2 presents some Quasi-complete graphs.

Definition 3 (Quasi-star graph). A graph G ∈ G(l) is called a Quasi-star graph, noted QS(l), if it has a set of p central agents with n -1 links, and the remaining l -p(n -1) links are set in order to construct another central agent.

A Quasi-star graph contains two, three or four classes of agents. Figure 3 presents some Quasi-star graphs. 8

Improving on existing networks

In this section we consider a policy maker who has the discretion to modify given network by reallocating some of its links, in order to improve the aggregate outcomes. Obviously, if the policy maker could add some new links to the network, this would unambiguously, but trivially, increase efforts and utilities of every agent. This is because the number of paths in the network would strictly increase. Here we assume that the number of links has to remain constant.

Improving aggregate effort

Single link reallocations can lead to counter intuitive results. For instance, Figure 4 shows that severing a link between two highly central agents i and j and allocating it between two other less central agents k and l can increase aggregate efforts. This is because the slightest modification of a network induces complicated changes. When reallocating a link in a network, an infinite number of paths are modified and every agent in the network is impacted. These indirect effects often lead to counter intuitive results and hence, understanding the net effects on the aggregate outcomes is challenging. Fortunately, we can express the variation of aggregate efforts induced by a replacement of a link ij by a link kl, as a function of these four individuals' centralities only. We rely on the following lemma:

Lemma 1. Let G be a network such that ij ∈ G and kl / ∈ G and let G = G -ij + kl.
Then the variation of the sum of Bonacich centralities between G and G only depends on individuals i, j, k and l. In particular,

B .1 -B.1 = δ[b k b l + b k b l -b i b j -b i b j ] ( 2
)
where B is the vector of Bonacich centralities after the reallocation.

The sign of equation ( 2) is in general ambiguous. However, we identify a specific reallocation which guarantees a systematic increase of aggregate efforts. This reallocation consists of switching a link between agents i and j with a link between i and k, whenever k is at least as central as j. We call this reallocation an S-switch.

Definition 4 (S-switch). Assume agents i, j and k are such that ij ∈ G, ik / ∈ G, and

b k (G, δ) ≥ b j (G, δ). An S-switch is a link reallocation such that G = G + ik -ij.
A typical S-switch is shown in Figure 5. It is a single link switch, and it only involves three individuals. After an S-switch from ij to ik, we get from equation ( 2 Theorem 1 holds for any network, independently from its structure, and for any admissible level of interactions. It is surprising that the overall feedback effects always go in the same direction and indeed, it is difficult to prove. The sketch of the proof of Theorem 1 is as follows. First, equation ( 2) adapted to an S-switch gives the net effect on aggregate efforts. We need to show that this quantity is positive. In order to do that, we express it as a function of elements of the matrix (I -δG) -1 which gives the Bonacich centralities. We then notice that this matrix is an inverse M -matrix. We next make an extensive use of properties of M -matrices to prove our result. In particular, we use three properties. First, M -matrices have positive principal minors. This is a consequence of the fact that the set of M -matrices is a subset of the set of P -matrices (see for instance Poole and Boullion, 1974). Second, an inverse M -matrix has the Path Product property defined as follows: if A = (a ij ) is an inverse M-matrix then a ik a jj ≥ a ij a jk [START_REF] Johnson | Path product matrices, Linear and Multilinear Algebra[END_REF]. Third, we use properties on the product of an M -matrix and an inverse M -matrix, which guarantee that in such a product there is always a nested sequence of positive principal minors [START_REF] Johnson | Matrix Classes That Generate all Matrices with Positive Determinants[END_REF]. Using these three properties as well as the Jacobi Identity, which relates the sign of a principal minor of a matrix to the sign of the corresponding principal minor of the inverse matrix, we are able to conclude that the net effect of an S-switch is positive.

) that B .1-B.1 = δ[b i (b k -b j ) + b i (b k -b j )]. All Bonacich
Three comments are in order. First, even though we are not concerned here with the cost of modifying a network, we observe that an S-switch is the least possibly costly operation, as it involves only three agents and one link. A policy maker can thus improve aggregate efforts by eventually implementing successive marginal changes to the network.

Second, although S-switches increase aggregate effort, the complex feedback effects can result in a decrease of the pivotal agent's effort and thus his utility, as illustrated in Figure 7. In this example, the initial network is the union of two disjoint communities, consisting each of a complete component with 7 agents. Thus, b j (G) = b k (G) so that the switch from link ij to ik is an S-switch. By Theorem 1, this reallocation will increase aggregate efforts, but with δ = .12, b i (G -ij + ik) -b i (G) = -.004. 9 Because this reallocation is the unique possible S-switch, this example cast doubts on the possibility of decentralising these improvements. In a general network formation game in which agents want to maximise their centrality as a way to maximise their utility, these switches will not take place without transfers between agents.

Third, the switch just identified does not guarantee an increase of the sum of utilities, as illustrated in Figure 6. In this example with 30 agents and 65 links, efforts are higher in the complete component than the effort of peripheral agents in the star, and the utility loss of agents in the complete subgraph is higher than the utility gain for agents in the star, even if aggregate effort increases.

Improving aggregate utilities

Single link reallocations do not guarantee an increase of the sum of utilities. We therefore need to resort to multiple link reallocations. Again, we would like to find a type of reallocation which would systematically work, and simple enough that it can be easily identified by a policy maker. The reallocation we suggest involves several links, but it remains local, in the sense that it only involves a specific subset of individuals. Defining N j\k (G) as the set of neighbours of j who are not neighbours of k, we define an N-switch as follows:

Definition 5 (N-switch). Assume agents j and k are such that b k (G, δ) ≥ b j (G, δ). An N-switch is a multiple link reallocation such that G = G + i∈N j\k (G) (ik -ij).
Figure 8 illustrates an N-switch. This reallocation can also be thought of as a repeated sequence of S-switches between j and k. Therefore, according to Theorem 1, N-switches guarantee an increase in aggregate efforts. However, if the sequence of S-switches leading to the corresponding N-switch does not guarantee a monotonic increase of aggregate utilities, we show that the collective reallocation does.

Theorem 2. Assume δ ∈ [0, δ max (l)[. Any N-switch increases aggregate efforts as well as aggregate utilities.

The intuition for the proof of Theorem 2 goes as follows: when reallocating links in a network, tracking down the effects on each individual is difficult because paths can be of arbitrary length. However, this specific type of reallocation guarantees that the only player who suffers from the reallocation is j, while all others benefit from k's higher centrality. Measuring how much j is hurt is not easy but the use of a Simultaneous Best-Response Algorithm (SBRA) allows us to conclude that the aggregate gains are higher than j's loss. Net effects are positive.

A policy maker can resort to N-switches to increase both the aggregate outcomes. However, he will be facing three kinds of trade-offs: First, N-switches are more complex and costly to implement than S-switches. Second, N-switches can result in the exclusion of individual j from the network. There is therefore a trade-off between the improvement of aggregate outcomes and ethical considerations such as social exclusion. Last, N-switches are such that only agent j suffers from the reallocation. Therefore, the other individuals involved in the switch are all better-off, and could very well coordinate in order to implement the improvement. The policy maker can therefore decentralise N-switches, contrary to S-switches.

Both Theorems 1 and 2 imply that links get accumulated around some highly central agents, thus exploiting the complementarities of the interactions. How this accumulation should be designed is what we analyse in the next section.

Optimal and efficient networks

In this section we assume a policy maker faces the problem of building an optimal or efficient network, given a restriction on the number of links (because of a limited budget for instance). Formally, the policy maker can face two problems:

Problem 1: Solve max G i b i (G, δ), G ∈ G(l) Problem 2: Solve max G i b 2 i (G, δ), G ∈ G(l)

A General Result

The policy maker should take into account the accumulation process alluded to in the previous section. Theorem 2 has several implications for the design of a network. We state them in a corollary and a theorem. A formal proof is skipped but the intuition is simple: assume j and k are in two separate components and are such that b j (G, δ) ≤ b k (G, δ) (as in Figure 9). An N-switch would consist of reallocating all links of j to k. This would merge the two components and exclude j from the network. According to Theorem 2, this reallocation results in an increase of both aggregate outcomes. Theorem 3. Assume δ ∈ [0, δ max (l)[. A network in G(l) maximizing aggregate effort or aggregate utilities is a Nested-Split Graph.

As mentioned before, complementarities encourage accumulation around a subset of agents. This is what NSG do, because agents in the first class of a NSG are connected to everyone else in the unique component, turning them into some (partially) central agents. This accumulation leads to very high centrality for these players, and to short distances which will guarantee strong feedback effects on other agents. Remark 2. If agents are heterogeneous, then an optimal or efficient NSG is such that b i (G, δ) > b j (G, δ) ⇐⇒ a i > a j (see proof of Theorem 3). Remark 3. If the policy maker is a weighted utilitarianist (i.e. maximises i θ i u i ), the result extends and furthermore b i (G, δ) > b j (G, δ) ⇐⇒ θ i > θ j . Indeed, it is clear that the ranking in centralities should correspond to the ranking of weights. Next, we note that on such ranked networks, N-switches will improve aggregate outcomes.

From an incentive point of view the stability of networks in the class of NSG remains an open issue. As pointed out earlier, S-switches would not be implemented and N-switches would require coordination. In a recent paper, [START_REF] König | A dynamic model of network formation with strategic interactions[END_REF] obtain the NSG as the stable outcome of a network formation game, but this result relies on the fact that there dynamic process starts in the class of NSG.

The class of NSG is small. Indeed, the fraction of NSG among the total number of graphs is bounded by n! 2 (n-1)(n-2)/2 (see Remark 4 in the Appendix). This fraction goes fast to 0. For instance, when n = 20 the fraction of NSG is of the order of 10 -33 . Nevertheless, we would like to identify the specific network that maximises each aggregate outcome. This network cannot be reached by successive S-or N-switches, because as we show in the proof of Theorem 3, a NSG is a graph such that no S-switch nor any N-switch can take place.

Minimal and Maximal Levels of Interaction

We analyse the problem of finding the optimal and efficient network structure with fixed number of links when the intensity of interaction is close to the bounds. These cases help us understand how these structures vary with δ.

We start with δ close to δ max (l). This question is addressed by Corbo et al. ( 2006), but they restrict their analysis to connected graphs. They rely on spectral graph theory and specifically on results from Czetkovic et al. (1997) which lead them to innovative, yet partial results. In particular they show that for some suitably chosen values of n and l, the Quasi-Star is the (non necessarily unique) connected graph which maximizes both objective functions. We provide here a complete answer for the case of maximal admissible interactions, for any possible value of n and l and we get uniqueness. With no restriction to connected graphs, our proposition contrasts with their findings. Proposition 1. When δ -→ δ max (l), the unique network in G(l) which maximizes both aggregate efforts and utilities is the Quasi-Complete network QC(l).

When network externalities grow, some individuals' centrality will go to infinity. As we get closer to δ max (l), the QC(l) is the first network for which this happens. The QC(l) is a NSG with a unique class of agents if l = k 2 and three classes of agents otherwise. Three remarks can be made. First, this result holds even if the idiosyncratic constants are heterogeneous. In that case the agents in the complete subgraph are those with the highest constants. Second, the accumulation process implied by Theorem 2 is confirmed here, because QC(l) consists of the formation of the largest possible subgroup of (partially) central agents. As the interaction level grows, long distances in the network start having a big weight in the centrality of players. As the number of paths of length k is growing polynomially, long distances matter more than short distances when δ is far enough from 0. Long distances are easily generated by cycles, which are provided in large numbers by QC(l). Third, QC(l) is the network with the greatest number of isolated individuals, which all have the lowest possible centrality, but the trade-off clearly goes in favor of accumulation around a small group. This obviously has important policy implications.

We turn to the case where δ tends to 0. When interactions asymptotically go to 0, the above intuition is reversed, because effects vanish faster as they transit along longer paths. Short paths contribute more to centralities and the optimal and efficient networks are the ones maximizing the number of short paths. Proposition 2. When δ tends to 0, the network in G(l) which maximizes both aggregate efforts and utilities is either the Quasi-Star, QS(l), or the Quasi-Complete, QC(l). In particular, if l ≤ 1 2 n 2 -n 2 then it is QS(l) and if l ≥ 1 2 n 2 + n 2 then it is QC(l). A formal proof can be found in the Appendix. The sketch of the proof goes as follows. We decompose the sum of Bonacich centralities in a network as the weighted sum of paths of length 0, 1 and 2 and the weighted sum of all paths of length greater than 3. We first show that the latter sum is always negligible with respect to the former sum whenever δ goes to 0. We are then left with three terms, out of which the first two are shown to be constant over the whole set of networks with n individuals and l links. Finding the optimal network then boils down to finding the network which maximizes the number of paths of length 2. Observing that the number of such paths is equal to the sum of squares of degrees in a network, we finally rely on the work of [START_REF] Abrego | Sum of Squares of Degrees in a Graph[END_REF] who recently solved this maximization problem. In their paper, they identify QS(l) and QC(l) but also other networks that can eventually do as well, for specific values of n and l. All the networks belong to the class of NSG. In case of equality between different networks, we then turn to paths of length 3 in order to discriminate. All the networks they have identified are beaten at the third order either by QS(l) or QC(l). As for the sum of utilities, we show that for low δ, maximising the sum of squares of efforts is equivalent to maximising the sum of efforts.

In contrast with Proposition 1, the optimal and efficient network is not unique as it depends on the density of links. When this density is low, QS(l) performs better, whereas QC(l) does when the density is high. This density-based condition reveals the trade off between having a hub linking a large number of individuals which can all transit through the hub to generate many short paths with few links, or to build many triangles with a complete subgraph.

Interestingly, the logics of accumulation of links on a subset of individuals is still what drives the result, but we clearly see here that there are two typical ways of accumulating. On the one hand, accumulation can be built around the biggest possible subset of individuals (as in QC(l)) while on the other hand it can be done by increasing as much as possible the centrality of one central agent before trying to include another central agent (as in QS(l)). Notice that the former structure maximizes the number of isolated individuals whereas the later, in contrast, is the structure with a unique component which minimizes this number.

General Levels of Interactions

The problem of discriminating between different NSG in the general case can hardly be tackled analytically. There are two main reasons to this: First, once in the class of NSG, any link reallocation implies a switch toward an agent with lower centrality than the original neighbour. Reallocations such as S-switches are not feasible anymore. Net effects for a single link reallocation are then difficult to derive. Second, in addition to the first difficulty, improving a NSG necessitates a multiple link reallocation involving at least four agents. This is illustrated by the graph in Figure 1 in which any single link reallocation reduces both aggregate efforts and utilities, for any δ. As such, the problem of finding the optimal and efficient networks, as a function of δ, remains an open issue. 10,11 In any case, a solution to the problem should depend both on δ and on the density of links in the network, as shown by the solution for low values of δ.

We have run simulations to compare Nested Split Graphs between themselves, to check whether any pattern emerges. We have tested for values of n between 3 and 24, and for every n we have fixed l from 3 to the number of links in the corresponding complete network. For each of these cases, we have simulated 10 4 values of δ between 0 and δ max (l), which was computed on the Quasi-Complete network for given n and l. Once n, l and δ are fixed, we computed the sum of efforts and utilities in every possible Nested-Split Graph in order to find the best one. The systematic generation of every NSG is made possible by observing that there is a mapping between the set of NSG with n agents and the integers between 0 and 2 n-1 . Specifically, a binary representation of an integer induces a unique NSG by applying the following network formation rule: an agent is a bit of the binary representation of the integer, and every agent coded with a 1 forms links to all of his predecessors while agents coded with a 0 does not form any link to his predecessors. The last individual, however, is not taken into account because he has no predecessor (hence the 2 n-1 and not 2 n ). With n = 4, all NSG are mapped by the numbers from 0 to 7, with respective binary sequences 000 to 111. The sequence 000 is the empty network, the sequence 111 is the complete network, and the sequence 101 for instance is the kite. Our simulations point out three observations. First, for any NSG with low density, it is often the case that only two networks are optimal and efficient for every value of δ: QC(l) and QS(l). The Quasi-Star dominates for low values of interaction while the Quasi-Complete dominates for high levels. In turn, the QC(l) is usually the only network dominating all others for every value of δ when density is high. Figures 10 and11 illustrate simulations with n = 10 and n = 20 respectively. The solid curve is the frontier of interaction levels δ under (resp. above) which QS(l) (resp. QC(l)) dominates for aggregate efforts. The dotted curve has the same interpretation for aggregate utilities. Some remarks can be made. First, QS(l) dominates for low levels of interactions whereas QC(l) dominates for high levels. Second, once the QC(l) starts dominating, it dominates for all larger values of δ. Third, these frontiers are non monotonic in l. We suspected that this could come from the links that make the networks non "pure" stars or complete. We thus extracted for n = 20 the different possible numbers of links such that the QC(l) is indeed a complete subgroup (l = 6, 10, 15, 21, • • • ). These subseries, plotted in Figure 11-down, confirm this intuition at least for the case studied, since the figures exhibits a invert-J shape with only one pike. Hence, beyond the irregularities inherent to peripheral links, the general feature of the frontier delineating the regions where QS and QC dominate seems to be a one-pike regime (for larger values of n however, the relationship seems to be decreasing).

Second, there are specific cases of n and l such that other NSG are optimal and efficient. From our simulations, we have identified several types of alternative optimal and efficient networks. Among these, we have identified some recurring structural patterns which we illustrate in Figures 12 to 14. In Figure 12 there are two examples of "QS-like" networks, which are formed of isolated agents and a Quasi-Star over the remaining agents. The one on the left (n = 8 and l = 11) is the network that dominates both QS and QC with the smallest number of agents (in efforts for δ ∈ [.001, .033], and in utilities for δ ∈ [.001, .025]). The one on the right is another example with the same structural characteristics for n = 14 and l = 21 (in efforts for δ ∈ [.038, .049], and in utilities for δ ∈ [.029, .038]). This structure appears for every number of agents we have tested. In Figure 13 we illustrate some structures that are hybrids of QC and QS, for n = 9 and l = 11 (that dominates for δ ∈ [.001, .053] in efforts and for δ ∈ [.001, .04] in utilities) as well as for n = 14 and l = 39 (that dominates for δ ∈ [.001, .015] in efforts and for δ ∈ [.001, .011] in utilities). We have also found other structures with various characteristics, however they all have four classes of agents. In figure 14 Third, every time we find an alternative optimal or efficient network, it dominates on a range of values of δ that includes the specific value for which aggregate outcomes in the QS and the QC are equal.

Remark: Although we have found some NSG with six classes of agents (not counting isolated agents) that dominate both QC and QS (this happens first for n = 16 and l = 39), none of them is the optimal or efficient network. In fact, every optimal or efficient network we have found has always four or less classes of agents.

Discussion

In this section, we examine the robustness of ours result to two variations of the model: imposing connectedness and relaxing linearity of best-responses.

Connectedness. In the previous section, we have used N-switches to prove that optimal and efficient networks are in the NSG class. These switches can sometimes disconnect individuals from the graph and indeed, the QC, which is often the best network, maximises the number of excluded individuals. Social exclusion can be a policy concern, especially when analyzing the design of social and economic networks. One way of avoiding social exclusion is to guarantee that every agent is connected to the social network. In the case of games with strategic complementarities, connectedness is also a way to increase minimal effort levels in the society (indeed, isolated agents exert very low effort), so that minimizing isolation can coincide with a Rawlsian objective.

We show (see corollary 2 in the appendix) that in any connected network which is not a NSG, both an S-switch and an N-switch which preserve connectedness exist. We can then apply Theorems 1 and 2. Figure 15 depicts a 6-player 8-link example with δ = .25, so that the QC is the optimal and efficient network. Starting from the connected network of the figure, a unique N-switch leads to the quasi-complete network. However, another sequence of N-switches, which preserves connectedness, leads to another NSG (which is the optimal connected network in this case).

Non-linear best-responses. Assume best-responses are such that x i = f ( j g ij x j ), with f > 0 to account for strategic complementarities. Introducing non linearities changes the analysis in terms of existence and uniqueness of equilibria. Irrespective of this, we make two observations. First, assume f is convex. Conditional on equilibrium existence, we provide a sufficient condition such that any N-switch leads to an equilibrium where aggregate outcomes have increased (see corollary 3). The idea is the following: In the proof of Theorem 2 we observe that after an N-switch from individual j to individual k, all agents but j are better off. The aggregate effects depend on the trade off between aggregate gains and j's loss. When f is convex, a sufficient condition such that these aggregate effects are positive is that f < 1. This is because the direct effect of the N-switch results in an increase of k's effort and a decrease of j's effort, and by convexity this implies that the sum of both efforts increases. However, the dynamics of best-replies might go in the opposite direction and the condition f < 1 guarantees that the feedback effects do not outweigh the direct effect.

Second, assume f is concave. If f > 1, then the reverse happens and this condition guarantees that the positive feedback effects dominate the negative direct effect of the Nswitch. However, this condition induces explosive feedbacks and may be incompatible with the existence of equilibrium. In turn, if f < 1, there is no guarantee that an N-switch will improve aggregate outcomes. Indeed, it is easy to build examples where, agent k's effort is high enough such that an N-switch from agent j to agent k results in a large loss for j and a small gain for k. Hence, optimal or efficient networks might not be NSG.

Conclusion

The present paper has considered a linear network game with complementarities and a level of interaction low enough to guarantee a well-defined equilibrium. We have identified a single-link reallocation which guarantees an increase in aggregate efforts but does not guarantee an increase in the sum of utilities. We have also shown that this reallocation may not be decentralised. We have then identified an alternative multiple-link reallocation which guarantees an increase in both aggregate outcomes. Contrary to the previous one, this reallocation can be decentralised under coordination of the agents. We have next turned to the problem of the design of an optimal and/or efficient network and have shown that they belong to the class of Nested Split Graphs.

We can think of at least two directions of research. First, the general issue of the decentralisation of the planner's objective deserves more interest. Second, in some economic applications, the dual problem may arise, of minimizing the sum of efforts. This is the case for crime networks, speculative attacks on financial markets etc. (see [START_REF] Vivès | Strategic complementarity, fragility, and regulation[END_REF] and references therein). This is left for future research.

B -B = δM AB (3)
and

B = (I -δM A) -1 B (4)
Observing that

A =          0
m i3 b 4 + m i4 b 3 -m i1 b 2 -m i2 b 1 . . .    and i b i - i b i = δ[b 3 b 4 + b 4 b 3 -b 1 b 2 -b 2 b 1 ] (5)
We give a definition before proving Theorem 1 Definition 6. An n × n real matrix has a nested sequence of positive principal minors if it contains a sequence of positive principal minors of orders 1, 2, ..., n, where each minor's index set is properly contained in the next.

Proof of Theorem 1. Along the proof we will use the standard Jacoby Identity as well as three results coming from recent developments in the theory of M-matrices:

1-Jacobi Identity (JI): this identity relates the sign of any minor of a matrix X to the sign of the corresponding minor of the inverse of X: let Q k,n = {α = (α 1 , ..., α k ) : 1 ≤ α 1 < ... < α k ≤ n} denote the strictly increasing sequences of k elements from 1, ..., n. For α, β ∈ Q k,n we denote by X[β, α] the submatrix of X with rows indexed by α, columns by β. The submatrix obtained from X by deleting the α-rows and β-columns is denoted by X[α , β ]. Then, for any non singular matrix

X ∈ R n×n , det X -1 [β, α] = (-1) s(α)+s(β) det X[α , β ] det X for any α, β ∈ Q k,n
, where s(α) is the sum of the integers in α. Note that for principal minors, we have α = β. All these properties will be useful because the matrix (I -δG) happens to be an M -matrix.

After an S-switch from 12 to 13, we get from equation ( 2) that

i b i - i b i = δ[b 1 (b 3 -b 2 ) + b 1 (b 3 -b 2 )] All Bonacich
We will now show that both terms with braces are positive which will guarantee the positivity of (6). Notice that m 22 m 33 -m 2 23 is a principal minor of the matrix (I -δG) -1 . By (JI), the sign of this principal minor is the sign of the corresponding principal minor of the inverse matrix (I -δG). As (I -δG) is an M-matrix, by (PPM) we can conclude that m 22 m 33 -m 2 23 > 0.

2-Positivity of 1 -δ(m 13 -m 12 ):

To prove this reveals difficult for the following reason : when the link reallocation takes place, the maximal admissible value for δ changes from δ max to δ max , where δ max < δ max .

The term 1 -δ(m 13 -m 12 ) can be shown to be positive whenever δ < δ max but it happens to be sometimes negative when δ max < δ < δ max . Therefore we need to prove the positivity of some terms of the matrix M under the constraint that the other matrix M is well defined. This makes the proof both lengthy and complicated.

First, notice that for any symmetric (0, 1)-matrix A such that G = G + A, we have (I -δM A) = (I -δG) -1 (I -δG) = M M -1 . Writing down (I -δM A) we get Notice that if (δm 22 -δm 23 ) > 0 then we have the desired result, so we assume that (δm 22 -δm 23 ) < 0 and we will show that even in that case we have 1 -δ(m 13 -m 12 ) > 0. First, notice that (I -δM A) = (I -δG) -1 (I -δG) implies

(I -δM A) =           1 +
(I + δM A) = (I -δG) -1 (I -δG) (7)
and therefore

(I + δM A) = (I -δM A) -1 (8)
Computing the first terms of each matrix, we get

(I + δM A) =           1
         (I-δM A) -1 = 1 Det            1 + δm 12 -
As Det > 0, we have Sgn(1 + δm 12 -δm 13 ) = Sgn(1 -δm 12 + δm 13 ). We will now show that if δm 22 -δm 23 < 0 then 1 -δm 12 + δm 13 > 0.

Notice that (I + δM A) = (I -δG) -1 (I -δG) is the product of a M -matrix and an inverse M -matrix so we have again property (NSPPM). Analysing every possible sequence in the same way as we did above, we observe that every sequence leads to the conclusion that except potentially for the sequence 1 + δm 13 > 0 followed by (1 + δm

which guarantees positivity of [START_REF] Corbo | A study of Nash equilibrium in contribution games for peer-to-peer networks[END_REF].

Proof of Theorem 2. We show that, after an N-switch, there is a sequence of myopic individual best-replies which leads to an equilibrium with aggregate effort and social welfare which are both higher than in the initial network.

Case 1: jk / ∈ G. We use a simultaneous best-reply algorithm (SBRA) applied to all agents on the network. Fix the equilibrium effort profile in the initial network at X 0 = X(G), and start a simple SBRA on the network G = G + s∈N j\k (sk -sj). X 0 satisfies:

     x 0 j = a j + δ c∈N j∩k (G) x 0 c + δ s∈N j\k (G) x 0 s x 0 k = a k + δ c∈N j∩k (G) x 0 c + δ p∈N k\j (G) x 0 p (12)
At step 1 of the process, we obtain:

             x 1 j = x 0 j -δ s∈N j\k (G) x 0 s x 1 k = x 0 k + δ s∈N j\k (G) x 0 s x 1 s = x 0 s + δ(x 0 k -x 0 j ) for all s ∈ N j\k (G) x 1 q = x 0 q for all q = j, k, s (13)
Since, by hypothesis, x 0 k ≥ x 0 j , all efforts weakly increase at step 1 except that of agent j. But individual k's increase in effort compensates individual j' decrease. Further, utilities being quadratic in effort, the increase in utility of agent k is larger than the loss of agent j by convexity (given that x 0 k ≥ x 0 j ). It follows that both the sum of efforts and the sum of utilities at X 1 are greater than at X 0 . However, agent j's loss could have feedback effects on other agents in future steps of the SBRA. This possibility is discarded from step 2:

         x 2 j = x 1 j x 2 k = x 1 k + δ s∈N j\k (G) (x 1 s -x 0 s ) x 2 s = x 1 s + δ(x 1 k -x 0 k ) x 2 q ≥ x 1 q for all q = j, k, s (14)
so that x 2 i ≥ x 1 i for all i ∈ N . Now, thanks to complementarities, the SBRA can only lead to an increase at each step. By a standard contraction property, the SBRA will converge to X ∞ = X(G ), in which aggregate effort as well as social welfare have increased compared to X 1 .

Case 2: jk ∈ G. The process needs to be decomposed into two sequential SBRA on the network G . In a first step, we take X 0 = X(G) as the initial condition on G and we restrict the SBRA to agents j and k, keeping all others' effort fixed. This process converges to X ∞ = Y 0 (G ), where only agent j and k's efforts have changed. In a second step, we take Y 0 (G ) as the initial condition and apply a SBRA over all agents. This process will converge to Y ∞ = X(G ), which is the equilibrium vector of efforts in the modified network.

As jk ∈ G, X 0 now satisfies:

    
x 0 j = a j + δ c∈N j∩k (G)

x 0 c + δ s∈N j\k (G)

x 0 s + δx 0

k x 0 k = a k + δ c∈N j∩k (G)
x 0 c + δ p∈N k\j (G)

x 0 p + δx 0 j (15)
The first SBRA, restricted to agents j and k, leads to the following equilibrium:

y 0 j + y 0 k = x 0 j + x 0 k y 0 k > x 0 k ( 16
)
To see this, notice that Y 0 is such that:

     y 0 j = a j + δ c∈N j∩k (G)
x 0 c + δy 0 k y 0 k = a k + δ c∈N j∩k (G)

x 0 c + δ s∈N j\k (G)

x 0 s + δ p∈N k\j (G)

x 0 p + δy 0 j [START_REF] Johnson | Matrix Classes That Generate all Matrices with Positive Determinants[END_REF] Using equations [START_REF] Hendricks | The Economics of Hubs: The Case of Monopoly[END_REF], we find:

x 0 j + x 0 k = y 0 j + y 0 k = a j + a k + 2 δ c∈N j∩k (G)
x 0 c + δ p∈N k\j (G)

x 0 p + δ s∈N j\k (G)

x 0 s 1 -δ

Moreover, y 0 k -x 0 k = δ s∈N j\k (G)

x 0 s + δ(y 0 j -x 0 j ) and also y 0 k -x 0 k = x 0 j -y 0 j . Therefore

y 0 k > x 0 k .
Now apply a second SBRA on network G , with Y 0 as initial conditions. This process is such that Y ∞ ≥ Y 0 . Indeed, after the first step, individuals who have reallocated their links (those labeled s) will increase their effort together with the exclusive neighbors of k (those labeled p), because y 0 k > x 0 j . Agents j and k do not modify their effort, neither do the common neighbors of j and k (those labeled c), because y 0 k -x 0 k = x 0 j -y 0 j . At the end of the first step, Y 1 ≥ Y 0 and by complementarities, Y ∞ = X(G ) ≥ Y 0 ≥ X 0 .

Proof of Theorem 3. We show that a network which is not a NSG always offers the possibility of an N-switch, i.e. there must be a pair j, k such that N j\k graphs in total. Of course, this number is largely overestimating because permutations between agents of the same class should not be counted.

Proof of Proposition 1. For any network with l links, the Bonacich centralities are well-defined only when δ < 1/µ(G) where G ∈ G(l). The solution is given by G * ∈ G(l) that maximises µ(G). [START_REF] Rowlinson | On the maximal index of graphs with a prescribed number of edges[END_REF] provides the solution to that problem.

Proof of Proposition 2. Let P k (G) be the number of paths of length k in network G appropriate S-switch). Consider a network G which is not a NSG. We thus can find three agents i, j, and k such that ij ∈ G, ik / ∈ G and b j (G, δ) ≤ b k (G, δ). Case 1: G is of diameter 2. Either jk ∈ G or agents j and k have a common neighbor. Then an N-switch can be made without disconnecting agent j (see figure 16).

Case 2: G is of diameter strictly greater than 2. Then there exists a chain of length three, i.e. four agents i, j, k and l such that ij, il, lk ∈ G and j and k do not share a common neighbour. An N-switch would disconnect agent j.

Either b l (G, δ) ≤ b k (G, δ) or b l (G, δ) > b k (G, δ). In the former case an N-switch from l to k will not disconnect anyone (case 2a on figure 17). In the latter case, either b l (G, δ) ≤ b i (G, δ), in which case an N-switch from i to l will ensure connectedness (case 2b on figure 17), or not and thus an N-switch from l to i ensures connectedness (case 2c on figure 17). Corollary 3. When f is convex and f < 1, an N-switch increases aggregate outcomes.

Proof of corollary 3. We follow the proof of Theorem 2. Consider an N-switch from agent j to agent k, and let agents j and k revise their strategies through a SBRA, keeping all other agents' efforts as fixed. For convenience, let s represent the sum of efforts of those agents who reallocate their connection from j to k. We can rewrite the system of equations ( 17) as

x k = f (a + s + x j ) x j = f (b -s + x k )
where a ≥ b, s > 0 and f increasing (thus x j ≤ x k for all s). Let h = f -1 . The system becomes

x j = h(x k ) -a -s x k = h(x j ) -b + s We obtain ∂(x k + y j ) ∂s = h (x k ) -h (x j ) 1 -h (x k )h (x j ) (25)
where h = ∂h ∂s (if h = 1). The N-switch improves aggregate outcomes if the RHS of equation ( 25) is nonnegative.

  centralities are positive and by hypothesis, b k ≥ b j , so the positivity of (b k -b j ) is sufficient to guarantee that B .1 -B.1 > 0. This is what we show in the next theorem. Theorem 1. Assume δ ∈ [0, δ max (l)[. Any S-switch increases aggregate effort.

Corollary 1 .

 1 Assume δ ∈ [0, δ max (l)[. A network in G(l) maximising aggregate efforts or aggregate utilities has a unique non trivial component.

  we illustrate two examples, for n = 11 and l = 25 (that dominates in efforts for δ ∈ [.001, .016], and in utilities for δ ∈ [.001, .012]) and for n = 18 and l = 30 (for δ ∈ [.027, .067], and δ ∈ [.021, .053] respectively).

1 .

 1 For convenience, assume that the four individuals are 1, 2, 3 and 4, with 12 ∈ G and 34 / ∈ G and G = G -12 + 34. In network G the Bonacich centralities are given by (I -δG)B = 1 while in G they are given by (I -δG )B = 1. By denoting A = G -G and M = (I -δG) -1 we get:

2 - 3 - 4 -

 234 Positive principal minors of M-matrices (PPM): An M-matrix is a P-matrix (see REF). As such, all principal minors of any M-matrix are positive (see for instance REF) Path product property (PPP): An inverse M-matrix satisfies the following property: if A = (a ij ) is an inverse M-matrix then a ik a jj ≥ a ji a jk (see REF Johnson and Smith 99). Nested sequences of positive principal minors (NSPPM): Let M be the set of M-matrices. If A ∈ M and B ∈ M -1 are n × n matrices, then AB (and BA) has a nested sequence of positive principal minors. (see Theorem 4.6 in Johnson et al. 2003)

3 -b 2 = b 3 -b 2 +

 3232 centralities are positive and by hypothesis, b 3 ≥ b 2 , so the positivity of (b 3 -b 2 ) is sufficient to guarantee that i b ii b i > 0. Using B = (I -δM A) -1 B we can write b δb 1 ( ? m 33 + m 22 -2m 23 ) 1 -δ(m 13 -m 12 ) ?

  (G) = ∅ and b k ≥ b j . Assume G is not a NSG. Then, by definition, there are three agents i, j and k such that ij ∈ G, deg(k, G) ≥ deg(j, G) and ik / ∈ G. Therefore, N j\k = ∅. Assume now b k < b j . If N k\j = ∅, because b k < b j there would be an N-switch on G (from k to j). Hence, N k\j = ∅, and therefore, N k (G) ⊆ N j (G). Together with the condition that deg(k, G) ≥ deg(j, G), we obtain deg(k, G) = deg(j, G) and b k = b j , a contradiction. Remark 4. The fraction of NSG among all possible networks is bounded by n! 2 (n-1)(n-2)/2 Proof of Remark 4. With n individuals, there are 2 n-1 different anonymous NSG and n! permutations of the individuals and there are 2 n(n-1) 2

FIGURES

  FIGURES

Figure 1 :

 1 Figure 1: n = 11, l = 13 -A nested split graph with 5 classes in the main component plus 3 isolated agents

Figure 2 : 5 30Figure 3 :

 253 Figure 2: Quasi-complete graphs with n = 5

Figure 4 :

 4 Figure 4: δ = .1 -above: in the left graph, b 3 > b 4 ; aggregate efforts increase after the switch from 35 to 45 -below: in the left graph, b 5 > b 2 ; aggregate efforts decrease after the switch from 45 to 24

Figure 5 :

 5 Figure 5: An S-switch

Figure 6 :

 6 Figure 6: n = 30, l = 65, δ = .05 -The sum of utilities decreases after the S-switch

Figure 7 :

 7 Figure 7: n = 14, l = 42, δ = .12 -Agent i's effort decreases after the S-switch

Figure 8 :Figure 9 :

 89 Figure 8: An N-switch

Figure 10 :Figure 11 :Figure 12 :Figure 14 :

 10111214 Figure 10: Comparing QC and QS for n = 10 -dash (resp. doted) line represents aggregate efforts (resp. utilities)

Figure 15 :Figure 16 :

 1516 Figure 15: Preserving connectedness

Figure 17 :

 17 Figure 17: An N-switch preserving connectedness: diameter greater than 2

1 -

 1 Positivity of m 33 + m 22 -2m 23 : If m 22 m 33 -m 2 23 > 0 then m 33 + m 22 -2m 23 > 0. Indeed, m 22 m 33 > m 2 23 implies 2m 33 m 22 -4m 2 23 > -2m 33 m 22 . Thus m 2 33 + m 2 22 + 2m 33 m 22 -4m 2 23 > (m 33 -m 22 ) 2 > 0. This implies (m 33 + m 22 ) 2 -4m 2 23 > 0 and because m ij ≥ 0 for all i, j, m 33 + m 22 -2m 23 > 0.

  δm 12 -δm 13 δm[START_REF] Cvetković | Eigenspaces of Graphs[END_REF] -δm 11 0 . . . 0 δm 22 -δm[START_REF] Radner | The Organization of Decentralized Information Processing[END_REF] 1 + δm 12 -δm 12 0 . . . 0 δm 23 -δm 33 and we observe that the term whose sign we are looking for is the upper right term. As observed before, M and M are M -matrices and therefore M M -1 is the product of an M -matrix by an inverse M -matrix. We thus have property NSPPM. Here there are only 6 possible distinct nested sequences. Two of them start with 1 -δ(m 13 -m 12 ) > 0, in which case the result is obtained. Two other sequences start with the term 1-δm 13 > 0, which also implies the result. We are thus left with two sequences which start with 1 + δm 12 > 0. Then, either (1 + δm 12 )(1 -δm 13 ) + δm 12 δm 13 > 0 or (1 + δm 12 )(1 + δm 12 -δm 13 ) -δm 11 (δm 22δm 23 ) > 0.The first possibility comes down to 1-δ(m 13 -m 12 ) > 0 which is the result we are looking for, so that the only remaining case is when the nested sequence starts with 1 + δm 12 > 0 and goes on with (1 + δm 12 )(1 + δm 12 -δm 13 ) -δm 11 (δm 22 -δm 23 ) > 0.

			
	. . . . . . . . .	δm 13 . . . . . . . . .	1 -δm 13 0 . . . 0 . . . 1 . . . 0 . . . . . . . . . . . . 0 . . . 1 . . .         

  -δm 12 + δm 13 -δm 11

			δm 11	0 . . . 0 
	δm 23 -δm 22	1 -δm 12	δm 12	0 . . . 0
	δm 33 -δm 23 . . .	-δm 13 1 + δm 13 0 . . . 0 . . . . . . 1 . . . 0
	. . .	. . .	. . .	. . .	. . .	. . .
	. . .	. . .	. . .	0 . . . 1

  δm 12 -δm 13 ) = 1 -δm 12 + δm 13

					
		. . . . . . . . .	. . . . . . . . . . . .	. . . . . . . . . . . .	0 . . . 0 1 . . . 0 . . . . . .          . . . 0 . . . 1 
	From (8) and using both upper right terms of the matrices, we get:
	1 Det	(1 +

δm 13 -δm 11 δm 11 0 . . . 0 -(δm 22 -δm 23 )(1 -δm 13 ) -δm 12 (δm 23 -δm 33 ) . . . . . . 0 . . . 0 δm 13 (δm 22 -δm 23 ) -(1 + δm 12 )(δm 23 -δm 33 )

  [START_REF] Garicano | Hierarchies and the organization of knowledge in production[END_REF] )(1 -δm 12 + δm 13 )δm 11 (δm 33 -δm 23 ) > 0.We now show that (δm 33 -δm 23 ) > 0 which will conclude the proof. By[START_REF] Calvó-Armengol | Social networks and crime decisions: the role of social structure in facilitating delinquent behavior[END_REF], we have (δm 33 -δm 23 ) = 1 Det (δm 13 (δm 22 -δm 23 ) -(1 + δm 12 )(δm 23 -δm 33 )) (10) By developing the RHS term of (10) and by using the property (PPP) which guarantees that δm 13 δm 22 > δm 12 δm 23 δm 12 δm 33 > δm 13 δm 23 By property (PPM) we also have δm 22 δm 33 > δm 23 δm 23 But as δm 22 -δm 23 < 0, it must be the case that δm 33 -δm 23 > 0 and hence δm 33 > δm 23 . Putting everything together, we get δm 13 δm 22 + δm 33 + δm 12 δm 33 > δm 23 (1 + δm 12 + δm 13 )

We also explore the extension to non linear interactions at the end of the paper

The discount factor is the interaction level parameter

The class of NSG encompasses the class of core-periphery networks

The ratio of NSG among every possible network goes fast to zero. It is about 10 -33 when n = 20.

By admissible we mean a value that guarantees a well-defined equilibrium.

See the paper of[START_REF] Ballester | Who's who in networks. Wanted: the key player[END_REF] for more details on this necessary and sufficient condition.

This will directly provide the solution to the more general problem of finding the best networks, net of link formation costs. Indeed, in order to solve this problem the planner needs to identify the optimal or efficient networks for every possible number of links.

Interestingly, QS(l) is the graph complement of QC( n(n-1) 2 -l).

Indeed, b i -b i = δ[b i (m ik -m ij ) + m ii (b k -b j )].As shown in the proof of Theorem 1, b k -b j > 0 and m ik = 0.

It is the same reason for which[START_REF] Ballester | Who's who in networks. Wanted: the key player[END_REF] are not able to identify key groups of players and restrict their attention to the key player only. As they mention, "It is important to note that this group target selection problem is not amenable to a sequential key player problem (...) In fact, optimal group targets belong to a wider class of problems that cannot admit exact sequential solutions." See also[START_REF] Ballester | Interactions with hidden complementarities[END_REF] for more detailed discussions on the key group.

The previous problem of finding the graph with fixed number of links having the largest index is complex, but the authors show that for any non optimal network, there is a single link reallocation which improves the index (see Cvetkovic 2008). This sequential improvement is what helps the authors solve the problem. The problem at hand does not offer such sequences, it is therefore more complex.

(including loops). Then

The first two terms of the sum are constant across any network in G(l). Furthermore, if G c is the complete network with n individuals (i.e. the network with n 2 links), then

while

Therefore,

As +∞ j=0 (δ(n -1)

which implies

Hence, when δ → 0, the network maximizing aggregate effort is the network which maximizes the number of paths of length 2. By noticing that in any network, P 2 (G) = i d 2 i , we can refer to [START_REF] Abrego | Sum of Squares of Degrees in a Graph[END_REF] to conclude.

In terms of social welfare, taking the sum of the squares of the Bonacich centralities leads to the same conclusion that the optimal network should maximize P 2 (G).

Corollary 2. On any network connected G which is not a NSG, there exists an N-switch (and thus an S-switch) which preserves connectedness.

Proof of corollary 2.

We start from a connected network G which is not a NSG. We will show that there exists an appropriate N-switch that preserves connectedness (this will imply the existence of an