Computing the Stackelberg/Nash equilibria using the extraproximal method: Convergence analysis and implementation details for Markov chains games

Trejo, K. K. ; Clempner, J. B. ; Poznyak, A. S.

International Journal of Applied Mathematics and Computer Science, Tome 25 (2015) no. 2, pp. 337-351.

Résumé

In this paper we present the extraproximal method for computing the Stackelberg/Nash equilibria in a class of ergodic controlled finite Markov chains games. We exemplify the original game formulation in terms of coupled nonlinear programming problems implementing the Lagrange principle. In addition, Tikhonov's regularization method is employed to ensure the convergence of the cost-functions to a Stackelberg/Nash equilibrium point. Then, we transform the problem into a system of equations in the proximal format. We present a two-step iterated procedure for solving the extraproximal method: (a) the first step (the extra-proximal step) consists of a “prediction” which calculates the preliminary position approximation to the equilibrium point, and (b) the second step is designed to find a “basic adjustment” of the previous prediction. The procedure is called the “extraproximal method” because of the use of an extrapolation. Each equation in this system is an optimization problem for which the necessary and efficient condition for a minimum is solved using a quadratic programming method. This solution approach provides a drastically quicker rate of convergence to the equilibrium point. We present the analysis of the convergence as well the rate of convergence of the method, which is one of the main results of this paper. Additionally, the extraproximal method is developed in terms of Markov chains for Stackelberg games. Our goal is to analyze completely a three-player Stackelberg game consisting of a leader and two followers. We provide all the details needed to implement the extraproximal method in an efficient and numerically stable way. For instance, a numerical technique is presented for computing the first step parameter (λ) of the extraproximal method. The usefulness of the approach is successfully demonstrated by a numerical example related to a pricing oligopoly model for airlines companies.

Détail

Keywords: extraproximal method, Stackelberg games, convergence analysis, Markov chains, implementation
Mots-clés : gry Stackelberga, analiza zbieżności, łańcuchy Markowa

Bibliographie

[1] Antipin, A.S. (2005). An extraproximal method for solving equilibrium programming problems and games, Computational Mathematics and Mathematical Physics 45(11): 1893–1914.

[2] Bos, D. (1986). Public Enterprise Economics, North-Holland, Amsterdam.

[3] Bos, D. (1991). Privatization: A Theoretical Treatment, Clarendon Press, Oxford.

[4] Breitmoser, Y. (2012). On the endogeneity of Cournot, Bertrand, and Stackelberg competition in oligopolies, International Journal of Industrial Organization 30(1): 16–29.

[5] Clempner, J.B. and Poznyak, A.S. (2011). Convergence method, properties and computational complexity for Lyapunov games, International Journal of Applied Mathematics and Computer Science 21(2): 349–361, DOI: 10.2478/v10006-011-0026-x.

[6] Clempner, J.B. and Poznyak, A.S. (2014). Simple computing of the customer lifetime value: A fixed local-optimal policy approach, Journal of Systems Science and Systems Engineering 23(4): 439–459.

[7] De Fraja, G. and Delbono, F. (1990 ). Game theoretic models of mixed oligopoly, Journal of Economic Surveys 4(1): 1–17.

[8] Harris, R. and Wiens, E. (1980). Government enterprise: An instrument for the internal regulation of industry, Canadian Journal of Economics 13(1): 125–132.

[9] Karpowicz, M.P. (2012). Nash equilibrium design and price-based coordination in hierarchical systems, International Journal of Applied Mathematics and Computer Science 22(4): 951–969, DOI: 10.2478/v10006-012-0071-0.

[10] Merril, W. and Schneider, N. (1966). Government firms in oligopoly industries: A short-run analysis, Quarterly Journal of Economics 80(5): 400–412.

[11] Moya, S. and Poznyak, A.S. (2009). Extraproximal method application for a Stackelberg–Nash equilibrium calculation in static hierarchical games, IEEE Transactions on Systems, Man, and Cybernetics, B: Cybernetics 39(6): 1493–1504.

[12] Nett, L. (1993). Mixed oligopoly with homogeneous goods, Annals of Public and Cooperative Economics 64(3): 367–393.

[13] Nowak, P. and Romaniuk, M. (2013). A fuzzy approach to option pricing in a Levy process setting, International Journal of Applied Mathematics and Computer Science 23(3): 613–622, DOI: 10.2478/amcs-2013-0046.

[14] Poznyak, A.S. (2009). Advance Mathematical Tools for Automatic Control Engineers, Vol. 1: Deterministic Techniques, Elsevier, Amsterdam.

[15] Poznyak, A.S., Najim, K. and Gomez-Ramirez, E. (2000). Selflearning Control of Finite Markov Chains, Marcel Dekker, Inc., New York, NY.

[16] Tanaka, K. and Yokoyama, K. (1991). On ε-equilibrium point in a noncooperative n-person game, Journal of Mathematical Analysis and Applications 160(2): 413–423.

[17] Trejo, K.K., Clempner, J.B. and Poznyak, A.S. (2015). A stackelberg security game with random strategies based on the extraproximal theoretic approach, Engineering Applications of Artificial Intelligence 37: 145–153.

[18] Vickers, J. and Yarrow., G. (1998). Privatization—An Economic Analysis, MIT Press, Cambridge, MA.

[19] von Stackelberg, H. (1934). Marktform und Gleichgewicht, Springer, Vienna.