О методе фиктивных неизвестных для численного решения матричных игр

Авторы

  • Е.В. Чижонков

Ключевые слова:

симметричные матричные игры
фиктивные неизвестные
задача наименьших квадратов
итерационные методы
вариационные неравенства
решение минимальной длины

Аннотация

Предложен новый подход к решению симметричных матричных игр, использующий введение фиктивных неизвестных. Показано, что на этой основе специализированными алгоритмами можно определять как частные оптимальные стратегии, так и решения минимальной длины. Проведенные расчеты демонстрируют вычислительную эффективность подхода для игр умеренной размерности. Работа выполнена при частичной финансовой поддержке РФФИ (код проекта 09-01-00625а).

Новые вычислительные технологии

Загрузки

Опубликован

2011-10-01

Выпуск

Том 12 (2011): Выпуск 3.

Раздел

Раздел 1. Вычислительные методы и приложения

Автор

Е.В. Чижонков

Московский государственный университет имени М.В. Ломоносова,
механико-математический факультет
Ленинские горы, 119899, Москва
• профессор

Библиографические ссылки

  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.