Geodesic
Algorithm for solving the problem of the first phase in a game problem with arbitrary situations
The Bulletin of Irkutsk State University. Series Mathematics, Tome 48 (2024), pp. 3-20
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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.
Keywords: game problem, first phase problem, dual problem, support, algorithm. 
@article{IIGUM_2024_48_a0,
     author = {Akmal R. Mamatov},
     title = {Algorithm for solving the problem of the first phase in a game problem with arbitrary situations},
     journal = {The Bulletin of Irkutsk State University. Series Mathematics},
     pages = {3--20},
     year = {2024},
     volume = {48},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IIGUM_2024_48_a0/}
}
TY  - JOUR
AU  - Akmal R. Mamatov
TI  - Algorithm for solving the problem of the first phase in a game problem with arbitrary situations
JO  - The Bulletin of Irkutsk State University. Series Mathematics
PY  - 2024
SP  - 3
EP  - 20
VL  - 48
UR  - http://geodesic.mathdoc.fr/item/IIGUM_2024_48_a0/
LA  - en
ID  - IIGUM_2024_48_a0
ER  - 
%0 Journal Article
%A Akmal R. Mamatov
%T Algorithm for solving the problem of the first phase in a game problem with arbitrary situations
%J The Bulletin of Irkutsk State University. Series Mathematics
%D 2024
%P 3-20
%V 48
%U http://geodesic.mathdoc.fr/item/IIGUM_2024_48_a0/
%G en
%F IIGUM_2024_48_a0
Akmal R. Mamatov. Algorithm for solving the problem of the first phase in a game problem with arbitrary situations. The Bulletin of Irkutsk State University. Series Mathematics, Tome 48 (2024), pp. 3-20. http://geodesic.mathdoc.fr/item/IIGUM_2024_48_a0/

[1] Azizov I., “Algorithm for calculating the $\epsilon$-optimal solution of a linear maximin problem with connected variables”, Vesti Academy of Sciences of the BSSR. Ser. fiz.-mat. navuk, 1986, no. 1, 14–18 (in Russian) | MR

[2] Falk J.E., “Linear maxmin problem”, Math. Program, 5:2 (1973), 169–188 | DOI | MR | Zbl

[3] Fedorov V.V., Numerical methods of maximin, Nauka Publ, M., 1979, 280 pp. (in Russian)

[4] Gabasov R., Optimization methods, Four quarters Publ, Minsk, 2011, 472 pp. (in Russian)

[5] Gabasov R., Kirillova F.M., and Tyatyushkin A.I., Constructive Optimization Methods, v. 1, Linear Problems, Universitetskoye Publ, Minsk, 1984, 214 pp. (in Russian) ; т. 3, 1980, 368 с. | MR

[6] Gabasov R., Kirillova F.M., Linear Programming Methods, v. 1, BGU Publ, Minsk, 1977, 176 pp. ; v. 3, 1980, 368 pp. (in Russian) | MR

[7] Ivanilov Yu.P., “Dual semi-games”, Izvestiya AN SSSR. Technical cybernetics, 1972, no. 4, 3–9 (in Russian) | MR | Zbl

[8] Lipski W., Combinatorial Analysis for Software Engineers, Wydawnictwa Naukowo-Techniczne, Warszawa, 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, 23:4 (2018), 328–332 | DOI | MR | Zbl

[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, 23:6 (2018), 480–486 | DOI | MR | Zbl

[11] Mamatov A.R., “High-Order Necessary Optimality Conditions in a Linear Maxmin Problem with Coupled Variables”, Comput. Math. Math. Phys., 50:6 (2010), 1017–1022 | DOI | MR | Zbl

[12] Mamatov A.R., “An algorithm for solving a two-person game with information transfer”, Comput. Math. Math. Phys., 46:10 (2006), 1699–1704 | DOI | MR

[13] Mamatov A.R., “An Algorithm for Solving a Linear Max-min Problem with Coupled Variables”, Comput. Math. Math. Phys., 45:6 (2005), 1006–1010 | MR | Zbl

[14] Mamatov A.R., “On theory of the duality linear maximin problems with connected variables”, Siberian J. Num. Math., 10:2 (2007), 187–193 (in Russian) | Zbl

[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, 41–49 | DOI | MR | Zbl

[16] Zheng Y., Fang D., Wan Z., “A solution approach to the weak linear bilevel programming problems”, Optimization, 2016, no. 7, 1437–1449 | DOI | MR | Zbl