{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,30]],"date-time":"2026-06-30T17:36:39Z","timestamp":1782840999791,"version":"3.54.5"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2022,3,14]],"date-time":"2022-03-14T00:00:00Z","timestamp":1647216000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,3,14]],"date-time":"2022-03-14T00:00:00Z","timestamp":1647216000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2024,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>One of the most important stability concepts for network formation is pairwise stability. We develop a homotopy algorithm that is effective in computing pairwise stable networks for a generic network formation problem. To do so, we reformulate the concept of pairwise stability as a Nash equilibrium of a non-cooperative game played by the links in the network and adapt the linear tracing procedure for non-cooperative games to the network formation problem. As a by-product of our main result, we obtain that the number of pairwise stable networks is generically odd. We apply the algorithm to the connections model and obtain a number of novel insights.<\/jats:p>","DOI":"10.1007\/s10107-022-01791-x","type":"journal-article","created":{"date-parts":[[2022,3,14]],"date-time":"2022-03-14T14:04:07Z","timestamp":1647266647000},"page":"443-473","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["The computation of pairwise stable networks"],"prefix":"10.1007","volume":"203","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1100-8601","authenticated-orcid":false,"given":"P. Jean-Jacques","family":"Herings","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5772-7321","authenticated-orcid":false,"given":"Yang","family":"Zhan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,3,14]]},"reference":[{"key":"1791_CR1","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1137\/1022003","volume":"22","author":"EL Allgower","year":"1980","unstructured":"Allgower, E.L., Georg, K.: Simplicial and continuation methods for approximating fixed points and solutions to systems of equations. SIAM Rev. 22, 28\u201385 (1980)","journal-title":"SIAM Rev."},{"key":"1791_CR2","doi-asserted-by":"publisher","first-page":"1393","DOI":"10.1287\/moor.2019.1032","volume":"45","author":"P Bich","year":"2020","unstructured":"Bich, P., Morhaim, L.: On the existence of pairwise stable weighted networks. Math. Oper. Res. 45, 1393\u20131404 (2020)","journal-title":"Math. Oper. Res."},{"key":"1791_CR3","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/s00182-006-0022-9","volume":"34","author":"F Bloch","year":"2006","unstructured":"Bloch, F., Jackson, M.O.: Definitions of equilibrium in network formation games. Int. J. Game Theory 34, 305\u2013318 (2006)","journal-title":"Int. J. Game Theory"},{"key":"1791_CR4","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/s00182-008-0140-7","volume":"38","author":"A Calv\u00f3-Armengol","year":"2009","unstructured":"Calv\u00f3-Armengol, A., \u0130lk\u0131l\u0131\u00e7, R.: Pairwise-stability and nash equilibria in network formation. Int. J. Game Theory 38, 51\u201379 (2009)","journal-title":"Int. J. Game Theory"},{"key":"1791_CR5","first-page":"13","volume":"11","author":"S Chakrabarti","year":"2007","unstructured":"Chakrabarti, S., Gilles, R.P.: Network potentials. Rev. Econ. Des. 11, 13\u201352 (2007)","journal-title":"Rev. Econ. Des."},{"key":"1791_CR6","doi-asserted-by":"publisher","first-page":"1249","DOI":"10.1016\/S0165-1889(98)00073-6","volume":"23","author":"BC Eaves","year":"1999","unstructured":"Eaves, B.C., Schmedders, K.: General equilibrium models and homotopy methods. J. Econ. Dyn. Control 23, 1249\u20131279 (1999)","journal-title":"J. Econ. Dyn. Control"},{"key":"1791_CR7","volume-title":"Pathways to Solutions, Fixed Points, and Equilibria","author":"CB Garcia","year":"1981","unstructured":"Garcia, C.B., Zangwill, W.I.: Pathways to Solutions, Fixed Points, and Equilibria. Prentice-Hall Series in Computational Mathematics, Prentice-Hall, Englewood Cliffs (1981)"},{"key":"1791_CR8","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/S0022-0531(03)00005-X","volume":"110","author":"S Govindan","year":"2003","unstructured":"Govindan, S., Wilson, R.: A global newton method to compute nash equilibria. J. Econ. Theory 110, 65\u201386 (2003)","journal-title":"J. Econ. Theory"},{"key":"1791_CR9","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1016\/j.jet.2008.06.002","volume":"144","author":"S Govindan","year":"2009","unstructured":"Govindan, S., Wilson, R.: Global newton method for stochastic Games. J. Econo. Theory 144, 414\u2013421 (2009)","journal-title":"J. Econo. Theory"},{"key":"1791_CR10","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/BF01737572","volume":"2","author":"JC Harsanyi","year":"1973","unstructured":"Harsanyi, J.C.: Oddness of the number of equilibrium points. Int. J. Game Theory 2, 235\u2013250 (1973)","journal-title":"Int. J. Game Theory"},{"key":"1791_CR11","volume-title":"A General Theory of Equilibrium Selection in Games","author":"JC Harsanyi","year":"1988","unstructured":"Harsanyi, J.C., Selten, R.: A General Theory of Equilibrium Selection in Games. MIT Press, Cambridge (1988)"},{"key":"1791_CR12","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/s00182-012-0335-9","volume":"42","author":"T Hellmann","year":"2013","unstructured":"Hellmann, T.: On the existence and uniqueness of pairwise stable networks. Int. J. Game Theory 42, 211\u2013237 (2013)","journal-title":"Int. J. Game Theory"},{"key":"1791_CR13","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/PL00004129","volume":"18","author":"PJJ Herings","year":"2001","unstructured":"Herings, P.J.J., Peeters, R.J.A.P.: A differentiable homotopy to compute nash equilibria of $$ n$$-person games. Econ. Theory 18, 159\u2013185 (2001)","journal-title":"Econ. Theory"},{"key":"1791_CR14","first-page":"32","volume":"118","author":"PJJ Herings","year":"2004","unstructured":"Herings, P.J.J., Peeters, R.J.A.P.: Stationary equilibria in stochastic games: structure, selection, and computation. J. Econ. Theory 118, 32\u201360 (2004)","journal-title":"J. Econ. Theory"},{"key":"1791_CR15","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/s00199-009-0441-5","volume":"42","author":"PJJ Herings","year":"2010","unstructured":"Herings, P.J.J., Peeters, R.J.A.P.: Homotopy methods to compute equilibria in game theory. Econ. Theory 42, 119\u2013156 (2010)","journal-title":"Econ. Theory"},{"key":"1791_CR16","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1016\/j.geb.2004.08.004","volume":"51","author":"MO Jackson","year":"2005","unstructured":"Jackson, M.O., van den Nouweland, A.: Strongly stable networks. Games Econ. Behav. 51, 420\u2013444 (2005)","journal-title":"Games Econ. Behav."},{"key":"1791_CR17","first-page":"299","volume":"14","author":"MO Jackson","year":"2001","unstructured":"Jackson, M.O., Watts, A.: The existence of pairwise stable networks. Seoul J. Econ. 14, 299\u2013321 (2001)","journal-title":"Seoul J. Econ."},{"key":"1791_CR18","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1006\/jeth.1996.0108","volume":"71","author":"MO Jackson","year":"1996","unstructured":"Jackson, M.O., Wolinsky, A.: A strategic model of social and economic networks. J. Econ. Theory 71, 44\u201374 (1996)","journal-title":"J. Econ. Theory"},{"key":"1791_CR19","unstructured":"Jongen, H.T., Jonker, P., Twilt, F.: Nonlinear optimization in $${\\mathbb{R}}^{n}$$, I. Morse Theory, Chebyshev Approximation, Methoden und Verfahren der Mathematischen Physik, 29, Peter Lang, Frankfurt (1983)"},{"key":"1791_CR20","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/0112033","volume":"12","author":"CE Lemke","year":"1964","unstructured":"Lemke, C.E., Howson, J.T., Jr.: Equilibrium points of bimatrix games. SIAM J. Appl. Math. 12, 413\u2013423 (1964)","journal-title":"SIAM J. Appl. Math."},{"key":"1791_CR21","doi-asserted-by":"publisher","first-page":"1325","DOI":"10.3982\/QE1386","volume":"11","author":"MP Leung","year":"2020","unstructured":"Leung, M.P.: Equilibrium computation in discrete network games. Quant. Econ. 11, 1325\u20131347 (2020)","journal-title":"Quant. Econ."},{"key":"1791_CR22","doi-asserted-by":"publisher","first-page":"667","DOI":"10.1007\/s10957-020-01703-z","volume":"186","author":"P Li","year":"2020","unstructured":"Li, P., Dang, C.: An arbitrary starting tracing procedure for computing subgame perfect equilibria. J. Optim. Theory Appl. 186, 667\u2013687 (2020)","journal-title":"J. Optim. Theory Appl."},{"key":"1791_CR23","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/BF01580239","volume":"6","author":"A Mas-Colell","year":"1974","unstructured":"Mas-Colell, A.: A note on a theorem of F. Browder. Math. Prog. 6, 229\u2013233 (1974)","journal-title":"Math. Prog."},{"key":"1791_CR24","doi-asserted-by":"crossref","unstructured":"Mas-Colell, A.: The Theory of General Economic Equilibrium. Cambridge University Press, Cambridge, A Differentiable Approach (1985)","DOI":"10.1017\/CCOL0521265142"},{"key":"1791_CR25","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1111\/j.1468-0262.2005.00567.x","volume":"73","author":"A McLennan","year":"2005","unstructured":"McLennan, A.: The expected number of nash equilibria of a normal form game. Econometrica 73, 141\u2013174 (2005)","journal-title":"Econometrica"},{"key":"1791_CR26","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1016\/j.jeconom.2016.08.001","volume":"195","author":"Y Miyauchi","year":"2016","unstructured":"Miyauchi, Y.: Structural estimation of pairwise stable networks with nonnegative externality. J. Econ. 195, 224\u2013235 (2016)","journal-title":"J. Econ."},{"key":"1791_CR27","volume-title":"Game Equilibrium Models II: Methods, Morals and Markets","author":"SH Schanuel","year":"1991","unstructured":"Schanuel, S.H., Simon, L.K., Zame, W.R.: The algebraic geometry of games and the tracing procedure. In: Selten, R. (ed.) Game Equilibrium Models II: Methods, Morals and Markets. Springer-Verlag, Berlin (1991)"},{"key":"1791_CR28","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1007\/PL00009438","volume":"21","author":"B von Stengel","year":"1999","unstructured":"von Stengel, B.: New maximal numbers of equilibria in bimatrix games. Discrete Comput. Geometry 21, 557\u2013568 (1999)","journal-title":"Discrete Comput. Geometry"}],"updated-by":[{"DOI":"10.1007\/s10107-022-01814-7","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2022,4,12]],"date-time":"2022-04-12T00:00:00Z","timestamp":1649721600000}}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01791-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-022-01791-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01791-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,12]],"date-time":"2024-02-12T18:05:41Z","timestamp":1707761141000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-022-01791-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,14]]},"references-count":28,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["1791"],"URL":"https:\/\/doi.org\/10.1007\/s10107-022-01791-x","relation":{"correction":[{"id-type":"doi","id":"10.1007\/s10107-022-01814-7","asserted-by":"object"}]},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,14]]},"assertion":[{"value":"7 December 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 February 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 March 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 April 2022","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"A Correction to this paper has been published:","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s10107-022-01814-7","URL":"https:\/\/doi.org\/10.1007\/s10107-022-01814-7","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}