рус eng
«THE BULLETIN OF IRKUTSK STATE UNIVERSITY». SERIES «MATHEMATICS»
«IZVESTIYA IRKUTSKOGO GOSUDARSTVENNOGO UNIVERSITETA». SERIYA «MATEMATIKA»
ISSN 1997-7670 (Print)
ISSN 2541-8785 (Online)

List of issues > Series «Mathematics». 2024. Vol 48

Algorithm for Solving the Problem of the First Phase in a Game Problem with Arbitrary Situations

Author(s)
Akmal R. Mamatov1

1Samarkand State University named after Sh. Rashidov, Samarkand, Uzbekistan

Abstract
The game problem of two persons (players) is considered. The two players alternately choose their strategies from the appropriate sets. First, the first player chooses his strategy, then, knowing the strategy of the first player, the second player chooses his strategy. The set of strategies of the second player depends on the strategy of the first player. It is required to determine the following: for any strategy of the first player, does there exist a corresponding strategy of the second player? This problem is solved using a special linear maximin problem with connected variables, the solution of which is reduced to determining the maximum value of the objective function of the problem’s dual to it on special strategies. The algorithm for solving the problem considered is given. Two examples that illustrate the algorithm and the results of numerical experiment is given.
About the Authors
Akmal R. Mamatov, Cand. Sci. (Phys.Math.), Senior Researcher, Samarkand State University named after Sh. Rashidov, Samarkand, 140104, Uzbekistan, akmm1964@rambler.ru
For citation

Mamatov A. R. Algorithm for Solving the Problem of the First Phase in a Game Problem with Arbitrary Situations. The Bulletin of Irkutsk State University. Series Mathematics, 2024, vol. 48, pp. 3–20. https://doi.org/10.26516/1997-7670.2024.48.3

Keywords
game problem, first phase problem, dual problem, support, algorithm
UDC
519.6, 519.83
MSC
49M05, 91A05
DOI
https://doi.org/10.26516/1997-7670.2024.48.3
References
  1. Azizov I. Algorithm for calculating the 𝜖 - optimal solution of a linear maximin problem with connected variables.Vesti Academy of Sciences of the BSSR. Ser. fiz.-mat. navuk., 1986, no. 1, pp. 14–18. (in Russian)
  2. Falk J.E. Linear maxmin problem. Math. Program., 1973. vol. 5, no. 2, pp. 169–188.
  3. Fedorov V.V. Numerical methods of maximin. Moscow, Nauka Publ., 1979, 280 p. (in Russian)
  4. Gabasov R. Optimization methods. Minsk, Four quarters Publ., 2011, 472 p. (in Russian)
  5. Gabasov R., Kirillova F.M., and Tyatyushkin A.I. Constructive Optimization Methods, Part 1: Linear Problems. Minsk, Universitetskoye Publ., 1984, 214 p. (in Russian)
  6. Gabasov R., Kirillova F.M. Linear Programming Methods. Minsk, BGU Publ., 1977, part 1, 176 p.; part 3, 1980, 368 p.(in Russian)
  7. Ivanilov Yu.P. Dual semi-games. Izvestiya AN SSSR. Technical cybernetics, 1972, no. 4, pp. 3–9. (in Russian)
  8. Lipski W. Combinatorial Analysis for Software Engineers. Warszawa, Wydawnictwa Naukowo-Techniczne, 1987.
  9. Liu June, Hong Yunfei, Zheng Yue. A New Variant of Penalty Method for Weak Linear Bilevel Programming Problems. Wuhan University Journal of Natural Sciences, 2018, vol. 23, no. 4, pp. 328–332. https://doi.org/10.1007/s11859-018-1330-1
  10. LIU June, HONG Yunfei, ZHENG Yue. A Branch and Bound-Based Algorithm for the Weak Linear Bilevel Programming Problems. Wuhan University Journal of Natural Sciences, 2018, vol. 23, no. 6, pp. 480–486.https://doi.org/10.1007/s11859-018-1352-8
  11. Mamatov A.R. High-Order Necessary Optimality Conditions in a Linear Maxmin Problem with Coupled Variables. Comput. Math. Math. Phys., 2010, vol. 50, no. 6, pp. 1017–1022. https://doi.org/10.1134/S0965542510060047
  12. Mamatov A.R. An algorithm for solving a two-person game with information transfer. Comput. Math. Math. Phys., 2006, vol. 46, no. 10, pp. 1699–1704. https://doi.org/10.1134/S0965542506100071
  13. Mamatov A.R. An Algorithm for Solving a Linear Max-min Problem with Coupled Variables. Comput. Math. Math. Phys., 2005, vol. 45, no. 6, pp. 1006–1010.
  14. Mamatov A.R. On theory of the duality linear maximin problems with connected variables. Siberian J. Num. Math., 2007, vol. 10, no. 2, pp. 187–193. (in Russian)
  15. Zheng Y., Wan Z., Sun K., Zhang T. An exact penalty method for weak linear bilevel programming problem. Journal of Applied Mathematics and Computing, 2013, no. 42, pp. 41–49. https://doi.org/10.1007/s12190-012-0620-6
  16. Zheng Y., Fang D., Wan Z. A solution approach to the weak linear bilevel programming problems.Optimization, 2016, no. 7, pp. 1437–1449.https://doi.org/10.1080/02331934.2016.1154553

Full text (english)