Geodesic
Search for locally optimal strategies in a linear game problem with favorable situations
Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 3, pp. 123-143 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

A linear game problem for two players is considered. The two players alternately choose their strategies from their respective sets. First, player 1 chooses his/her strategy, then player 2, knowing the strategy of player 1, does the same. The set of strategies of player 2 depends on the strategy of player 1. The goal of player 1 is to choose a strategy to maximize a convex and piecewise linear function (the minimum function of the strategy of player 2). The goal of player 2 is to minimize the linear function. An algorithm is proposed that allows constructing strategies in this problem, as well as strategies in the dual problem, that satisfy necessary “higher-order” optimality conditions. This algorithm uses a formula for the increment of the objective function in the dual problem. Theorems that assert the finiteness of the proposed algorithm and its modification are proved. An example illustrating the operation of the algorithm is given. The results of a numerical experiment on the construction of strategies that satisfy the necessary “higher-order” optimality conditions in problems whose elements were generated by a random number generator are also presented. Based on the results of the numerical experiment, we can conclude that with the proposed algorithm, it is often possible to switch from one locally optimal strategy of player 1 to another one increasing the objective function. Tab. 1, illustr. 1, bibliogr. 21.
Keywords: linear game, maximin problem, optimality condition, support, algorithm. 
@article{DA_2024_31_3_a5,
     author = {A. R. Mamatov},
     title = {Search for locally optimal strategies in~a~linear game problem with~favorable situations},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {123--143},
     year = {2024},
     volume = {31},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2024_31_3_a5/}
}
TY  - JOUR
AU  - A. R. Mamatov
TI  - Search for locally optimal strategies in a linear game problem with favorable situations
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2024
SP  - 123
EP  - 143
VL  - 31
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DA_2024_31_3_a5/
LA  - ru
ID  - DA_2024_31_3_a5
ER  - 
%0 Journal Article
%A A. R. Mamatov
%T Search for locally optimal strategies in a linear game problem with favorable situations
%J Diskretnyj analiz i issledovanie operacij
%D 2024
%P 123-143
%V 31
%N 3
%U http://geodesic.mathdoc.fr/item/DA_2024_31_3_a5/
%G ru
%F DA_2024_31_3_a5
A. R. Mamatov. Search for locally optimal strategies in a linear game problem with favorable situations. Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 3, pp. 123-143. http://geodesic.mathdoc.fr/item/DA_2024_31_3_a5/

[1] B. N. Pshenichnyi, Necessary Conditions for Extremum, Nauka, M. (Russian)

[2] B. Sh. Mordukhovich, “On necessary conditions for an extremum in non-smooth optimization”, Soviet Math. Dokl., 32 (1985), 215–220

[3] F. H. Clarke, Optimization and Nonsmooth Analysis, New York, 1983 (John Wiley Sons)

[4] V. F. Demyanov, A. M. Rubinov, Nonsmooth Analysis Foundations and Quasi-Differential Calculus, Nauka, M., 1990 (Russian)

[5] V. V. Gorokhovik, Convex and Nonsmooth Vector Optimization Problems, Nauka Tekh., Minsk, 1990 (Russian)

[6] A. D. Ioffe, “On necessary conditions for a minimum”, Fundam. Prikl. Mat., 19:4 (2014), 121–152 (Russian)

[7] V. V. Fyodorov, Numerical Maximin Methods, Nauka, M., 1979 (Russian)

[8] R. Gabasov, E. I. Shilkina, “A direct exact method for solving one class of minimax problems”, Dokl. Akad. Nauk BSSR, 25:11 (1981), 971–973 (Russian)

[9] I. Azizov, A finite algorithm for solving a linear maximin problem with bound variables and results of a numerical experiment, Prepr. 18(203), Inst. Mat. AN BSSR, Minsk, 1984 (Russian)

[10] R. Gabasov, F. M. Kirillova, E. A. Kostina, “Global maximization of special classes of convex functions on a convex polyhedral set”, Comput. Math. Math. Phys., 32:8 (1992), 1171–1177

[11] E. G. Golshtein, Duality Theory in Mathematical Programming and Its Aplications, Nauka, M., 1971 (Russian)

[12] R. Gabasov, F. M. Kirillova, A. I. Tyatyushkin, Constructive Optimization Methods, v. 1, Linear Problems, Universitetskoe, Minsk, 1984 (Russian)

[13] Yu. P. Ivanilov, “Dual semi-games”, Izv. Akad. Nauk SSSR, Tekh. Kibern., 1972, no. 4, 3–9 (Russian)

[14] Yu. B. Germeier, Games with Non-Opposite Interests, Nauka, M., 1976 (Russian)

[15] D. D. Lozovanu, “Maximin linear problems with connected variables and their applications to the study and solution of cyclic games”, Bul. Acad. Stiinte Repub. Mold., Mat., 1990, no. 2, 22–29 (Russian)

[16] J. E. Falk, “Linear max-min problem”, Math. Program, 5:2 (1973), 169–188 | DOI

[17] J. Liu, Y. Hong, Y. Zheng, “A branch and bound-based algorithm for the weak linear bilevel programming problems”, Wuhan Univ. J. Nat. Sci, 23:6 (2018), 480–486 | DOI

[18] A. R. Mamatov, “A dual algorithm for computing a local optimum in a linear maximin problem with coupled variables”, Uzb. Zh. "Probl. Inform. Energ.", 2000, no. 1, 7–12 (Russian)

[19] A. R. Mamatov, “High-order necessary optimality conditions in a linear maxmin problem with coupled variables”, Comput. Math. Math. Phys., 50:6 (2010), 963–968 | DOI

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

[21] R. Gabasov, F. M. Kirillova, V. V. Alsevich, A. I. Kalinin, V. V. Krakhotko, N. S. Pavlyonok, Optimization Methods, Chetyre Chetverti, Minsk, 2011 (Russian)