An optimal strong equilibrium solution for cooperative multi-leader-follower Stackelberg Markov chains games

Trejo, Kristal K.   ; Clempner, Julio B.   ; Poznyak, Alexander S.

Kybernetika, Tome 52 (2016) no. 2, pp. 258-279

Abstract (VO)

This paper presents a novel approach for computing the strong Stackelberg/Nash equilibrium for Markov chains games. For solving the cooperative $n$-leaders and $m$-followers Markov game we consider the minimization of the $L_{p}-$norm that reduces the distance to the utopian point in the Euclidian space. Then, we reduce the optimization problem to find a Pareto optimal solution. We employ a bi-level programming method implemented by the extraproximal optimization approach for computing the strong $L_{p}-$Stackelberg/Nash equilibrium. We validate the proposed method theoretically and by a numerical experiment related to marketing strategies for supermarkets.

Détail

DOI : 10.14736/kyb-2016-2-0258

Classification : 35K20, 93B05
Keywords: strong equilibrium; Stackelberg and Nash; $L_{p}-$norm; Markov chains

Bibliographie

[1] Aiyoshi, E., Shimizu, K.: Hierarchical decentralized systems and its new solution by abarrier method. IEEE Trans. Systems, Man, and Cybernet. 11 (1981), 444-449. | DOI | MR

[2] Antipin, A. S.: An extraproximal method for solving equilibrium programming problems and games. Comput. Math. and Math. Phys. 45 (2005), 11, 1893-1914. | MR

[3] Bard, J.: Coordination of a multidivisional organization through two levels of management. Omega 11 (1983), 5, 457-468. | DOI

[4] Bard, J.: Practical Bilevel Optimization: Algorithms and Applications, vol 30. Kluwer Academic, Dordrecht 1998. | DOI | MR

[5] Bard, J., Falk, J.: An explicit solution to the multi-level programming problem. Comput. Oper. Res. 9 (1982), 77-100. | DOI | MR

[6] Bianco, L., Caramia, M., Giordani, S.: A bilevel flow model for hazmat transportation network design. Transport. Res. Part C: Emerging Technol. 17 (2009), 2, 175-196. | DOI

[7] Brotcorne, L., Labb, M., Marcotte, P., Savard, G.: A bilevel model for toll optimization on a multicommodity transportation network. Transport. Sci. 35 (2001), 345-358. | DOI

[8] Clempner, J. B., Poznyak, A. S.: Simple computing of the customer lifetime value: A fixed local-optimal policy approach. J. Systems Sci. and Systems Engrg. 23 (2014), 4, 439-459. | DOI

[9] Clempner, J. B., Poznyak, A. S.: Stackelberg security games: Computing the shortest-path equilibrium. Expert Systems Appl. 42 (2015), 8, 3967-3979. | DOI

[10] Cote, J., Marcotte, P., Savard, G.: A bilevel modelling approach to pricing and fare optimisation in the airline industry. J. Revenue and Pricing Management 2 (2003), 1, 23-36. | DOI

[11] Deb, K., Sinha, A.: An efficient and accurate solution methodology for bilevel multi-objective programming problems using a hybrid evolutionary-local-search algorithm. Evolutionary Comput. J. 18 (2010), 3, 403-449. | DOI

[12] Dempe, S.: Discrete Bilevel Optimization Problems. Technical ReportInstitut fur Wirtschaftsinformatik, Universitat Leipzig 2001.

[13] Dempe, S., Kalashnikov, V., Rios-Mercado, R: Discrete bilevel programming: Application to a natural gas cash-out problem. Europ. J. Oper. Res. 166 (2005), 2, 469-488. | DOI | MR | Zbl

[14] DeNegre, S., Ralphs, T.: A branch-and-cut algorithm for integer bilevel linear programs. Oper. Res. Cyber-Infrastruct. 47 (2009), 65-78. | DOI

[15] Fampa, M., Barroso, L., Candal, D., Simonetti, L.: Bilevel optimization applied to strategic pricing in competitive electricity markets. Comput. Optim. Appl. 39 (2008), 2, 121-142. | DOI | MR | Zbl

[16] Fortuny-Amat, J., McCarl, B.: A representation and economic interpretation of a two-level programming problem. J. Oper. Res. Soc. xx (1981), 783-792. | DOI | MR | Zbl

[17] Germeyer, Y. B.: Introduction to the Theory of Operations Research. Nauka, Moscow 1971. | MR

[18] Germeyer, Y. B.: Games with Nonantagonistic Interests. Nauka, Moscow 1976.

[19] Herskovits, J., Leontiev, A., Dias, G., Santos, G.: Contact shape optimization: a bilevel programming approach. Struct. Multidiscipl. Optim. 20 (2000), 214-221. | DOI

[20] Koppe, M., Queyranne, M., Ryan, C. T.: A parametric integer programming algorithm for bilevel mixed integer programs. J. Optim. Theory Appl. 146 (2009), 1, 137-150. | DOI | MR

[21] Labbe, M., Marcotte, P., Savard, G.: A bilevel model of taxation and its application to optimal highway pricing. Management Sci. 44 (1998), 1608-1622. | DOI | Zbl

[22] Lim, C., Smith, J.: Algorithms for discrete and continuous multicommodity flow network interdiction problems. IIE Trans. 39 (2007), 1, 15-26. | DOI

[23] Morton, D., Pan, F., Saeger, K.: Models for nuclear smuggling interdiction. IIE Trans. 39 (2007), 1, 3-14. | DOI

[24] Naoum-Sawaya, J., Elhedhli, S.: Controlled predatory pricing in a multiperiod stackelberg game: an mpec approach. J. Global Optim. 50 (2011), 345-362. | DOI | MR | Zbl

[25] Poznyak, A. S.: Advance Mathematical Tools for Automatic Control Engineers. Vol 2 Deterministic Techniques. Elsevier, Amsterdam 2009. | MR

[26] Poznyak, A. S., Najim, K., Gomez-Ramirez, E.: Self-Learning Control of Finite Markov Chains. Marcel Dekker, New York 2000. | MR | Zbl

[27] Salmeron, J., Wood, K., Baldick, R.: Analysis of electric grid security under terrorist threat. IEEE Trans. Power Syst. 19 (2004), 2, 905-912. | DOI

[28] Tanaka, K.: The closest solution to the shadow minimum of a cooperative dynamic game. Comp. Math. Appl. 18 (1989), 1-3, 181-188. | DOI | MR | Zbl

[29] Tanaka, K., Yokoyama, K.: On $\epsilon$-equilibrium point in a noncooperative n-person game. J. Math. Anal. Appl. 160 (1991), 413-423. | DOI | MR

[30] Trejo, K. K., Clempner, J. B., Poznyak, A. S.: Computing the Stackelberg/Nash equilibria using the extraproximal method: Convergence analysis and implementation details for Markov chains games. Int. J. Appl. Math. Computer Sci. 25 (2015), 2, 337-351. | DOI | MR

[31] Trejo, K. K., Clempner, J. B., Poznyak, A. S.: A stackelberg security game with random strategies based on the extraproximal theoretic approach. Engrg. Appl. Artif. Intell. 37 (2015), 145-153. | DOI