Методы и модели игры

Часть I МАТРИЧНЫЕ ИГРЫ

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

Предположим, что игрок А имеет m стратегий — А₁, А₂, ..., А_m, а игрок В имеет n стратегий В₁, В₂, ..., В_n.

Пусть игрок А выбрал стратегию A_i, а игрок В стратегию В_k. Будем считать, что выбор игроками стратегий A_i и В_k однозначно определяет исход игры — выигрыш а_ik игрока А и выигрыш b_ik игрока В, причем эти выигрыши связаны равенством

(отрицательный выигрыш на бытовом  языке обычно называют проигрышем).

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

Если нам известны значения а_ik выигрыша при каждой паре стратегий (в каждой ситуации) { A_i, В_k }, i = 1, 2,..., m, k = 1, 2,..., n, то их удобно записывать или в виде прямоугольной таблицы, строки которой соответствуют стратегиям игрока А, а столбцы – стратегиям игрока В:

	В1	В1	…	Вn
А1	a11	a11		a11
А2	a11	a11		a11
Аm	am1	a11		amn

 

или в виде матрицы

Полученная матрица имеет размер m x n и называется матрицей игры, или платежной матрицей (отсюда и название игры — матричная).

Рассматриваемую игру часто называют игрой m x n или m x n игрой.

Замечание. Матричные игры относятся к разряду так называемых антагонистических игр, то есть игр, в которых интересы игроков прямо противоположны.

Пример 1. Каждый из двух игроков А и В одновременно и независимо друг от друга записывает на листе бумаги любое целое число. Если выписанные числа имеют одинаковую четность, то игрок А получает от игрока В 1 рубль, а если разную, то наоборот – игрок А платит 1 рубль игроку В.

У игрока А две стратегии: А₁ – записать четное число и А₂ – записать нечетное число. У игрока В такие же две стратегии: В₁ – записать четное число и В₂ – записать нечетное число. Выбор игроками соответственно стратегий А_i и В_k однозначно определяет исход игры – выигрыш игрока А.

Матрица этой 2x2 игры имеет  следующий вид

(здесь строки соответствуют  стратегиям игрока А, а столбцы — стратегиям игрока В).

 

1. Равновесная  ситуация

Рассмотрим следующий пример.

Пример 2. Два игрока А и В, не глядя друг на друга, кладут на стол по картонному кружку красного (г), зеленого (g) или синего (b) цветов, сравнивают цвета кружков и расплачиваются друг с другом так, как покапано в матрице игры

(напомним, что у этой 3 х 3-матрицы  строки соответствуют стратегиям  игрока А, а столбцы - стратегиям игрока В).

Считая, что эта 3 х 3 игра повторяется  многократно, попробуем определить оптимальные стратегии каждого из игроков.

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

Так, на стратегию А, он ответит стратегией В_r, (минимальный выигрыш равен -2, что на самом деле означает проигрыш игрока А, равный 2), на стратегию А_g – cстратегией  B_g или В_b (минимальный выигрыш игрока А равен 1), а на стратегию A_b – стратегией B_g (минимальный выигрыш игрока А равен -3).

Запишем эти минимальные выигрыши в правом столбце таблицы:

	Br	Bg	Bb
Ar	-2	2	-1	-2
Ag	2	1	1	1
Ab	3	-3	1	-3

maxmin. Неудивительно, что игрок А останавливает свой выбор на стратегии А_g, при которой его минимальный выигрыш максимален (из трех чисел -2, 1 и -3 максимальным является 1):

	Br	Bg	Bb
Ar	-2	2	-1	-2
Ag	2	1	1	1
Ab	3	-3	1	-3

 

maxmin = 1.

Если игрок А будет придерживаться этой стратегии, то ему гарантирован выигрыш, не меньший 1, при любом поведении противника в игре.

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

Выбирая свою стратегию, игрок В должен учитывать, что при этом стратегией его противника А может оказаться та, при которой выигрыш игрока А будет максимальным. Так, на стратегию В_r он ответит стратегией A_b (максимальный выигрыш игрока А равен 3), на стратегию B_g – стратегией A_r (максимальный выигрыш игрока А равен 2), а на стратегию B_b – стратегией А_g или A_b (максимальный выигрыш игрока А равен 1). Эти максимальные выигрыши записаны в нижней строке таблицы

	Br	Bg	Bb
Ar	-2	2	-1	-2
Ag	2	1	1	1
Ab	3	-3	1	-3
	3	2	1

minmax. Неудивительно, вели игрок В остановит свой выбор на стратегии B_b, при которой максимальный выигрыш игрока А минимален (из трех чисел 3, 2 и 1 минимальным является 1):

	Br	Bg	Bb
Ar	-2	2	-1	-2
Ag	2	1	1	1
Ab	3	-3	1	-3
	3	2	1

 

minmax = 1.

Если игрок В будет придерживаться этой стратегии, то при любом поведении противника он проиграет не больше 1.

В рассматриваемой игре числа maxmin и minmax совпали:

maxmin = minmax = 1

(соответствующие элементы в  таблице

	Br	Bg	Bb
Ar	-2	2	-1
Ag	2	1	1
Ab	3	-3	1

выделены жирным шрифтом).

 

Выделенные стратегии A_g и B_b являются оптимальными стратегиями игроков А и В,

A_g = A_opt, B_b = B_opt

в следующем смысле:

 

при многократном повторении игры отказ от выбранной  стратегии любым из игроков уменьшает его шансы на выигрыш (увеличивает шансы на проигрыш).

 

В самом деле, если игрок А будет придерживаться не стратегии A_opt, а выберет иную стратегию, например, А_r, то вряд ли стоит рассчитывать на то, что игрок В этого не заметит. Конечно, заметит и не преминет воспользоваться своим наблюдением. Ясно, что в этом случае он отдаст предпочтение стратегии В_r. А на выбор A_b игрок В ответит, например, так – B_g. В результате отказа от стратегии A_g, выигрыш игрока А уменьшится.

Если же от стратегии B_opt отказывается игрок В, выбирая, например, стратегию В_r, то игрок А 
может ответить на это стратегией A_b и, тем самым, увеличить свой выигрыш. В случае стратегии B_g ответ игрока А – А_r .

Тем самым, ситуация { A_g, В_b } оказывается равновесной.

 

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

Матрица выплат игроку В получается из матрицы игры заменой каждого ее элемента на противоположный по знаку.

Рассмотрим теперь произвольную матричную  игру

 

(строки заданной m x n-матрицы соответствуют стратегиям игрока А, а столбцы -  стратегиям игрока В) и опишем общий алгоритм, посредством которого можно определить, есть ли в этой игре ситуация равновесия или ее нет.

 

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

 

Действия игрока А

1-й шаг. В каждой строке матрицы А ищется минимальный элемент

, i = 1, 2, … , m.

Полученные числа

α₁, α_{2, …} , α_m

приписываются к заданной таблице  в виде правого добавочного столбца

a11	a12	…	a1n	α1
a21	a22	…	a2n	α2
…	…	…	…	…
am1	am2	…	amn	αm

 

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

2-й шаг. Среди чисел

α₁, α_{2, …} , α_m

выбирается максимальное число

или, подробнее,

Специально отметим, что  выбранное число α является одним из элементов заданной матрицы А.

Пояснение. Действуя наиболее осторожно и рассчитывая на наиболее разумное поведение противника, игрок А должен остановиться на той стратегии A_i, для которой число а_i, является максимальным.

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

Число α называется нижней ценой игры.

Принцип построения стратегии игрока А, основанный на максимизации минимальных выигрышей, называется принципом максимина, а выбираемая в соответствии с этим принципом стратегия А_i⁰ — максиминной стратегией игрока А.

 

Действия игрока В

1 шаг. В каждом столбце матрицы А ищется максимальный элемент

, k = 1, 2, … , n.

Полученные числа

β₁, β₂, … , β_n

приписываются к заданной таблице  в виде нижней добавочной строки

a11	a12	…	a1n	α1
a11	a22	…	a2n	α2
…	…	…	…	…
a11	am2	…	amn	αm
β1	β2	…	βn