7.2 Моделирование конфликтов в теории игр

При управлении производством очень часто приходится принимать решения, не имея достаточной информации, то есть в условиях неопределенности и риска.

Методами обоснования решений в условиях неопределенности и риска занимается математическая теория игр.

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

Так как цели противоположны, а результат мероприятия каждой из сторон зависит от действий конкурента, то эти действия называют конфликтными ситуациями. В конфликтной ситуации сталкиваются противоположные интересы двух участников. Формализованная (схематизированная) модель конфликтной ситуации называется игрой. Результат игры – победа или поражение, которые не всегда имеют количественное выражение, можно выразить (условно) числами (например, в шахматах: 1, 0, 1/2).

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

Развитие игры во времени представляется как ряд последовательных «ходов». Ходы могут быть сознательные и случайные. Случайный ход - результат, получаемый не решением игрока, а каким-либо механизмом случайного выбора (покупательский спрос, задержка с поставкой материалов и т. п.). Сознательный ход - выбор игроком одного из возможных вариантов действия (стратегии) и принятие решения о его осуществлении.

Возможные варианты (исходы) игры сводятся в прямоугольную таблицу (табл.15) – платежную матрицу, в которой строки соответствуют различным стратегиям игрока , столбцы – стратегиям игрока . Для условности предположим, что игрок – выигрывает, а игрок – проигрывает.

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

Цель теории игр – выработка рекомендаций для различного поведения игроков в конфликтной ситуации, то есть выбор оптимальной стратегии для каждого из них.

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

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

Где

– максиминный выигрыш (максимин), а соответствующая ей стратегия – максиминная.

Таблица 15 – Платежная матрица

			…
			…
			…
…	…	…	…	…
			…

Таблица 16 – Платежная матрица с добавочными столбцом и строкой

			…
			…
			…
…	…	…	…	…
			…

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

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

Из всех значений находят минимальное:

Которое дает минимаксный выигрыш или минимакс.

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

Если , то число называют чистой ценой игры или седловой точкой.

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

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

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

Из этого определения следует, что сумма компонент этого вектора равна единице, а сами компоненты не отрицательны.

Обычно смешанную стратегию первого игрока обозначают как вектор

, а второго игрока - как вектор , где

, , . (36)

Если u° – оптимальная стратегия первого игрока, – оптимальная стратегия второго игрока, то число – называют ценой игры.

Для того чтобы число - было ценой игры, а и – оптимальными стратегиями, необходимо и достаточно выполнение неравенств:

, (), (37)

, (). (38)

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

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

Однако не следует забывать, что:

1) применение смешанных стратегий рисковано, когда игра не повторяется;

2) если игра повторяется, надо иметь уверенность, что у противника нет информации о конкретных решениях другого игрока;

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

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

Теорема фон Неймана. Любая матричная игра имеет седловую точку в смешанных стратегиях.

Доказательство. Множества и ограничены и замкнуты, так как , , а функция непрерывна по и . Линейна по при фиксированных , следовательно, вогнута по при фиксированных . Аналогично выпукла по при фиксированных . и выпуклы.

Действительно, рассмотрим такие и , что , , тогда , .

Складывая, получим.

Кроме того,

Следовательно, при и тоже смешанная стратегия.

Применяя фундаментальную теорему, получим то, что требуется доказать:

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

Пусть и оптимальные смешанные стратегии, - цена игры, тогда