| Наименование статьи | Гибридный метод поиска решения биматричных игр |
|---|
| Страницы | 89 |
|---|
| Аннотация | Для нахождения решения биматричной игры в смешанных стратегиях можно использовать приближенный метод решения биматричных игр (2LP-метод) и/или метод Лемке-Хаусона (LH-метод). В 2LP-методе поиск решения биматричной игры сводится к итеративному поиску глобального минимума функции Нэша, имеющего большое число локальных минимумов, не совпадающих с глобальным минимумом. Тем не менее поочередная минимизация этой функции по одной из двух переменных (стратегий) при фиксации другой переменной легко сводится к линейному программированию. Осуществляя перебор начальных чистых стратегий и решая на каждой итерации две задачи линейного программирования, 2LP-метод позволяет найти точное решение игры, если выполнено условие дополнительности либо некоторое приближение к множеству точек Нэша при незначительном нарушении условия дополнительности. Достоинством метода является его простота, главным недостатком - снижение эффективности при малой заполненности и/или при наличии взаимозависимости матриц, задающих функции выигрышей игроков. В LH-методе поиск решения биматричной игры заменяется поиском решения связанной с игрой системы линейных равенств. Начиная с единичного базиса метод делает шаги симплексного типа с целью уменьшить число нарушенных условий дополнительности. Как правило, но не всегда, этим методом удается найти точное решение игры. Предлагаемый нами гибридный метод производит дооптимизацию приближенного решения, полученного 2LP-алгоритмом, при помощи LH-алгоритма, использующего базис приближенного решения. Эффективность метода Лемке-Хаусона и нашего гибридного метода оказалась примерно одинаковой. С помощью гибридного метода удалось найти решение нескольких игр, для которых точное решение не было получено ни 2LP-методом, ни LH-методом. |
|---|
| Ключевые слова | биматричная игра, выпуклая структура, чистая стратегия, смешанная стратегия, точка Нэша, функция Нэша, условие дополнительности, метод Лемке-Хаусона, гибридный метод |
|---|
| Журнал | Экономика и математические методы |
|---|
| Номер выпуска | 2 |
|---|
| Автор(ы) | Гольштейн Е. Г., Малков У. Х., Соколов Н. А. |
|---|