A multi-level method for solving large-scale matrix games

Authors

Keywords:

matrix games, iterative methods, direct solver, basic iterative method, procedure of restriction, procedure of prolongation, multi-level method

Abstract

A multi-level method is proposed to solve the matrix games of a special class. The essence of the paper is the adaptation of ideas of the Fedorenko-Bakhvalov method, well known as a multi-grid method for solving elliptic differential problems, to the iterative solution of matrix games. The work was supported by the Russian Foundation for Basic Research (project no. 09–01–00625a).

Author Biography

E.V. Chizhonkov

References

  1. Karmarkar N. A new polonomial-time algorithm for linear programming // Combinatorica. 1984. 4, N 4. 373-395.
  2. Wright M.H. The interior-point revolution in optimization: history, recent developments, and lasting consequences // Bull. Amer. Math. Soc. 2004. 42, N 1. 39-56.
  3. Nemirovski A.S., Todd M.J. Interior-point methods for optimization // Acta Numerica. 2008. 17. 191-234.
  4. Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. М.: Факториал, 1998.
  5. Хачиян Л.Г. Сложность задач линейного программирования. М.: Знание, 1987.
  6. Colombo M. Advances in interior point methods for large-scale linear programming. PhD Thesis in Optimization. School of Mathematics. University of Edinburgh. Edinburgh, 2007.
  7. Бабенко К.И. Основы численного анализа. М.: Наука, 1986.
  8. Федоренко Р.П. Релаксационный метод решения разностных эллиптических уравнений // Журн. вычисл. матем. и матем. физ. 1961. 1, № 5. 922-927.
  9. Федоренко Р.П. О скорости сходимости одного итерационного процесса // Журн. вычисл. матем. и матем. физ. 1964. 4, № 3. 227-235.
  10. Бахвалов Н.С. О сходимости одного релаксационного метода для эллиптического оператора с естественными ограничениями // Журн. вычисл. матем. и матем. физ. 1966. 6, № 5. 101-135.
  11. Ольшанский М.А. Лекции и упражнения по многосеточным методам. М.: Физматлит, 2005.
  12. Нейман Дж., Моргенштерн О. Теория игр и экономическое поведение. М.: Наука, 1970.
  13. Brown G.W. Iterative solution of games by fictitious play // Activity analysis of production and allocation. / Edited by T.C. Koopmans. New York: Wiley, 1951. 374-376.
  14. Robinson J. An iterative method of solving a game // Ann. Math. 1951. 54. 296-301.
  15. Shapiro H.N. Note on a computation method in the theory of games // Commun. Pure Appl. Math. 1958. 11. 587-593.
  16. Szacute ep J., Forgacute o F. Introduction to the theory of games. Dordrecht: Reidel, 1985.
  17. Беленький В.З., Волконский В.А., Иванков С.А., Поманский А.Б., Шапиро А.Д. Итеративные методы в теории игр и программировании. М.: Наука, 1974.
  18. Gaas S.I, Zafra P.M., Qui Z. Modified fictitious play for solving matrix games and linear programming problems // Comp. Oper. Res. 1995. 22. 893-903.
  19. Washburn A. A new kind of fictitious play // Naval Research Logistics. 2001. 48. 269-280.
  20. Садовский А.Л. Монотонный итеративный алгоритм решения матричных игр // Доклады АН СССР. 1978. 238, № 3. 538-540.
  21. Gale D., Kuhn H.W., Tucker A.W. On symmetric games // Contributions to the theory of games / Edited by H.W. Kuhn and A.W. Tucker. Annals of Mathematics Study N 24. Princeton: Princeton University Press. 1950. 1. 81-87.
  22. Матричные игры / Под ред. Н.Н. Воробьева. М.: ГИФМЛ, 1961.
  23. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.
  24. Бахвалов Н.С. Численные методы. М.: Наука, 1973.
  25. Vaserstein L.N. Matrix games, linear programming, and linear approximation // arXiv.org, math.cs/0609056v1[cs.GT], 27 Jan 2006.

Published

17-09-2009

How to Cite

Чижонков Е. A Multi-Level Method for Solving Large-Scale Matrix Games // Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie). 2009. 10. 327-339

Issue

Section

Section 1. Numerical methods and applications

Most read articles by the same author(s)

1 2 > >>