Paper deep dive
A Network Formation Game for Katz Centrality Maximization: A Resource Allocation Perspective
Balaji R, Prashil Wankhede, Pavankumar Tallapragada
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 93%
Last extracted: 4/10/2026, 1:57:26 AM
Summary
This paper introduces a network formation game where agents maximize their Katz centrality by allocating constrained resources to outgoing edges, subject to topological constraints defined by an underlying graph. The authors characterize Nash equilibrium networks, demonstrate that sequential best-response dynamics (BRD) converge to these equilibria, and show that equilibrium networks exhibit hierarchical structures and sparsity, with centralities proportional to budgets in complete topologies.
Entities (4)
Relation Signals (3)
Agents → maximize → Katz centrality
confidence 100% · agents seek to maximize their influence by allocating constrained resources... we use Katz centrality to model agents' influence
Best-Response Dynamics → convergesto → Nash equilibrium
confidence 95% · We show that it converges to the set of Nash equilibria under very mild assumptions.
Nash equilibrium → exhibits → hierarchical structure
confidence 90% · hierarchical networks form at Nash equilibria
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:In this paper, we study a network formation game in which agents seek to maximize their influence by allocating constrained resources to choose connections with other agents. In particular, we use Katz centrality to model agents' influence in the network. Allocations are restricted to neighbors in a given unweighted network encoding topological constraints. The allocations by an agent correspond to the weights of its outgoing edges. Such allocation by all agents thereby induces a network. This models a strategic-form game in which agents' utilities are given by their Katz centralities. We characterize the Nash equilibrium networks of this game and analyze their properties. We propose a sequential best-response dynamics (BRD) to model the network formation process. We show that it converges to the set of Nash equilibria under very mild assumptions. For complete underlying topologies, we show that Katz centralities are proportional to agents' budgets at Nash equilibria. For general underlying topologies in which each agent has a self-loop, we show that hierarchical networks form at Nash equilibria. Finally, simulations illustrate our findings.
Tags
Links
- Source: https://arxiv.org/abs/2604.03056v1
- Canonical: https://arxiv.org/abs/2604.03056v1
Trouble viewing inline? Open PDF directly →
Full Text
67,285 characters extracted from source content.
Expand or collapse full text
A Network Formation Game for Katz Centrality Maximization: A Resource Allocation Perspective Balaji R1, Prashil Wankhede1 and Pavankumar Tallapragada1 This work was partially supported by Science and Engineering Research Board under grant CRG/2023/008573.1 Balaji R, Prashil Wankhede and Pavankumar Tallapragada are with the Indian Institute of Science, Bengaluru, India. rbalaji, prashilw, pavant@iisc.ac.in Abstract In this paper, we study a network formation game in which agents seek to maximize their influence by allocating constrained resources to choose connections with other agents. In particular, we use Katz centrality to model agents’ influence in the network. Allocations are restricted to neighbors in a given unweighted network encoding topological constraints. The allocations by an agent correspond to the weights of its outgoing edges. Such allocation by all agents thereby induces a network. This models a strategic-form game in which agents’ utilities are given by their Katz centralities. We characterize the Nash equilibrium networks of this game and analyze their properties. We propose a sequential best-response dynamics (BRD) to model the network formation process. We show that it converges to the set of Nash equilibria under very mild assumptions. For complete underlying topologies, we show that Katz centralities are proportional to agents’ budgets at Nash equilibria. For general underlying topologies, in which each agent has a self-loop we show that hierarchical networks form at Nash equilibria. Finally, simulations illustrate our findings. I INTRODUCTION Many real-world systems are fundamentally networked, with outcomes determined not only by agents’ actions but also by the structure of interactions among them; importantly, this structure often emerges endogenously through strategic decisions. Network formation games provide a natural framework to study how self-interested agents choose connections and allocate limited resources to maximize utility, which may depend on access to information, influence, or resources. This perspective is particularly relevant in social and information networks, financial systems, and communication or collaboration networks, where links are formed under costs and constraints. In this work, we model strategic network formation in which agents allocate limited resources to form connections so as to maximize their influence in the network, measured via Katz centrality. Literature review Network formation games have been widely studied over the years across a variety of application domains. For instance, the work [15] analyzes the stability of social and economic networks from a game theoretic perspective. A non-cooperative model of social network formation, in which agents form connections based on a trade-off between the rewards and costs of forming and severing links, was proposed in [1]. Research [11] proposes a network formation game to study the emergence of hierarchical networks in groups contaning consensual and non-consensual agents. The paper [16] surveys models of undirected network formation and also studies their structure and efficiency. The works [7, 8] study pairwise stability of Nash equilibirium in network formation games. Network centrality measures are used to quantify the importance or influence of individual nodes within a network. We refer the reader to [19, 6] for definitions and introductions to commonly used centrality measures. The work in [24] considers a network formation game, wherein each player’s utility function is a weighted sum of “Cobb-Douglas” functions and the weights are commonly agreed valuations of the players. For this game, the paper analyzes the relationship between the Nash equilibria and various centrality measures. In the present work, we consider the well-known Katz centrality, originally proposed in [17], to model agents’ utilities in the network formation game. Katz centrality finds widespread application in various domains, such as influence maximization in social networks [23], consensus protocols [22], opinion dynamics [12], the characterization of Nash equilibria in Cournot games [5], and online social networks [21]. Furthermore, a control-theoretic perspective of Katz centrality was proposed in [25]. Several works adopt a centrality-maximization perspective in network formation games. The paper [28] proposes a game-theoretic model in which each agent aims to maximize its relative Katz centrality and the size of the network, while incurring costs for link formation. The work [4] introduces a network formation model where each agent seeks to maximize its betweenness centrality subject to budget constraints. The work in [20] proposes a game, in which each agent purchases outgoing links under a budget constraint to minimize the sum of preference-weighted distances to other nodes. The paper [11] studies a network formation game in which agents’ utilities depend on their (out) degree centralities. A dynamic model of network formation, in which agents seek to maximize their Bonacich centrality and which converges to nested split graphs, was proposed in [18]. The work [9] employs Best-Response Dynamics (BRD) to analyze network formation among agents aiming to maximize their Bonacich centrality. The paper [10] proposes a finite potential game for PageRank centrality maximization, in which asynchronous BRD converges to a Nash equilibrium in finite time. The work [13] studies the effect of deviator rules on the efficiency of Nash equilibria reached under BRD in network formation games. Research [3] uses the so-called double best-response dynamics to model network formation in wireless networks, showing that it generates more efficient networks compared to algorithms based on standard best-response dynamics. On a slightly related note, papers such as [2, 29, 14, 27, 26] model network formation using random processes, without the context of a game, and analyze properties of network topologies that arise from such processes. Contributions 1. To the best of our knowledge, our work is the first to model a network formation game for Katz centrality maximization. We view the game as one of strategic resource allocation by the agents. Each agent can form outward weighted links only to the agents that are out-neighbors in an underlying graph topology. The weight allocations by an agent are also subject to a hard budget constraint. We also use the solution concept of Nash equilibria which is more robust than pairwise stability. 2. We show the mutual reinforcement property of the Katz centrality, that is better responses of an agent do not reduce the centrality of other agents in the network. Hence, unilateral better responses at Nash equilibria are still Nash equilibria. This property also results in all Nash equilibria having the same agent centralities. We also show that there are Nash equilibrium networks that are sparse, that is where every agent has exactly one outgoing link. Under complete underlying topologies, we show that Nash equilibrium centralities are proportional to the agent’s budgets. When the underlying topology allows for self-loops, agents influence neighbours with higher centrality at Nash equilibrium. Hence a hierarchical structure emerges in the condensation graph of Nash equilibria where all agents in a strongly connected component have the same centrality and the sinks have the highest centralities, thereby, containing the most influential agents in the network. 3. Finally, we propose a best response dynamics for this game and show that it converges to the set of Nash equilibria. The convergence is aided by the mutual reinforcement property and the fact that best responses result in networks where agents exhaust their bounded budgets on neighbours with the highest centrality. 4. Comparatively, in [28], the players seek to maximize their relative Katz centrality and the size of the network and incur a cost for formation of unweighted links. Then, the paper does a static equilibrium analysis of the game using the notion of pairwise stability. [24] studies a network formation game and analyzes various centralities (including Katz centrality) of the nodes in the equilibrium networks. Literature contains works wherein there is a cost to link formation, such as in [11, 28] or a constraint on the number of links a player can form as in [10]. The budget constraints on link formation in our work are similar to those in [24, 4, 20]. To the best of our knowledge, there is no previous work in the literature that imposes a constraint on which other agents an agent could form links with. Notation Throughout the paper, we use non-bold letters for denoting scalars, bold lowercase letters for denoting vectors, and bold uppercase letters for denoting matrices. The sets of natural numbers, real numbers, non-negative real numbers and positive real numbers are denoted by ℕ,N,, ≥0 and >0, respectively. For any vectors ∈ℝnw ^n and i∈ℝnx_i ^n, wjw_j and xijx_ij denote their jjth elements, respectively and supp(i):=j∈1,…,n,|,xij≠0supp(x_i):=\j∈\1,…,n\,|,x_ij≠ 0\. Let 0 and 1 denote the vectors (of appropriate dimension) with all zero and all one elements, respectively. Let nI_n denote the n dimensional identity matrix. For any matrix ∈n×nA∈^n× n, ρ()∈ℝ≥0ρ(A) _≥ 0 denotes its spectral radius. For any vector ∈ℝnw ^n, ⊤w denotes its transpose and () diag(w) denotes a diagonal matrix with w as its main diagonal. Let ie_i denote the i th standard basis vector of ℝnR^n. For any a∈a∈, |a||a| denotes its absolute value. For a collection of sets ii∈1,…,n\S_i\_i∈\1,…,n\, their Cartesian product is given by ⨉i=1ni _i=1^nS_i. The empty set is denoted by ∅ . ∙ Basic graph theory Let :=(,ℰ,) G:=(V,E,A) denote an arbitrary graph (or network), where V is the set of nodes, ℰE is the set of edges, and ∈n×nA∈^n× n is the corresponding adjacency matrix with row i and column j entry wij∈w_ij∈ denoting the edge weights. The graph G is said to be directed or digraph if the adjacency matrix is not necessarily symmetric, whereas it is undirected if =⊤A=A . For any ∈n×nA∈^n× n, a directed edge from node i to node j exists, denoted by (i,j)∈ℰ(i,j) , if and only if wij≠0w_ij≠ 0. For undirected graphs (i,j)∈ℰ⇔(j,i)∈ℰ(i,j) (j,i) . A graph G is weighted if the entries of A can take arbitrary real values. It is unweighted if A is a binary matrix with elements in 0,1\0,1\ such that (i,j)∈ℰ(i,j) if and only if wij=1w_ij=1. For any graph G, the out-neighbor set of any agent i∈i is denoted by i():=j∈∣wij≠0⊆N_i( G):=\j w_ij≠ 0\ . In a graph G, a (directed) walk of length (l−1)(l-1) from a node i1∈i_1 to any node il∈i_l is a sequence of nodes i1↦i2↦…↦ili_1 i_2 … i_l such that (is,is+1)∈ℰ,∀s∈1,2,…,l−1(i_s,i_s+1) ,\ ∀ s∈\1,2,…,l-1\. A walk is said to be simple if no node appears more than once, except possibly when the initial node coincides with the terminal node; in this case, the walk is called a cycle. An undirected graph is connected if there exists a walk between any two nodes. A digraph ′=(′,ℰ′) G =(V ,E ) is a subgraph of a digraph =(,ℰ) G=(V,E) if ′⊆V and ℰ′⊆ℰE . The subgraph of (,ℰ)(V,E) induced by ′⊆V is the digraph (′,ℰ′)(V ,E ), where ℰ′E contains all edges in ℰE between two nodes in ℰ′E . A digraph G is said to be strongly connected if there exists a directed walk from any node to any other node. It is said to be weakly connected if the undirected version of the digraph is connected. A subgraph ′ G of G is called a Strongly Connected Component (SCC) if ′ G is strongly connected and no subgraph of G that strictly contains ′ G is strongly connected. A Weakly Connected Component (WCC) is defined similarly. ∙ I Modeling and Problem Setup Consider a set :=1,…,nV:=\1,…,n\ of n agents that seek to maximize their influence in the network by choosing their social connections subject to a fixed resource budget. We first introduce the resource constraints. We then define an agent’s Katz centrality, which represents the agent’s overall influence in the network. Finally, we describe the resulting network formation game and the process of network formation itself. Resource allocation profiles, budget constraints, underlying topology and agents’ Katz centrality We model the action or strategy of an agent in the network formation game as one of allocating a limited resource to the weights of its outgoing edges in the network. In particular, we denote the allocation profile of any agent i∈i by i:=[wi1,…,win]⊤∈ℝnw_i:=[w_i1,…,w_in] ^n, where the element wijw_ij represents the resource (such as time, money, etc.) allocated by agent i to agent j. Let :=[1⊤,…,n⊤]⊤∈n×nw:=[w_1 ,…,w_n ] ∈^n× n denote the allocation profile of all agents with iw_i as the ithi^th subvector. When, we want to view the allocation profile from the perspective of agent i∈i we write it as =(i,−i)∈n×nw=(w_i,w_-i)∈^n× n, where i∈nw_i∈^n is the allocation profile of agent i∈i and −i∈n(n−1)w_-i∈^n(n-1) is the allocation profile of all agents other than i. The allocation profile w induces a weighted graph ()==(,ℰ,) G(w)= G=(V,E,A) with the adjacency matrix ():=[1,…,n]⊤∈n×nA(w):=[w_1,…,w_n] ∈^n× n. Each agent has a limited budget Bi>0B_i>0 on the total resources that they can allocate. We further assume that the agents are constrained to allocate only to their social out-neighbors i(†)N_i( G ) in an unweighted digraph, called the underlying topology †=(,ℰ†,†) G =(V,E ,A ). This models topological constraints on agents such as communication limitations, geographical proximity, or pre-existing social relationships. Formally, the resource allocation constraint set for any agent i∈i is given by i(†):= _i( G ):= i∈≥0n|supp(i)⊂i,∑j∈i(†)wij≤Bi. \w_i∈^n_≥ 0 |supp(w_i) _i,\ _j _i( G )w_ij≤ B_i \. (1) Also, let (†):=⨉i=1ni(†)⊂≥0n2K( G ):= _i=1^nK_i( G )⊂^n^2_≥ 0. We call i∈i(†)w_i _i( G ) a feasible allocation of i. Henceforth, we omit the arguments of G, A, iN_i, iK_i and K for brevity whenever no confusion arises. Note that, for any feasible allocation profile ∈w , the unweighted version of the graph () G(w) is a subgraph of the unweighted graph † G . The allocation profile w then determines the network centralities of the agents, which we introduce next. The Katz centrality of any agent i∈i in a network () G(w) induced by an allocation profile =(i,−i)∈n×nw=(w_i,w_-i)∈^n× n is ci()=ci(i,−i):=∑k=1∞∑j∈δkwij(k),c_i(w)=c_i(w_i,w_-i):= _k=1^∞ _j δ^kw_ij^(k), (2) where δ∈(0,1/ρ(()))δ∈(0,1/ρ(A(w))) is the discount factor and wij(k)w_ij^(k) is the ijthij^th element of k()A^k(w), where recall that ()A(w) is the adjacency matrix of the weighted graph () G(w). An agent i’s Katz centrality (2) is the discounted sum of all (weighted) directed walks emanating from it in the network G. Intuitively, if wijw_ij measures the direct influence of i on j, and wij(k)w_ij^(k) denotes the k-hop indirect influence of i on j, then the Katz centrality in (2) quantifies the total influence of i on all agents in V by aggregating both direct and indirect influences. Here, the indirect influence is propagated through walks of arbitrary length, with longer walks discounted according to the discount factor δ. Moreover, δ∈(0,1/ρ())δ∈(0,1/ρ(A)) ensures that the infinite series in (2) converges. We impose the following standing assumptions on the underlying topology † G , resource parameters BiB_i’s and the discount factor δ, and justify it in the discussion that follows. (SA1) The underlying topology † G is such that i(†)≠∅,∀i∈N_i( G )≠ ,∀ i . ∙ (SA2) Bi<1,∀i∈B_i<1,∀ i and δ=1δ=1 in (2). ∙ Both (SA1) and (SA2) are made without loss of generality. If i(†)=∅N_i( G )= then i=∅K_i= i.e., there exists no feasible allocation for i. To show that there is no loss of generality in the assumption (SA2), let Bi>0B_i>0 be the budget of agent i∈i . Given any allocation profile ∈w , consider the allocation profile ¯:=δ w:= , with (1/δ)>maxi∈Bi(1/δ)> _i \B_i\. Thus, (¯)=δ()A( w)= (w). Then, letting ():=[c1(),…,cn()]⊤c(w):= [c_1(w),…,c_n(w) ] denote the stacked vector containing the centralities of all agents, note that ()=∑k=1∞δkk()=∑k=1∞k(¯).c(w)= _k=1^∞δ^kA^k(w)1= _k=1^∞A^k( w)1. (3) Moreover, the allocation profile ¯=δ w= , which induces ¯ A, satisfies the constraints in (1) with resource budget parameters B¯i=δBi<1 B_i=δ B_i<1. Due to this equivalence, there is no loss of generality in the Assumption (SA2). Viewing centralities of all agents together, as in (3), immediately yields the following result, which is useful in the subsequent analysis. Lemma I.1 (Interdependence between agent centralities.) Consider the Katz centralities defined in (2). Let ∈w be a feasible allocation profile, satisfying (1). Then, the Katz centrality of any agent i∈i in () G(w) satisfies ci()=∑j∈i(†)wij[1+cj()].c_i(w)= _j _i( G )w_ij [1+c_j(w) ]. (4) Proof: Let =()A=A(w). Then, from (3) and from Assumption (SA2), we can easily verify that ()=(n−)−1c(w)= (I_n-A )^-1A1. Thus, ()=[+()]c(w)=A[1+c(w)]. The claim now follows from the element-wise equalities. ■ Network formation game In this paper, we consider the strategic form game (†):=⟨,(i)i∈,(ci)i∈⟩G( G ):= , (K_i )_i , (c_i )_i among the set of agents V, with the strategy of agent i∈i being its allocation i∈iw_i _i and its utility function being its Katz centrality cic_i. We refer to G as the network formation game. The set of Nash equilibria of this game G is ℰ :=∗∈|∀i∈, :=\w^* \,\,|\,\,∀ i , ci(i∗,−i∗)≥ci(i,−i∗),∀i∈i. c_i(w_i^*,w_-i^*)≥ c_i(w_i,w_-i^*), _i _i\\,. (5) Thus, ∗∈ℰw^* if and only if i∗∈ℬℛi(−i∗)w_i^* _i(w_-i^*) for all i∈i , where ℬℛi(−i):=argmaxi∈ici(i,−i) _i(w_-i):= *argmax_w_i _ic_i(w_i,w_-i) is the set of best responses of agent i to −iw_-i. For a ∗∈ℰw^* , we refer to the graph (∗) G(w^*), or ∗ G^* for short when there is no confusion, as a Nash equilibrium network. Network formation process In this paper, we also study the process of the network formation itself. In particular, we consider sequential Best Response Dynamics (BRD) as the network formation process, which proceeds as follows. The process starts with an initial allocation profile (0)∈w(0) . At each time step k∈ℕk , an agent ik∈i_k is selected arbitrarily (randomly or otherwise) and the agent iki_k updates its allocation ik(k)w_i_k(k) by playing a best response to the allocation of the other agents −ik(k−1)w_-i_k(k-1), i.e., ik(k)∈argmax∈ikcik(,−ik(k−1)).w_i_k(k)∈ *argmax_x _i_k\>c_i_k(x,w_-i_k(k-1)). (6) We now briefly outline the main objectives of this work. Objectives For the proposed network formation game, our goal is to understand the relationship between Katz centralities and resources within a Nash equilibrium network. Furthermore, we seek to characterize the set of all Nash equilibrium networks and analyze the convergence of BRD to this set. Finally, we aim to identify the structural properties of these equilibrium networks—specifically their sparsity and hierarchy—for various underlying network topologies. I Analysis of the Game and Sequential BRD In this section, we analyze the network formation game G in detail. In particular, we investigate the existence and structural properties of Nash equilibria in the setting of resource-constrained network formation. We also analyze the convergence of BRD. We begin our analysis by establishing that, for any agent i∈i , a best response to any allocation −iw_-i of the other agents always exists. This ensures that the BRD in (6) is well-posed. We first provide an alternative representation of the Katz centralities (2), which will be useful in the subsequent analysis. Recall that the Katz centrality (2) of any agent i∈i in a graph G induced by an allocation profile =(i,−i)∈w=(w_i,w_-i) is given by the sum of all weighted directed walks of all possible lengths emanating from i. Thus, Assumption (SA2) allows us to rewrite cj()c_j(w), for any j∈j and for some i∈∖ji \j\, as follows cj() c_j(w) =∑m=1∞Sj,m,i′()+∑m=1∞Sj,m,i()[1+ci()], = _m=1^∞S _j,m,i(w)+ _m=1^∞S_j,m,i(w) [1+c_i(w) ], =:pji(−i)+qji(−i)[1+ci()], =:p_ji(w_-i)+q_ji(w_-i)[1+c_i(w)], (7) where Sj,m,i′()S _j,m,i(w) is the sum of all weighted directed walks of length m starting from node j that do not reach node i, and Sj,m,i()S_j,m,i(w) is the sum of all weighted directed walks of length m starting from node j that reach node i exactly once and terminate at i. Further, we define ∀i∈∀ i and ∀j∈∖i∀ j \i\ pji(−i):=∑m=1∞Sj,m,i′(),qji(−i):=∑m=1∞Sj,m,i() p_ji(w_-i):= _m=1^∞S _j,m,i(w),\ \ q_ji(w_-i):= _m=1^∞S_j,m,i(w) dji(−i):=pji(−i)+qji(−i)+1, d_ji(w_-i):=p_ji(w_-i)+q_ji(w_-i)+1, and qii(−i):=1,dii(−i):=1,∀i∈.q_i(w_-i):=1,\ \ d_i(w_-i):=1, ∀ i . Note that, since Sj,m,i′()S _j,m,i(w) only includes walks that do not pass through i and Sj,m,i()S_j,m,i(w) only includes walks that reach i exactly once and terminate at i, pji(−i)p_ji(w_-i), qji(−i)q_ji(w_-i) and dji(−i)d_ji(w_-i) are independent of iw_i and depend only on −iw_-i. Then, for any =(i,−i)∈w=(w_i,w_-i) , from (4), (I), we have ci(i,−i)=∑j∈idji(−i)wij1−∑j∈iqji(−i)wij.c_i(w_i,w_-i)= _j _id_ji(w_-i)w_ij 1- _j _iq_ji(w_-i)w_ij. (8) The following lemma gives a basic fact that we reuse later. Lemma I.1 Let ∈w . Then, 1−∑j∈iqji(−i)wij>0,∀i∈.1- _j _iq_ji(w_-i)w_ij>0, ∀ i . Proof: Consider any ∈w and any i∈i . If i=w_i=0 then the claim holds trivially. If i≠w_i 0 then from (2), Ci(i,−i)>0,∀−i∈−iC_i(w_i,w_-i)>0, _-i _-i. Since pji(−i)≥0p_ji(w_-i)≥ 0 and qji(−i)≥0q_ji(w_-i)≥ 0, pji(−i)+qji(−i)+1>0,∀j∈i∖ip_ji(w_-i)+q_ji(w_-i)+1>0,∀ j _i \i\. The claim now follows from (8). ■ We are now ready to state the next result, which establishes (among other things) that a best response allocation i∈iw_i _i to −i∈−iw_-i _-i always exists for any agent i∈i . Lemma I.2 (On best response set.) Let † G be a given underlying topology. Consider the network formation game G and any ∈w . For any agent i∈i , ℬℛi(−i)BR_i(w_-i) is non-empty, convex and Bij∈ℬℛi(−i),∀j∈argmaxk∈i(†)dki(−i)1−qki(−i)Bi.B_ie_j _i(w_-i),\ ∀ j∈ *argmax_k _i( G ) \ d_ki(w_-i)1-q_ki(w_-i)B_i \. Proof: Since −i∈−iw_-i _-i is a fixed parameter as far as ℬℛi(−i)BR_i(w_-i) is concerned, we will drop −iw_-i from most of the notation in this proof. Non-emptiness and single edge allocations in ℬℛi(−i)BR_i(w_-i): We first introduce a change of variables and rewrite the expression for ci(i,−i)c_i(w_i,w_-i) in (8) more concisely. Let fji:=dji1−qjiBi,zij:=(1−qjiBi)wij1−∑k∈iqkiwik,∀j∈. f_ji:= d_ji1-q_jiB_i,\ z_ij:= (1-q_jiB_i)w_ij1- _k _iq_kiw_ik, ∀ j . Now, notice from (8) that ci(i,−i)=∑j∈ifjizijc_i(w_i,w_-i)= _j _if_jiz_ij. Moreover, Lemma I.1 implies that (1−qjiBi)>0(1-q_jiB_i)>0 for all j∈ij _i. Further, ∑j∈izij=∑j∈iwij−Bi∑j∈iqjiwij1−∑j∈iqjiwij, _j _iz_ij= _j _iw_ij-B_i _j _iq_jiw_ij1- _j _iq_jiw_ij, from which we can reason that ∑j∈izij≤Bi _j _iz_ij≤ B_i iff ∑j∈iwij≤Bi _j _iw_ij≤ B_i. From these observations, we can say that (S1) If i∈iw_i _i then i∈iz_i _i and supp(i)=supp(i)supp(w_i)=supp(z_i). Next, observe that 11−∑j∈iqjiwij−∑j∈iqjizij1−qjiBi 11- _j _iq_jiw_ij- _j _i q_jiz_ij1-q_jiB_i =11−∑j∈iqjiwij[1−∑j∈iqjiwij]=1. = 11- _j _iq_jiw_ij [1- _j _iq_jiw_ij ]=1. We thus have the inverse map from iz_i to iw_i as wij=zij1−qjiBi+∑k∈iqkizik.w_ij= z_ij1-q_jiB_i+ _k _iq_kiz_ik. By similar arguments as above we can say that (S2) If i∈iz_i _i then i∈iw_i _i and supp(i)=supp(i)supp(w_i)=supp(z_i). Thus, the task of finding the best response set ℬℛi(−i)BR_i(w_-i) is equivalent to solving and transforming the set :=argmaxi∈i∑j∈ifjizijS:= *argmax_z_i _i _j _if_jiz_ij (9) back to the w space. The optimization problem in (9) is a linear program and given iK_i, we can say that Bij∈B_ie_j for all j∈argmaxj∈ifjij∈ *argmax_j _if_ji. Notice from the inverse map that if i=Bijz_i=B_ie_j then i=i=Bijw_i=z_i=B_ie_j. Hence, Bij∈ℬℛi(−i)B_ie_j _i(w_-i) for all j∈argmaxj∈ifjij∈ *argmax_j _if_ji. This proves the non-emptiness of and the existence of single edge allocations in ℬℛi(−i)BR_i(w_-i). Convexity of ℬℛi(−i)BR_i(w_-i): From (8), we can write ci(i,−i)=i⊤i1−i⊤ic_i(w_i,w_-i)= d_i w_i1-q_i w_i. Let ^i,¯i∈ℬℛi(−i) w_i, w_i _i(w_-i) be two best responses by agent i to −iw_-i. We thus have i⊤¯i=i⊤^i(1−i⊤¯i1−i⊤^i).d_i w_i=d_i w_i ( 1-q_i w_i1-q_i w_i ). Now consider i:=λ^i+(1−λ)¯iw_i:=λ w_i+(1-λ) w_i, with λ∈[0,1]λ∈[0,1]. So, ci(i,−i) c_i(w_i,w_-i) =i⊤[λ^i+(1−λ)¯i]1−i⊤[λ^i+(1−λ)¯i] = d_i [λ w_i+(1-λ) w_i]1-q_i [λ w_i+(1-λ) w_i] =i⊤^i[λ+(1−λ)(1−i⊤¯i1−i⊤^i)]1−i⊤[λ^i+(1−λ)¯i] = d_i w_i [λ+(1-λ) ( 1-q_i w_i1-q_i w_i ) ]1-q_i [λ w_i+(1-λ) w_i] =ci(i^,−i). =c_i( w_i,w_-i). Thus, i:=λ^i+(1−λ)¯i∈ℬℛi(−i)w_i:=λ w_i+(1-λ) w_i _i(w_-i), and hence ℬℛi(−i)BR_i(w_-i) is a convex set. ■ Lemma I.2 shows the non-emptiness and convexity of the best response set for any agent i∈i . Further there exist some best responses to −iw_-i wherein the entire resource budget is allocated to a single well-chosen agent j∈ij _i. The next result establishes certain properties of better responses. Recall that a better response of any agent i∈i to the allocations −i∈−iw_-i _-i of the other agents with respect to i∈iw_i _i is any allocation i∈iy_i _i such that ci(i,−i)≥ci(i,−i)c_i(y_i,w_-i)≥ c_i(w_i,w_-i). If the above inequality is strict, then iy_i is called a strict better response. We will use ℛi(i,−i)R_i(w_i,w_-i) and ℛis(i,−i)R_i^s(w_i,w_-i) to denote the sets of better responses and strict better responses with respect to i∈iw_i _i, respectively. Note that, in general, ℬℛi(−i)⊆ℛi(i,−i)BR_i(w_-i) _i(w_i,w_-i) and ℛis(i,−i)⊆ℛi(i,−i)R_i^s(w_i,w_-i) _i(w_i,w_-i). Moreover, whenever ℛis(i,−i)≠∅R_i^s(w_i,w_-i)≠ , it holds that ℬℛi(−i)⊆ℛis(i,−i)BR_i(w_-i) _i^s(w_i,w_-i). Lemma I.3 (On the better and best responses.) Let † G be a given underlying topology. Consider the network formation game G with Katz centralities given in (2). Define the function vi():=Bi[1+maxj∈ixj],∈ℝ≥0n.v_i(x):=B_i[1+ _j _ix_j],\ x ^n_≥ 0. (10) Then for any agent i∈i and =(i,−i)∈w=(w_i,w_-i) , 1. If i∈ℛi(i,−i)y_i _i(w_i,w_-i) then cj(i,−i)≥cj(i,−i),c_j(y_i,w_-i)≥ c_j(w_i,w_-i), ∀j∈∀ j . 2. i∈ℛis(i,−i)y_i _i^s(w_i,w_-i) if and only if ∑j∈i(yij−wij)[1+cj()]>0 _j _i(y_ij-w_ij)[1+c_j(w)]>0. 3. i∈ℬℛi(−i)w_i _i(w_-i) if and only if ℛis(i,−i)=∅R_i^s(w_i,w_-i)= if and only if ci()=vi(())c_i(w)=v_i(c(w)). Moreover, for any i∈ℬℛi(−i)w_i _i(w_-i), ∑j∈iwij=Bi _j _iw_ij=B_i and wij>0w_ij>0 implies j∈argmaxk∈ick(i,−i)j∈ *argmax_k _ic_k(w_i,w_-i). Proof: Consider an agent i∈i and an allocation profile ∈w . Recall the form of cj(i,−i)c_j(w_i,w_-i) from (I). Suppose i∈ℛi(i,−i)y_i _i(w_i,w_-i). Claim 1 now follows from the fact that qji(−i)≥0q_ji(w_-i)≥ 0 and pji(−i)≥0p_ji(w_-i)≥ 0, and that both are independent of iw_i. Next, for any i∈iy_i _i, observe from (4) and (I) that ci(i,−i)−ci(i,−i)=∑j∈i(yij−wij)[1+cj()]1−∑j∈iyijqji(−i).c_i(y_i,w_-i)-c_i(w_i,w_-i)= _j _i(y_ij-w_ij)[1+c_j(w)] 1- _j _iy_ijq_ji(w_-i). Claim 2 now follows from Lemma I.1. Next, notice by definition, i∈ℬℛi(−i)w_i _i(w_-i) if and only if ℛis(i,−i)=∅R_i^s(w_i,w_-i)= . From Claim 2, observe that for any feasible i∈iy_i _i, i∉ℛis(i,−i)y_i _i^s(w_i,w_-i) if and only if ∑j∈i(yij−wij)[1+cj()]≤0 _j _i(y_ij-w_ij)[1+c_j(w)]≤ 0. Equivalently, ℛis(i,−i)=∅R_i^s(w_i,w_-i)= if and only if maxi∈i∑j∈iyij[1+cj()]=∑j∈iwij[1+cj()]=ci() _y_i _i _j _iy_ij[1+c_j(w)]= _j _iw_ij[1+c_j(w)]=c_i(w), where the last equality follows from (4). Using the definition of iK_i given in (1), and since ci()≥0c_i(w)≥ 0 for all ∈w , it follows that the above linear program attains the optimal value maxi∈i∑j∈iyij[1+cj()]=Bi[1+maxj∈icj()] _y_i _i _j _iy_ij[1+c_j(w)]=B_i[1+ _j _ic_j(w)]. Claim 3 now follows from (10). Finally, from (10) and (4), it can be easily seen that Bi(1+maxj∈icj(i,−i))=∑j∈iwij[1+cj(i,−i)]B_i(1+ _j _ic_j(w_i,w_-i))= _j _iw_ij[1+c_j(w_i,w_-i)]. Since i∈iw_i _i and RHS ≤ LHS trivially, the above equality holds if and only if ∑j∈iwij=Bi _j _iw_ij=B_i and wij>0w_ij>0 implies j∈argmaxk∈ick(i,−i)j∈ *argmax_k _ic_k(w_i,w_-i). The proof is now complete. ■ Lemma I.3 provides the following insights. At a given allocation profile ∈w , if any individual agent chooses an allocation i∈ℛi(i,−i)y_i _i(w_i,w_-i), then it does not decrease the Katz centralities of the other agents. Thus, agent i choosing a better response does not penalize the other agents. The same holds for best response allocations i∈ℬℛi(−i)y_i _i(w_-i), since a best response is also a better response. The above result also helps us provide a necessary and sufficient condition for a network () G(w) induced by an allocation profile ∈w to be a Nash equilibrium network. Theorem I.4 (Characterization of Nash equilibria.) Let † G be a given underlying topology. Consider the network formation game G with Katz centralities given in (2). Let vi(⋅)v_i(·) be as defined in (10). Then, 1. ∗∈ℰw^* if and only if vi((∗))=ci(∗),∀i∈v_i(c(w^*))=c_i(w^*),∀ i . 2. For any agent i∈i , if wij∗>0w_ij^*>0 for some j∈i(†)j _i( G ) then ci(∗)=Bi[1+cj(∗)]c_i(w^*)=B_i[1+c_j(w^*)]. 3. ∃ an unique ∗∈ℝ≥0nc^* ^n_≥ 0 such that ℰ=∈∣()=∗NE=\w (w)=c^*\. Proof: By definition ∗=(i∗,−i∗)∈ℰw^*=(w_i^*,w_-i^*) if and only if i∗∈ℬℛi(−i∗),∀i∈w_i^* _i(w_-i^*),∀ i . Claim 1 now follows from Lemma I.3. If wij∗>0,j∈i(†)w_ij^*>0,j _i( G ), then from Lemma I.3, j∈argmaxk∈i(†)ck(∗)j∈ *argmax_k _i( G )c_k(w^*). Claim 2 follows from (10). Finally, let ():=[v1(),…,vn()]⊤v(x):=[v_1(x),…,v_n(x)] , where vi()v_i(x) is as defined in (10). For any ∈w , we know from (2) that ()≥c(w) 0. Thus, (⋅):ℝ≥0n→ℝ≥0nv(·):R^n_≥ 0 ^n_≥ 0. Consider any ,∈ℝ≥0nx,y ^n_≥ 0. Then ‖()−()‖∞ \|v(x)-v(y)\|_∞ =maxi∈Bi|maxj∈ixj−maxj∈iyj|, = _i B_i \\> | _j _ix_j- _j _iy_j |\> \, ≤maxi∈Bi‖−‖∞. ≤ _i B_i\|x-y\|_∞. The above implies that (⋅)v(·) is a contraction on ℝ≥0nR^n_≥ 0, by virtue of (SA2). Since (ℝ≥0nR^n_≥ 0, ∥⋅∥∞\|·\|_∞) is a complete metric space, by the Banach fixed point theorem, (⋅)v(·) has a unique fixed point ∗∈ℝ≥0nc^* ^n_≥ 0. From Claim 1, we know that i∗∈ℰw_i^* if and only if ((∗))=(∗)v(c(w^*))=c(w^*). Claim 3 now follows. ■ Claim 1 in Theorem I.4 states that the network (∗) G(w^*) induced by ∗∈w^* is a Nash equilibrium network if and only if the resulting centrality vector (∗)c(w^*) is a fixed point of the function (⋅)v(·). Claim 3 in Theorem I.4 further states that any two distinct Nash equilibrium networks (if they exist) yield the same Katz centralities. However, Theorem I.4 only guarantees the existence of ∗c^*. One can use the Banach fixed-point iteration to compute ∗c^*. The next result establishes a invariance property of ℰNE under BRD for any general underlying topology † G . Specifically, it shows that if an agent unilaterally switches to another best-response strategy, then the resulting network is still a Nash equilibrium network. Thus, no other agent has an incentive to deviate, as their centralities cannot be improved. Corollary I.5 (Invariance of ℰNE under unilateral best response deviations.) Let † G be a given underlying topology. Consider the network formation game G with Katz centralities given in (2). Let ∗=(i∗,−i∗)∈ℰw^*=(w_i^*,w_-i^*) . Suppose ∃i∈∃ i and =(i,−i)∈x=(x_i,w_-i) such that ci(∗)=ci()c_i(w^*)=c_i(x). Then, ∈ℰx . ∙ Proof: Under the stated assumptions, i∈ℬℛi(−i∗)x_i _i(w_-i^*). Also, i∗∈ℬℛi(−i∗)w_i^* _i(w_-i^*). Thus, from (I), we have that cj(∗)=cj(),∀j∈c_j(w^*)=c_j(x),∀ j . Hence, ()=(∗)c(x)=c(w^*). The result now follows from Claim 3 in Theorem I.4. ■ Finally, we conclude this section with the main convergence result of BRD. Theorem I.6 (Convergence of BRD to ℰNE.) Let † G be a given underlying topology. For a given initial network (0)∈w(0) , consider the sequential BRD (6) with an agent update sequence ikk∈ℕ\i_k\_k in which every agent in V updates infinitely often (i.o). Let (k)w(k) denote the network at time step k generated by this BRD. Then, the sequence of networks (k)k∈ℕ\w(k)\_k converges to ℰNE. Proof: Consider any (0)∈w(0) . Under the sequential BRD (6) with an agent update sequence ikk∈ℕ\i_k\_k in which each agent appears i.o, Lemma I.3 implies that, for every i∈i , the sequence ci((k))k∈ℕ\c_i(w(k))\_k , with (k)=(i(k),−i(k))w(k)=(w_i(k),w_-i(k)), is monotonically increasing. It is also bounded since ci(⋅)c_i(·) is continuous, (k)∈,∀kw(k) ,∀ k, and K is compact. Hence, ((k))k∈ℕ\c(w(k))\_k converges to some ∗∈ℝ≥0nc^* ^n_≥ 0. Now, observe that under (6), at any time step k∈ℕk , the agent iki_k chooses ik(k)∈ℬℛik(−ik(k−1))w_i_k(k) _i_k(w_-i_k(k-1)), and hence, from Lemma I.3, vik(((k)))=cik((k))v_i_k(c(w(k)))=c_i_k(w(k)). This implies that limk→∞(((k)))=(limk→∞((k)))=(∗)=∗, _k→∞v(c(w(k)))=v\! ( _k→∞c(w(k)) )=v(c^*)=c^*, where we have used the fact that vi(⋅),∀i∈v_i(·),∀ i , as defined in Lemma I.3, is continuous. The claim now follows from Theorem I.4 and its proof. ■ Remark I.7 (On the existence of Nash equilibrium network.) For any ∈w , let s():=i∈∣ℛis(i,−i)≠∅V_s(w):=\i _i^s(w_i,w_-i)≠ \. We can then consider the following modified BRD. Given any initial network (0)∈w(0) , at any time step k∈ℕk , choose an agent ik∈s((k−1))i_k _s(w(k-1)) and restrict the best response to ik(k)=Bikj∈ℬℛik(−ik(k−1))w_i_k(k)=B_i_ke_j _i_k(w_-i_k(k-1)), as established by Lemma I.2. One can then use the strictly monotone evolution of centralities under the modified BRD, along with the finiteness of possible networks due to the structure of the best responses above, to show convergence of this modified BRD to a Nash equilibrium in finite time. Hence, ℰ≠∅NE≠ . Since this modified BRD is not the focus of this paper, we omit the proof for brevity. ∙ IV About the Nash Equilibrium Networks In this section, we analyze the properties of Nash equilibrium networks under specific underlying topologies. We begin by considering the case where the underlying topology † G is complete. Theorem IV.1 (Properties of Nash equilibrium networks when † G is complete.) Consider the network formation game G with Katz centralities given in (2) and suppose that the underlying topology † G is complete. Define ℋ:=∈∣∀i∈,∑j∈i(†)wij=Bi,wij>0⇒Bj=BMH:=\w ∀ i , _j _i( G )w_ij=B_i,w_ij>0 B_j=B_M\ where BM:=maxi∈BiB_M:= _i B_i. Then ℋ=ℰ=∈∣ci()=Bi1−BM,∀i∈H=NE= \w c_i(w)= B_i1-B_M,∀ i \. Proof: Let the underlying topology † G be complete i.e., i(†)=,∀i∈N_i( G )=V,∀ i . We begin by proving the second equality. From Theorem I.4 and (10), we know that ci(∗)=Bi(1+maxj∈cj(∗)),∀i∈c_i(w^*)=B_i(1+ _j c_j(w^*)),∀ i . From here, we can easily reason that the centralities ci(∗)=Bi1−BM,∀i∈c_i(w^*)= B_i1-B_M,∀ i satisfy the above set of equations. We can also verify that ci(∗)=vi((∗))c_i(w^*)=v_i(c(w^*)). The result now follows from Lemma I.3 and Claim 3 in Theorem I.4 and its proof. In order to prove the first equality, let us define M:=i∈∣Bi=BMV_M:=\i B_i=B_M\. Let ∈ℋw and let () G(w) be the graph induced by it. It is easy to see that for any i∈Mi _M, wij>0w_ij>0 if and only if j∈Mj _M. Let MA_M denote the adjacency matrix of the subgraph of () G(w) induced 111The term “induced” is used here in the standard graph-theoretic sense. by MV_M. Then, M=BMA_M1=B_M1 and MA_M is strictly sub-stochastic by virtue of (SA2). This means that (−M)−1−=BM1−BM(I-A_M)^-11-1= B_M1-B_M1 and from (2), ci()=BM1−BM,∀i∈Mc_i(w)= B_M1-B_M,∀ i _M. Thus, for any j∉Mj _M, from Lemma I.1 we get cj()=Bj1−BMc_j(w)= B_j1-B_M. From the second equality of the claim, we get that ∈ℰw . Next, suppose ∈ℰw . Based on the second equality of the claim, it follows that, ci()=Bi1−BM,∀i∈c_i(w)= B_i1-B_M,∀ i . Hence, from Lemma I.3, ∑j∈i(†)wij=Bi _j _i( G )w_ij=B_i and for any i,j∈i,j such that wij>0w_ij>0, we have cj()=maxk∈ck()=BM1−BMc_j(w)= _k c_k(w)= B_M1-B_M. Thus, Bj=BMB_j=B_M. This implies ∈ℋw . ■ From Theorem IV.1, we see that when the underlying topology G is complete, then at any Nash equilibrium network ∗ G^* induced by ∗∈ℰw^* , for any two agents i,j∈i,j , ci(∗)≤cj(∗)c_i(w^*)≤ c_j(w^*) if and only if Bi≤BjB_i≤ B_j. Theorem IV.1 also shows that when the underlying topology is complete, every agent allocates their entire budget to the agent with the maximum budget in a Nash equilibrium network. For example, this means that in the case where there is only one agent with maximum resources, i.e., |M|=1|V_M|=1, the Nash equilibrium network corresponds to a star network, with every other agent allocating their entire budget to that particular agent, which consequently has the highest centrality. We now consider general underlying graph topologies, albeit with the following assumption. (A1) (All agents have self-loops in the underlying topology.) For any agent i∈i , i∈i(†)i _i( G ). ∙ Lemma IV.2 (Agents connect only to nodes with centrality at least as high as their own in a Nash equilibrium network with self-loops allowed in † G .) Let † G be a given underlying topology. Consider the network formation game G with Katz centralities given in (2). Suppose that Assumption (A1) holds. Let ∗∈ℰw^* and let ∗:=(∗) G^*:= G(w^*) denote the Nash equilibrium network induced by it. Then for any i∈i , if j∈i(∗)j _i( G^*) then ci(∗)≤cj(∗)c_i(w^*)≤ c_j(w^*). Proof: Since ∗∈ℰw^* , i∗∈ℬℛi(−i∗),∀i∈w_i^* _i(w_-i^*),∀ i , by definition. From Lemma I.3, if j∈i(∗)j _i( G^*), then j∈argmaxk∈i(∗)ck()j∈ *argmax_k _i( G^*)c_k(w). The claim now follows since i∈i(†)i _i( G ) under the stated assumptions. ■ In the following result, we show that agents in an SCC of Nash equilibrium network ∗=(∗) G^*= G(w^*) induced by ∗∈ℰw^* have same budget and centralities. Theorem IV.3 (Agents belonging to a SCC of a Nash equilibrium network with self-loops in † G have same budget and centralities.) Let † G be a given underlying topology. Consider the network formation game G with Katz centralities given in (2). Suppose that Assumption (A1) holds. Let ∗∈ℰw^* , and let ∗:=(∗) G^*:= G(w^*) denote the Nash equilibrium network induced by it. If ′:=(′,ℰ′,′) G :=(V ,E ,A ) is an SCC of ∗ G^*, then ∃α≥0∃α≥ 0 and ∃γ>0∃γ>0 such that ci(∗)=α,c_i(w^*)=α, Bi=γB_i=γ, ∀i∈′∀ i . Additionally, if |′|≥2|V |≥ 2 and ′:=(′,ℰ′,′) G :=(V ,E ,A ) is another SCC of ∗ G^* such that wij∗>0w_ij^*>0 for some i∈′i and j∈′j , then ck(∗)=α,∀k∈′c_k(w^*)=α,∀ k . Proof: Under the stated assumptions, notice that for any agent i∈′i∈ G , there exists a directed cycle starting at i and terminating at i while passing through every node in ′V . First part of claim now follows from Lemma IV.2 and Theorem I.4. Next, if there is an edge from ′ G to ′ G , then ∃i∈′∃ i and ∃j∈′∃ j such that wij∗>0w_ij^*>0. Since |′|≥2|V |≥ 2, there is an edge from i to an agent k∈′k i.e., wik∗>0w_ik^*>0. The result now follows from the first part, Lemma I.3 and Theorem I.4. ■ Lemma IV.2 states that in a Nash equilibrium network, any agent forms connections only with agents whose centralities are greater than or equal to its equilibrium centrality. Thus, a hierarchical structure emerges in the Nash equilibrium network with respect to agents’ Katz centralities. Further, Theorem IV.3 states that all agents within a SCC of the Nash equilibrium network have the same budget and centrality. Moreover, if a SCC with at least two agents is connected to another SCC, then all agents in both SCCs have the same budget and centrality. Next, we consider another special case of an undirected underlying topology. The following result characterizes the centralities of agents in a cycle (if one exists) of the Nash equilibrium network formed in this case. The proof, being similar to that of Theorem IV.3, is omitted for brevity. Theorem IV.4 (Properties of cycles in the Nash equilibrium network when † G is undirected.) Let † G be a given underlying topology. Consider the network formation game G with Katz centralities given in (2). Suppose that † G is undirected. Let ∗∈ℰw^* , and let ∗:=(∗) G^*:= G(w^*) denote the Nash equilibrium network induced by it. Consider any cycle (if there exists one) of length l in ∗ G^*. Then, if l is odd, all agents in the cycle have the same budgets and centralities. Alternatively, if l is even, every pair of alternate agents in the cycle has the same budgets and centralities. ∙ V Simulations In this section, we present simulations to illustrate some of our analytical results. All simulations were run in MATLAB. We consider 10 agents with their Katz centralities as defined in (2). In the first set of simulations, we simulate BRD with random agent selection at every time step. The underlying topology † G is as shown in Figure 1 and contain self-loops at each node. Thus, Assumption (A1) holds. The budget vector containing BiB_i’s is B≈[0.89 13⊤0.17 13⊤0.3 13⊤0.86]⊤B≈ bmatrix0.89\;1_3 &0.17\;1_3 &0.3\;1_3 &0.86 bmatrix . The non-zero allocation values at ∗∈ℰw^* attained under BRD are as follows: w11∗≈0.17w_11^*≈ 0.17, w12∗≈0.71w_12^*≈ 0.71, w22∗≈0.1w_22^*≈ 0.1, w23∗≈0.79w_23^*≈ 0.79, w31∗≈0.81w_31^*≈ 0.81, w33∗≈0.07w_33^*≈ 0.07, w42∗≈0.09w_42^*≈ 0.09, w43∗≈0.08w_43^*≈ 0.08, w59∗≈0.17w_59^*≈ 0.17, w62∗≈0.09w_62^*≈ 0.09, w63∗≈0.09w_63^*≈ 0.09 w73∗≈0.3w_73^*≈ 0.3, w82∗≈0.3w_82^*≈ 0.3, w91∗≈0.3w_91^*≈ 0.3, w10,1∗≈0.62w_10,1^*≈ 0.62, w10,3∗≈0.24w_10,3^*≈ 0.24. The corresponding Nash equilibrium network (∗) G(w^*) is shown in Figure 1. The above data can be used to verify claims in Lemma I.3. The evolution of centralities under BRD as shown in Figure 2 is monotonic verifying claim 1 in Lemma I.3. The equilbrium centrality vector is (∗)≈[7.82 13⊤1.510.621.512.64 13⊤7.57]⊤c(w^*)≈ bmatrix7.82\;1_3 &1.51&0.62&1.51&2.64\;1_3 &7.57 bmatrix . Here, 31_3 denotes a 3 dimesnional vector of all ones. Using the above data, it can be verified that ((∗))=(∗)v(c(w^*))=c(w^*) thus (∗)c(w^*) is a fixed point of (⋅)v(·) (10) verifying that ∗∈ℰw^* as suggested by Theorem I.4. The data also verifies the claims in Theorem IV.3. Figure 1: Convergence of BRD. (Left) Underlying topology with self-loops at every node. (Right) Unweighted Nash equilibrium network attained by BRD with self loops at nodes 1,2,3\1,2,3\. The color bar represents the continuum of centrality values in [0,10][0,10]. Figure 2: Evolution of cic_i’s under BRD with † G as shown in Figure 1. In the second set of simulations shown in Figure, we assume the underlying topology † G to be complete. We again simulate BRD with random agent selection at each time step. Figure 3 shows the (unweighted) Nash equilibrium topology attained under BRD. We omit the allocation data ∗w^* due to space constraints. The vector containing the budgets of all agents is B≈[0.2 13⊤0.83 13⊤0.69 13⊤0.17]⊤B≈ bmatrix0.2\;1_3 &0.83\;1_3 &0.69\;1_3 &0.17 bmatrix . The Nash equilbrium centrality vector is (∗)≈[1.15 13⊤4.77 13⊤3.98 13⊤0.98]⊤c(w^*)≈ bmatrix1.15\;1_3 &4.77\;1_3 &3.98\;1_3 &0.98 bmatrix . The above data and the plot on the right side of Figure 3 verify the claims in Theorem IV.1 and the observation made below it. Figure 3: When † G is complete. (Left) Plot of centralities vs agents’ budgets. (Right) Unweighted Nash equilibrium network reached under BRD. Self loops exist at nodes 4,5,6\4,5,6\. The color bar represents the continuum of centrality values in [0,10][0,10]. VI Conclusion In this paper, we have studied a strategic network formation game where agents form directed weighted networks to maximize their Katz centrality. We have provided necessary and sufficient conditions for a network to be a Nash equilibrium and have characterized the set of Nash equilibrium networks under special underlying topologies. We have also shown that unilateral better responses at Nash equilibria are still Nash equilibria. We have shown that sequential best response dynamics converge to the set of Nash equilibria. Finally, we have provided simulation results to verify our theoretical findings. Future work includes further analysis of the Nash equilibrium networks for different classes of underlying topologies and budget constraints, modeling and analysis of bounded rationality in the network formation game and network formation process in terms of limited information and computational limitations of the agents. References [1] V. Bala and S. Goyal (2000) A noncooperative model of network formation. Econometrica 68 (5), p. 1181–1230. External Links: Document Cited by: §I. [2] A. Barabási and R. Albert (1999) Emergence of scaling in random networks. Science 286 (5439), p. 509–512. External Links: Document Cited by: §I. [3] N. I. Bazenkov (2015-02) Double best response dynamics in topology formation game for ad hoc networks. Automation and Remote Control 76 (2), p. 323–335. External Links: Document, Link Cited by: §I. [4] X. Bei, W. Chen, S. Teng, J. Zhang, and J. Zhu (2011) Bounded budget betweenness centrality game for strategic network formations. Theoretical Computer Science 412 (35), p. 4667–4682. Cited by: item 4, §I. [5] K. Bimpikis, S. Ehsani, and R. Ilkılıç (2019) Cournot competition in networked markets. Management Science 65 (6), p. 2467–2481. Cited by: §I. [6] F. Bloch, M. O. Jackson, and P. Tebaldi (2023) Centrality measures in networks. Social Choice and Welfare 61 (2), p. 413–453. Cited by: §I. [7] F. Bloch and M. O. Jackson (2006) Definitions of equilibrium in network formation games. International Journal of Game Theory 34 (3), p. 305–318. Cited by: §I. [8] A. Calvó-Armengol and R. Ilkiliç (2009) Pairwise-stability and nash equilibria in network formation. International Journal of Game Theory 38 (1), p. 51–79. Cited by: §I. [9] M. Castaldo, G. Como, and F. Fagnani (2020) On a centrality maximization game. IFAC-PapersOnLine 53 (2), p. 442–447. Cited by: §I. [10] M. Catalano, A. Castaldo, G. Como, and F. Fagnani (2024) On a network centrality maximization game. Mathematics of Operations Research. Note: Online 2022–2024 Cited by: item 4, §I. [11] P. Cisneros-Velarde and F. Bullo (2021) A network formation game for the emergence of hierarchies. PLoS ONE 16 (8), p. e0255990. External Links: Document, Link Cited by: item 4, §I, §I. [12] S. Dhamal, W. Ben-Ameur, T. Chahed, and E. Altman (2020) A two phase investment game for competitive opinion dynamics in social networks. Information processing & management 57 (2), p. 102064. Cited by: §I. [13] M. Feldman, N. Immorlica, B. Lucier, and Y. Mansour (2020) The efficiency of best-response dynamics. arXiv:2002.11461. Cited by: §I. [14] M. O. Jackson and A. Watts (2005) On the formation of interaction networks. Games and Economic Behavior 51 (2), p. 265–295. Note: Often cited as 2002 preprint/evolution paper Cited by: §I. [15] M. O. Jackson and A. Wolinsky (1996) A strategic model of social and economic networks. Journal of Economic Theory 71 (1), p. 44–74. External Links: Document Cited by: §I. [16] M. O. Jackson (2005) A survey of network formation models: stability and efficiency. Group formation in economics: Networks, clubs, and coalitions 664, p. 11–49. Cited by: §I. [17] L. Katz (1953) A new status index derived from sociometric analysis. Psychometrika 18 (1), p. 39–43. External Links: Document Cited by: §I. [18] M. D. König, C. J. Tessone, and Y. Zenou (2010) A dynamic model of network formation with strategic interactions. Working paper / conference version. Cited by: §I. [19] A. Landherr, B. Friedl, and J. Heidemann (2010) A critical review of centrality measures in social networks. Business & Information Systems Engineering 2 (6), p. 371–385. Cited by: §I. [20] N. Laoutaris, L. Poplawski, R. Rajaraman, R. Sundaram, and S. Teng (2014) Bounded budget connection (bbc) games or how to make friends and influence people, on a budget. Journal of Computer and System Sciences 80 (7), p. 1266–1284. External Links: ISSN 0022-0000, Document, Link Cited by: item 4, §I. [21] A. R. Masson, E. Altman, and Y. Hayel (2015) Controlling the katz-bonacich centrality in social network: application to gossip in online social networks. In 2015 IEEE/ACM 8th International Conference on Utility and Cloud Computing (UCC), Vol. , p. 442–447. External Links: Document Cited by: §I. [22] M.J. Park, O.M. Kwon, and J.H. Ryu (2018) A katz-centrality-based protocol design for leader-following formation of discrete-time multi-agent systems with communication delays. Journal of the Franklin Institute 355 (13), p. 6111–6131. External Links: ISSN 0016-0032, Document, Link Cited by: §I. [23] A. Salehi and B. Masoumi (2020) KATZ centrality with biogeography-based optimization for influence maximization problem. Journal of Combinatorial Optimization 40 (1), p. 205–226. Cited by: §I. [24] H. Salonen (2016) Equilibria and centrality in link formation games. International Journal of Game Theory 45 (4), p. 1133–1151. Cited by: item 4, §I. [25] K. J. Sharkey (2017) A control analysis perspective on katz centrality. Scientific reports 7 (1), p. 17247. Cited by: §I. [26] T. A. B. Snijders, G. G. van de Bunt, and C. E. G. Steglich (2010) Introduction to stochastic actor-based models for network dynamics. Social Networks 32 (1), p. 44–60. Cited by: §I. [27] T. A. B. Snijders (2001) The statistical evaluation of social network dynamics. Sociological Methodology 31, p. 361–395. Cited by: §I. [28] R. Tatko and C. Griffin (2012) Game theoretic formation of a centrality based network. In 2012 International Conference on Social Informatics, Vol. , p. 56–61. External Links: Document Cited by: item 4, §I. [29] A. Watts (2001) A dynamic model of network formation. Games and Economic Behavior 34 (2), p. 331–341. Cited by: §I.