Файл: Теория принятия решений преподаватель доцент кафедры ису, к т. н. Бушуева Марина Евгеньевна биматричные игры.ppt

Предыдущие рассмотрения касались игр двух лиц, в которых интересы игроков были прямо противоположны. Однако ситуации, в которых интересы игроков хотя и не совпадают, но уже необязательно являются противоположными, встречаются значительно чаще.
Игрок А. Стратегии А1, …, Аm , Игрок В. Стратегии В1, …, Вn

		B1	..	Bn
	A1	b11	..	b1n
B=	A2	b21	..	b2n
	:	:		:
	Am	bm1	..	bmn

		B1	..	Bn
	A1	a11	..	a1n
A=	A2	a21	..	a2n
	:	:		:
	Am	am1	..	amn

А – платежная матрица игрока А,
В – платежная матрица игрока В,

ПРИМЕРЫ БИМАТРИЧНЫХ ИГР

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

ПРИМЕР 1: БОРЬБА ЗА РЫНКИ

А1, А2 - выбор рынков игроком A

В1, В2 – выбор рынков игроком B

		B1	B2
A=	A1	-10	2
	A2	1	-1

		B1	B2
B=	A1	5	-2
	A2	-1	1

ПРИМЕР 2: ДИЛЕММА УЗНИКОВ

Два узника А и В находятся в предварительном заключении по подозрению в совершении преступления. При отсутствии улик их осуждение зависит от того, будут ли они говорить или лгать. Если оба будут молчать, то наказание – лишь срок предварительного заключения. Если сознаются, то получат срок, учитывающий признание как смягчающее обстоятельство: потери -6. Если заговорит один из узников, а другой будет молчать, то тот, который заговорит – на свободу. Его потери 0, а хранящий молчание получит -9.

		М	Г
А =	М	-1	-9
	Г	0	-6

В =		М	Г
	М	-1	0
	Г	-9	-6

СМЕШАННАЯ СТРАТЕГИЯ

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

Смешанная стратегия в биматричных играх также определяет средний выигрыш игроков А и В, но тут нет дискриминации игрока В

- выигрыш игрока А

- выигрыш игрока В

Биматричные игры 2х2. Ситуация равновесия

Рассмотрим ситуацию, когда у каждого две стратегии:

p	b11	b12
B =
1-p	b21	b22
	q	(1-q)

Запишем средний выигрыш исходя из формул:

p	a11	a12
A =
1-p	a21	a22
	q	(1-q)

ОСНОВНОЕ ОПРЕДЕЛЕНИЕ: будем говорить. Что пара чисел (р*,q*), где р*,q* - вероятности от 0 до 1, определяют равновесную ситуацию для всех р и q, если одновременно выполняются следующие неравенства:

НА (р,q*) ≤ НА (р*,q*)

НВ (р*,q) ≤ НВ (р*,q*)

ТЕОРЕМА НЭША: Всякая биматричная игра имеет хотя бы одну равновесную ситуацию (точку равновесия) в смешанных стратегиях

Выполнение неравенств (1) равносильно выполнению следующих неравенств:

НА(0,q*) ≤ НА(р*,q*) НВ(р*,0) ≤ НВ(р*,q*)
НА(1,q*) ≤ НА(р*,q*) НВ(р*,1) ≤ НВ(р*,q*)

(1)

Запишем средние выигрыши игроков А и В в более удобной форме:

НА(p,q) = (a11-a12-a21-+a22)pq + (a12 – a22)p + (a21-a22)q + a22

НB(p,q) = (b11-b12-b21+b22)pq + (b12 – b22)p + (b21-b22)q + b22

Рассмотрим НА (p,q), полагая р = 0, потом р = 1:

НА(0,q) = (a21-a22)q + a22
HA(1,q) = (a11- a12 - a21+a22)q + (a21- a22)q + a12

Рассмотрим разности:

НА(p,q) - HA (1,q) = (a11-a12-a21+a22)pq + (a12 - a22)p - (a11- a12-
- a21+a22)q + а22 – а12
НА(p,q) - HA (0,q) = (a11- a12- a21+ a22)pq + (a12 – a22)p

Вводятся следующие обозначения:

Вводятся следующие обозначения:

С = a11- a12- a21+ a22
α = а22- а12

НА(p,q) - HA (1,q) = (р-1)(Сq-α)
НА(p,q) - HA (0,q) = p(Cq-α)

Тогда

В случае, когда пара (р,q) определяет точку равновесия, все эти разности ≥ 0.

(р-1)(Сq-α) ≥ 0
p(Cq-α) ≥ 0

Для игрока A

Для игрока B

Для игрока B

Рассмотрим НB , пологая q = 0, потом q = 1

НB (p,0)

= (b12-b22)p + b22
HB (p,1) = (b11-b12-b21+ b22)p + (b12-b22)p + b21

Рассмотрим разности:

НB(p,q) - HB (p,1) и НB(p,q) - HB (p,0)

Вводятся следующие обозначения:

D = b11-b12-b21+b22
β = b22-b21

Для игрока B

(q-1)(Dp-β) ≥ 0
q(Dp-β) ≥ 0

ВЫВОД

Для того, чтобы в биматричной игре

	a11	a12
A =
	a21	a22

	b11	b12
B =
	b21	b22

пара (р,q) определяла равновесную ситуацию, необходимо и достаточно выполнение следующих неравенств

(р-1)(Сq-α) ≥ 0
p(Cq-α) ≥ 0

(q-1)(Dp-β) ≥ 0
q(Dp-β) ≥ 0

С = a11-a12-a21+ a22 , α = а22- а12

D = b11-b12-b21+ b22 , β = b22- b21

ПРИМЕР 1: БОРЬБА ЗА РЫНКИ

		B1	B2
A=	A1	-10	2
	A2	1	-1

		B1	B2
B=	A1	5	-2
	A2	-1	1

С = a11-a12-a21+ a22 = -10 - 2 – 1 - 1= -14, α = а22- а12 = -1 – 2 = -3

D = b11-b12-b21+ b22 = 5 + 2 +1 + 1 = 9, β = b22- b21 = 1+1 = 2

(р-1)(-14q +3) ≥ 0
p(-14q +3) ≥ 0

Получаем

(q-1)(9p-2) ≥ 0
q(9p-2) ≥ 0

(р-1)(-14q +3) ≥ 0 p(-14q +3) ≥ 0

Рассмотрим ситуацию для игрока A

1. p=1 -14q +3 ≥ 0 , q  3/14

2. p=0 - (-14q +3) ≥ 0 , q ≥ 3/14

3. 0 < p < 1 -14q +3 = 0 , q = 3/14

Рассмотрим ситуацию для игрока B

(q-1)(9p-2) ≥ 0
q(9p-2) ≥ 0

1. q=1, p ≥ 2/9

2. q=0, p  2/9

3. 0 < q < 1 p = 2/9

РЕШЕНИЕ

НА(p,q) = (a11-a12-a21-a22)pq + (a12 – a22)p + (a21-a22)q + a22

НB(p,q) = (b11-b12-b21-b22)pq + (b12 – b22)p

+ (b21-b22)q + b22

НB(2/9, 3/14) = 1/3

НА(2/9, 3/14) = -4/7

ПРИМЕР 2: ДИЛЕММА УЗНИКОВ

		B1	B2
А =	A1	-1	-9
	A2	0	-6

В =		B1	B2
	A1	-1	0
	A2	-9	-6

С = a11-a12-a21+ a22 = 2, α = а22- а12 = 3

D = b11-b12-b21+ b22 = 2, β= b22- b21 = 3

1. p=1, q ≥ 3/2

2. p=0, q  3/2

3. 0 < p < 1, q = 3/2

1. q=1, p ≥ 3/2

2. q=0, p  3/2

3. 0 < q < 1 p = 3/2

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

ЗАДАЧА 1. СЕМЕЙНЫЙ СПОР

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