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

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

 

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

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

 

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

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

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

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

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

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

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

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

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

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

 

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

 

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

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

А ₁, …, А_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	a 11 … am 1	… … …	a 1 n … 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 ₄; υ }.