Методы решения матричных игр. Итерационный метод Брауна-Робинсона

Лекция №9

Методы решения матричных игр.

Итерационный метод Брауна-Робинсона.

Этот метод ориентирован на произвольную игру G(m×n).

Не требует условия aij>0.

Рассмотрим метод на примере игры G(3×3).

Ai \ Bj	B1	B2	B3
A1	7	2	9
A2	2	9	0
A3	9	0	11

SA=(p1,p2,p3)

SB=(q1,q2,q3)

Строится следующая матрица:

k	i	B1	B2	B3	j	A1	A2	A3	V	V	V*
1	3	9	0	11	2	2	9	0	0	9	4.5
2	2	11	9	11	2	4	18	0	4.5	9	6.75
3	2	13	18	11	3	13	18	11	3.67	6	4.84
4	2	13	18	11	3	22	18	22	…	…	…
5	…	…	…	…	…	…	…	…	…	…	…
…	…	…	…	…	…	…	…	…	…	…	…

где:

k – номер партии.

i – номер стратегии, выбираемой игроком A.

j – номер стратегии, выбираемой игроком В.

Bj – накопленный игроком А выигрыш за k партий, при условии, что в данной партии B выбирает стратегию Bj.

Аi – накопленный игроком В проигрыш за k партий, при условии, что в данной партии A выбирает стратегию Аi.

V – нижняя оценка игры = min (накопленный выигрыш)/k.

V – верхняя оценка игры = max (накопленный проигрыш)/k.

Доказано, что

V*=(V+V)/2, V* à V при k à ¥ и

– количество раз, которое выбиралась Аi стратегия.

– количество раз, которое выбиралась Bj стратегия.

Семинар №9

поиск решения матричных игр

Задача №1: Игра G(3×3)

Ai \ Bj	B1	B2	B3
A1	7	2	9
A2	2	9	0
A3	9	0	11

SA=(p1,p2,p3)

SB=(q1,q2,q3)

k	i	B1	B2	B3	j	A1	A2	A3	V	V	V*
1	3	9	0	11	2	2	9	0	0	9	4.5
2	2	11	9	11	2	4	18	0	4.5	9	6.75
3	2	13	18	11	3	13	18	11	3.67	6	4.84
4	2	13	18	11	3	22	18	22	2.75	5.5	4.125
5	…	…	…	…	…	…	…	…	…	…	…
…	…	…	…	…	…	…	…	…	…	…	…

V*=4.125

p1=0

p2=1

p3=0

q1=0

q2=1/2

q3=1/2

Задача №2: Задача о двух фирмах

Объявлен конкурс (тендер) на выполнение 2-х проектов.

На проект 1 выделено а денежных единиц.

На проект 2 выделено b денежных единиц.

В конкурсе участвуют 2 фирмы (Ф):

Ф1(А) – 4 отдела,

Ф2(В) – 3 отдела.

Практика показывает, что если фирма выделяет больше отделов на проект, то она и получает этот проект, если же они выделяют одинаковое количество отделов, то получения проекта Ф1 и Ф2 равновероятны.

Стратегии: (a, b)

a - количество отделов, выделяемых под 1 проект,

b - количество отделов, выделяемых под 2 проект.

Ф1(А): А1=(4,0); А2=(3,1); А3=(2,2); А4=(1,3); А5=(0,4).

Ф2(В): В1=(3,0); В2=(2,1); В3=(1,2); В4=(0,3);

Для того, чтобы свести парную игру к антагонистической, вычисляем средний выигрыш – (a+b)/2 и вычитаем его из V – выигрыш игрока А (V – (a+b)/2).

G(5×4):

a11 = a – a/2 = a/2

a12 = a13 = a14 = a – (a+b)/2 = (a-b)/2

a21 = a/2 + b – (a+b)/2 = b/2

a22 = a + b/2 – (a+b)/2 = a/2

a23 = a24 = a – (a+b)/2 = (a-b)/2

a31 = b – (a+b)/2 = (b-a)/2

a32 = a/2 + b – (a+b)/2 = b/2

a33 = a + b/2 – (a+b)/2 = a/2

a34 = a – (a+b)/2 = (a-b)/2

a41 = a42 = b – (a+b)/2 = (b-a)/2

a43 = a/2 + b – (a+b)/2 = b/2

a44 = a + b/2 – (a+b)/2 = a/2

a51 = a52 = a53 = b – (a+b)/2 = (b-a)/2

a54 = a/2 + b – (a+b)/2 = b/2

	В1	В2	В3	В4
А1	а/2	(a-b)/2	(a-b)/2	(a-b)/2
А2	b/2	a/2	(a-b)/2	(a-b)/2
А3	(b-a)/2	b/2	a/2	(a-b)/2
А4	(b-a)/2	(b-a)/2	b/2	a/2
А5	(b-a)/2	(b-a)/2	(b-a)/2	b/2

Пусть а=b.

1)

	В1	В2	В3	В4
А1	a/2	0	0	0
А2	a/2	a/2	0	0
А3	0	a/2	a/2	0
А4	0	0	a/2	a/2
А5	0	0	0	a/2

2)

	В1	В2	В3	В4
А2	a/2	a/2	0	0
А3	0	a/2	a/2	0
А4	0	0	a/2	a/2

3)

	В1	В4
А2	a/2	0
А3	0	0
А4	0	a/2

G(2×2):

	В1	В4
А2	a/2	0
А4	0	a/2

Из-за симметричности матрицы игры решение получим по методу Лагранжа:

p2=p4=1/2 q1=q4=1/2

SA=(0,1/2,0,1/2,0)

SB=(1/2,0,0,1/2)

V=( a11*p2+a21*p4)*q1+( a12*p2+a22*p4)*q4=a/4

VФ1=a/4+a=5a/4

VФ2=3a/4