Kybernetika 52 no. 2, 258-279, 2016

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

Kristal K. Trejo, Julio B. Clempner and Alexander S. PoznyakDOI: 10.14736/kyb-2016-2-0258

Abstract:

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.

Keywords:

Markov chains, strong equilibrium, $L_{p}-$norm, Stackelberg and Nash

Classification:

35K20, 93B05

paper.pdf

References:

  1. E. Aiyoshi and K. Shimizu: 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
  2. A. S. Antipin: An extraproximal method for solving equilibrium programming problems and games. Comput. Math. and Math. Phys. 45 (2005), 11, 1893-1914.   CrossRef
  3. J. Bard: 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. J. Bard: Practical Bilevel Optimization: Algorithms and Applications, vol 30. Kluwer Academic, Dordrecht 1998.   DOI:10.1007/978-1-4757-2836-1
  5. J. Bard and J. Falk: An explicit solution to the multi-level programming problem. Comput. Oper. Res. 9 (1982), 77-100.   DOI:10.1016/0305-0548(82)90007-7
  6. L. Bianco, M. Caramia and S. Giordani: 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. L. Brotcorne, M. Labb, P. Marcotte and G. Savard: 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. J. B. Clempner and A. S. Poznyak: 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. J. B. Clempner and A. S. Poznyak: 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. J. Cote, P. Marcotte and G. Savard: 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. K. Deb and A. Sinha: 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. S. Dempe: Discrete Bilevel Optimization Problems. Technical ReportInstitut fur Wirtschaftsinformatik, Universitat Leipzig 2001.   CrossRef
  13. S. Dempe, V. Kalashnikov and R Rios-Mercado: 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
  14. S. DeNegre and T. Ralphs: 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. M. Fampa, L. Barroso, D. Candal and L. Simonetti: 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
  16. J. Fortuny-Amat and B. McCarl: 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
  17. Y. B. Germeyer: Introduction to the Theory of Operations Research. Nauka, Moscow 1971.   CrossRef
  18. Y. B. Germeyer: Games with Nonantagonistic Interests. Nauka, Moscow 1976.   CrossRef
  19. J. Herskovits, A. Leontiev, G. Dias and G. Santos: Contact shape optimization: a bilevel programming approach. Struct. Multidiscipl. Optim. 20 (2000), 214-221.   DOI:10.1007/s001580050149
  20. M. Koppe, M. Queyranne and C. T. Ryan: 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
  21. M. Labbe, P. Marcotte and G. Savard: A bilevel model of taxation and its application to optimal highway pricing. Management Sci. 44 (1998), 1608-1622.   CrossRef
  22. C. Lim and J. Smith: 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. D. Morton, F. Pan and K. Saeger: Models for nuclear smuggling interdiction. IIE Trans. 39 (2007), 1, 3-14.   DOI:10.1080/07408170500488956
  24. J. Naoum-Sawaya and S. Elhedhli: 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
  25. A. S. Poznyak: Advance Mathematical Tools for Automatic Control Engineers. Vol 2 Deterministic Techniques. Elsevier, Amsterdam 2009.   CrossRef
  26. A. S. Poznyak, K. Najim and E. Gomez-Ramirez: Self-Learning Control of Finite Markov Chains. Marcel Dekker, New York 2000.   CrossRef
  27. J. Salmeron, K. Wood and R. Baldick: Analysis of electric grid security under terrorist threat. IEEE Trans. Power Syst. 19 (2004), 2, 905-912.   DOI:10.1109/tpwrs.2004.825888
  28. K. Tanaka: 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
  29. K. Tanaka and K. Yokoyama: 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
  30. K. K. Trejo, J. B. Clempner and A. S. Poznyak: 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
  31. K. K. Trejo, J. B. Clempner and A. S. Poznyak: 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