§5.1 Игровые модели. Платежная матрица. Нижняя и верхняя цена игры.

   Методы решения задач с конфликтными ситуациями разработаны математической теорией, которая носит название теория игр.

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

    Для каждой игры вводятся правила, т.е. система условий, определяющая:

1. варианты дейсвтия игроков;
2. объем информации каждого игрока о поведении партнеров;
3. выйгрыш, к которому приводит каждая совокупность действий.

Как правило, выйгрыш (или проигрыш) может быть задан количественно.

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

    Парная игра называется игрой с нулевой суммой, или антагонистической, если выйгрыш одного из игроков равен проигрышу другого.

    Выбор и осуществление одного из предусмотренных правилами действий называется ходом игрока. Ходы могут быть личными, когда это сознательный выбор игроком одного из возможных дейсвтий и случайными, когда это случайно выбранное действие. Далее  будем рассматривать только личные ходы игроков.

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

Опр.Оптимальной стратегией игрока называется такая, которая обеспечивает ему наилучшее положение в данной игре, т.е. максимальный выйгрыш.

Опр.Игра называется конечной, если у каждого игрока имеется конечное число стратегий, и бесконечной – в противном случае.

Для того чтобы решить игру или найти решение игры, следует для каждого игрока выбрать стратегию, которая удовлетворяет условию оптимальности,т.е. один из игроков должен получить максимальный выйгрыш, когда второй придерживается своей стратегии. Задача теории игр – выявление стратегий игроков.

   Если игра повторяется достаточно много раз, то игроков может интересовать не выйгрыш и проигрыш в каждой конкретной партии, а средний выигрыш (проигрыш) во всех партиях.

              Целью теории игр является определении оптимальной стратегии для каждого игрока.

Рассмотрим парную конечную игру с нулевой суммой. Пусть игрок А располагает m различными стратегиями, котороые обозначим . Пусть у игрока В имеется n различных стратегий, . В этом случае игра имеет размерность . В результате выбора игроками любой пары стратегий и (; .) однозначно определяется исход игры, т.е. выйгрыш игрока А (положительный или отрицательный) и проигрыш игрока В. Если предположить, что значения известны для любой пары стратегий (, ), то матрица (; ).

     Строки этой таблицы соответствуют стратегиям игрока А, а столбцы – стратегиям игрока В.

Пример. Каждый из двух игроков А и В одновременно и независимо друг от друга записывает на листе бумаги любое целое число. Если выписанные числа имеют одинаковую четность, то игрок А получает от игрока В 1 рубль, а если разную, то наоборот – игрок А платит 1 рубль игроку В.

Решение. У игрока  А две стратегии: - записать нечетное число, - записать нечетное число. У игрока В такие же две стратегии:

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

.

Рассмотрим игру с матрицей (; ) и определим наилучшую среди стратегий . Выбирая стратегию , игрок А должен рассчитывать, что игрок В ответит на нее той из стратегий , для которой выйгрыш для игрока А минимален.

Обозначим через наименьший выйгрыш игрока А при выборе им стратегии для всех возможных стратегий игрока В (наименьшее число в i-й строке платежной матрицы), т.е. .

Среди всех чисел () выберем наибольшее – нижняя цена игры, или максимальный выигрыш (максимин). Это гарантированный выйгрыш игрока А при любой стратегии игрока В. Следовательно,

Стратегия, соответствующая максимуму, называется максиминной стратегией. Игрок B заинтересован в том, чтобы уменьшить выигрыш игрока A. Выбирая стратегию , он учитывает максимально возможный при этом выигрыш для A. Пусть

.

Среди всех чисел выберем наименьшее – верхняя цена игры,илиминимальный выигрыш(минимакс). Это гарантированный проигрыш игрока B. Следовательно,

Стратегия, соответствующая минимаксу, называется минимаксной стратегией.

Принцип, диктующий игрокам выбор наиболее «осторожных» минимаксной и максиминной стратегией, называется принципом минимакса.

Пример. Два игрока А и В, не глядя друг на друга, кладут на стол по картонному кружку красного (r), зеленого (g) или синего (b) цветов и расплачиваются друг с другом так, как показанов матрице игры

.

Считая, что эта 3х3 игра повторяется многократно, попробуем определить оптимальные стратегии каждого из игроков.

Начнем с последовательного анализа стратегий игрока A, не забывая о том, что выбирая стратегию игрока A, должно принимать в расчет, что его противник B может ответить на нее той из своих стратегий, при которой выигрыш игрока A будет минимальным.

Запишем эти минимальные выигрыши в правом столбце таблицы:

Если игрок A будет придерживаться этой стратегии, то ему гарантирован выигрыш, не меньший 1, при любом поведении противника в игре.

Аналогичные рассуждения можно провести и за игрока B. Так как игрок B заинтересован в том, чтобы обратить выигрыш игрока A в минимум, то ему нужно проанализировать каждую свою стратегию с точки зрения максимального выигрыша игрока A.

       Если игрок B будет придерживаться этой стратегии, то при любом поведении противника он проиграет не больше 1.

       В рассматриваемой игре числа maxmin и minmax совпали:

.

        Это значение называется чистой ценой игры или ценой игры.

       Минимаксные стратегии, соответствующие цене игры, являются оптимальными стратегиями, а их совокупность – оптимальным решением, или решением игры.

       Выделенные стратегии и являются оптимальными для игроков A и B, ,, это означает, что при многократном повторении игры отказ от выбранной стратегии любым из игроков уменьшает его шансы на выигрыш (увеличивает шансы на проигрыш).

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

В предыдущем примере - седловая точка.