{'fraction_non_alphanumeric': 0.04446004959511949, 'fraction_numerical': 0.010445697733108035, 'mean_word_length': 4.143921435827972, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 22, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Being Central on the Cheap: Stability in Heterogeneous Multiagent Centrality Games

We study strategic network formation games in which agents attempt to form (costly) links in order to maximize their network centrality. Our model derives from Jackson and Wolinsky's symmetric connection model, but allows for heterogeneity in agent utilities by replacing decay centrality (implicit in the Jackson-Wolinsky model) by a variety of classical centrality and game-theoretic measures of centrality. We are primarily interested in characterizing the asymptotically pairwise stable networks, i.e. those networks that are pairwise stable for all sufficiently small, positive edge costs. We uncover a rich typology of stability: - we give an axiomatic approach to network centrality that allows us to predict the stable network for a rich set of combination of centrality utility functions, yielding stable networks with features reminiscent of structural properties such as"core periphery"and"rich club"networks. - We show that a simple variation on the model renders it universal, i.e. every network may be a stable network. - We also show that often we can infer a significant amount about agent utilities from the structure of stable networks.


Introduction
Centrality in social networks is a topic that has seen an overwhelming amount of recent work at the intersection of Social Network Analysis Wasserman and Faust (1994), Physics of Complex Systems Newman (2018), Economics Jackson (2008), Theoretical Computer Science and Artificial Intelligence Easley and Kleinberg (2010). Many of the leading models of network formation are stochastic. In reality, networks form and evolve as a consequence of agent incentives. Among these incentives, centrality maximization is certainly a pervasive one. To give just one all too familiar example: the increasingly competitive nature of the scientific enterprise, coupled perhaps with an ever more common 1 reliance on quantitative measures 2 and rankings of individuals and publishing venues as proxies for research quality, has often resulted in a significant explosion in the number of submissions to venues perceived as "top ones". The decisive factor seems to be, of course, authors' perception that publication in such venues is a way to increase their papers' impact, which ultimately increases their own "centrality", that they want maximized.
Somewhat less clear are the strategic consequences of agents' propensity for competing for central positions. By this we mean understanding the manner in which agents' preferences for central network positions influences the formation and evolution of networks: in spite of a significant amount of work on the structure of networks (witnessed e.g. by concepts such as core-periphery structure Borgatti and Everett (2000), the rich-club effect Zhou and Mondragón (2004), or small-world networks Watts (1999)), and on strategic network formation Jackson and Wolinsky (1996); Bala and Goyal (2000); Fabrikant et al. (2003), the impact of agents' incentives on the network structure is not completely understood. On the other hand, the inverse problem, that of inferring node utilities from the structure of stable networks, has not seen a comparable amount of investigation.
The goal of this paper is to contribute to understanding network formation from a game-theoretic perspective that assumes that agents are willing to modify network structure (at a small cost per extra link) in order to improve their centrality. We start from the realisation that the most well-known model of strategic network formation, the symmetric connection model Jackson and Wolinsky (1996); Jackson (2008) can be seen as maximizing agents' decay centrality Coronicová et al. (2018); Tsakas (2018), subject to constant edge cost. In reality, centrality objectives may differ from agent to agent. The extension we propose accommodates this heterogeneity via an axiomatic approach to network centrality Boldi and Vigna (2014), presenting axioms that isolate salient features of such measures, which influence the structure of emerging networks in predictible ways.
A key design dimension for models of network formation is their handling of tie strength: It is well-known that weak ties play an important role in social dynamics, being extremely useful for information dissemination Granovetter (1973). Our model restricts agents tie manipulation attempts to weak ties only, whose cost of establishing/maintainance can realistically be assumed to be a tiny positive constant. An explanation for such a restriction is not merely modeling convenience, but the existing tension between breaking strong links and centrality maximization: in real life strong links could be either exogeneously imposed (e.g. agents interacting as being part of the same organization, e.g. being coworkers) or have such a high intrinsic cost of breaking (e.g. family ties) that the objective of centrality maximization becomes unrealistic. It is an interesting question to extend our framework to networks with strong ties as well.
We follow the philosophy of Jackson and Wolinsky (1996) (rather than that of Fabrikant et al. (2003)) by assuming that our model is symmetric: link establishment must benefit both endpoints. The main questions motivating us are: 1. Given a set of agents with diverse centrality objectives, can one predict the structure of stable nets ?
2. Can we obtain richer classes of stable networks than the ones for the classic symmetric connections model ? Are observed features of real-world graphs (e.g. rich-club, core-periphery) compatible with explanations based on centrality maximization ?
3. Can we infer (at least something about) agents' centrality objectives from the (set of) stable networks ?
Given the extreme potential heterogeneity of agent objectives, it could seem that no substantive positive answer could be given to the questions above. A first contribution of our paper is to show that this is not the case: we provide well-behaved examples where the answers to the three previous questions are affirmative. Remarkably, stable networks in our models display (stylized versions of) features such as core-periphery and rich club effect, suggesting that suitable extensions of the J-W model may be able to reproduce such features. A second contribution is the identification of a fundamental limit of prediction in centrality maximization models, a plausible variation in the model specification that renders it universal, in the sense that every network can arise as an equilibrium. The property we highlight is natural, assuming that agents' utility is subject to a threshold beyond which no extra gain in centrality increases their utility.
The following is an outline of our main results (for all the missing proofs we refer to the Appendix): we first show (Theorem 3) that for mixtures of agents satisfying monotonicity axioms, stable networks may contain an unique complex component consisting of a "core" (clique) and a "periphery" of nodes only connected to core nodes. On the other hand (Theorem 5), for degree homophilic measures stable networks display a rich club effect : they consist of a sequence of cliques of rapidly decreasing sizes. For betweenness centrality games we show (Theorem 6) that connected stable networks have small diameter and are characterized by a property related to neighborhood domination in graphs. We provide some futher analytical results and conjectures (based on simulations) for some less well-behaved centralities. Finally, we show that adding thresholds to the model makes it universal (Theorem 8). Some of these cases are complemented by results (Theorems 4, 9) on learning agent types from the (set of) stable networks.

Preliminaries
We assume familiarity with basics of graph theory, coalitional game theory (see Chalkiadakis, Elkind, and Wooldridge (2011)), strategic network formation (e.g. Jackson (2008)) and centrality measures in social networks Koschützki et al. (2005); Das, Samanta, and Pal (2018). In particular, given network g and vertex i of g, we will denote by deg(i) the degree of i in g, by N (i) the set of neighbors of i in g, and by N (i) the set {i}∪N (i). We also denote by g +ij the network obtained by adding missing edge ij, by d(i, j) the distance between i and j, and by Conn(i) the connected component of i in g. We will write g 1 +g 2 for the disjoint union of two networks g 1 , g 2 . An edge is called a bridge edge if its removal disconnects the graph. The neighborhood domination relation is a classical concept in graph theory (e.g. Definition 1.16 in Brandstädt, Le, and Spinrad (1999)), formulated (as vicinal preorder ) in Foldes and Hammer (1978) as follows: Given vertices x, y, say that y dominates Definition 1. Given node i in network g, define: -The eccentricity centrality of i is defined [ 3 ] as C ecc (i) = 0 if i is isolated, min( n−1 d(i,j) : j ∈ Conn(g)) otherwise. -The random walk closeness centrality of i is defined White and Smyth (2003) ht [j,i] , where ht[j, i] is the expected time for a random walk started at j to first hit i.
-The decay centrality of i is defined as C dec [i] = j∈g β d(i,j) , where β is a fixed parameter, 0 < β < 1.
σyz , that is the sum of percentages of shortest paths between arbitrary vertices y, z that pass through i.
-The random walk betwenness centrality (a.k.a. current flow betweenness centrality) of i is defined Newman (2005) r j,k is the probability that a random walk starting at node j with absorbing node k passes through node i.
-The eigenvector centrality of i is defined as where w is the eigenvector corresponding to the largest eigenvalue of the adj. matrix of g.
-The Katz centrality of i is defined as α is a parameter, 0 < α < 1.
Our last centrality is defined using coalitional games:

Model and Axiomatic Setting
Our framework is specified as follows: Definition 3. The symmetric connection model with generalized centralities (C i ) and edge cost c is defined as follows: the utility of player i on network g is We will occasionally avoid mentioning the family of centralities (C i ) when it is clear from the context. When all C i 's are equal to the decay centrality we recover the classical symmetric connection model Jackson and Wolinsky (1996).
An edge flip of a pair of nodes i, j of a network g is the addition of ij to g, if ij ∈ g, or its removal from g, if ij ∈ g. The outcome of an edge flip is the resulting network h.
Definition 4. An edge flip is a weakly improving move for player i if u i (h) ≥ u i (g), and a strongly improving move if u i (h) > u i (g). An edge flip is an improving move iff: -it is an edge addition that is strongly improving for at least one endpoint and at least weakly improving for both, or -is an edge deletion, strongly improving for some endpoint.
The main model of stable network structure employed in the area of strategic network formation, defined in Jackson and Wolinsky (1996) is: Definition 5. Network g is called pairwise stable if no edge flip is an improving move.
In this paper we use a version of pairwise stability that is appropriate to our setting that assumes weak ties only, in which the edge cost is a tiny (but positive) value ǫ > 0. Therefore, the following variant of pairwise stability will be our main notion of interest: Definition 6. Network g is called asymptotically pairwise stable (APSN) if there exists ǫ 0 > 0 such that (∀ǫ), 0 < ǫ < ǫ 0 , g is pairwise stable in the model with edge cost ǫ.
APSN is a version of pairwise stability, so results on APSN relate to preexisting literature. For instance the original theorem of Jackson-Wolinsky implies the fact that for decay centrality games the unique family of APSN is formed by complete graphs K n .

Axioms for Monotone Network Centralities
The first axiom is a simple one, and has been discussed before in the literature Boldi and Vigna (2014). It formalizes the intuition that adding edges always improves the centrality of adjacent nodes: If C is a centrality measure satisfying some axiom then C ′ = 1/(1 + C) (or even C ′ = 1/C, when C is strictly positive) satisfies a correspondingly modified "dual" axiom. For instance, here's the dual of Axiom 1: Our next axiom encodes a different type of monotonicity: one in which the benefit of extra links only incurs for agents already in the same connected component. It is a more precise version of an axiom due to Boldi et al. (2017): Axiom 2. A centrality measure C is componentwise if it satisfies the following conditions: If ij ∈ g and i, j are in the same connected component then C[i, g + ij] > C[i, g]. If ij ∈ g and i, j are not in the same connected component in g then In the dual scenario agent only benefit when forming bridges between previously disconnected components: Axiom 2 ′ . A centrality measure C is peripheral if it satisfies the following conditions: If ij ∈ g and i, j are in the same connected component then The setting of Axiom 2 (and, consequently, 2 ′ ) is not vacuous, as we have: Theorem 1. Closeness centrality and random walk closeness centrality satisfy Axiom 2.
The next axiom has a different flavor, and encode a scenario when agents benefit by connecting only when they were "of the same/different types". In our particular setting homophily is assessed with respect to agents' degree.
Axiom 3. A centrality measure C is degree homophilic if the following is true: there exists a strictly increasing function f such that for any network g and edge ij ∈ g, adding edge ij to g is an improving move for i iff deg(j) ≤ f (deg(i)).
Another axiom refers, among other things, to the role links among unrelated agents have on one agent's centrality: Axiom 4. Increasing centrality measure C is called regular if the following are true: -whenever g is a network and i an isolated node in g, C[i, g] = 0.
-whenever i, j are nodes, g is a network such that ij ∈ g and k = i, j, we In other words the addition of an edge cannot increase the centrality of an unrelated node.
The table in Figure 1 displays a synthetic view of the axioms various centrality measures satisfy. We will say that a game satisfies a certain axiom if all the players satisfy it.
Finally, many of our results (even theoretical ones) arise from implementing our model in Python using the networkx package Hagberg, Swart, and Chult (2008) and performing computational experiments. We will provide a link to public versions of our programs in the non-anonymized version.

APSN for Mixtures of Monotone Centralities
In this section we consider mixtures of agents satisfying axioms 1, 1 ′ , and 2, 2 ′ . For latter types improving moves are clear by definition. The following result, whose proof is trivial, characterizes them for the former types as well: Lemma 1. Consider an agent i whose utility function has the form in equation (1). The following is true: If centrality C satisfies Axiom 1 then adding any missing edge is an improving move for i, while removing an edge is not improving, both statements being true for small enough cost c. Dually, if centrality C satisfies Axiom 1 ′ then removing any edge is an improving move for i, while adding an edge is not improving, both statements being true for small enough cost c.
The next result characterizes stable networks as those whose connected components are (perhaps single node) complete graphs plus, maybe, one complex component, which is not a complete graph. This complex component displays an extreme form of core-perifery structure: it consists of a core, a clique of nodes of type 1 and 2, and a periphery consisting of nodes of type 2 ′ attached to core nodes only: Theorem 3. The APSN in the centrality model with agents satisfying one of Axioms 1,1 ′ , 2,2 ′ are precisely those networks g satisfying the following rules: -All agents of type 1 ′ are isolated.
-There is a single connected component that contains all agents of type 1. Agents of type 1 and 2 in this component form a clique ("the core"). All agents of type 2 ′ belong to this component, and are pendant vertices attached to vertices of type 1 of the clique ("the periphery").
-All other connected components are complete graphs (including isolated nodes) containing agents of type 2 only. As a corollary of the previous result, we can infer quite a lot about agent types from the structure of stable networks: Theorem 4. Consider, in the setting of Theorem 3, an asymptotically pairwise stable network g. Then: a). Isolated nodes are either of type 1 ′ or 2. b). An agent y in complete graph components of size ≥ 2 may be of type 1 or 2.
It is guaranteed to be of type 2 when there exists a complex component in g which doesn't contain y, or when some agent x in a different component than y is known to be of type 1 (Figure 2). 5 Degree-homophily yields rich-club APSN Next we study centrality games for degree-homophilic centrality measures. The following result shows that in this case APSN have a "rich club", hierarchical structure: Theorem 5. Let h be an APSN for the centrality game with degree homophilic . . (and one can assume w.l.o.g., by removing multiple copies of the same value, that Then all graphs of type K a1 + K a2 +. . .+K ap +rK 0 ("stratified clique graphs") are APSN for degree homophilic centrality games with function f and conversely, all APSN are unions of cliques with this structure.
Proof. We use the definition of degree homophily: , and similarly f (deg(j)) ≥ deg(i). If i, j were not connected, then adding ij would be an improving move for both of them. b). Similar to (a): (j), and similarly f (deg(i)) ≥ deg(j). If i, j were not connected, then adding ij would be an improving move.
, which means that removing edge ij is an improving move for j, since in the graph h = g − ij adding edge ij is not an improving move for j.
For a proof of the corollary, see the Technical Appendix.

Domination and APSN for Betwenness Games
In this section we characterize APSN for centrality games for betweenness centrality, a measure that satisfies none of the previous axioms. First, simple computations provide examples of APSN with components that are not complete graphs: networks C 4 + nK 1 , n ≥ 0. We will show that the domination relation plays a decisive role in their characterization of APSN. To accomplish this, we first prove: Lemma 2. The following statements are true: -Adding any bridge edge ij weakly increases i's betweenness centrality, strictly unless i was an isolated node. Consequently adding a bridge edge is improving for i, unless i was isolated. Conversely, a disconnecting edge removal would be improving for i iff i was a pendant node.
-Adding any non-bridge edge ij weakly increases i's betweenness centrality.
We now prove the following result, which gives an unexpected (and fairly elegant) algorithmic characterization of APSN for betweenness games using the domination relation: Theorem 6. Graphs g that are APSN for betweenness centrality games consist of isolated vertices plus at most one connected component C with at least two vertices which satisfies the following condition: deg(l) ≥ 2 for every l ∈ C, diam(C) = 2 and for every i = j ∈ C, ij ∈ E(g) if and only if sets N (i) \ {j} and N (j) \ {i} are incomparable, i.e. if none of i, j dominates the other.
Proof. It is easy to see that the networks that satisfy the condition of Theorem 6 are APSN: first, by Lemma 2 isolated vertices have no incentive to connect to anyone else, as their utility would decrease, and can be subsequently ignored. Consider, two vertices i, j in a larger component C. If ij ∈ E(g) then, by the condition of the theorem, there exist vertices k ∈ N (i)\N (j) and l ∈ N (j)\N (i). Since d(k, j) ≤ 2 it follows that [k; i; j] is a shortest path between k and j that would disappear if we dropped edge ij, decreasing the betweenness centrality of i and ultimately its utility. Similar arguments hold for j. So if we dropped edge ij the utility of both i, j would decrease, hence dropping ij it is not an improving move. On the other hand if ij ∈ E(g) then N (i) \ {j} and N (j) \ {i} are comparable. Assume w.l.o.g. that N (i) \ {j} ⊆ N (j) \ {i}. Then every shortest path [s; i; t] stays a shortest path when we add edge ij: This is clear when s, t = j, while cases s = j and t = j cannot happen, since ij ∈ E(g). Adding edge ij creates no new shortest paths: Indeed, assume [s; i; j] were a newly created shortest path through i. Since N (i) \ {j} ⊆ N (j) \ {i}, sj ∈ E(g), a contradiction. Since the set of shortest paths through i stays the same, adding ij is not an improving move.
Let us now prove the converse direction, that APSN satisfy the conditions in the theorem. A first thing to prove is that any APSN has at most one component with ≥ 2 vertices. Indeed, if there existed two such connected components then, by Lemma 2, joining them by an edge ij would be an improving move for both i, j. Second, we claim that this nontrivial component has diameter 2: indeed, it cannot have diameter 1, as complete graphs are not APSN. Assume it contained a shortest path of length 3 [p; q; r; s]. Then p, s would increase their utility by connecting since, e.g., now there is a shortest path from q to s through p. Third, this component has no pendant nodes: any such node would have, by Lemma 2, an incentive to disconnect.
To prove the domination condition, consider a connected APSN g and a pair ij ∈ g, and assume w.l.o.g. that adding edge ij decreases the utility of i for small ǫ > 0, so that the move is not improving. Hence adding ij does not increase the betweenness of i. Paths that contributed positively to the betweenness of i before adding ij are between unconnected nodes k 1 , k 2 ∈ N (i), so that a shortest path between k 1 , k 2 goes through i. Then adding edge ij does not change the ratio corresponding to k 1 , k 2 in the betweenness of i. Consider now the shortest paths between k 1 ∈ N (i) \ {j} and j. Since the betweenness of i does not increase as a result of adding edge ij, k 1 must be connected to j. Hence j dominates i.
Consider now an edge ij ∈ g. Since the removal of ij is not improving for either i or j, there exists a shortest path between some vertices s 1 = i = t 1 that uses edge ij. As diam(g) = 2, one of s 1 , t 1 (say t 1 ) must be j, hence Hence none of i, j dominates the other.
Observation 1. Complete bipartite graphs K a,b , a, b ≥ 2 satisfy the conditions of the theorem, hence they are APSN. One could conjecture that these are all connected APSN with at least 2 vertices, but this is not true: for a counterexample, found using computer simulations, see the graph g in Figure 3. Graph g is not bipartite as it has, e.g. triangle 4,5,9.

Other Centralities: Results and Conjectures
In this section we study centrality games for some measures that appear to satisfy none of Axioms 1,2,3: eccentricity centrality, random walk betweenness and eigenvector centrality.
First, we show that eccentricity centrality is very close to obeying Axiom 2: Lemma 3. Let g be a network, i a node in g and j another node such that ij ∈ g. The following are true: -If j ∈ Conn(i) then EC(i, g + ij) ≤ EC(i, g).
-If j ∈ Conn(i) then EC(i, g + ij) ≥ EC(i, g). The inequality is strict iff j is on all shortest paths in g to all vertices k that are farthest from i.
In spite of this result, the structure of APSN for eccentricity centrality games is quite different from the one for centrality games with measures satisfying Axiom 2: Theorem 7. All vertices in connected components of size at least three of an APSN have degree at least two. On the other hand all connected, eccentricityone graphs with min. degree 2 and at least two nodes with degree at most n − 2 are APSN. There exist (Fig. 4) APSN with eccentricity two. We weren't able to obtain a full characterization of APSN in this case, or analytical results for random walk betweenness and eigenvector centrality. However, computer simulations suggest that the following statements are true: Conjecture 1. For random walk betweenness centrality the only APSN are the empty graph ∅ n and the complete K n .
As for eigenvector centrality, although it seems not to have any monotonicity properties, experimental evidence is consistent with the following conjecture, that seems to situate this measure together with the monotonic ones: Conjecture 2. The complete graphs K n are the only asymptotically pairwise stable networks for eigenvector centrality.
8 Models with Truncated Centralities: Universality, Existence, Inference So far we have assumed that agents are unrestricted optimizers: they increase their centrality, subject to maintaining reasonable costs for their direct contacts. In reality, agents' utilities may be subject to diminishing returns: the marginal benefit from increased centrality diminishes (or even plateaus) beyond a point. A simple way of incorporating this observation into the model is via the following: Definition 7. Given centrality measure C and threshold θ, the θ-truncation of C is the centrality C θ defined by Note that for θ = ∞ (or just a large integer) we get the original utility. So truncations really extend our previous framework.
This simple variation has a profound effect on APSN: the following result first shows that truncation makes the model universal. Then we give a condition for recognizing APSN in games with increasing measures.
Theorem 8. The following are true: a). For every network g and family of increasing centralities C i there exist thresholds (θ i ) s.t. g is an APSN for the truncated centrality game with thresholds θ i . b). On the other hand, if agents' original centrality measures are all increasing, then for all families (θ i ) of thresholds, the APSN for the truncated centrality games with thresholds θ i , if they exist, can be characterized as the graphs with "Pareto optimal centralities", i.e. graphs h satisfying the following properties: c). APSN exist in all truncated centrality games with linear centralities. d). Consider a truncated centrality game with regular centralities (C i ) and nonnegative thresholds (θ i ).

note that the left-to-right implication is trivial). Then APSN exist for such games.
In spite of the previous result, we can still talk about learning agent utility functions. However, now we will not want to learn agent centralities (which we will, in fact, assume known), but agent thresholds. The learning model we will assume is a type of oracle learning Angluin (1988). In our case oracle queries are pairs (g, i) consisting of a network g and an agent index i. Given query (g, i) the oracle will either reply with an APSN h such that C i [h] > C i [g], or with "NONE", in the case such an APSN h does not exist.
Thresholds may fail to be identifiable in this model. One reason is the coarse resolution of our model : for instance, any values between two consecutive integers (e.g. 2.3 and 2.7) are completely equivalent as thresholds for degree centrality, since degrees in graphs are integral, and jumps in centrality (as a result of an edge flip) have a magnitude at least one. Also, the fact that (consistent with the model in our Theorem 4) we only get APSN as oracle answers may further impede the precision identification of θ i . One such "bad" case is when for all APSN g, C i [g] < θ i : in this case all estimates provided by the oracle on the value of the threshold are too low. Nevertheless we can prove the following result that, in a sense, provides the best we can hope for: a numerical interval (arising from a single edge flip) encompassing the threshold value: Theorem 9. Given an agent i, assume that there exists an APSN h with θ i ≤ C i [h]. Then there exists an algorithm that uses oracle queries and outputs an APSN g and an edge ij ∈ E(g) such that If C i is a linear centrality than this algorithm runs in polynomial time.

Related Literature
The area of network games is quite large, and a comprehensive survey is impossible. We list here two such overviews: the first one, most relevant to our interests, is due to Jackson (2005). Another one with an algorithmic bent is due to Tardos and Wexler (2007). The model that we are concerned with is a variant of the symmetric connection model Jackson and Wolinsky (1996) (see also Jackson (2008)). Some notable subsequent work includes Dutta and Mutuswami (1997); Jackson and Watts (2002); Gilles, Johnson, and others (2000). For an alternative model see Bala and Goyal (2000).
A lot of related work exists in the theoretical computer science literature: for example, Fabrikant et al. (2003) (and a whole host of papers that extend this model) consider a game where edges are added at the incentive of one of the endpoints. In contrast, our model takes a pairwise perspective, similar to Jackson and Wolinsky (1996). Other relevant work in this direction includes Hopcroft and Sheldon (2008), who discuss an oriented model in which nodes have control over outgoing edges. There is no cost for changing their links, and their purpose is to increase their Pagerank. They show that the Nash equilibria in this game have a fairly sophisticated structure (see also Chen et al. (2009)). Undirected versions of this game have been studied as well (Avis, Iwama, and Paku, 2014). On the other hand Avin et al. (2018) prove that preferential attachment models can be seen as Nash equilibria of some network games.
Other related work comes from the sociology literature Hummon (2000); Buskens and Van de Rijt (2008); Narayanam and Narahari (2011). For instance, in the Buskens and Van De Rijt model every node strives to fill "structural holes" (including lack of connnectedness) between nodes. This is somewhat analogous to maximizing betweenness, but the precise model (and the results) are different.
Our model allows heterogeneity in agents' utilities, corresponding to distinct measures of centrality. Heterogeneous network formation models have been studied previously, e.g. Galeotti, Goyal, and Kamphorst (2006).
Finally, several papers (e.g. Crescenzi et al. (2016); Bergamini et al. (2018)) have treated the problem of improving the centrality of a node by adding or removing links. Our work is different in several respects: first of all, in our setting all agents aim to improve their respective centralities. Second, in our model maintaining a link has a (small) cost.

Conclusions and Possible Extensions
We have shown that our models can accommodate a wide range of agent centrality objectives. Still, we do not see our results as adequate enough yet for the analysis of real-life networks. They have, instead, more of a proof-of-concept nature, showing that realistic network topologies could arise from strategic models of centrality maximisation, and could conceivably be made more realistic in many ways. Some variations (we believe) worth investigating are listed below: Probabilistic edge addition/removal: In real life an edge may only form with some probability even though both agents would benefit from it. Studying such a variation would be interesting, especially as it could produce networks with core structures that are dense but not quite complete. Strong and weak links, forced links, affiliation models: In the version that we have discussed all the links are weak links. A natural extension allows for both strong and weak links. This would entail using two types of costs: fixed, constant costs for the strong links, small ("ǫ") costs for weak links. A second, orthogonal, distinction that could be useful is that of forced versus free links. Forced links may be a consequence of affiliation: people meet as the result of joining the same clubs. A possibly relevant model is the social effort model of Borgs et al. (2011). Another one is the social clubs model of Fershtman and Persitz (2018). For centrality in affiliation networks see Faust (1997).

Manipulating link strength:
In such a scenario presumably the agent could manipulate the strength of the link. Whether to completely sever a link is a different decision. Further extensions could incorporate such decisions. Tagged networks: One possibility is that agents have a tag and care about the tags of their neighbors/components. The most natural model is that they care about their neighbors, like in Schelling's segregation model. Spatial agents: Agents interaction may result from placement in space. A standard reference for the spatial version of the connection model is Gilles, Johnson, and others (2000). Multilayer networks: Sometimes (e.g. Dickison, Magnani, and Rossi (2016)) link formation may encompass multiple, correlated, link types. E.g. two coworkers may end up being friends as well. It would be interesting to formulate multilayer models of network formationá la Jackson-Wolinsky. Overlapping community structure: networks may have overlapping communities. For centrality in such models see Szczepanski et al. (2014); Tarkowski et al. (2016); Gupta, Singh, and Cherifi (2016); Ghalmane et al. (2019). Dynamic models: Finally, our concepts of network stability are steady-state concepts. It would be interesting to study the emerging networks in dynamic models of network formation with a similar philosophy.
Finally, our work leaves a large number of issues open: we list, for instance, only one of them: can one define (truncated) centrality games for which APSN fail to exist ?
so closeness centrality satisfies Axiom 2. For random walk closeness centrality a fairly similar proof works: First consider the case j ∈ Conn(i). Then the expected hitting times of nodes H ki of nodes k ∈ Conn(i) do not change as a result of adding edge ij. Indeed, a random walk started in Conn(i) cannot reach j without reaching i.
On the other hand in the formula of random walk closeness centrality we get terms corresponding to the new k ∈ Conn(j) that can now reach i as a result of adding edge ij.
Consider now the case when j ∈ Conn(i). Then it is true that H ′ ki ≤ H ki for every k ∈ Con(i) Lovász et al. (1993). Therefore C i (g + ij) ≥ C i (g). In fact the inequality is strict. We did not find a reference to quote, but the derivation is very easy: from elementary considerations. Let, indeed N (i) = {n 1 , . . . n p }. We have: where in the right-hand side X (l,s) n+1,v is the event that at time n + 1 the random walk (run in graph h = g \ {i}) is in state v after having been before l times in j and s 1 , s 2 , . . . s p times in n 1 , v 2 , . . . , n p .
When adding an edge from j to i we get a corresponding formula: The difference between the two formulas lies in the factor (1 − 1 deg(j)+1 ) l in the second product. This is because in g + ij we also have to condition on the walk not going from j to i in the first n steps.
For large enough n, P r[T ′ k,i > n] < P r[T k,i > n]. So

Proof of Lemma 2
The first part is easy: some new shortest paths form between previously disconnected vertices, and all of them pass through i. All other shortest paths are not affected. Hence betweenness centrality strictly increases by at least 1, unless i was an isolated node (and hence there is no newly connected pair s, t. Consider now two nodes s, t and let's add missing non-bridge edge ij. This has the following possible effects: -Case 1: The distance between s, t strictly decreases. Then all the (new) shortest paths betweeen s, t must pass through edge ij, i.e. through i. The fraction attributable to s, t in the betweenness centrality of i becomes 1, which is at least the corresponding fraction before adding edge ij.
-Case 2: The distance between s, t stays the same. Then all previous shortest paths remain shortest paths. On the other hand, by adding edge ij one may add c ≥ 0 new shortest paths between s, t that use the edge ij. Since, for a ≤ b and c ≥ 0, a+c b+c ≥ a b , the fraction corresponding to s, t in the formula for the betweenness centrality of i weakly increases in this case as well.

Proof of Theorem 2
Proof. Let H be an APSN.
The formula for agents' utility is: Consider a pair ij ∈ g, and let h = g + ij.
Thus adding edge ij to g is an improving move for i iff

Proof of Lemma 3
Since ij is a bridge edge, new nodes are reachable from i by adding ij (those of the connected component of j in g), hence the maximum distance from i cannot decrease.
The second statement is equally simple: by adding an edge within a connected component shortest path distances cannot but decrease. So eccentricity (weakly) increases.
14 Proof of Corollary 1 We need the following simple Lemma 4. Let g be a network and ij ∈ E(g). Then removing edge ij from g is an improving move Proof. Removing edge ij is an improving move iff for at least one of the two nodes i, j its betweenness centrality stays the same when removing the edge. In this case adding edge ij to h = g − ij is not an improving move and viceversa: if adding edge ij to h is not an improving then one of i, j has the same betweenness centrality in g as in h, hence removing edge ij is an improving move in g.
By definition, adding edge ij to h is not improving Consider now a sequence a 1 > a 2 > . . . > a p > a p+1 = 1 be a sequence of integers such that a i − 1 > f (a i+1 − 1) for all i = 1, . . . , p. We first need to prove that all graphs of type K a1 + K a2 + . . . + K ap + lK 0 , l ≥ 0, are APSN. This is easy, by applying points a),b),c) of the theorem: let, indeed, y, z be nodes in the same clique K ar , 1 ≤ r ≤ p. We need to show that removing edge yz is not an improving move. Since they are in the same clique, the degrees of y, z are both equal to a r − 1. Since a r − 1 ≤ f (a r − 1) (because a r ≥ 2 and f (x) ≥ x for x ≥ 1), the desired conclusion follows by Lemma 4.
Let now y, z be nodes in different cliques, y ∈ K ar , z ∈ K as , a r > a s . We have deg(y) = a r − 1 > f (a s − 1) = f (deg(z)). By the definition, adding edge yz is not an improving move.
Since 0 > f (0) = −1 connecting any isolated node to any other node is not an improving move. So g is an APSN.
Conversely, let g be an APSN. By applying points a) and b) of the Theorem, we get that g has edges between every two vertices whose degrees are in the same interval [n * i , n * i−1 ], where by convention n * 0 = m. To infer the fact that g has the structure claimed in the corollary we need to prove that no other edges are present. Point c) of the theorem excludes edges between node whose degrees are not in the same interval.
The only potential trouble is that there might be a node x of degree n * i who is connected with nodes whose degrees are in both intervals [n * i+1 , n * i ] and [n * i , n * i−1 ], thus "joining two cliques". We will show that something like this doesn't happen by induction on i.
Case i = 1: Let z be a node of maximum degree m. Let A be the set of nodes with degree in the range [n * 1 , n * 0 ]. Then all the nodes in A are connected to each other. z is not connected to any node outside A. If there were some other node w in A that is connected to a node outside A then w would have degree higher than m, a contradiction. Hence nodes in A form a connected component that is a clique.
The induction step: Assume we have obtained l−1 connected components that are cliques of size a 1 > a 2 > . . . > a l−1 satisfying the condition a i − 1 > f (a i+1 − 1) for i = 1, . . . , l − 2. Applying the reasoning in the induction case i = 1 to the remaining graph we obtain a connected component of size a l that is a clique. Furthermore a l−1 − 1 > f (a l − 1), since nodes in the l'th clique component are not connected to those in the l − 1'st component.
It is possible that the tail of the resulting sequence a 1 , . . . , a s is composed of components of size 1, that is isolated nodes. The required condition is satisfied,

Proof of Theorem 7
Assume there was a node p of degree 1. Let q be the unique neighbor of p. The degree of q must be at least two, otherwise the connected component of q would contain two vertices. Then q's eccentricity would not change if removing the edge pq, so q has an incentive to remove edge pq.
The second part is easy as well: Consider an eccentricity-one APSN g. The eccentricity of the nodes in the center is one, i.e. center nodes are connected to all nodes.
Suppose we remove some edge ij. As the minimum degree of the graph is two and its eccentricity is one, this removal does not disconnect the graph: if it did then ij would be a bridge edge, and since i, j have degree at least two, the eccentricity of the graph would be at least three.
Thus the eccentricity of nodes i, j goes from one to two, making their utility decrease for small enough costs. So the nodes i, j do not have any incentive to remove their edge.
Suppose there are two unconnected nodes i, j. Nor do any two non-central nodes have any incentive to connect: there's still going to be another non-central node keeping their eccentricity to two. Thus the network is APSN.

Proof of Theorem 8
Proof.
a. Let θ i = C i [g]. We claim that g is an APSN with respect to the truncated centrality game with centralities C i and thesholds θ i .
Indeed, consider an edge ij of g. Nodes i, j don't want to drop edge ij, since their current centrality values are θ i , θ j while, by Axiom 1, their centralities would decrease below these values if they dropped ij.
Let now i, j be vertices such that ij ∈ g. Since their current centrality values are θ i , θ j (at the threshold), adding edge ij would not increase their truncated centralities, while incurring the extra (positive) cost of edge ij. So adding edge ij is not an improving move. b. First, by essentially repeating the proof at point a., it is easy to see that graphs with Pareto optimal centralities are APSN.
The opposite direction is equally easy: consider an APSN h and two vertices i, j. If ij ∈ E(h) then adding edge ij must not be an improving move for one of i, j. Since C i , C j are increasing, the only possibility is that C i [h] ≥ θ i (so that adding edge ij does not increase the truncated centrality of i and, in fact, decrease its utility, because of the extra cost of edge ij) or, similarly, C j [h] ≥ θ j .
Consider now the case when ij ∈ h. Because centralities are increasing and removing edge ij is not an improving move, removing ij must strictly decrease truncated centralities for both nodes i, j. This is only possible if the centralities of i, j in the resulting network l satisfy C i [l] < θ i and C j [l] < θ j .
c. First of all, a comment about the result of the previous section: it does not establish the existence of APSN, since it is not clear that the conditions in the characterization are actually feasible. This is what we show next: prove the existence of a network that satisfies them.
For games with truncated linear centralities we will prove the existence of APSN as follows: Sort the edges in decreasing weight order w e1 ≥ w e2 ≥ . . . ≥ w e ( n 2 ) . Consider the following algorithm: start with the empty graph g = ∅ n .
for i = 1 to n 2 : let e i = (a, b).
if C a [g] < θ a and C b [g] < θ b : g = g ∪ e i return g.
We claim that g is an APSN. Indeed, none of the missing edges could be added because the condition is false: So if ab ∈ E(g) then C a [g] ≥ θ a or C b [g] ≥ θ b at the moment when edge at was considered for inclusion. Since centralities only increase during the algorithm, the condition is valid at the end of the algorithm as well.
On the other hand if ab ∈ E(g) then at the moment node a had its centrality ≥ θ a no more edges adjacent to a are added anymore. Since edges are in decreasing order, removing any edge adjacent to a reduces the centrality of a at least as much as the last added edge, thus bringing the centrality of a below θ a . A similar argument works for node b.
d. To prove the existence of APSN for truncated centrality games satisfying the additional conditions in the hypothesis, consider a system of nonnegative thresholds θ i . Let G be the set of networks g such that C l [g] ≤ M l for every vertex l. G is nonempty, since it contains the empty graph on n vertices.
Let h be an edge-maximal member of G. We claim that h is an APSN. To prove this, will use the characterization of APSN as networks with "Pareto optimal centralities".
The second condition in this characterization is satisfied: indeed, assume that ij ∈ E(h). Observation 2. In the conditions of point d., the reciprocal is also true: APSN are maximal edge-members of the set G.

Proof of Theorem 9
Assume that θ i > C i [∅ n ], otherwise the result is trivial. The algorithm is the obvious one: start with the empty graph g = ∅ n .
while (oracle answer is not NONE): query the oracle on pair (g, i).
let h be the oracle answer set g = h return g.
Let g be the APSN produced by the algorithm. Clearly, θ i ≤ C i [g], since the algorithms returns an APSN with the highest centrality of i which is, by the hypothesis, at least θ i . We claim that for every edge ij ∈ E(g), C i [g − ij] < θ i . Indeed, if this were not the case, then i would have an incentive to drop edge ij, since its truncated centrality would not decrease, while its edge cost would.
So every edge adjacent to i is a good answer.
In the case of linear centralities, the centrality of each node is integral, so any oracle step increases the centrality of i by at least one. But the centrality of i is upper bounded by the sum k w i,k , so the algorithm runs in polynomial time in the problem size.
Note: we assumed in this proof that integers w i,k are written in unary. Otherwise we would have a pseudo-polynomial/NP-complete complexity distinction similar to that of the knapsack problem, depending on the representation.