On the method of fictitious unknowns for the numerical solution of matrix games

Authors

  • E.V. Chizhonkov

Keywords:

symmetric matrix games
fictitious unknowns
least squares problem
iterative methods
variational inequalities
minimum-length solution

Abstract

A new approach based on the introduction of fictitious unknowns is proposed to solve symmetric matrix games. It is shown that on this basis it is possible to find both partial optimal strategies and a least-length solution by specialized algorithms. The numerical results obtained illustrate the computational efficiency of the approach for games of moderate size. The work was partially supported by the Russian Foundation for Basic Research (project 09-01-00625).

New computational technologies

Downloads

Published

2011-10-01

Issue

Vol. 12 (2011): Issue 3.

Section

Section 1. Numerical methods and applications

Author Biography

E.V. Chizhonkov

Lomonosov Moscow State University,
Faculty of Mechanics and Mathematics
• Professor

References

  1. Nemirovski A.S., Todd M.J. Interior-point methods for optimization // Acta Numerica. 2008. 17. 191-234.
  2. Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. М.: Факториал Пресс, 2008.
  3. Brown G.W. Iterative solution of games by fictitious play // Activity Analysis of Production and Allocation / Ed. by T.C. Koopmans. New York: Wiley, 1951. 374-376.
  4. Robinson J. An iterative method of solving a game // Ann. Math. 1951. 54. 296-301.
  5. 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.
  6. Washburn A. A new kind of fictitious play // Naval Research Logistics. 2001. 48. 269-280.
  7. Чижонков Е.В. Итерационное решение матричных игр методами сеточных вариационных неравенств // Журн. вычисл. матем. и матем. физики. 2010. 50, N 8. 1367-1380.
  8. Лоусон Ч., Хенсон Р. Численное решение задач метода наименьших квадратов. М.: Наука, 1986.
  9. Нейман Дж., Моргенштерн О. Теория игр и экономическое поведение. М.: Наука, 1970.
  10. Воробьев Н.Н. Теория игр для экономистов-кибернетиков. М.: Наука, 1985.
  11. Оуэн Г. Теория игр. М.: Изд-во ЛКИ, 2008.
  12. Крушевский А.В. Теория игр. Киев: Вища школа, 1977.
  13. www.netlib.org
  14. Mendelsohn N.S. A psychological game // American Mathematical Monthly. 1946. 53. 86-88.
  15. Лапин А.В. Итерационные методы решения сеточных вариационных неравенств. Казань: Изд-во Казанского государственного университета, 2008.
  16. Гловински Р., Лионс Ж.-Л., Тремольер Р. Численное исследование вариационных неравенств. М.: Мир, 1979.
  17. Зарубежные библиотеки и пакеты программ по вычислительной математике / Ред. У. Кауэлл. М.: Наука, 1993.
  18. Голуб Дж., Ван Лоун Ч. Матричные вычисления. М.: Мир, 1999.
  19. Björck A. Numerical methods for least squares problems. Philadelphia: SIAM, 1996.
  20. Чижонков Е.В. Многоуровневый метод решения больших матричных игр // Вычислительные методы и программирование. 2009. 10, N 2. 141-153.