A Network Formation Game for Katz Centrality Maximization: A Resource Allocation Perspective

This paper develops a noncooperative model of directed network formation in which agents create links to access valuable information while sharing the costs generated along the paths through which information is obtained. Each agent is endowed with a positive amount of information and chooses, simultaneously, which other agents to contact. A directed link initiated by one agent allows her to access the information of the contacted agent and of the latter's reachable network, but each link in the resulting information path entails a unit cost. Payoffs therefore depend on the total value of accessible information net of the accumulated connection costs required to obtain it. The paper characterizes the relationship between strategy profiles and directed graphs, defines accessibility, paths, components, and minimal connectedness, and studies the Nash architectures induced by individual best responses. The central result is that strict Nash equilibria must take the form of circular directed networks. Moreover, circular networks are exactly the Nash networks that use the minimum number of links while allowing every agent to access all available information. Although noncircular weak Nash networks may exist, they are structurally redundant and do not satisfy the same minimality property. The model also shows that strict Nash networks are both Pareto optimal and efficient in terms of aggregate welfare. Finally, the paper compares this framework with Bala and Goyal's model, emphasizing that shared path costs and heterogeneous information values generate different equilibrium implications. The analysis supports the equivalence between strict stability and minimal connectivity in directed information networks.

The Kelly or proportional allocation mechanism is a simple and efficient auction-based scheme that distributes an infinitely divisible resource proportionally to the agents bids. When agents are aware of the allocation rule, their interactions form a game extensively studied in the literature. This paper examines the less explored repeated Kelly game, focusing mainly on utilities that are logarithmic in the allocated resource fraction. We first derive this logarithmic form from fairness-throughput trade-offs in wireless network slicing, and then prove that the induced stage game admits a unique Nash equilibrium NE. For the repeated play, we prove convergence to this NE under three behavioral models: (i) all agents use Online Gradient Descent (OGD), (ii) all agents use Dual Averaging with a quadratic regularizer (DAQ) (a variant of the Follow-the-Regularized leader algorithm), and (iii) all agents play myopic best responses (BR). Our convergence results hold even when agents use personalized learning rates in OGD and DAQ (e.g., tuned to optimize individual regret bounds), and they extend to a broader class of utilities that meet a certain sufficient condition. Finally, we complement our theoretical results with extensive simulations of the repeated Kelly game under several behavioral models, comparing them in terms of convergence speed to the NE, and per-agent time-average utility. The results suggest that BR achieves the fastest convergence and the highest time-average utility, and that convergence to the stage-game NE may fail under heterogeneous update rules.

A planner in a network of strategic agents faces three entangled challenges: the optimum depends on agents' private information, queried agents may misreport to steer the outcome, and exact computation does not scale. We study these challenges in multi-activity network games with heterogeneous private technologies, in which the planner sets non-discriminatory prices. We show that the optimal prices admit a centrality-based decomposition of the welfare kernel: each agent's contribution scales with its squared centrality in a network reweighted by agents' preferences across activities. This decomposition motivates Poll, a polling algorithm in which the planner samples one agent per round, walks briefly through the agent's neighborhood, and updates the price from a local report. From the same decomposition flow three forms of efficiency: computationally, Poll uses significantly fewer operations than exact computation and other distributed methods, requiring up to three orders of magnitude less communication on a real-world network with over 300,000 agents; statistically, its query complexity scales with topology and preference heterogeneity rather than explicitly with population size; and economically, it converges to welfare-maximizing prices while admitting behavior-specific implementations that induce truthful reports and detect adversarial deviations.