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

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

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

А = ,

то проведение каждой партии матричной игры с матрицей А сводится к выбору игроком 1i–й строки, а игроком 2j–го столбца и получения игроком 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	2	3
стратегии 1–го игрока	1	1	–3	–2	–3
	2	0	5	4	0
	3	2	3	2	2
		2	5	4

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

Пример 2

Пусть .

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

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

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

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

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

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

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

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

		Стратегии 2–го игрока
		t12	t13	t23	t24
Стратегии 1-игрока	s12	0	2	–3	0
	s13	–2	0	0	3
	s23	3	0	0	–4
	s24	0	–3	4	0

Пример 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
X0	4	2	1	0
X1	1	3	0	–1
X2	–2	2	2	–2
X3	–1	0	3	1
X4	0	1	2	4