Рассмотрим парную конечную игру. Пусть игрок А располагает личными стратегиями: А1;А2,…Аm. Аналогично игрок В: В1,В2,…,Вn.. Обозначим «аi» - выигрыш игрока А, а проигрыш игрока В «-аi». Матрица {аij} называется платежной матрицей.
Аi Вi | B1 | B2 | ... | Bn |
A1 | a11 | a12 | … | a1n |
A2 | a21 | a22 | … | |
-- | --- | --- | --- | --- |
Am | am1 | am2 | … | amn |
Выбирая стратегию, игрок А должен помнить, что игрок В стремится «навредить» ему, а следовательно, ответит на нее такой стратегией, для которой выигрыш игрока А будет наименьшим. Нижняя цена игры (максимин) α гарантированный выигрыш игрока А при любой стратегии игрока В:
. (8)
Игрок В заинтересован в том, чтобы уменьшить выигрыш игрока А. Выбирая стратегию Вj, он учитывает максимально возможный при этом выигрыш для А. Верхняя цена игры (минимакс) β – это гарантированный проигрыш игрока В:
. (9)
Если α = β = V, то общее значение верхней и нижней цены игры совпадает, и V называется чистой ценой игры.
Минимаксные стратегии, соответствующие цене игры, являются оптимальными стратегиями. Элемент aij , являющийся одновременно и наибольшим в своем столбце и наименьшим в строке, называют седловой точкой.
|
|
8 | |||
Пример 26 Имеет ли игра седловую точку, если платежная матрица Р =
Решение.
Ai Вi | B1 | B2 | B3 | B4 | min α i |
A1 | |||||
A2 | |||||
A3 | |||||
A4 | |||||
max β j | 6 6 |
α = β = 6. Чистая цена игры V = 6. Оптимальная стратегия (А2, В2).
Если игра не имеет седловой точки, то применение чистых стратегией не дает оптимальное решение.
Смешанной стратегией SА игрока А называется применение чистых стратегией А1, А2, …, Аm с вероятностями р1, р2, …, рm, причем . Смешанная стратегия записывается в виде:
SA = (p1, p2, …, pm). Аналогично, SB = (q1, q2, …, qn).
Оптимальное решение игры – это пара оптимальной стратегией SA*, SB*. Выигрыш, соответствующий оптимальному решению, называется ценой игры V.
Если чистая стратегия входит в оптимальную смешанную стратегию с не нулевой вероятностью, то она называется активной.
Теорема Неймана: каждая конечная игра имеет, по крайней мере, одно оптимальное решение, возможно, среди смешанных стратегий.
Теорема: если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш остается неизменным и равным цене игры V, если второй игрок не выходит за пределы своих активных стратегий.
Для оптимальной стратегии SA средний выигрыш не меньше цены V, то есть:
а11р1 + а21р2 + … + аm1рm ≥ V
…
a1np1 + a2np2 + …+ amnpm ≥ V
p1 + p2 + … + pm = 1.
Разделим каждое уравнение на V и обозначим хi = pi/v, тогда
|
|
а11х1 + а21х2 + … + аm1xm ≥ 1
…
a1nx1 + a2nx2 + … + amnxm ≥ 1
х1 + х2 + … + хm = 1/V
Цель игрока А максимизировать свой гарантированный выигрыш, т.е. цену игры. Максимизация цены игры V будет эквивалентна минимизации величины 1/V. Следовательно, необходимо определить значение переменных хi ≥ 0 так, чтобы они удовлетворяет линейным ограничениям и при этом линейная функция:
F = х1 + х2 + … + хm à min.
Получим задачу ЛП, решая которую получим оптимальное решение и оптимальную стратегию SA*:
V = 1/Fmin; рi = хi/v
Аналогично получаем стратегию SB:
a11q1 + a12q2 + … + a1nqn ≤ V
…
am1q1 + am2q2 + … + amnqn ≤ V
q1 + q2 + … + qn = 1.
Разделим каждое уравнение на V и обозначим уj = qj/v, тогда
a11y1 + a12y2 + … + a1nyn ≤ 1
….
am1y1 + am2y2 + … + amnyn ≤ 1
y1 + y2 + … + yn = 1/V
Z = y1 + y2 + … + yn à max
Получили взаимно-двойственные задачи.
2.3. Принятие решений в условиях неопределенности
(игры с природой)
В условиях неопределенности возникают в ситуации, когда известны все последствия всевозможных решений, но не известны их вероятности, т.е. выбор любой альтернативы может привести к одному из нескольких исходов и отсутствует даже стохастическая зависимость между альтернативами и исходами. Задачи принятия решений в условиях неопределенности моделируется игрой с природой и ее решение находится по соответствующим критериях.
Множество состояний природы обозначим через П, отдельное состояние Пj (j = 1, n). Множество решений (стратегий) статистика обозначим через А, отдельное решение – Аi (i = 1, m).
Во взаимоотношениях с природой статистик может использовать любые стратегии А1…, Аm в зависимости от состояний Пj природы. Необходимо отыскать оптимальное решение, которое и будет его оптимальной стратегией. При этом он может пользоваться как чистыми, так и смешанными стратегиями. Пусть аij - эффективность комбинации (Аi, Пj), тогда получим платежную матрицу.
Матрицей риска называется матрица, элементы которой (rij) равны разности между максимально возможным выигрышем и тем выигрышем, которой статистик получит в тех же условиях Пj, применяя стратегию Аi, т.е.
rij = βj - aij, где βj = max aij. (10)
Оптимальную стратегию можно определить, используя ряд критериев:
а) при частичной неопределенности, если известна вероятность появления состояние Пj.
Критерий Байеса. За оптимальную стратегию принимается чистая стратегия Аi, при которой максимизируется средний выигрыш:
а* = max аi*, где (i = 1, m). (11)
или за оптимальную стратегию принимается чистая стратегия Аi, при который минимизируется средний риск, т.е
r* = min ri*, где (i=1, m). (12)
Критерий Лапласа. В случае, когда вероятности состояний природы правдоподобны, для их оценки используют принцип недостаточного основания, согласно которому все состояния природы равновероятны: q1 = q2 = … = qn = 1/n.
б) при полной неопределенности.
Критерий максимакса (критерий крайнего оптимизма).Наилучшим признается решение, при котором достигается максимальный выигрыш, равный
α = max max aij. (13)
i j
Следует отметить, что ситуации, требующие применения такого критерия, в экономике в общем нередки, и пользуются им не только безоглядные оптимисты, но и игроки, поставленные в безвыходное положение, когда они вынуждены руководствоваться принципом «или пан, или пропал».
Критерий Вальда (критерий крайнего пессимизма).
С позиций данного критерия природа рассматривается как агрессивно настроенный и сознательно действующий противник типа тех, которые противодействуют в стратегических играх. За оптимальную стратегию принимает чистая стратегия, которая в наихудших условиях гарантирует наибольший выигрыш, т.е.
α = max min aij. (14)
i j
Критерий Сэвиджа. За оптимальную стратегию принимается стратегия, при которой величина наибольшего риска наименьша в наихудших условиях:
|
|
r = min max rij. (15)
i j
Критерий Гурвица. Этот критерий при выборе решения рекомендует руководствоваться некоторым средним результатом, характеризующим состояние между крайним пессимизмом и безудержным оптимизмом. Согласно этому критерию, за оптимальную стратегию принимается та, при которой
max (λ min aij + (1 - λ) max aij), где 0 ≤ λ ≤ 1. (16)
j j
При отсутствии ярко выраженных склонностей целесообразно положить λ = 0.5.
Обобщенный критерий Гурвица. Предположим для определенности, что игра с природой задана матрицей выигрышей А. Переставим выигрыши ai1, ai2, …, ain при каждой стратегии Ai, т.е. элементы каждой строки матрицы А, расположив их в неубывающем порядке, и обозначим получившуюся матрицу B = (bij). Пусть числа λ1, λ2, …, λn удовлетворяют условию λj ≥ 0, Σλj = 1.
Обобщенным показателем эффективности стратегии Ai назовем число Gi(λ1, λ2, …, λn) = Σλj*bij. Обобщенным критерием Гурвица относительно выигрышей с коэффициентами λj называется критерий, по которому оптимальной считается стратегия с максимальным показателем эффективности: A* = Arg max { Gi(λ1, λ2, …, λn).
Числа и назовем показателями пессимизма и оптимизма соответственно. Коэффициенты λj выбираются из субъективных соображений следующим образом: чем опаснее ситуация, тем ближе к единице должен быть коэффициент пессимизма; в безопасной ситуации наоборот.
Формальный способ подсчета этих коэффициентов. Пусть
bj = Σ bij сумма всех выигрышей, стоящих в j -ом столбце матрицы В, среднее значение выигрышей, стоящих в j -м столбце матрицы В, сумма всех элементов матрицы В.
В случае, когда принимающий решение оценивает для себя ситуацию как опасную, он, естественно, хочет подстраховаться и потому при выборе стратегии ведет себя достаточно осторожно, проявляя больше пессимизма, чем оптимизма, поэтому показатель пессимизма должен быть больше показателя оптимизма. В этом случае показатель оптимизма можно найти по формуле: а коэффициенты λ1, λ2, …, λn − в соответствии с принципом невозрастания средних выигрышей по формуле Если же принимающий решение считает ситуацию безопасной, то показатель оптимизма должен быть больше показателя пессимизма. Это можно выразить выбором показателя оптимизма и неубывающей последовательности коэффициентов λ1, λ2, …, λn по принципу неубывания средних выигрышей:
|
|
Пример 27. В соответствии со спросом на некоторую продукцию в городе планируется построить предприятия по производству этой продукции. Спрос на продукцию в течение года выражается величинами 10, 20, 30, 40 тыс. шт.
Планирующий орган предприятия может принять одно из решений: построить предприятие, которое могло бы удовлетворить спрос потребителей. Работа такого предприятия показывает, что предприятие терпит издержки в количестве 5 ден. ед. от не реализации единицы продукции, а доход от реализации составляет 15 ден. ед. Требуется:
1) придать описанной ситуации игровую схему, установить характер игры и выявить ее участников;
2) вычислить элементы платежной матрицы и составить ее;
3) дать обоснованные рекомендации планирующему органу на строительство предприятия, которое могло бы обеспечить спрос потребителей на q продукцию.
При изучении аналоговых предприятий планирующий орган располагает некоторой дополнительной информацией, снижающей неопределенность ситуации:
а) известны вероятности спроса на данную продукцию по кварталам года 0,3; 0,2; 0,4; 0,1;
б) спрос на продукцию в каждом равновероятен;
в) о вероятностях спроса на указанную продукцию по кварталам ничего определенно сказать нельзя.
Решение. В качестве статиста выступает планирующий орган, который может принять одно из следующих решений:
А1- построить предприятие, способное удовлетворит спрос в 10 тыс. ед.; А2 - спрос в 20 тыс. ед.; А3 - спрос в 30 тыс.ед.; А4 - спрос в 40 тыс.ед.
Природой выступает совокупность объективных внешних условий, в которых формулируется спрос потребителей: П1 - спрос равен 10 тыс. ед.; П2 – 20 тыс. ед; П3 – 30 тыс. ед.; П4 - 40 тыс. ед.
Рассчитаем элементы платежной матрицы:
(А1, П1): статист планирует построить предприятие N = 10 тыс. ед, что соответствует состоянию спроса в 10 тыс. ед. Доход:
а11 = 10*15 = 150 тыс. ед.
(А1, П2): N = 10, P = 20 а12 = 10*15 = 150.
(А1, П3): N = 10, P = 30 => a13 = 10*15 = 150;
(А1, П4): N = 10, P = 40 => a14 = 10*15 = 150;
(А2, П4): N = 20, P = 10. Т.к. спрос удовлетворяется лишь на 10 тыс. ед., то предприятие терпит убытки. Доход составит
a21 = 10*15 - 10*5 = 100;
(А2, П2): N = 20, P = 20 => a22 = 20*15 = 300;
(А2, П3): N = 20, P = 30 => a23 = 20*15 = 300;
(А2, П4): N = 20, P = 40 => a24 = 20*15 = 300;
(А3, П1): N = 30, P = 10 => a31 = 10*15 - 20*5 = 50;
(А3, П2): N = 30, P = 20 => a32 = 20*15 - 10*55 = 250;
(А3, П3): N = 30, P = 30 => a33 = 30*15 = 450;
(А3, П4): N = 30, P = 40 => a34 = 30*15 = 450;
(А4, П1): N = 40, P = 10 => a41 = 10*15 - 30*5 = 0;
(А4, П2): N = 40, P = 20 => a42 = 20*15 - 20*5 = 200;
(А4, П3): N = 40, P = 30 => a43 = 30*15 - 10*5 = 400;
(А4, П4): N = 40, P = 40 => a44 = 40*15 = 600.
Получим платежную матрицу.
П1 | П2 | П3 | П4 | |
A1 | ||||
A2 | ||||
A3 | ||||
A4 |
Вычислим средний выигрыш, используя различные критерии в условиях частичной неопределенности.
а) Критерий Байеса. Для подсчета столбца ai в «Мастере функций» выбираем команду СУММПРОИЗ и вводим массив 1 – строка q; массив 2 – строка Аi. Оптимальная стратегия А3.
П1 | П2 | П3 | П4 | ||
A1 | |||||
A2 | |||||
A3 | |||||
A4 | |||||
q | 0,3 | 0,2 | 0,4 | 0,1 | мах - 310 |
б) Критерий Лапласа: q1 = q2 = q3 = q4 = ¼. Оптимальная стратегия А3 .
П1 | П2 | П3 | П4 | ||
A1 | |||||
A2 | |||||
A3 | |||||
A4 | |||||
q | 0,25 | 0,25 | 0,25 | 0,25 | мах - 325 |
в) Критерий Сэвиджа. Построим матрицу рисков: rij = βj - aij, где βj = max aij: r11 = β1 - a11, β1 = max ai1 = 150 => r11 = 0;
r12 = β2 - a12, β2 = max ai2 = 300 => r12 = 150;
r13 =450 - 300; r14 = 600 – 150 = 450;
r21 = 150 – 100 = 50; r22 = 300 – 300 = 0; r23 = 450 – 300 = 150;
r24 = 600 – 300 = 300; r31 = 150 – 50 = 100; r32 = 300 – 250 = 50;
r33 = 0; r34 = 600 – 450 = 150; r41 = 150 – 0 = 150;
r42 = 300 – 200 = 100; r43 = 450 – 400 = 50; r44 = 0.
Оптимальная стратегия A3 и A4.
мах | |||||
R = | |||||
мин |
д) Критерий Байеса для матрицы риска. Оптимальная стратегия A3.
ai | |||||
R= | |||||
q | 0,3 | 0,2 | 0,4 | 0,1 | Мин - 45 |
е) Критерий Лапласа: q1 = q2 = q3 = q4 = ¼. Оптимальная стратегия A3.
ai | |||||
237,5 | |||||
R= | 137,5 | ||||
62,5 | |||||
87,5 | |||||
q | 0,25 | 0,25 | 0,25 | 0,25 | 62,5 |
Вычислим средний выигрыш, используя различные критерии в условиях полной неопределенности.
а) Критерий оптимиста: α = maxmахaij. Оптимальная стратегия А4.
П1 | П2 | П3 | П4 | max | |
A1 | |||||
A2 | |||||
A3 | |||||
A4 | |||||
max |
б) Критерий Вальда: α = maxmin aij. Оптимальная стратегия А1.
П1 | П2 | П3 | П4 | min | |
A1 | |||||
A2 | |||||
A3 | |||||
A4 | |||||
max |
в) Критерий Гурвица λ = 0,5. Оптимальная стратегия А4.
П1 | П2 | П3 | П4 | (1 – λ)*max | λ*min | ∑ | |
A1 | |||||||
A2 | |||||||
A3 | |||||||
A4 | |||||||
max |
Ответ: принять стратегию А3, т.е. построить предприятие мощностью 30 т.ед., прибыль при этом составит:
а) если вероятность спроса известна, то 290 т.ед.;
б) при равновероятном условии 300 т.ед.
Пример 28. Инвестор может приобрести акции одной из трех компаний. Доходность акций зависит от состояния рынка ценных бумаг. Имеются статистические данные о доходности акций за четыре месяца
A = 8 4 6 20
7 7 7 7
6 12 8 10.
Инвестору необходимо принять решение, какой из компаний отдать предпочтение.
Решение. Воспользуемся обобщенным критерием Гурвица в опасной и безопасной ситуации. Составим матрицу
B = 4 6 8 20
7 7 7 7
6 8 10 12
В опасной ситуации выбираем коэффициенты λj по принципу невозрастания средних выигрышей:
; ; ; . Обобщенные показатели эффективности стратегий G 1(λ1, λ2, …, λn) ≈ 7,98; G 2(λ1, λ2, …, λn) = 7; G 3(λ1, λ2, …, λn) ≈ 8,31. Оптимальной в опасной ситуации является третья стратегия.
В безопасной ситуации коэффициенты λ j находим по принципу неубывания средних выигрышей: ; ; ; . Обобщенные показатели эффективности стратегий G 1(λ1, λ2, …, λn) ≈ 11,51; G 2(λ1, λ2, …, λn) = 7; G 3(λ1, λ2, …, λn) ≈ 9,69 и оптимальной в опасной ситуации является первая стратегия.
Таким образом, обобщенный критерий Гурвица различает опасную и безопасную ситуации.