On a Network Centrality Maximization Game
(2025) In Mathematics of Operations Research 50(3). p.2112-2140- Abstract
We study a network formation game where n players, identified with the nodes of a directed graph to be formed, choose where to wire their outgoing links in order to maximize their PageRank centrality. Specifically, the action of every player i consists in the wiring of a predetermined number di of directed out-links, and her utility is her own PageRank centrality in the network resulting from the actions of all players. We show that this is a potential game and that the best response correspondence always exhibits a local structure in that it is never convenient for a node i to link to other nodes that are at incoming distance more than di from her. We then study the equilibria of this game determining necessary... (More)
We study a network formation game where n players, identified with the nodes of a directed graph to be formed, choose where to wire their outgoing links in order to maximize their PageRank centrality. Specifically, the action of every player i consists in the wiring of a predetermined number di of directed out-links, and her utility is her own PageRank centrality in the network resulting from the actions of all players. We show that this is a potential game and that the best response correspondence always exhibits a local structure in that it is never convenient for a node i to link to other nodes that are at incoming distance more than di from her. We then study the equilibria of this game determining necessary conditions for a graph to be a (strict, recurrent) Nash equilibrium. Moreover, in the homogeneous case, where players all have the same number d of out-links, we characterize the structure of the potential-maximizing equilibria, and in the special cases d = 1 and d = 2, we provide a complete classification of the set of (strict, recurrent) Nash equilibria. Our analysis shows in particular that the considered formation mechanism leads to the emergence of undirected and disconnected or loosely connected networks.
(Less)
- author
- Catalano, Costanza ; Castaldo, Maria ; Como, Giacomo LU and Fagnani, Fabio
- organization
- publishing date
- 2025-08
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- network centrality, network formation games, ordinal potential games
- in
- Mathematics of Operations Research
- volume
- 50
- issue
- 3
- pages
- 29 pages
- publisher
- INFORMS Inst.for Operations Res.and the Management Sciences
- external identifiers
-
- scopus:105014214949
- ISSN
- 0364-765X
- DOI
- 10.1287/moor.2022.0251
- language
- English
- LU publication?
- yes
- additional info
- Publisher Copyright: © 2024 INFORMS.
- id
- 9654a807-536b-4198-ae2a-5f3e9617657d
- date added to LUP
- 2025-10-20 15:04:46
- date last changed
- 2025-10-20 15:06:07
@article{9654a807-536b-4198-ae2a-5f3e9617657d,
abstract = {{<p>We study a network formation game where n players, identified with the nodes of a directed graph to be formed, choose where to wire their outgoing links in order to maximize their PageRank centrality. Specifically, the action of every player i consists in the wiring of a predetermined number d<sub>i</sub> of directed out-links, and her utility is her own PageRank centrality in the network resulting from the actions of all players. We show that this is a potential game and that the best response correspondence always exhibits a local structure in that it is never convenient for a node i to link to other nodes that are at incoming distance more than d<sub>i</sub> from her. We then study the equilibria of this game determining necessary conditions for a graph to be a (strict, recurrent) Nash equilibrium. Moreover, in the homogeneous case, where players all have the same number d of out-links, we characterize the structure of the potential-maximizing equilibria, and in the special cases d = 1 and d = 2, we provide a complete classification of the set of (strict, recurrent) Nash equilibria. Our analysis shows in particular that the considered formation mechanism leads to the emergence of undirected and disconnected or loosely connected networks.</p>}},
author = {{Catalano, Costanza and Castaldo, Maria and Como, Giacomo and Fagnani, Fabio}},
issn = {{0364-765X}},
keywords = {{network centrality; network formation games; ordinal potential games}},
language = {{eng}},
number = {{3}},
pages = {{2112--2140}},
publisher = {{INFORMS Inst.for Operations Res.and the Management Sciences}},
series = {{Mathematics of Operations Research}},
title = {{On a Network Centrality Maximization Game}},
url = {{http://dx.doi.org/10.1287/moor.2022.0251}},
doi = {{10.1287/moor.2022.0251}},
volume = {{50}},
year = {{2025}},
}