| Title:
|
An optimal strong equilibrium solution for cooperative multi-leader-follower Stackelberg Markov chains games (English) |
| Author:
|
Trejo, Kristal K. |
| Author:
|
Clempner, Julio B. |
| Author:
|
Poznyak, Alexander S. |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 (print) |
| ISSN:
|
1805-949X (online) |
| Volume:
|
52 |
| Issue:
|
2 |
| Year:
|
2016 |
| Pages:
|
258-279 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
strong equilibrium |
| Keyword:
|
Stackelberg and Nash |
| Keyword:
|
$L_{p}-$norm |
| Keyword:
|
Markov chains |
| MSC:
|
35K20 |
| MSC:
|
93B05 |
| idZBL:
|
Zbl 1374.35201 |
| idMR:
|
MR3501161 |
| DOI:
|
10.14736/kyb-2016-2-0258 |
| . |
| Date available:
|
2016-07-17T12:05:48Z |
| Last updated:
|
2018-01-10 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/145774 |
| . |
| Reference:
|
[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. MR 0631815, 10.1109/tsmc.1981.4308712 |
| Reference:
|
[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 |
| Reference:
|
[3] Bard, J.: Coordination of a multidivisional organization through two levels of management..Omega 11 (1983), 5, 457-468. 10.1016/0305-0483(83)90038-5 |
| Reference:
|
[4] Bard, J.: Practical Bilevel Optimization: Algorithms and Applications, vol 30..Kluwer Academic, Dordrecht 1998. MR 1680111, 10.1007/978-1-4757-2836-1 |
| Reference:
|
[5] Bard, J., Falk, J.: An explicit solution to the multi-level programming problem..Comput. Oper. Res. 9 (1982), 77-100. MR 0768598, 10.1016/0305-0548(82)90007-7 |
| Reference:
|
[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. 10.1016/j.trc.2008.10.001 |
| Reference:
|
[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. 10.1287/trsc.35.4.345.10433 |
| Reference:
|
[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. 10.1007/s11518-014-5260-y |
| Reference:
|
[9] Clempner, J. B., Poznyak, A. S.: Stackelberg security games: Computing the shortest-path equilibrium..Expert Systems Appl. 42 (2015), 8, 3967-3979. 10.1016/j.eswa.2014.12.034 |
| Reference:
|
[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. 10.1057/palgrave.rpm.5170046 |
| Reference:
|
[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. 10.1162/evco_a_00015 |
| Reference:
|
[12] Dempe, S.: Discrete Bilevel Optimization Problems..Technical ReportInstitut fur Wirtschaftsinformatik, Universitat Leipzig 2001. |
| Reference:
|
[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. Zbl 1064.90029, MR 2136379, 10.1016/j.ejor.2004.01.047 |
| Reference:
|
[14] DeNegre, S., Ralphs, T.: A branch-and-cut algorithm for integer bilevel linear programs..Oper. Res. Cyber-Infrastruct. 47 (2009), 65-78. 10.1007/978-0-387-88843-9_4 |
| Reference:
|
[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. Zbl 1147.90392, MR 2373242, 10.1007/s10589-007-9066-4 |
| Reference:
|
[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. Zbl 0459.90067, MR 0626944, 10.1057/jors.1981.156 |
| Reference:
|
[17] Germeyer, Y. B.: Introduction to the Theory of Operations Research..Nauka, Moscow 1971. MR 0327275 |
| Reference:
|
[18] Germeyer, Y. B.: Games with Nonantagonistic Interests..Nauka, Moscow 1976. |
| Reference:
|
[19] Herskovits, J., Leontiev, A., Dias, G., Santos, G.: Contact shape optimization: a bilevel programming approach..Struct. Multidiscipl. Optim. 20 (2000), 214-221. 10.1007/s001580050149 |
| Reference:
|
[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. MR 2657828, 10.1007/s10957-010-9668-3 |
| Reference:
|
[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. Zbl 0989.90014, 10.1287/mnsc.44.12.1608 |
| Reference:
|
[22] Lim, C., Smith, J.: Algorithms for discrete and continuous multicommodity flow network interdiction problems..IIE Trans. 39 (2007), 1, 15-26. 10.1287/mnsc.44.12.1608 |
| Reference:
|
[23] Morton, D., Pan, F., Saeger, K.: Models for nuclear smuggling interdiction..IIE Trans. 39 (2007), 1, 3-14. 10.1080/07408170500488956 |
| Reference:
|
[24] Naoum-Sawaya, J., Elhedhli, S.: Controlled predatory pricing in a multiperiod stackelberg game: an mpec approach..J. Global Optim. 50 (2011), 345-362. Zbl 1231.91126, MR 2799570, 10.1007/s10898-010-9585-x |
| Reference:
|
[25] Poznyak, A. S.: Advance Mathematical Tools for Automatic Control Engineers. Vol 2 Deterministic Techniques..Elsevier, Amsterdam 2009. MR 2582931 |
| Reference:
|
[26] Poznyak, A. S., Najim, K., Gomez-Ramirez, E.: Self-Learning Control of Finite Markov Chains..Marcel Dekker, New York 2000. Zbl 0960.93001, MR 1760540 |
| Reference:
|
[27] Salmeron, J., Wood, K., Baldick, R.: Analysis of electric grid security under terrorist threat..IEEE Trans. Power Syst. 19 (2004), 2, 905-912. 10.1109/tpwrs.2004.825888 |
| Reference:
|
[28] Tanaka, K.: The closest solution to the shadow minimum of a cooperative dynamic game..Comp. Math. Appl. 18 (1989), 1-3, 181-188. Zbl 0686.90047, MR 1000409, 10.1016/0898-1221(89)90135-1 |
| Reference:
|
[29] Tanaka, K., Yokoyama, K.: On $\epsilon$-equilibrium point in a noncooperative n-person game..J. Math. Anal. Appl. 160 (1991), 413-423. MR 1126126, 10.1016/0022-247x(91)90314-p |
| Reference:
|
[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. MR 3363520, 10.1515/amcs-2015-0026 |
| Reference:
|
[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. 10.1016/j.engappai.2014.09.002 |
| . |
