Некоторые модели теории игр
Игровые модели в исследовании операций
Введение
Исследование операций – прикладное направление кибернетики, изучающее способы выработки оптимальных решений выполнения различных операций на основе мат.моделей и соответствующих методов.
Операция – система действий и мероприятий, объединенных единым замыслом и направленных к достижению определенной цели с наибольшей эффективностью.
Исследование операций появилось впервые в 1939-42 гг., когда в Англии, США, Канаде в ВВС и ВМС были созданы отделы по исследованию операций, которые были укомплектованы квалифицированными математиками и поставлена задача разработки рекомендаций по планированию военных операций. Модели и методы долгое время были засекречены. Начиная с 1962 года, исследование операций стало широко применяться в экономике.
Поиск оптимальных планов, выполнение различных операций во многих случаях требуется проверять в условиях неопределенности. Неопределенность может быть связана с двумя основными причинами:
1. Наличие противоположной стороны, которая сознательно препятствует достижению заданной цели (злонамеренный противник). Модели и методы поиска оптимальных решений при наличии злонамеренного противника изучаются в теории игр.
2. Неопределенность, связанная с описанием информации о состоянии определенной среды. В этом случае нет злонамеренного противника, но недостаток информации о состоянии определенной среды устанавливает процесс принятия наилучшего решения.
Модели и методы исследования операций в этих случаях строятся с использованием теории статистических решений.
Простой моделью в теории игр является модель парной игры с нулевой суммой. Имеются два игрока: А и В. У игрока А имеется m-возможных вариантов выбора своей стратегии, у игрока В – n-возможных вариантов выбора своей стратегии. Задана платежная матрица:
B1 | B2 | … | Bn | ||
A1 | a11 | a12 | … | a1n | α1 |
A2 | a21 | a22 | … | a2n | α2 |
… | … | … | … | … | … |
Am | am1 | am2 | … | amn | αm |
β1 | β2 | … | βn |
aij – ожидаемый выигрыш игрока А, если он выбирает стратегию Ai, а B выберет Bj. В играх с нулевой суммой предполагается, что выигрыш одного игрока равен проигрышу другого.
aij = +10 – выигрыш; aij = -10 – проигрыш
Имея эту платежную матрицу даты количественной рекомендуемый игрокам по выбора наилучшей стратегии.
Следует различать:
1. выдача рекомендованной з/однократной игры
2. выдача рекомендованной в условиях, когда игра многократно повторяется в одних и тех же условиях.
В первом случае может определяться разумным использование принципа минимакса.
1. По каждой строке платежной матрицы найдем минимальный выигрыш: αi = min aij;
2. Найдем максимум из всех αi: α = max αi = max min αi, где α – нижняя цена игры; обозначим i* - номер строки, соответствующей нижней цене игры;
3. Если игрок А в одной игре выбирает стратегию Ai* (стратегия максимина), то он гарантирует себе выигрыш α независимо от того, какую стратегию выберет В. Максиминная стратегия игрока А характерна для очень осторожного игрока, который не рассчитывает на то, что игрок В в чем то ошибется;
4. Для игрока В определяется βj = max aij – максимальный проигрыш В;
5. Определяется β = min βj = min max aij, где β – верхняя цена игры, а соответствующая стратегия Bj* называется минимаксной стратегией игрока В;
6. Если игрок В выберет стратегию Вj*, то он гарантирует, что в одной игре он не проиграет больше чем β.
Особый интерес представляет платежная матрица, в которой нижняя цена игры равна верхней цене игры: α=β. Тогда α=β – цена игры. Если существует цена игры, то ни одному из игроков не выгодно отклоняться от Вj*, Ai* при многократном повторении игры, т.к. если он отклонится, то противник его накажет.
Если существует цена игры, т.е. α=β = ai*j*, то это означает, что имеется пара оптимальных стратегий Ai*, Bj* и каждому игроку при многократном повторении игры невыгодно отклоняться от оптимальной стратегии, т.к. если другой игрок при многократном повторении игры обнуляет это отклонение, то он может наказать противника.
Стратегии Ai*, Bj* в случае, если существуют цены игры, называются чистыми стратегиями. Если α≠β, т.е. цены игры не существуют, то игроки А и В не должны руководствоваться никакой чистой стратегией, а должны применять смешенные стратегии.
Пример 1. Игрок А может спрятаться в одном из двух мест: А1, А2. Игрок В, зная эти места, приходит в одно из них и, если он обнаруживает там игрока А, то А платит ему 1 рубль, Если В не обнаруживает А, то В платит 1 рубль.
B1 | B2 | αi | |
A1 | -1 | -1 | |
A2 | -1 | -1 | |
βj | α=-1, β=+1 |
α≠β – цена игры не существует, и не существуют оптимальные чистые стратегии. При отсутствии цены игры наилучшим выбором стратегии каждым из игроков является чисто случайный выбор без количественной закономерности (с помощью шапки).
Пример 2. «Игра в три пальца»
Игроки А и В одновременно выбрасывают по одному, двум или трем пальцам. Если сумма пальцев четная, то соответствующее количество рублей выигрывает игрок А, если нечетная – выигрывает игрок В.
B1 | B2 | B3 | αi | |
A1 | +2 | -3 | +4 | -3 |
A2 | -3 | +4 | -5 | -5 |
A3 | +4 | -5 | +6 | -5 |
βj | +4 | +4 | +6 | α=-3, β=+4 |
α≠β – цена игры не существует, и не существуют оптимальные чистые стратегии. При многократном повторении игры оба игрока должны применять смешанные стратегии, т.е. некоторым случайным образом менять выбираемую стратегию.
Пример 3. «Вооружение и самолет»
У обороняющейся стороны если три вида вооружений: А1, А2, А3; у противника – три вида самолетов: B1, B2, B3. Платежная матрица задает вероятности поражения самолета Bj вооружением Аi.
B1 | B2 | B3 | αi | |
A1 | 0.5 | 0.6 | 0.8 | 0.5 |
A2 | 0.9 | 0.7 | 0.8 | 0.7 |
A3 | 0.7 | 0.5 | 0.6 | 0.5 |
βj | 0.9 | 0.7 | 0.8 | α=β=0.7 |
α=β – цена игры существует. Стратегия A2B2 является оптимальной чистой стратегией.