Article
Full entry |
PDF
(0.5 MB)
Feedback
PDF
(0.5 MB)
Feedback
Keywords:
strong equilibrium; Stackelberg and Nash; $L_{p}-$norm; Markov chains
strong equilibrium; Stackelberg and Nash; $L_{p}-$norm; Markov chains
Summary:
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.
References:
[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 10.1109/tsmc.1981.4308712 | MR 0631815
[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 2203222
[3] Bard, J.: Coordination of a multidivisional organization through two levels of management. Omega 11 (1983), 5, 457-468. DOI 10.1016/0305-0483(83)90038-5
[4] Bard, J.: Practical Bilevel Optimization: Algorithms and Applications, vol 30. Kluwer Academic, Dordrecht 1998. DOI 10.1007/978-1-4757-2836-1 | MR 1680111
[5] Bard, J., Falk, J.: An explicit solution to the multi-level programming problem. Comput. Oper. Res. 9 (1982), 77-100. DOI 10.1016/0305-0548(82)90007-7 | MR 0768598
[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 10.1016/j.trc.2008.10.001
[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 10.1287/trsc.35.4.345.10433
[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 10.1007/s11518-014-5260-y
[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.1016/j.eswa.2014.12.034
[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 10.1057/palgrave.rpm.5170046
[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 10.1162/evco_a_00015
[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 10.1016/j.ejor.2004.01.047 | MR 2136379 | Zbl 1064.90029
[14] DeNegre, S., Ralphs, T.: A branch-and-cut algorithm for integer bilevel linear programs. Oper. Res. Cyber-Infrastruct. 47 (2009), 65-78. DOI 10.1007/978-0-387-88843-9_4
[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 10.1007/s10589-007-9066-4 | MR 2373242 | Zbl 1147.90392
[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 10.1057/jors.1981.156 | MR 0626944 | Zbl 0459.90067
[17] Germeyer, Y. B.: Introduction to the Theory of Operations Research. Nauka, Moscow 1971. MR 0327275
[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 10.1007/s001580050149
[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 10.1007/s10957-010-9668-3 | MR 2657828
[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 10.1287/mnsc.44.12.1608 | Zbl 0989.90014
[22] Lim, C., Smith, J.: Algorithms for discrete and continuous multicommodity flow network interdiction problems. IIE Trans. 39 (2007), 1, 15-26. DOI 10.1287/mnsc.44.12.1608
[23] Morton, D., Pan, F., Saeger, K.: Models for nuclear smuggling interdiction. IIE Trans. 39 (2007), 1, 3-14. DOI 10.1080/07408170500488956
[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 10.1007/s10898-010-9585-x | MR 2799570 | Zbl 1231.91126
[25] Poznyak, A. S.: Advance Mathematical Tools for Automatic Control Engineers. Vol 2 Deterministic Techniques. Elsevier, Amsterdam 2009. MR 2582931
[26] Poznyak, A. S., Najim, K., Gomez-Ramirez, E.: Self-Learning Control of Finite Markov Chains. Marcel Dekker, New York 2000. MR 1760540 | Zbl 0960.93001
[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 10.1109/tpwrs.2004.825888
[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 10.1016/0898-1221(89)90135-1 | MR 1000409 | Zbl 0686.90047
[29] Tanaka, K., Yokoyama, K.: On $\epsilon$-equilibrium point in a noncooperative n-person game. J. Math. Anal. Appl. 160 (1991), 413-423. DOI 10.1016/0022-247x(91)90314-p | MR 1126126
[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 10.1515/amcs-2015-0026 | MR 3363520
[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 10.1016/j.engappai.2014.09.002
Search
Partner of
