Некоторые модели теории игр

Игровые модели в исследовании операций

Введение

Исследование операций – прикладное направление кибернетики, изучающее способы выработки оптимальных решений выполнения различных операций на основе мат.моделей и соответствующих методов.

Операция – система действий и мероприятий, объединенных единым замыслом и направленных к достижению определенной цели с наибольшей эффективностью.

Исследование операций появилось впервые в 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 является оптимальной чистой стратегией.