pith. machine review for the scientific record. sign in

arxiv: 2604.03056 · v1 · submitted 2026-04-03 · 💻 cs.GT · cs.MA· cs.SI

Recognition: 2 theorem links

· Lean Theorem

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

Balaji R , Prashil Wankhede , Pavankumar Tallapragada
Authors on Pith no claims yet

Pith reviewed 2026-05-13 18:02 UTC · model grok-4.3

classification 💻 cs.GT cs.MAcs.SI
keywords network formation gameKatz centralityNash equilibriumresource allocationbest-response dynamicshierarchical networks
0
0 comments X

The pith

Agents allocate budgets to neighbors to maximize Katz centrality, forming Nash equilibrium networks that are hierarchical or budget-proportional depending on the underlying topology.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper examines a strategic game in which agents with limited budgets allocate resources to form connections and maximize their individual Katz centralities. The authors characterize the Nash equilibrium networks that arise and demonstrate that best-response dynamics converge to these equilibria under mild conditions. For complete underlying networks, the equilibria feature Katz centralities directly proportional to agents' budgets. In general networks with self-loops, hierarchical structures emerge at equilibrium. A sympathetic reader would care because this provides a formal model for how influence and power distribute in strategic settings like social or organizational networks.

Core claim

We study a network formation game where agents allocate constrained resources to neighbors in an underlying unweighted network to maximize their Katz centralities. We characterize the Nash equilibrium networks and show that sequential best-response dynamics converge to the set of Nash equilibria. For complete underlying topologies, Katz centralities are proportional to agents' budgets at Nash equilibria. For general underlying topologies with self-loops, hierarchical networks form at Nash equilibria.

What carries the argument

The strategic-form game in which each agent's strategy is an allocation of its budget to outgoing edges in the underlying topology, inducing a weighted network whose Katz centralities determine the utilities.

Load-bearing premise

Agents treat their Katz centrality exactly as their utility and are restricted to allocating resources only along edges of a fixed underlying unweighted network.

What would settle it

A simulation or empirical observation where, in a complete underlying network, the resulting Katz centralities at equilibrium are not proportional to the agents' budgets would falsify the proportionality claim.

Figures

Figures reproduced from arXiv: 2604.03056 by Balaji R, Pavankumar Tallapragada, Prashil Wankhede.

Figure 1
Figure 1. Figure 1: Convergence of BRD. (Left) Underlying topology with self-loops at [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Evolution of ci’s under BRD with G: as shown in [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. 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 t4, 5, 6u. The color bar represents the continuum of centrality values in r0, 10s. VI. CONCLUSION In this paper, we have studied a strategic network forma￾tion game where agents form directed weighted networks to maximize their Katz centrality. We hav… view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper introduces a network formation game in which agents allocate constrained resources to form weighted connections within a given unweighted network to maximize their Katz centralities. The authors characterize the Nash equilibrium networks, propose sequential best-response dynamics that converge to equilibria under mild assumptions, show that Katz centralities are proportional to budgets at equilibria for complete topologies, and demonstrate that hierarchical networks form at equilibria for general topologies with self-loops. Simulations are used to illustrate the results.

Significance. If the characterizations and convergence results hold, this work provides a valuable game-theoretic perspective on strategic network formation for influence maximization using Katz centrality. The specific findings on proportionality in complete graphs and hierarchy in self-loop graphs are noteworthy contributions that could inform models of resource allocation in social and communication networks. The use of standard game-theoretic tools for the analysis is a strength, and the mild assumptions for convergence enhance the applicability.

major comments (2)
  1. Abstract: the claim that best-response dynamics converges to the set of Nash equilibria under 'very mild assumptions' is load-bearing for the practical relevance of the equilibria characterization; the main text must explicitly list and verify these assumptions (e.g., continuity, compactness, or acyclicity conditions) rather than leaving them implicit.
  2. Complete-topology result: the proportionality of Katz centralities to agents' budgets at Nash equilibria must be shown to follow directly from the utility definition and budget constraints without additional implicit normalization; any step that reduces the ratio by construction should be flagged.
minor comments (2)
  1. Simulations: provide explicit parameter values, network sizes, and convergence metrics so that the numerical illustrations can be reproduced and directly compared to the theoretical predictions for both complete and general topologies.
  2. Notation: define the mapping from allocation vectors to the weighted adjacency matrix and the precise Katz centrality formula (including the attenuation factor) at the first appearance to avoid ambiguity when reading the equilibrium conditions.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments and positive assessment of the paper. We address each major comment below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: Abstract: the claim that best-response dynamics converges to the set of Nash equilibria under 'very mild assumptions' is load-bearing for the practical relevance of the equilibria characterization; the main text must explicitly list and verify these assumptions (e.g., continuity, compactness, or acyclicity conditions) rather than leaving them implicit.

    Authors: We agree that the assumptions should be stated explicitly. In the revised manuscript we will add a dedicated paragraph in the best-response dynamics section that lists them: (i) continuity of Katz centrality in the allocation variables, (ii) compactness of each agent's budget-constrained strategy set, and (iii) acyclicity of the best-response correspondence induced by the underlying topology. We will also verify that these conditions hold under the problem formulation. revision: yes

  2. Referee: Complete-topology result: the proportionality of Katz centralities to agents' budgets at Nash equilibria must be shown to follow directly from the utility definition and budget constraints without additional implicit normalization; any step that reduces the ratio by construction should be flagged.

    Authors: The proportionality follows directly from the first-order optimality conditions of each agent's utility maximization subject to the budget constraint; in the complete-network case the Katz centrality expression yields identical marginal returns across neighbors, so the equilibrium allocations equate the Lagrange multipliers and produce centrality proportional to budget. To address the concern we will revise the proof to insert an explicit remark that no auxiliary normalization is introduced and to flag every algebraic step that preserves the ratio. revision: yes

Circularity Check

0 steps flagged

No significant circularity in the derivation chain

full rationale

The paper defines a strategic-form game whose utilities are exactly the Katz centralities induced by the agents' joint allocation of edge weights on a fixed underlying unweighted graph. Nash equilibria, best-response dynamics convergence, the proportionality result on complete graphs, and the hierarchical-network result on graphs with self-loops are all obtained by direct application of standard equilibrium conditions and best-response analysis to this definition. No parameter is fitted to data and then relabeled a prediction, no output is defined in terms of itself, and no load-bearing step reduces to a self-citation whose content is itself unverified. The derivation therefore remains self-contained against the model's stated assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard assumptions from game theory and the definition of Katz centrality, with no free parameters or new entities introduced in the abstract.

axioms (2)
  • domain assumption Agents' utilities are given by their Katz centralities in the induced network.
    This is the core modeling choice stated in the abstract for representing influence.
  • domain assumption Allocations by agents are restricted to neighbors in a given unweighted network encoding topological constraints.
    Defines the feasible actions in the game as per the abstract.

pith-pipeline@v0.9.0 · 5491 in / 1497 out tokens · 88292 ms · 2026-05-13T18:02:40.062739+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages

  1. [1]

    A strategic model of social and economic networks,

    M. O. Jackson and A. Wolinsky, “A strategic model of social and economic networks,”Journal of Economic Theory, vol. 71, no. 1, pp. 44–74, 1996

    work page 1996

  2. [2]

    A noncooperative model of network formation,

    V . Bala and S. Goyal, “A noncooperative model of network formation,” Econometrica, vol. 68, no. 5, pp. 1181–1230, 2000

    work page 2000

  3. [3]

    A network formation game for the emergence of hierarchies,

    P. Cisneros-Velarde and F. Bullo, “A network formation game for the emergence of hierarchies,”PLoS ONE, vol. 16, no. 8, p. e0255990,

    work page

  4. [4]

    Available: https://journals.plos.org/plosone/article?id= 10.1371/journal.pone.0255990

    [Online]. Available: https://journals.plos.org/plosone/article?id= 10.1371/journal.pone.0255990

    work page doi:10.1371/journal.pone.0255990

  5. [5]

    A survey of network formation models: stability and efficiency,

    M. O. Jackson, “A survey of network formation models: stability and efficiency,”Group formation in economics: Networks, clubs, and coalitions, vol. 664, pp. 11–49, 2005

    work page 2005

  6. [6]

    Definitions of equilibrium in network formation games,

    F. Bloch and M. O. Jackson, “Definitions of equilibrium in network formation games,”International Journal of Game Theory, vol. 34, no. 3, pp. 305–318, 2006

    work page 2006

  7. [7]

    Pairwise-stability and nash equi- libria in network formation,

    A. Calv ´o-Armengol and R. Ilkilic ¸, “Pairwise-stability and nash equi- libria in network formation,”International Journal of Game Theory, vol. 38, no. 1, pp. 51–79, 2009

    work page 2009

  8. [8]

    A critical review of cen- trality measures in social networks,

    A. Landherr, B. Friedl, and J. Heidemann, “A critical review of cen- trality measures in social networks,”Business & Information Systems Engineering, vol. 2, no. 6, pp. 371–385, 2010

    work page 2010

  9. [9]

    Centrality measures in networks,

    F. Bloch, M. O. Jackson, and P. Tebaldi, “Centrality measures in networks,”Social Choice and Welfare, vol. 61, no. 2, pp. 413–453, 2023

    work page 2023

  10. [10]

    Equilibria and centrality in link formation games,

    H. Salonen, “Equilibria and centrality in link formation games,” International Journal of Game Theory, vol. 45, no. 4, pp. 1133–1151, 2016

    work page 2016

  11. [11]

    A new status index derived from sociometric analysis,

    L. Katz, “A new status index derived from sociometric analysis,” Psychometrika, vol. 18, no. 1, pp. 39–43, 1953

    work page 1953

  12. [12]

    Katz centrality with biogeography- based optimization for influence maximization problem,

    A. Salehi and B. Masoumi, “Katz centrality with biogeography- based optimization for influence maximization problem,”Journal of Combinatorial Optimization, vol. 40, no. 1, pp. 205–226, 2020

    work page 2020

  13. [13]

    A katz-centrality-based protocol design for leader-following formation of discrete-time multi-agent systems with communication delays,

    M. Park, O. Kwon, and J. Ryu, “A katz-centrality-based protocol design for leader-following formation of discrete-time multi-agent systems with communication delays,”Journal of the Franklin Institute, vol. 355, no. 13, pp. 6111–6131, 2018. [Online]. Available: https: //www.sciencedirect.com/science/article/pii/S0016003218304319

    work page 2018

  14. [14]

    A two phase investment game for competitive opinion dynamics in social networks,

    S. Dhamal, W. Ben-Ameur, T. Chahed, and E. Altman, “A two phase investment game for competitive opinion dynamics in social networks,”Information processing & management, vol. 57, no. 2, p. 102064, 2020

    work page 2020

  15. [15]

    Cournot competition in networked markets,

    K. Bimpikis, S. Ehsani, and R. Ilkılıc ¸, “Cournot competition in networked markets,”Management Science, vol. 65, no. 6, pp. 2467– 2481, 2019

    work page 2019

  16. [16]

    Controlling the katz- bonacich centrality in social network: Application to gossip in online social networks,

    A. R. Masson, E. Altman, and Y . Hayel, “Controlling the katz- bonacich centrality in social network: Application to gossip in online social networks,” in2015 IEEE/ACM 8th International Conference on Utility and Cloud Computing (UCC), 2015, pp. 442–447

    work page 2015

  17. [17]

    A control analysis perspective on katz centrality,

    K. J. Sharkey, “A control analysis perspective on katz centrality,” Scientific reports, vol. 7, no. 1, p. 17247, 2017

    work page 2017

  18. [18]

    Game theoretic formation of a centrality based network,

    R. Tatko and C. Griffin, “Game theoretic formation of a centrality based network,” in2012 International Conference on Social Infor- matics, 2012, pp. 56–61

    work page 2012

  19. [19]

    Bounded budget betweenness centrality game for strategic network formations,

    X. Bei, W. Chen, S.-H. Teng, J. Zhang, and J. Zhu, “Bounded budget betweenness centrality game for strategic network formations,” Theoretical Computer Science, vol. 412, no. 35, pp. 4667–4682, 2011

    work page 2011

  20. [20]

    Bounded budget connection (bbc) games or how to make friends and influence people, on a budget,

    N. Laoutaris, L. Poplawski, R. Rajaraman, R. Sundaram, and S.-H. Teng, “Bounded budget connection (bbc) games or how to make friends and influence people, on a budget,”Journal of Computer and System Sciences, vol. 80, no. 7, pp. 1266–1284, 2014. [Online]. Available: https://www.sciencedirect.com/science/article/pii/ S0022000014000579

    work page 2014

  21. [21]

    A dynamic model of network formation with strategic interactions,

    M. D. K ¨onig, C. J. Tessone, and Y . Zenou, “A dynamic model of network formation with strategic interactions,”Working paper / conference version, 2010

    work page 2010

  22. [22]

    On a centrality maximization game,

    M. Castaldo, G. Como, and F. Fagnani, “On a centrality maximization game,”IFAC-PapersOnLine, vol. 53, no. 2, pp. 442–447, 2020

    work page 2020

  23. [23]

    On a network centrality maximization game,

    M. Catalano, A. Castaldo, G. Como, and F. Fagnani, “On a network centrality maximization game,”Mathematics of Operations Research, 2024, online 2022–2024

    work page 2024

  24. [24]

    The efficiency of best-response dynamics,

    M. Feldman, N. Immorlica, B. Lucier, and Y . Mansour, “The efficiency of best-response dynamics,”arXiv:2002.11461, 2020

    work page arXiv 2002

  25. [25]

    Double best response dynamics in topology formation game for ad hoc networks,

    N. I. Bazenkov, “Double best response dynamics in topology formation game for ad hoc networks,”Automation and Remote Control, vol. 76, no. 2, pp. 323–335, February 2015. [Online]. Available: https://doi.org/10.1134/S0005117915020125

    work page doi:10.1134/s0005117915020125 2015

  26. [26]

    Emergence of scaling in random networks,

    A.-L. Barab ´asi and R. Albert, “Emergence of scaling in random networks,”Science, vol. 286, no. 5439, pp. 509–512, 1999

    work page 1999

  27. [27]

    A dynamic model of network formation,

    A. Watts, “A dynamic model of network formation,”Games and Economic Behavior, vol. 34, no. 2, pp. 331–341, 2001

    work page 2001

  28. [28]

    On the formation of interaction networks,

    M. O. Jackson and A. Watts, “On the formation of interaction networks,”Games and Economic Behavior, vol. 51, no. 2, pp. 265– 295, 2005, often cited as 2002 preprint/evolution paper

    work page 2005

  29. [29]

    The statistical evaluation of social network dynam- ics,

    T. A. B. Snijders, “The statistical evaluation of social network dynam- ics,”Sociological Methodology, vol. 31, pp. 361–395, 2001

    work page 2001

  30. [30]

    Introduction to stochastic actor-based models for network dynamics,

    T. A. B. Snijders, G. G. van de Bunt, and C. E. G. Steglich, “Introduction to stochastic actor-based models for network dynamics,” Social Networks, vol. 32, no. 1, pp. 44–60, 2010

    work page 2010