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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

αi = min aij (i = 1, …, m).

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

α = max αi = max min aij. (1)

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

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

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

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

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

βj = max aij (j = 1, …, n),

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

β = min βj = min max aij.(2)

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

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

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

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

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

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

Пример.

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

Матричные игры в чистых стратегиях - student2.ru

Решение.

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

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

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

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

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

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

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

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

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

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

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

а элемент ai*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 седловые точки (А1; В2) и (А1; В4).

Для игрока А максиминной является стратегия А1, для игрока В минимаксными являются стратегии В2 и В4.

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

Седловой элемент ai*j* является наименьшим в i* - строке и наибольшим в j* - столбце, т. е. aij*≤ ai*j* ≤ ai*j.

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

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

В рассмотренном примере решениями игры будут{A1; B2; υ} { A1; B4; υ }.


Наши рекомендации