A Network Formation Game for Katz Centrality Maximization: A Resource Allocation Perspective
This work addresses network influence optimization for agents in strategic settings, but it is incremental as it builds on existing game-theoretic and centrality models.
The paper tackles the problem of network formation where agents allocate resources to maximize their influence, modeled by Katz centrality, and characterizes Nash equilibrium networks and their properties. It shows that sequential best-response dynamics converge to Nash equilibria, with Katz centralities proportional to budgets in complete topologies and hierarchical networks forming in general topologies with self-loops.
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.