IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v37y2025i4p917-932.html

Pairwise Stability in Weighted Network Formation Games: Selection and Computation

Author

Listed:
  • 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)

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.

Suggested Citation

  • Caihua Chen & Junhao Tao & Yang Zhan, 2025. "Pairwise Stability in Weighted Network Formation Games: Selection and Computation," INFORMS Journal on Computing, INFORMS, vol. 37(4), pages 917-932, July.
    • Handle: RePEc:inm:orijoc:v:37:y:2025:i:4:p:917-932
    DOI: 10.1287/ijoc.2024.0546
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2024.0546
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2024.0546?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Bich, Philippe & Fixary, Julien, 2022. "Network formation and pairwise stability: A new oddness theorem," Journal of Mathematical Economics, Elsevier, vol. 103(C).
    2. John C. Harsanyi & Reinhard Selten, 1988. "A General Theory of Equilibrium Selection in Games," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262582384, December.
    3. Bich, Philippe & Teteryatnikova, Mariya, 2023. "On perfect pairwise stable networks," Journal of Economic Theory, Elsevier, vol. 207(C).
    4. Philippe Bich & Lisa Morhaim, 2020. "On the existence of Pairwise stable weighted networks," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) halshs-03969712, HAL.
    5. P. Herings & Ronald Peeters, 2010. "Homotopy methods to compute equilibria in game theory," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 42(1), pages 119-156, January.
    6. Philippe Bich & Lisa Morhaim, 2020. "On the Existence of Pairwise Stable Weighted Networks," Mathematics of Operations Research, INFORMS, vol. 45(4), pages 1393-1404, November.
    7. Philippe Bich & Lisa Morhaim, 2020. "On the existence of Pairwise stable weighted networks," PSE-Ecole d'économie de Paris (Postprint) halshs-03969712, HAL.
    8. Francis Bloch & Matthew Jackson, 2006. "Definitions of equilibrium in network formation games," International Journal of Game Theory, Springer;Game Theory Society, vol. 34(3), pages 305-318, October.
    9. Philippe Bich & Julien Fixary, 2022. "Network formation and pairwise stability: A new oddness theorem," Post-Print hal-03969600, HAL.
    10. Philippe Bich & Julien Fixary, 2022. "Network formation and pairwise stability: A new oddness theorem," PSE-Ecole d'économie de Paris (Postprint) hal-03969600, HAL.
    11. Tim Hellmann, 2013. "On the existence and uniqueness of pairwise stable networks," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(1), pages 211-237, February.
    12. Philippe Bich & Julien Fixary, 2022. "Network formation and pairwise stability: A new oddness theorem," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) hal-03969600, HAL.
    13. Chuangyin Dang & P. Jean-Jacques Herings & Peixuan Li, 2022. "An Interior-Point Differentiable Path-Following Method to Compute Stationary Equilibria in Stochastic Games," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1403-1418, May.
    14. Ron N. Borkovsky & Ulrich Doraszelski & Yaroslav Kryukov, 2010. "A User's Guide to Solving Dynamic Stochastic Games Using the Homotopy Method," Operations Research, INFORMS, vol. 58(4-part-2), pages 1116-1132, August.
    15. Philippe Bich & Lisa Morhaim, 2020. "On the existence of Pairwise stable weighted networks," Post-Print halshs-03969712, HAL.
    16. Michael P. Leung, 2020. "Equilibrium computation in discrete network games," Quantitative Economics, Econometric Society, vol. 11(4), pages 1325-1347, November.
    17. Andrea Mantovani & Francisco Ruiz-Aliseda, 2016. "Equilibrium Innovation Ecosystems: The Dark Side of Collaborating with Complementors," Management Science, INFORMS, vol. 62(2), pages 534-549, February.
    18. Bramoulle, Yann & Kranton, Rachel, 2007. "Public goods in networks," Journal of Economic Theory, Elsevier, vol. 135(1), pages 478-494, July.
    19. Xin Fang & Soo-Haeng Cho, 2014. "Stability and Endogenous Formation of Inventory Transshipment Networks," Operations Research, INFORMS, vol. 62(6), pages 1316-1334, December.
    20. Eaves, B. Curtis & Schmedders, Karl, 1999. "General equilibrium models and homotopy methods," Journal of Economic Dynamics and Control, Elsevier, vol. 23(9-10), pages 1249-1279, September.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Caihua Chen & Peixuan Li & Junhao Tao & Yang Zhan, 2026. "Computing Perfect Pairwise Stable Networks," Annals of Operations Research, Springer, vol. 356(1), pages 257-275, January.
    2. Fixary, Julien, 2025. "Unknottedness of graphs of pairwise stable networks & network dynamics," Journal of Mathematical Economics, Elsevier, vol. 120(C).
    3. Herings, P. Jean-Jacques & Zhan, Yang, 2021. "The computation of pairwise stable networks," Research Memorandum 004, Maastricht University, Graduate School of Business and Economics (GSBE).
    4. Akhil Jalan & Deepayan Chakrabarti & Purnamrita Sarkar, 2024. "Incentive-Aware Models of Financial Networks," Operations Research, INFORMS, vol. 72(6), pages 2321-2336, November.
    5. Bich, Philippe & Teteryatnikova, Mariya, 2023. "On perfect pairwise stable networks," Journal of Economic Theory, Elsevier, vol. 207(C).
    6. Herings, P. Jean-Jacques, 2024. "Globally and universally convergent price adjustment processes," Journal of Mathematical Economics, Elsevier, vol. 113(C).
    7. Khai Chiong & Anyan Qi, 2025. "Stability of Procurement Networks," Manufacturing & Service Operations Management, INFORMS, vol. 27(6), pages 1923-1938, November.
    8. John Higgins & Tarun Sabarwal, 2023. "Control and spread of contagion in networks with global effects," Journal of Public Economic Theory, Association for Public Economic Theory, vol. 25(6), pages 1149-1187, December.
    9. John Higgins & Tarun Sabarwal, 2021. "Control and Spread of Contagion in Networks," WORKING PAPERS SERIES IN THEORETICAL AND APPLIED ECONOMICS 202201, University of Kansas, Department of Economics, revised Jan 2022.
    10. Bich, Philippe & Fixary, Julien, 2024. "Oddness of the number of Nash equilibria: The case of polynomial payoff functions," Games and Economic Behavior, Elsevier, vol. 145(C), pages 510-525.
    11. Yiyin Cao & Chuangyin Dang & Yixiong Yu, 2025. "Efficient Differentiable Path-Following Methods for Computing Nash Equilibria," Computational Economics, Springer;Society for Computational Economics, vol. 66(6), pages 5155-5188, December.
    12. Yiyin Cao & Chuangyin Dang, 2025. "A Characterization of Reny's Weakly Sequentially Rational Equilibrium through $\varepsilon$-Perfect $\gamma$-Weakly Sequentially Rational Equilibrium," Papers 2505.19496, arXiv.org.
    13. Steffen Eibelshäuser & Victor Klockmann & David Poensgen & Alicia von Schenk, 2023. "The Logarithmic Stochastic Tracing Procedure: A Homotopy Method to Compute Stationary Equilibria of Stochastic Games," INFORMS Journal on Computing, INFORMS, vol. 35(6), pages 1511-1526, November.
    14. Philippe Bich & Lisa Morhaim, 2020. "On the Existence of Pairwise Stable Weighted Networks," Mathematics of Operations Research, INFORMS, vol. 45(4), pages 1393-1404, November.
    15. Zaruhi Hakobyan & Christos Koulovatianos, 2021. "Symmetric Markovian Games of Commons with Potentially Sustainable Endogenous Growth," Dynamic Games and Applications, Springer, vol. 11(1), pages 54-83, March.
    16. Yiyin Cao & Yin Chen & Chuangyin Dang, 2024. "A Variant of the Logistic Quantal Response Equilibrium to Select a Perfect Equilibrium," Journal of Optimization Theory and Applications, Springer, vol. 201(3), pages 1026-1062, June.
    17. Yiyin Cao & Chuangyin Dang, 2025. "A Characterization of Nash Equilibrium in Behavioral Strategies through Local Sequential Rationality," Papers 2504.00529, arXiv.org, revised Apr 2025.
    18. Kris De Jaegher, 2016. "Endogenous thresholds and assurance networks in collective action," Rationality and Society, , vol. 28(2), pages 202-252, May.
    19. Yiyin Cao & Chuangyin Dang & Yabin Sun, 2022. "Complementarity Enhanced Nash’s Mappings and Differentiable Homotopy Methods to Select Perfect Equilibria," Journal of Optimization Theory and Applications, Springer, vol. 192(2), pages 533-563, February.
    20. Chuangyin Dang & P. Jean-Jacques Herings & Peixuan Li, 2022. "An Interior-Point Differentiable Path-Following Method to Compute Stationary Equilibria in Stochastic Games," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1403-1418, May.

    More about this item

    Keywords

    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:37:y:2025:i:4:p:917-932. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.