- Код статьи
- S042473880000015-5-1
- DOI
- 10.7868/s0424738818020073
- Тип публикации
- Статья
- Статус публикации
- Опубликовано
- Авторы
- Том/ Выпуск
- Том 54 / Выпуск 2
- Страницы
- 89-103
- Аннотация
- Для нахождения решения биматричной игры в смешанных стратегиях можно ис- пользовать приближенный метод решения биматричных игр (2LP-метод) и/или метод Лем- ке – Хаусона (LH-метод). В 2LP-методе поиск решения биматричной игры сводится к итера- тивному поиску глобального минимума функции Нэша, имеющего большое число локальных минимумов, не совпадающих с глобальным минимумом. Тем не менее поочеред- ная минимизация этой функции по одной из двух переменных (стратегий) при фиксации другой переменной легко сводится к линейному программированию. Осуществляя перебор начальных чистых стратегий и решая на каждой итерации две задачи линейного програм- мирования, 2LP-метод позволяет найти точное решение игры, если выполнено условие до- полнительности либо некоторое приближение к множеству точек Нэша при незначительном нарушении условия дополнительности. Достоинством метода является его простота, глав- ным недостатком – снижение эффективности при малой заполненности и/или при нали- чии взаимозависимости матриц, задающих функции выигрышей игроков. В LH-методе по- иск решения биматричной игры заменяется поиском решения связанной с игрой системы линейных равенств. Начиная с единичного базиса метод делает шаги симплексного типа с целью уменьшить число нарушенных условий дополнительности. Как правило, но не всег- да, этим методом удается найти точное решение игры. Предлагаемый нами гибридный ме- тод производит дооптимизацию приближенного решения, полученного 2LP-алгоритмом, при помощи LH-алгоритма, использующего базис приближенного решения. Эффективность метода Лемке – Хаусона и нашего гибридного метода оказалась примерно одинаковой. С по- мощью гибридного метода удалось найти решение нескольких игр, для которых точное ре- шение не было получено ни 2LP-методом, ни LH-методом.
- Ключевые слова
- биматричная игра, выпуклая структура, чистая стратегия, смешанная стратегия, точка Нэша, функция Нэша, условие дополнительности, метод Лемке–Хаусона, гибридный метод
- Дата публикации
- 29.06.2018
- Год выхода
- 2018
- Всего подписок
- 14
- Всего просмотров
- 2151
123
Библиография
- 1. Гольштейн Е. Г., Малков У. Х., Соколов Н. А. (2013). Об одном численном методе решения биматричных игр // Экономика и математические методы. Т. 49. № 4. С. 94–104.
- 2. IBM ILOG CPLEX Optimization Studio (2011). [Электронный ресурс] Режим доступа: http://www‑03.ibm. com/software/products /ru/ibmilogcpleoptistud, свободный. Загл. с экрана. Яз. англ. (дата обращения: июль 2017 г.).
- 3. Lemke C. E., Howson J. T. Jr. (1964). Equilibrium Points of Bimatrix Games // Journal of the Society for Industrial and Applied Mathematics. Vol. 12. P. 778–780.
- 4. MATLAB (2012). The Language of Technical Computing. [Электронный ресурс] Режим доступа: http://www. mathworks.com/products /matlab/, свободный. Загл. с экрана. Яз. англ. (дата обращения: июль 2017 г.).
