A multi-level method for solving large-scale matrix games
Keywords:
matrix games, iterative methods, direct solver, basic iterative method, procedure of restriction, procedure of prolongation, multi-level methodAbstract
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).
References
- Karmarkar N. A new polonomial-time algorithm for linear programming // Combinatorica. 1984. 4, N 4. 373-395.
- 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.
- Nemirovski A.S., Todd M.J. Interior-point methods for optimization // Acta Numerica. 2008. 17. 191-234.
- Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. М.: Факториал, 1998.
- Хачиян Л.Г. Сложность задач линейного программирования. М.: Знание, 1987.
- Colombo M. Advances in interior point methods for large-scale linear programming. PhD Thesis in Optimization. School of Mathematics. University of Edinburgh. Edinburgh, 2007.
- Бабенко К.И. Основы численного анализа. М.: Наука, 1986.
- Федоренко Р.П. Релаксационный метод решения разностных эллиптических уравнений // Журн. вычисл. матем. и матем. физ. 1961. 1, № 5. 922-927.
- Федоренко Р.П. О скорости сходимости одного итерационного процесса // Журн. вычисл. матем. и матем. физ. 1964. 4, № 3. 227-235.
- Бахвалов Н.С. О сходимости одного релаксационного метода для эллиптического оператора с естественными ограничениями // Журн. вычисл. матем. и матем. физ. 1966. 6, № 5. 101-135.
- Ольшанский М.А. Лекции и упражнения по многосеточным методам. М.: Физматлит, 2005.
- Нейман Дж., Моргенштерн О. Теория игр и экономическое поведение. М.: Наука, 1970.
- 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.
- Robinson J. An iterative method of solving a game // Ann. Math. 1951. 54. 296-301.
- Shapiro H.N. Note on a computation method in the theory of games // Commun. Pure Appl. Math. 1958. 11. 587-593.
- Szacute ep J., Forgacute o F. Introduction to the theory of games. Dordrecht: Reidel, 1985.
- Беленький В.З., Волконский В.А., Иванков С.А., Поманский А.Б., Шапиро А.Д. Итеративные методы в теории игр и программировании. М.: Наука, 1974.
- 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.
- Washburn A. A new kind of fictitious play // Naval Research Logistics. 2001. 48. 269-280.
- Садовский А.Л. Монотонный итеративный алгоритм решения матричных игр // Доклады АН СССР. 1978. 238, № 3. 538-540.
- 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.
- Матричные игры / Под ред. Н.Н. Воробьева. М.: ГИФМЛ, 1961.
- Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.
- Бахвалов Н.С. Численные методы. М.: Наука, 1973.
- Vaserstein L.N. Matrix games, linear programming, and linear approximation // arXiv.org, math.cs/0609056v1[cs.GT], 27 Jan 2006.
Downloads
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