1. bookVolume 25 (2015): Issue 2 (June 2015)
Journal Details
License
Format
Journal
First Published
05 Apr 2007
Publication timeframe
4 times per year
Languages
English
access type Open Access

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

Published Online: 25 Jun 2015
Page range: 337 - 351
Received: 21 Mar 2014
Journal Details
License
Format
Journal
First Published
05 Apr 2007
Publication timeframe
4 times per year
Languages
English

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.

Keywords

Antipin, A.S. (2005). An extraproximal method for solving equilibrium programming problems and games, Computational Mathematics and Mathematical Physics 45(11): 1893-1914.Search in Google Scholar

Bos, D. (1986). Public Enterprise Economics, North-Holland, Amsterdam.Search in Google Scholar

Bos, D. (1991). Privatization: A Theoretical Treatment, Clarendon Press, Oxford.Search in Google Scholar

Breitmoser, Y. (2012). On the endogeneity of Cournot, Bertrand, and Stackelberg competition in oligopolies, International Journal of Industrial Organization 30(1): 16-29.Search in Google Scholar

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.Search in Google Scholar

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.Search in Google Scholar

De Fraja, G. and Delbono, F. (1990 ). Game theoretic models of mixed oligopoly, Journal of Economic Surveys 4(1): 1-17.Search in Google Scholar

Harris, R. and Wiens, E. (1980). Government enterprise: An instrument for the internal regulation of industry, Canadian Journal of Economics 13(1): 125-132.Search in Google Scholar

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.Search in Google Scholar

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

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.Search in Google Scholar

Nett, L. (1993). Mixed oligopoly with homogeneous goods, Annals of Public and Cooperative Economics 64(3): 367-393.Search in Google Scholar

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.Search in Google Scholar

Poznyak, A.S. (2009). Advance Mathematical Tools for Automatic Control Engineers, Vol. 1: Deterministic Techniques, Elsevier, Amsterdam.Search in Google Scholar

Poznyak, A.S., Najim, K. and Gomez-Ramirez, E. (2000). Selflearning Control of Finite Markov Chains, Marcel Dekker, Inc., New York, NY.Search in Google Scholar

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.Search in Google Scholar

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.Search in Google Scholar

Vickers, J. and Yarrow., G. (1998). Privatization-An Economic Analysis, MIT Press, Cambridge, MA. von Stackelberg, H. (1934). Marktform und Gleichgewicht, Springer, Vienna Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo