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

Рассмотрим биматричную игру с нулевой суммой. Пусть для первого игрока X ₁={1,2,..., m }, для второго X ₂={1,2,..., n }. Выбираемые стратегии будем обозначать соответственно i и j. Каждой паре стратегий (i, j) поставлено в соответствие некоторое число j ₁(i, j)= а_ij, выражающее выигрыш игрока 1, j ₂(i, j)=– а_ij – выигрыш 2–го игрока (а_ij – его проигрыш). Для первого игрока предпочтителен выбор пары (i, j), увеличивающий значение а_ij. Для второго игрока предпочтителен выбор пары (i, j), уменьшающий значение а_ij. Эту модель будем записывать так

Такая игра является антагонистической игрой двух лиц. Допустим, что каждый из игроков делает один ход: игрок 1 выбирает свою i –ю стратегию i =1,2,3,…, m, а игрок 2 – свою j –ю стратегию j =1,2,3,…, n. После выполнения ходов игрок 1 получает выигрыш а_ij за счёт игрока 2 (если а_ij< 0, то это значит, что игрок 1 платит второму сумму | а_ij |). На этом игра заканчивается. Стратегии игроков i =1,2,3,…, m, и j =1,2,3,…, n будем называть чистыми стратегиями.

Если рассмотреть матрицу

А = ,

то проведение каждой партии матричной игры с матрицей А сводится к выбору игроком 1 i –й строки, а игроком 2 j –го столбца и получения игроком 1 (за счёт игрока 2) выигрыша а_ij.

Введем понятие гарантированных стратегий игроков. В это понятие вложим следующий смысл: стратегия игрока называется гарантированной, если применение этой стратегии обеспечивает выигрыш, который не может быть уменьшен при всевозможных стратегиях другого игрока. Исходя из этих позиций, игрок 1 исследует матрицу выигрышей А следующим образом: для каждого значения i =1,2,3,…, m определяется j (i), для которого значение выигрыша по стратегиям 2–го игрока минимально

Среди значений i =1,2,3,…, m и соответствующих им значений j (i) выбирается то значение i ₁, j ₁= j (i ₁) для которого

Это выражение можно переписать

(3. 1).

 

Определение 3. 1. Число , определённое по формуле (3. 1), называется нижней чистой це н ой игры и показывает, какой выигрыш может гарантировать себе игрок 1, применяя свои чистые стратегии при всевозможных действиях игрока 2.

Игрок 2 при при поиске своего гарантированного проигрыша должен стремится по возможности за счёт своих стратегий максимально уменьшить выигрыш игрока 1. Поэтому для игрока 2 определяется с начала для каждого j =1,2,3,…, n определяется i (j), для которого

,

т.е. для каждого j =1,2,3,…, n определяется величина наибольшего проигрыша. Затем среди этих проигрышей выбирается наименьший, т.е. выбираем j ₂ и соответственно i ₂= i (j ₂), для которых

при условии, что игрок 2 применит свою j –ю чистую стратегию, затем игрок 2 отыскивает такую свою j = j ₂ стратегию, при которой он получает гарантированный проигрыш, т.е. находит

(3. 2).

Определение 3. 2. Число , определяемое по формуле (3.2), называется чистой верх н ей ценой игры и показывает, какой проигрыш за счёт своих стратегий может себе гарантировать игрок 2.

Другими словами, применяя свои чистые стратегии, игрок 1 может обеспечить себе выигрыш не меньше , а игрок 2 за счёт применения своих чистых стратегий может себе обеспечить проигрыш не более, чем .

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

Не трудно видеть, что точка (i ₀, j ₀) является седловая точкой функции а_ij, i = 1,2,..., m, j = 1,2,..., n.

Вопрос о существовании равновесия в матричной игре двух игроков с нулевой суммой определяется следующей теоремой.

Теорема. Для того, чтобы в задаче существовала седловая точка, необходимо и достаточно, чтобы

(3.3)

 

Таким образом, исходя из (3.3), седловой элемент является минимальным в i ₀ –й строке и максимальным в j ₀ – м столбце в матрице А. Отыскание седловой точки матрицы А происходит следующим образом: в матрице А последовательно в каждой строке находят минимальный элемент и проверяют, является ли этот элемент максимальным в своём столбце. Если да, то он и есть седловой элемент, а пара стратегий, ему соответствующая, образует седловую точку. Пара чистых стратегий (i ₀, j ₀) игроков 1 и 2, образующая седловую точку и седловой элемент называется реше н ием игры. При этом i ₀ и j ₀ являются чистыми стратегиями, гарантирующие выигрыш и проигрыш соответственно игроков 1 и 2.

 

Пример 1.

Пусть .

Всю информацию по матрице и результаты анализа запишем в таблицу:

		стратегии 2–го игрока
стратегии 1–го игрока			–3	–2	–3

 

 

Точкой равновесия является пара (i ₀; j ₀)=(3,1), при которой . Заметим, что хотя выигрыш в ситуации (3;3) также равен , она не является равновесной, т.к. этот выигрыш не является максимальным среди выигрышей третьего столбца.

Пример 2

Пусть .

Всю информацию по матрице и результаты анализа запишем в таблицу:

		стратегии 2–го игрока
стратегии 1–го игрока			–3	–2	–3

 

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

 

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

Пример 3. Два игрока кладут одновременно на стол по монете. Если обе монеты выложены одной стороной, то они достаются первому игроку, в противном случае они достаются второму игроку.

Для нее матрица игры будет иметь вид

Пример 4. Игра Морро.

Игроки одновременно показывают не более m пальцев и в тоже время называют число, не большее n. Если число, названное одним из игроков, совпадает с общим числом пальцев, то игрок получит от своего противника выигрыш равный этому числу. Если оба угадают верно, то чистый платёж будет равен нулю. Таблица игры для случая m =2, n =4 будет иметь вид. В ней s_kl означает, l – показанных пальцев, k – названное число первым игроком. Аналогично t_kl для второго игрока.

		Стратегии 2–го игрока
		t 12	t 13	t 23	t 24
Стратегии 1-игрока	s 12			–3
s 13	–2
s 23				–4
s 24		–3

 

Пример 5. Оборона города («Игра полковника Блотто»)

Полковник Блотто имеет т полков, а его противник — n полков. Противник защищает две позиции. Позиция будет занята полковником Блотто, если на ней наступающие полки окажутся в численном превосходстве. Противоборствующим сторонам требуется распределить полки между двумя позициями.

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

Игра, очевидно, антагонистическая. Опишем стратегии игроков. Пусть, для определенности, т>п. Игрок I имеет следующие стратегии: х ₀=(т,0) — послать все полки на первую позицию, x_l =(т—i, i)—(m–i) полков послать на первую позицию, а i — на вторую, х _m = (0, m). Противник имеет такие стратегии: У ₀=(п,0), у ₁=(п —i, i),..., у„ =(0, п).

Так, при m =4, n = 3, рассмотрев всевозможные ситуации, получим матрицу выигрышей этой игры:

	Y0	Y1	Y2	Y3
X 0
X 1				–1
X 2	–2			–2
X 3	–1
X 4

 

Самостоятельная работа № 5.

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

		Число показываемых пальцев
Называемое число

 

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

		Значение n
Значение m