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

• Volume: 25, Issue: 2, page 337-351
• ISSN: 1641-876X

top

## Abstract

top
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.

## How to cite

top

Kristal K. Trejo, Julio B. Clempner, and Alexander S. Poznyak. "Computing the Stackelberg/Nash equilibria using the extraproximal method: Convergence analysis and implementation details for Markov chains games." International Journal of Applied Mathematics and Computer Science 25.2 (2015): 337-351. <http://eudml.org/doc/270754>.

@article{KristalK2015,
abstract = {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.},
author = {Kristal K. Trejo, Julio B. Clempner, Alexander S. Poznyak},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {extraproximal method; Stackelberg games; convergence analysis; Markov chains; implementation},
language = {eng},
number = {2},
pages = {337-351},
title = {Computing the Stackelberg/Nash equilibria using the extraproximal method: Convergence analysis and implementation details for Markov chains games},
url = {http://eudml.org/doc/270754},
volume = {25},
year = {2015},
}

TY - JOUR
AU - Kristal K. Trejo
AU - Julio B. Clempner
AU - Alexander S. Poznyak
TI - Computing the Stackelberg/Nash equilibria using the extraproximal method: Convergence analysis and implementation details for Markov chains games
JO - International Journal of Applied Mathematics and Computer Science
PY - 2015
VL - 25
IS - 2
SP - 337
EP - 351
AB - 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.
LA - eng
KW - extraproximal method; Stackelberg games; convergence analysis; Markov chains; implementation
UR - http://eudml.org/doc/270754
ER -

## References

top
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. Zbl1272.91030
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. Zbl1286.91011
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. Zbl1280.91174
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. Zbl0960.93001
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. Zbl0749.90093
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.

top

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.