The computation of pairwise stable networks. (English) Zbl 1533.90032
Summary: 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.
MSC:
| 90B10 | Deterministic network models in operations research |
| 90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |
| 91A43 | Games involving graphs |
| 91-08 | Computational methods for problems pertaining to game theory, economics, and finance |
References:
| [1] | Allgower, EL; Georg, K., Simplicial and continuation methods for approximating fixed points and solutions to systems of equations, SIAM Rev., 22, 28-85 (1980) · Zbl 0432.65027 · doi:10.1137/1022003 |
| [2] | Bich, P.; Morhaim, L., On the existence of pairwise stable weighted networks, Math. Oper. Res., 45, 1393-1404 (2020) · Zbl 1451.90026 · doi:10.1287/moor.2019.1032 |
| [3] | Bloch, F.; Jackson, MO, Definitions of equilibrium in network formation games, Int. J. Game Theory, 34, 305-318 (2006) · Zbl 1178.91033 · doi:10.1007/s00182-006-0022-9 |
| [4] | Calvó-Armengol, A.; İlkılıç, R., Pairwise-stability and nash equilibria in network formation, Int. J. Game Theory, 38, 51-79 (2009) · Zbl 1211.91080 · doi:10.1007/s00182-008-0140-7 |
| [5] | Chakrabarti, S.; Gilles, RP, Network potentials, Rev. Econ. Des., 11, 13-52 (2007) · Zbl 1274.91358 |
| [6] | Eaves, BC; Schmedders, K., General equilibrium models and homotopy methods, J. Econ. Dyn. Control, 23, 1249-1279 (1999) · Zbl 1016.91074 · doi:10.1016/S0165-1889(98)00073-6 |
| [7] | Garcia, CB; Zangwill, WI, Pathways to Solutions, Fixed Points, and Equilibria (1981), Prentice-Hall, Englewood Cliffs: Prentice-Hall Series in Computational Mathematics, Prentice-Hall, Englewood Cliffs · Zbl 0512.90070 |
| [8] | Govindan, S.; Wilson, R., A global newton method to compute nash equilibria, J. Econ. Theory, 110, 65-86 (2003) · Zbl 1042.91001 · doi:10.1016/S0022-0531(03)00005-X |
| [9] | Govindan, S.; Wilson, R., Global newton method for stochastic Games, J. Econo. Theory, 144, 414-421 (2009) · Zbl 1154.91331 · doi:10.1016/j.jet.2008.06.002 |
| [10] | Harsanyi, JC, Oddness of the number of equilibrium points, Int. J. Game Theory, 2, 235-250 (1973) · Zbl 0274.90085 · doi:10.1007/BF01737572 |
| [11] | Harsanyi, JC; Selten, R., A General Theory of Equilibrium Selection in Games (1988), Cambridge: MIT Press, Cambridge · Zbl 0693.90098 |
| [12] | Hellmann, T., On the existence and uniqueness of pairwise stable networks, Int. J. Game Theory, 42, 211-237 (2013) · Zbl 1282.91278 · doi:10.1007/s00182-012-0335-9 |
| [13] | Herings, PJJ; Peeters, RJAP, A differentiable homotopy to compute nash equilibria of \(n\)-person games, Econ. Theory, 18, 159-185 (2001) · Zbl 0986.91001 · doi:10.1007/PL00004129 |
| [14] | Herings, PJJ; Peeters, RJAP, Stationary equilibria in stochastic games: structure, selection, and computation, J. Econ. Theory, 118, 32-60 (2004) · Zbl 1117.91009 |
| [15] | Herings, PJJ; Peeters, RJAP, Homotopy methods to compute equilibria in game theory, Econ. Theory, 42, 119-156 (2010) · Zbl 1185.91028 · doi:10.1007/s00199-009-0441-5 |
| [16] | Jackson, MO; van den Nouweland, A., Strongly stable networks, Games Econ. Behav., 51, 420-444 (2005) · Zbl 1099.91011 · doi:10.1016/j.geb.2004.08.004 |
| [17] | Jackson, MO; Watts, A., The existence of pairwise stable networks, Seoul J. Econ., 14, 299-321 (2001) |
| [18] | Jackson, MO; Wolinsky, A., A strategic model of social and economic networks, J. Econ. Theory, 71, 44-74 (1996) · Zbl 0871.90144 · doi:10.1006/jeth.1996.0108 |
| [19] | 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) · Zbl 0527.90064 |
| [20] | Lemke, CE; Howson, JT Jr, Equilibrium points of bimatrix games, SIAM J. Appl. Math., 12, 413-423 (1964) · Zbl 0128.14804 · doi:10.1137/0112033 |
| [21] | Leung, MP, Equilibrium computation in discrete network games, Quant. Econ., 11, 1325-1347 (2020) · Zbl 1466.91057 · doi:10.3982/QE1386 |
| [22] | Li, P.; Dang, C., An arbitrary starting tracing procedure for computing subgame perfect equilibria, J. Optim. Theory Appl., 186, 667-687 (2020) · Zbl 1447.91017 · doi:10.1007/s10957-020-01703-z |
| [23] | Mas-Colell, A., A note on a theorem of F. Browder, Math. Prog., 6, 229-233 (1974) · Zbl 0285.90068 · doi:10.1007/BF01580239 |
| [24] | Mas-Colell, A.: The Theory of General Economic Equilibrium. Cambridge University Press, Cambridge, A Differentiable Approach (1985) |
| [25] | McLennan, A., The expected number of nash equilibria of a normal form game, Econometrica, 73, 141-174 (2005) · Zbl 1152.91326 · doi:10.1111/j.1468-0262.2005.00567.x |
| [26] | Miyauchi, Y., Structural estimation of pairwise stable networks with nonnegative externality, J. Econ., 195, 224-235 (2016) · Zbl 1443.62495 · doi:10.1016/j.jeconom.2016.08.001 |
| [27] | Schanuel, SH; Simon, LK; Zame, WR; Selten, R., The algebraic geometry of games and the tracing procedure, Game Equilibrium Models II: Methods, Morals and Markets (1991), Berlin: Springer-Verlag, Berlin · Zbl 0813.90134 |
| [28] | von Stengel, B., New maximal numbers of equilibria in bimatrix games, Discrete Comput. Geometry, 21, 557-568 (1999) · Zbl 0956.91003 · doi:10.1007/PL00009438 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
