Матричные игры в чистых стратегиях

Элементы теории матричных игр

Конфликтные ситуации – это ситуации, в которых интересы отдельных лиц (участников, групп, сторон) либо прямо противоположны (антагонистичны), либо, не будучи непримиримыми всё же не совпадают.

Эффективность решений, принимаемых в ходе конфликта каждой из сторон, существенно зависит от действий другой стороны.

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

Например, выпуск и объем продукции на конкурируемых предприятиях.

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

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

Игра – это упрощённая модель конфликтной ситуации, отличающаяся от реального конфликта тем, что ведётся по определенным правилам.

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

Исход игры – это значение некоторой платёжной функции, называемой функцией выигрыша (платёжной функцией).

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

Партией называют вариант поведения игры определенным образом.

Ход – это выбор и реализация игроком одного из возможных вариантов поведения.

Матричные игры в чистых стратегиях

Зададим парную игру с нулевой суммой.

У каждого из двух игроков А и В конечное число возможных действий – чистых стратегий.

А₁, …, А_m – чистые стратегии игрока А. m – количество этих стратегий.

В₁, …, В_n – чистые стратегии игрока В. n – количество этих стратегий.

a_ij – выигрыш игрока А за счёт игрока В или проигрыш игрока В.

При a_ij < 0 игрок А платит игроку В сумму | a_ij |.

Выбор пары чистых стратегий (А_i; B_j) определяет исход игры.

Если известны значения a_ij выигрыша каждой пары (А_i; B_j) стратегий, то можно составить матрицу игры – платёжную матрицу (таблица 1).

Таблица 1 - Платёжная матрица

Аi	Bj	αi
В1	…	Вn
А1 … Аm	a11 … am1	… … …	a1n … amn	α1 … αm
βj	β1	…	βn

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

Цель игроков:

игрок А стремится максимизировать выигрыш,

игрок В – минимизировать проигрыш.

Стратегию игрока А называют оптимальной, если при ее применении выигрыш игрока А не уменьшается, какими бы стратегиями не пользовался игрок В.

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

Для каждой своей чистой стратегии А_i игрок А определяет минимальное значение α_i выигрыша в зависимости от применяемых игроком В чистых стратегий B_j, т.е.

α_i = min a_ij (i = 1, …, m).

Затем по минимальным выигрышам α_i он отыскивает такую чистую стратегию А_iо, при которой этот минимальный выигрыш будет максимальным, т.е. находит

α = max α_i = max min a_ij. (1)

Число α определяемое по ф. (1), называется нижней чистой ценой игры (максимином).

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

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

Игрок В при наилучшем своём поведении максимально уменьшает проигрыш.

Поэтому для каждой чистой стратегии В_j он отыскивает

β_j = max a_ij (j = 1, …, n),

а затем по β_j находит такую свою стратегию B_jо, при которой его проигрыш будет минимальным, т.е.

β = min β_j = min max a_ij.(2)

Число β определяемое по ф. (2), называется верхней чистой ценой игры (минимаксом).

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

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

Т. о., используя чистые стратегии, игрок А обеспечивает выигрыш не меньше α, а игрок В в результате применения своих чистых стратегий может не позволить игроку А выиграть больше, чем β.

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

Максиминную и минимаксную стратегии игроков для краткости иногда называют минимаксной.

Пример.

Найти максиминную и минимаксную стратегии в игре с матрицей

Решение.

Таблица 2 - Платёжная матрица

Аi	Bj	αi
В1	В2	В3	В4
А1 А2 А3			-1 -2	-1	-1 -2
βj

В последнем столбце таблицы 2 выписаны минимальные по строкам элементы α_i.

Наибольшим из них будет 0.

Итак, максимин α = max min a_ij = 0, а максиминной чистой стратегией игрока А является А₂.

В последней строке таблицы приведены максимальные элементы соответствующих столбцов β_j.

Наименьшим из них является 2, значит, минимакс β = min max a_ij = 2, а минимаксной для игрока В является стратегия В₃.

Теорема 1. В матричной игре нижняя чистая цена игры не превосходит верхней чистой цены игры, т.е. α ≤ β.

Если в матричной игре нижняя и верхняя цены игры совпадают, т.е. α = β, то говорят, что эта игра имеет седловую точку в чистых стратегиях и чистую цену игры υ = α = β.

Обозначим через i_* и j_* номера чистых стратегий, при которых имеет место равенство α = β.

Пару чистых стратегий (А_i*; B_j*) игроков А и В, при которых достигается это равенство, называют седловой точкой матричной игры,

а элемент a_i*j* матрицы, стоящий на пересечении i_* - строки и j_* - столбца, - седловым элементом платёжной матрицы.

Пример 2.

Таблица 3 - Платёжная матрица

Аi	Bj	αi
В1	В2	В3	В4
А1 А2 А3		-2	-1 -5	-3	-3 -5
βj

Решение.

α = max α_i = max (2; -3; -5) = 2,

β = min β_j = min (9; 2; 3; 2) = 2,

υ = α = β= 2.

В данном случае имеются 2 седловые точки (А₁; В₂) и (А₁; В₄).

Для игрока А максиминной является стратегия А₁, для игрока В минимаксными являются стратегии В₂ и В₄.

Отв.: Матрица игры содержит 2 седловых элемента а₁₂ = 2 и а₁₄ = 2.

Седловой элемент a_i*j* является наименьшим в i_* - строке и наибольшим в j_* - столбце, т. е. a_ij*≤ a_i*j* ≤ a_i*j.

Поэтому назовём чистые стратегии А_i* и B_j*, образующие седловую точку и выделяющие в матрице игры седловой элемент, оптимальными чистыми стратегиями соответственно игроков А и В.

Набор {A_i*; B_j*; υ} будем называть решением игры.

В рассмотренном примере решениями игры будут{A₁; B₂; υ} { A₁; B₄; υ }.