A Network Formation Game for Katz Centrality Maximization

Prashil Wankhede

During the academic year 2025–26, our research focused on strategic decision-making under resource constraints using tools from game theory, graph theory and dynamical systems. The resulting works [1, 2] investigate how resource limitations influence collective behavior in opinion dynamics and network formation. The first work [1] studies opinion formation over the allocation of limited resources across multiple topics. We propose a multi-topic opinion dynamics model in which agents are subject to hard budget constraints and seek to maximize individual utility functions. The resulting opinion evolution is modeled as a projected dynamical system, where agents myopically adjust their opinions in the direction of increasing utility while respecting feasibility constraints. Coupling among agents arises through an undirected social network, whereas coupling across topics emerges from shared resource constraints. We establish convergence of the opinion dynamics to the equilibrium set. For networks with sufficiently weak antagonistic interactions, we further prove convergence to a unique equilibrium point. In addition, we show that the underlying opinion formation problem can be formulated as a potential game, enabling a characterization of Nash equilibria through the potential function. For networks without antagonistic relations, we derive the unique Nash equilibrium explicitly and demonstrate its correspondence with the equilibrium of the dynamical system. Numerical simulations validate the theoretical findings and illustrate the influence of resource constraints on collective decision-making. The second work [2] investigates a strategic network formation game in which agents allocate limited resources to establish and strengthen connections with other agents in order to maximize their influence. Influence is quantified using Katz centrality, and agents are allowed to distribute resources only among neighbors in a prescribed underlying network representing topological constraints. The resulting allocations determine weighted outgoing edges and collectively induce a network structure. We characterize the Nash equilibrium networks of this game and analyze their structural properties. To model network evolution, we introduce a sequential best-response dynamics (BRD) and show that it converges to the set of Nash equilibria under mild assumptions. For complete underlying topologies, we prove that equilibrium Katz centralities are proportional to agents’ budgets. For more general topologies in which every agent possesses a self-loop, we establish that Nash equilibria exhibit hierarchical network structures. Numerical experiments further illustrate the theoretical results and provide insights into the emergence of influence hierarchies under resource constraints. List of Publications References [1] P. Wankhede, N. Mandal, S. Mart’inez, and P. Tallapragada, “Multi-Topic Projected Opinion Dynamics for Resource Allocation,” in Proceedings of the 64th IEEE Conference on Decision and Control (CDC), 2025, pp. 3469–3476. [2] Balaji. R, P. Wankhede, and P. Tallapragada, “A Network Formation Game for Katz Centrality Maximization: A Resource Allocation Perspective,” arXiv preprint, arXiv:2604.03056, 2026. (Accepted for presentation at the 65th IEEE Conference on Decision and Control (CDC), 2026)