Geodesic
Iteration in a subspace for solving matrix games
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 52 (2012) no. 9, pp. 1601-1613 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

A new method for solving symmetric matrix games is proposed and justified. It is based on iterating vectors in the null space of a specially constructed matrix. According to the numerical tests performed, the efficiency of the proposed method is comparable with that of the available iterative algorithms having about the same computational complexity. This approach is also applicable to more complicated problems than the calculation of particular optimal strategies. For instance, it can be used for finding the unique minimum length solution. 
@article{ZVMMF_2012_52_9_a2,
     author = {E. V. Chizhonkov},
     title = {Iteration in a~subspace for solving matrix games},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {1601--1613},
     year = {2012},
     volume = {52},
     number = {9},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2012_52_9_a2/}
}
TY  - JOUR
AU  - E. V. Chizhonkov
TI  - Iteration in a subspace for solving matrix games
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2012
SP  - 1601
EP  - 1613
VL  - 52
IS  - 9
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2012_52_9_a2/
LA  - ru
ID  - ZVMMF_2012_52_9_a2
ER  - 
%0 Journal Article
%A E. V. Chizhonkov
%T Iteration in a subspace for solving matrix games
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2012
%P 1601-1613
%V 52
%N 9
%U http://geodesic.mathdoc.fr/item/ZVMMF_2012_52_9_a2/
%G ru
%F ZVMMF_2012_52_9_a2
E. V. Chizhonkov. Iteration in a subspace for solving matrix games. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 52 (2012) no. 9, pp. 1601-1613. http://geodesic.mathdoc.fr/item/ZVMMF_2012_52_9_a2/

[1] Wright M. H., “The interior-point revolution in optimization: history, recent developments, and lasting consequences”, Bull. Amer. Math. Soc., 42:1 (2004), 39–56 | DOI | MR

[2] Nemirovski A. S., Todd M. J., “Interior-point methods for optimization”, Acta Numerica, 17 (2008), 191–234 | DOI | MR | Zbl

[3] Vasilev F. P., Ivanitskii A. Yu., Lineinoe programmirovanie, Faktorial-Press, M., 2008 | MR

[4] Brown G. W., “Iterative solution of games by fictitious play”, Activity analysis of production and allocation, Wiley, New York, 1951, 374–376 | MR

[5] Robinson J., “An iterative method of solving a game”, Ann. Math., 54 (1951), 296–301 | DOI | MR | Zbl

[6] Gaas S. I., Zafra P. M., Qui Z., “Modified fictitious play for solving matrix games and linear programming problems”, Comp. Oper. Res., 22 (1995), 893–903 | DOI | MR

[7] Washburn A., “A new kind of fictitious play”, Naval Research Logistics, 48 (2001), 269–280 | DOI | MR

[8] Chizhonkov E. V., “Iteratsionnoe reshenie matrichnykh igr metodami setochnykh variatsionnykh neravenstv”, Zh. vychisl. matem. i matem. fiz., 50:8 (2010), 1367–1380 | MR | Zbl

[9] Neiman Dzh., Morgenshtern O., Teoriya igr i ekonomicheskoe povedenie, Nauka, M., 1970 | MR

[10] Vorobev N. N., Teoriya igr dlya ekonomistov-kibernetikov, Nauka, M., 1985 | MR

[11] Gale D., Kuhn H. W., Tucker A. W., “On symmetric games”, Contributions to the theory of games, v. 1, Annals of Mathematics study, 24, Princeton University Press, Princeton, New York, 1950, 81–87 | MR

[12] Voevodin V. V., Kuznetsov Yu. A., Teoriya matrits, Nauka, M., 1984 | MR | Zbl

[13] Lapin A. V., Iteratsionnye metody resheniya setochnykh variatsionnykh neravenstv, Izd-vo Kazansk. gos. un-ta, Kazan, 2008

[14] U. Kauell (red.), Zarubezhnye biblioteki i pakety programm po vychislitelnoi matematike, Nauka, M., 1993 | MR

[15] Golub Dzh., Van-Loun Ch., Matrichnye vychisleniya, Mir, M., 1999

[16] Mendelsohn N. S., “A psychological game”, Amer. Math. Monthly, 53 (1946), 86–88 | DOI | MR

[17] Wright S. J., “Modified Cholesky factorizations in interior-point algorithms for linear programming”, SIAM J. Optimiz., 9:4 (1999), 1159–1191 | DOI | MR | Zbl

[18] Limsakul P., Iterative algorithms for two-person zero-sum games, Master's thesis, Naval Postgraduate School, Monterey, California, 1999

[19] Brown B. W., Lovato J., RANLIB: Library of Fortran Routines for Random Number Generation, Department of Biomathematics, M. D. Anderson Cancer Centre, University of Texas, Houston, 1994

[20] Belenkii V. Z., i dr., Iterativnye metody v teorii igr i programmirovanii, Nauka, M., 1974 | MR

[21] Shapiro H. N., “Note on a computation method in the theory of games”, Commun. Pure Appl. Math., 11 (1958), 587–593 | DOI | MR | Zbl

[22] Szép J., Forgó F., Introduction to the theory of games, Reidel, Dordrecht, 1985 | MR | Zbl

[23] Louson Ch., Khenson R., Chislennoe reshenie zadach metoda naimenshikh kvadratov, Nauka, M., 1986 | MR

[24] Glovinski R., Lions Zh.-L., Tremoler R., Chislennoe issledovanie variatsionnykh neravenstv, Mir, M., 1979 | MR

[25] Chizhonkov E. V., “Mnogourovnevyi metod resheniya bolshikh matrichnykh igr”, Vychisl. metody i programmirovanie, 10:2 (2009), 141–153

[26] Olshanskii M. A., Lektsii i uprazhneniya po mnogosetochnym metodam, Fizmatlit, M., 2005 | Zbl

[27] Chizhonkov E. V., “O metode fiktivnykh neizvestnykh dlya chislennogo resheniya matrichnykh igr”, Vychisl. metody i programmirovanie, 12 (2011), 338–347