Решение матричной игры в чистых и смешанных стратегиях

 

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

Предположим, что игроку А надлежит сделать свой выбор. Анализируя платежную матрицу, он для каж­дой чистой стратегии A_i сначала найдет минималь­ное значение α _i ожидаемого выигрыша: , а затем из всех α _i выделит наибольшее и выберет соответствующую ему чистую стратегию . Это и будет наи­более предпочтительная (гарантирующая) в данных условиях стратегия игрока А. Ее называют максиминной, поскольку она отвечает величине

 

. (7.1)

 

Число α , определяемое по формуле (7.1), называется ниж­ней чистой ценой игры (максимином). Оно показывает, какой минимальный выигрыш может получить игрок А, правильно применяя свои чистые стратегии при любых действиях игро­ка В.

В свою очередь, игрок В, стремясь минимизировать проиг­рыш, при выборе наиболее предпочтительной стратегии, исполь­зует принцип осторожности так: сначала он для каждой чистой стратегии В_j ( ) найдет максимально возможный про­игрыш ( ), а затем среди β _j вы­берет минимальное значение , которому и будет со­ответствовать искомая чистая стратегия . Ее называют ми­нимаксной, так как она соответствует величине

 

. (7.2)

 

Число β , определяемое по формуле (7.2), называется верх­ней чистой ценой игры (минимаксом). Оно показывает, какой максимальный проигрыш может быть у игрока В при пра­вильном выборе им своих чистых стратегий независимо от действий игрока А.

Если в матричной игре нижняя и верхняя чистые цены совпадают, т.е. α = β , то эта игра имеет седловую точку в чистых стратегиях и чистую цену игры ν = α = β . Оптимальными для игроков будут соот­ветственно максиминная и минимаксная стратегии, а чистой ценой игры – седловой элемент платежной матрицы. Если игра седловой точки не имеет, то решение игры следует найти в смешанных стратегиях.

Обозначим через р₁, ..., р_m вероятности, с которыми игрок А использует в ходе игры свои чистые стратегии A₁, ..., А_m. Для вероятностей р_i выполняются условия:

 

. (7.3)

Упорядоченное множество , элементы кото­рого удовлетворяют условиям (7.3), полностью определяет ха­рактер игры игрока А и называется его смешанной стратеги­ей.

Аналогично упорядоченное множество , эле­менты которого удовлетворяют соотношениям

, (7.4)

 

является смешанной стратегией игрока В.

Итак, пусть игроки А и В применяют смешанные стратегии р и q. Это означает, что игрок А использует стратегию A_i с вероятностью p_i, а игрок В – стратегию В_j с вероятностью q_j. При использовании смешанных стратегий игра приобрета­ет случайный характер, случайной становится и величина вы­игрыша игрока А (проигрыша игрока В). В связи с этим мож­но вести речь лишь о средней величине (математическом ожи­дании) выигрыша (проигрыша). Эта величина явля­ется функцией от смешанных стратегий р и q и определяется по формуле

. (7.5)

 

Функция (7.5) называется платежной функцией игры с матрицей.

Нижней ценой игры будем называть число α , определяемое по формуле , a верхней ценой игры – число β , определяемое по формуле

. (7.6)

 

Оптимальными являются смешанные стратегии р* и q* игроков А и В, удовлетворяющие равенству

 

= = . (7.7)

 

Величину , полученную по формуле (7.7), называют ценой игры v.

Пример решения задачи

 

Постановка задачи. На каждой из двух торговых баз ассортиментный ми­нимум составляет одинаковый набор товаров из четырех видов. Магазины, обо­значим их А и В, конкурируют между собой. Один и тот же вид товара в обоих магазинах продается по одной и той же цене. Однако товар, поставляемый в ма­газин В, более высокого качества. Если магазин А завезет с базы товар, отлич­ный от товара, завезенного в магазин В, то товар будет пользоваться спросом, и магазин А от его реализации получит прибыль с, денежных единиц. Если же в магазины А и В завезены товары одинакового вида, то товар в магазине А спро­сом пользоваться не будет, поскольку такой же товар, по такой же цене, но бо­лее высокого качества, можно купить в магазине В, и потому магазин А понесет убытки по хранению и, возможно, порче товара в размере d, денежных единиц.

Требуется формализовать конфликтную ситуацию, построить матрицу иг­ры и дать рекомендации по выбору оптимальной смешанной стратегии магази­на А при следующих числовых данных:

 

с1	с2	с3	с4	d1	d2	d3	d4

 

Решение задачи

 

1 Представим данную ситуацию в виде матричной игры. У руководства ма­газина А четыре стратегии: А_i - продавать товар i-го вида (i = 1, 4). Аналогично у руководства магазина В стратегии В_j - продавать товар j-го вида (j = 1, 4).

Построим платежную матрицу данной игры на рабочем листе MS Excel в ячейках А1: Е5 (таблица 7.1).

 

Таблица 7.1 – Платежная матрица

 

	А	В	С	D	E
		В1	В2	В3	В4
	А1	-13
	А2		-12
	А3			-20
	А4				-7

 

Определим, имеет ли игра оптимальное решение в чистых стратегиях, т.е. проверим наличие седловой точки. Чтобы рассчитать верхнюю и нижнюю чис­тые цены игры, в столбец а_i (F1: F5) вводим функцию МИН, а в строку β _j (A6: E6) - функцию МАКС, получаем матрицу следующего вида (таблица 7.2).

 

Таблица 7.2 – Определение седловой точки

 

	А	В	С	D	E	F
		В1	В2	В3	В4	ai
	А1	-13				-13
	А2		-12			-12
	А3			-20		-20
	А4				-7	-7
	β j

 

Далее аналогично вычисляем:

; .

Так как а β , то игра не имеет решения в чистых стратегиях.

2 Решение игры в смешанных стратегиях

 

2.1 Преобразование платежной матрицы. Чтобы свести игру к задаче ли­нейного программирования, увеличим все элементы платежной матрицы на 20 (таблица 7.3).

 

 

Таблица 7.3 – Преобразование платежной матрицы

 

	А	В	С	D	E
		В1	В2	В3	В4
	А1
	А2
	А3
	А4

 

2.2 Построение математической модели.

Задача линейного программирования для игрока А:

 

где , p_j – вероятность, с которой игрок А применяет свою j-ю чистую стратегию, v - цена игры.

 

2.3. Технология решения задачи средствами Excel. Строим следующую таблицу (таблица 7.4).

 

Таблица 7.4 – Решение задачи в Excel

	А	В	С	D	E	F	G	H
	Имя	Переменные
	Х1	Х2	Х3	Х4
	Значение	0, 0129	0, 0168	0, 009
	Нижняя граница
	Верхняя граница
						ЦФ	Направление ЦФ
	Коэффициент ЦФ					0, 039	min
		Ограничения
	Вид					левая часть	знак	правая часть
							>
							>
							>
						1, 387	>

 

Решив данную задачу средствами Excel, получаем:

х₁ = 0, 0129; х₂ = 0, 0168; х₃ = 0, 009; f_min = 0, 039.

 

Для определения смешанной стратегии, воспользуемся формулами:

 

.

 

Отсюда смешанная стратегия: р = (0, 333; 0, 434; 0, 233; 0), N =25, 79.

 

3 Анализ полученных результатов

Итак, оптимальной стратегией магазина А будет продажа товаров в сле­дующей пропорции: 33, 3 % товара 1-го вида; 43, 4 % товара 2-го вида; 23, 3 % товара 3-го вида. Средняя прибыль составит 25, 79 ден. ед.

 

⇐ Предыдущая3456789101112Следующая ⇒

Поделиться: