×

Computing perfect stationary equilibria in stochastic games. (English) Zbl 07931344

Summary: The notion of stationary equilibrium is one of the most crucial solution concepts in stochastic games. However, a stochastic game can have multiple stationary equilibria, some of which may be unstable or counterintuitive. As a refinement of stationary equilibrium, we extend the concept of perfect equilibrium in strategic games to stochastic games and formulate the notion of perfect stationary equilibrium (PeSE). To further promote its applications, we develop a differentiable homotopy method to compute such an equilibrium. We incorporate vanishing logarithmic barrier terms into the payoff functions, thereby constituting a logarithmic-barrier stochastic game. As a result of this barrier game, we attain a continuously differentiable homotopy system. To reduce the number of variables in the homotopy system, we eliminate the Bellman equations through a replacement of variables and derive an equivalent system. We use the equivalent system to establish the existence of a smooth path, which starts from an arbitrary total mixed strategy profile and ends at a PeSE. Extensive numerical experiments, including relevant applications like dynamic oligopoly models and dynamic legislative voting, further affirm the effectiveness and efficiency of the method.

MSC:

91-XX Game theory, economics, finance, and other social and behavioral sciences

References:

[1] Abbring, JH; Campbell, JR; Tilly, J., Very simple Markov-perfect industry dynamics: theory, Econometrica, 86, 2, 721-735, 2018 · Zbl 1419.91457
[2] Acemoglu, D., Egorov, G., Sonin, K.: Equilibrium refinement in dynamic voting games. MIT Department of Economics Working Paper Series, Working Paper 09-26, Massachusetts Institute of Technology (2009)
[3] Allgower, EL; Georg, K., Numerical Continuation Methods: An Introduction, 2012, Berlin: Springer, Berlin
[4] Amir, R.; Mertens, J.; Neyman, A.; Neyman, A.; Sorin, S., Stochastic games in economics and related fields: an overview, Stochastic Games and Applications, 2003, Dordrecht: Springer, Dordrecht
[5] Browder, FE, On continuity of fixed points under deformations of continuous mappings, Summa Bras. Math., 4, 183-191, 1960 · Zbl 0102.37807
[6] Chatterjee, K.; Dutta, B.; Ray, D., A noncooperative theory of coalitional bargaining, Rev. Econ. Stud., 60, 2, 463-477, 1993 · Zbl 0776.90092
[7] Chen, Y.; Dang, C., A reformulation-based simplicial homotopy method for approximating perfect equilibria, Comput. Econ., 54, 3, 877-891, 2019
[8] Chen, Y.; Dang, C., A differentiable homotopy method to compute perfect equilibria, Math. Program., 185, 77-109, 2021 · Zbl 1458.91018
[9] Dang, C.; Herings, PJJ; Li, P., An interior-point differentiable path-following method to compute stationary equilibria in stochastic games, INFORMS J. Comput., 34, 3, 1403-1418, 2022 · Zbl 07552214
[10] Dirkse, SP; Ferris, MC, The path solver: a nommonotone stabilization scheme for mixed complementarity problems, Optim. Methods Softw., 5, 2, 123-156, 1995
[11] Doraszelski, U.; Pakes, A., A framework for applied dynamic analysis in IO, Handb. Ind. Organ., 3, 1887-1966, 2007
[12] Doraszelski, U.; Satterthwaite, M., Computable Markov-perfect industry dynamics, Rand J. Econ., 41, 2, 215-243, 2010
[13] Duggan, J.; Kalandrakis, T., Dynamic legislative policy making, J. Econ. Theory, 147, 5, 1653-1688, 2012 · Zbl 1247.91073
[14] Eaves, BC; Schmedders, K., General equilibrium models and homotopy methods, J. Econ. Dyn. Control, 23, 9-10, 1249-1279, 1999 · Zbl 1016.91074
[15] Eibelshäuser, S., Poensgen, D.: Markov quantal response equilibrium and a homotopy method for computing and selecting Markov perfect equilibria of dynamic stochastic games. Available at SSRN 3314404 (2019)
[16] Eraslan, H.; Evdokimov, KS; Zápal, J.; Karagozoglu, E.; Hyndman, KB, Dynamic legislative bargaining, Bargaining: Current Research and Future Directions, 151-175, 2022, Cham: Palgrave Macmillan, Cham
[17] Ericson, R.; Pakes, A., Markov-perfect industry dynamics: a framework for empirical work, Rev. Econ. Stud., 62, 1, 53-82, 1995 · Zbl 0828.90026
[18] Fink, AM, Equilibrium in a stochastic \(n \)-person game, J. Sci. Hiroshima Univ. Ser. AI (Math.), 28, 1, 89-93, 1964 · Zbl 0126.36506
[19] Goldlücke, S.; Kranz, S., Discounted stochastic games with voluntary transfers, Econ. Theory, 66, 1, 235-263, 2018 · Zbl 1416.91031
[20] Gomes, A.; Jehiel, P., Dynamic processes of social and economic interactions: on the persistence of inefficiencies, J. Political Econ., 113, 3, 626-667, 2005
[21] Govindan, S.; Wilson, R., Global Newton method for stochastic games, J. Econ. Theory, 144, 1, 414-421, 2009 · Zbl 1154.91331
[22] Hansen, K.A., Miltersen, P.B., Sørensen, T.B.: The computational complexity of trembling hand perfection and other equilibrium refinements. In: International Symposium on Algorithmic Game Theory. Springer, Berlin, pp. 198-209 (2010) · Zbl 1310.91014
[23] Harsanyi, JC, The tracing procedure: a Bayesian approach to defining a solution for \(n\)-person noncooperative games, Int. J. Game Theory, 4, 61-94, 1975 · Zbl 0319.90078
[24] Harsanyi, JC; Selten, R., A General Theory of Equilibrium Selection in Games, 1988, Cambridge: MIT Press, Cambridge · Zbl 0693.90098
[25] He, W., Discontinuous stochastic games, Econ. Theory, 73, 4, 827-858, 2022 · Zbl 1492.91040
[26] Herings, PJJ, Two simple proofs of the feasibility of the linear tracing procedure, Econ. Theory, 15, 2, 485-490, 2000 · Zbl 0956.91008
[27] Herings, PJJ; Peeters, RJAP, A differentiable homotopy to compute Nash equilibria of \(n\)-person games, Econ. Theory, 18, 1, 159-185, 2001 · Zbl 0986.91001
[28] Herings, PJJ; Peeters, RJAP, Stationary equilibria in stochastic games: structure, selection, and computation, J. Econ. Theory, 118, 32-60, 2004 · Zbl 1117.91009
[29] Herings, PJJ; Schmedders, K., Computing equilibria in finance economies with incomplete markets and transaction costs, Econ. Theory, 27, 3, 493-512, 2006 · Zbl 1087.91032
[30] Herings, PJJ; Peeters, R.; Schinkel, MP, Intertemporal market division: a case of alternating monopoly, Eur. Econ. Rev., 49, 5, 1207-1223, 2005
[31] Li, P.; Dang, C., An arbitrary starting tracing procedure for computing subgame perfect equilibria, J. Optim. Theory Appl., 186, 2, 667-687, 2020 · Zbl 1447.91017
[32] Manea, M., Intermediation and resale in networks, J. Political Econ., 126, 3, 1250-1301, 2018
[33] Mas-Colell, A., The Theory of General Economic Equilibrium: A Differentiable Approach, 1989, Cambridge: Cambridge University Press, Cambridge
[34] Maskin, E.; Tirole, J., Markov perfect equilibrium: I. Observable actions, J. Econ. Theory, 100, 2, 191-219, 2001 · Zbl 1011.91022
[35] McKelvey, RD; Palfrey, TR, Quantal response equilibria for normal form games, Games Econ. Behav., 10, 1, 6-38, 1995 · Zbl 0832.90126
[36] Mertens, JF, Stable equilibria-a reformulation: Part I. Definition and basic properties, Math. Oper. Res., 14, 4, 575-625, 1989 · Zbl 0687.90097
[37] Myerson, RB, Refinements of the Nash equilibrium concept, Int. J. Game Theory, 7, 2, 73-80, 1978 · Zbl 0392.90093
[38] Okada, A., Dynamic bargaining with voluntary participation and externalities, Econ. Theory, 75, 2, 427-452, 2023 · Zbl 1520.91195
[39] Osborne, MJ; Rubinstein, A., A Course in Game Theory, 1994, Cambridge: MIT Press, Cambridge · Zbl 1194.91003
[40] Schanuel, SH; Simon, LK; Zame, WR; Selten, R., The algebraic geometry of games and the tracing procedure, Game Equilibrium Models II, 9-43, 1991, Berlin: Springer, Berlin · Zbl 0813.90134
[41] Selten, R., Reexamination of the perfectness concept for equilibrium points in extensive games, Int. J. Game Theory, 4, 1, 25-55, 1975 · Zbl 0312.90072
[42] Shapley, LS, Stochastic games, Proc. Natl. Acad. Sci., 39, 10, 1095-1100, 1953 · Zbl 0051.35805
[43] Sobel, M., Noncooperative stochastic games, Ann. Math. Stat., 42, 6, 1930-1935, 1971 · Zbl 0229.90059
[44] Takahashi, M., Equilibrium points of stochastic non-cooperative \(n \)-person games, J. Sci. Hiroshima Univ. Ser. AI (Math.), 28, 1, 95-99, 1964 · Zbl 0133.13103
[45] van den Elzen, A.; Talman, AJJ, A procedure for finding Nash equilibria in bi-matrix games, Z. Oper. Res., 35, 27-43, 1991 · Zbl 0729.90093
[46] von Stengel, B.; van den Elzen, A.; Talman, D., Computing normal form perfect equilibria for extensive two-person games, Econometrica, 70, 2, 693-715, 2002 · Zbl 1103.91319
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.