Pairwise Stability in Weighted Network Formation Games: Selection and Computation

Caihua Chen (), Junhao Tao () and Yang Zhan ()
Additional contact information
Caihua Chen: School of Management and Engineering, Nanjing University, Nanjing 210093, China
Junhao Tao: School of Management and Engineering, Nanjing University, Nanjing 210093, China
Yang Zhan: School of Management and Engineering, Nanjing University, Nanjing 210093, China; and Shenzhen Research Institute of Nanjing University, Shenzhen 518000, China

INFORMS Journal on Computing, 2025, vol. 37, issue 4, 917-932

Abstract: This paper is concerned with the selection and computation of pairwise stable networks when agents have differentiable and concave utility functions. We show that a pairwise stable network can be obtained by finding a Nash equilibrium of a noncooperative game played by the nodes and links in the network. Based on this observation, we introduce a logarithmic tracing procedure and a path-following algorithm for network formation games. We apply the algorithm to several models in the literature and make comparisons with two existing algorithms: a path-following algorithm based on the linear tracing procedure (LinTP) and a decompose and exhaustive search method (DaE). Numerical results indicate that the proposed method is more than four times as efficient as LinTP. Although DaE demonstrates exceptional efficiency for small-scale problems, our method outperforms it significantly for large-scale problems, where DaE may fail to find a solution. We also show that the decomposition technique of DaE can be used to further accelerate our algorithm for a special class of problems.

Keywords: network formation game; pairwise stable network; equilibrium computation; equilibrium selection (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2024.0546 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:37:y:2025:i:4:p:917-932

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().