Формальное описание антагонистической игры

Антагонистической игрой называется тройка G=< X, Y, H> , где X − множество стратегий первого игрока, Y − множество стратегий второго игрока, (x, y) − ситуация игры, H=H(x, y) – функция выигрыша, где xєX, yєY.

Функция выигрыша для каждой ситуации показывает выигрыш 1-го игрока и проигрыш 2-го (или наоборот). Эта игра называется игрой с нулевой суммой.

Процесс разыгрывания состоит в следующем: 1-й игрок независимо от 2-го выбирает стратегию x, а 2-й игрок независимо от 1-го выбирает стратегию y.

Образуется ситуация игры (x, y). При этом 1-й игрок получит выигрыш, равный H(x, y), а второй – проигрыш, равный H(x, y). Целью первого игрока является максимизация своего выигрыша, а целью второго – минимизация выигрыша противника.

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

Пусть X, Y − конечные множества чистых стратегий игроков: X ={x₁, x₂, ..., x_m}, Y ={y₁, y₂, ..., y_n}, тогда H=||h_ij|| − матрица порядка mxn, где 1-й индекс указывает на выбранную 1-м игроком стратегию, а 2-й индекс указывает на выбранную 2-м игроком и h_ij − платеж второго игрока первому.

Эта матрица называется платежной матрицей или матрицей потерь.

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

Редуцировать игру значит сократить в ней число дублирующих и заведомо невыгодных стратегий.

Если, например, стратегия x₁ доминирует над стратегией x₂, то x₂ вычеркиваем.

Игры с седловой точкой

Максимином или нижней ценой игры называется элемент платежной матрицы, равной максимуму из минимумов по строкам матрицы:

Минимаксом или верхней ценой игры называется такой элемент матрицы, который равен минимуму из максимумов по столбцам матрицы:

Оптимальная стратегия 1-го игрока − это максиминная стратегия. Действительно, он независимо от поведения противника гарантирует себе выигрыш не менее, чем максимин, т.е. не менее нижней цены игры.

Оптимальная стратегия 2-го игрока − это минимаксная стратегия. Он гарантирует себе, что проиграет не более верхней цены игры.

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

Седловая точка − это элемент платежной матрицы, равный одновременно максимину и минимаксу. Значение этого элемента − чистая цена игры.

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

Цена игры − платеж, соответствующий паре оптимальных смешанных стратегий:

Рассмотрим пример матричной игры, для которой цена игры существует. Пусть для G=< X, Y, H> X={1, 2, 3}, Y={1, 2, 3}. Платежная матрица с вычисленными максимумами по столбцам и минимумами по строкам:

Тогда  i₀ = 2,  j₀ = 1 и .

Максимин и минимакс равны, седловая точка имеет координаты (2, 1), значение цены игры равно 2.

Рассмотрим пример матричной игры, в которой цены игры в чистых стратегиях нет .

 Пусть для G = < X, Y, H > X={1, 2}, Y={1, 2}. Платежная матрица имеет вид:

Тогда  i₀ = 2,  j₀ = 2. Значит, .

Если игра не имеет седловой точки, то устойчивое решение лежит в области смешанных стратегий, то есть существует пара оптимальных смешанных стратегий.

 

Смешанное расширение игры

Смешанным расширением игры G называется игра , где S , S  − множества смешанных стратегий соответственно 1-го и 2-го игроков, а М _H − математическое ожидание выигрыша.

Смешанной стратегией игрока называется вектор вероятностей выбора игроком чистых стратегий. Так как Х и Y − конечные множества, то их элементы можно пронумеровать.

Смешанной стратегией 1-го игрока назовем распределение на множестве Х. Тогда смешанная стратегия 1-го игрока имеет вид:

 

x1	x2	…	xm
x1	x2	…	xm

 

где x₁, x₂, ..., x_m − чистые стратегии, x₁, x₂, ..., x_m – вероятности их выбора. Множество смешанных стратегий 1-го игрока будем обозначать  Аналогично, смешанной стратегией 2-го игрока назовем распределение на множестве Y:

 

y 1	y 2	…	yn
h1	h2	…	hn

 

где y₁, y₂, ..., y_n − чистые стратегии 2-го игрока, h₁, h₂, ..., h_n – вероятности их выбора.

Множество смешанных стратегий 2-го игрока:

Пусть 1-й игрок выбирает свою стратегию x_j с вероятностью x_i, а второй игрок − свою стратегию y_j с вероятностью h_j. Тогда создается ситуация (x_i, y_j) с вероятностью  (игроки выбирают свои стратегии независимо). При этом 1-й игрок получит выигрыш h_ij с вероятностью

Мера выигрыша − математическое ожидание

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

Первый способ решения игры 2 x 2. Пусть дана платежная матрица H:

Матрица H не имеет седловой точки, так как

Пусть 1-й игрок выберет стратегию x₁ с вероятностью x₁, а стратегию x₂ с вероятностью x₂, (x₁+x₂=1); 2-й игрок выберет стратегию y₁с вероятностью h₁, а стратегию y₂ с вероятностью h₂, (h₁+h₂=1). Выбор игроками стратегий – независимые случайные события. Вычислим математическое ожидание выигрыша

 =

=1x₁h₁ + 3x₁ (1 - h₁) + 4 (1 - x₁) h₁ + 2 (1 - x₁)(1 - h₁) =

=-4x₁h₁ + x₁ + 2h₁ + 2 = = - 4 (x₁- 0, 5)(h₁ – 0, 25) + 2, 5.

 

Проведем анализ игры. Если 1-й игрок выберет свою первую стратегию с вероятностью x₁=0, 5, то при любых действиях 2-го игрока М _H =2, 5. Если 2-й игрок выберет свою первую стратегию с вероятностью h₁ = 0, 25, то М _H=2, 5, независимо от действий первого игрока.

Следовательно, оптимальными смешанными стратегиями игроков в этой игре будут для первого игрокаx₀=(0, 5; 0, 5), для второго игрокаh₀ =(0, 25; 0, 75), а цена игры М _H =2, 5.

Второй способ решения игры 2 x 2. Пусть платежная матрица  не имеет седловой точки. Найдем решение игры в смешанных стратегиях, т.е. найдем (x₀, h₀, М _H), где x₀=(x₁, x₂), h₀=(h₁, h₂), V = М _H  – цена игры. По теореме об активных стратегиях [10] имеем:

Из полученной системы уравнений найдем x₁, x₂, V:

По теореме об активных стратегиях имеем:

Из полученной системы уравнений найдем h₁, h₂:

Графические способы решения матричных игр мы не рассматриваем в данном пособии, они представлены достаточно подробно в [10].

Если матричная игра имеет большую размерность, то ее, как правило, невозможно решить ни графическим методом, ни аналитическим способом. В таком случае имеет смысл использовать метод Брауна-Робинсона, который также называют методом фиктивного разыгрывания или итеративным процессом поиска частного решения в смешанных стратегиях. Данный метод является приблизительным и способен дать решение игры для обоих игроков с определенной точностью – той, которую мы заранее зададим. Разберём этот метод более подробно.

 

Метод Брауна-Робинсона

Задана матричная игра:

 − платежная матрица;

 − i-тая стратегия первого игрока на k-той итерации;

 − j-тая стратегия второго игрока на k-той итерации.

Требуется найти:

− оптимальные стратегии игроков, седловую точку, цену игры (или верхнюю, нижнюю цены игры, если седловой точки нет);

− смешанные стратегии игроков и диапазон, в который попадает значение цены игры.

Сравните результаты при игре в чистых и смешанных стратегиях.

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

На каждой итерации определяется по одному элементу каждой из них.

1. На первой итерации стратегии выбираются произвольно: пусть i₁ =1 и j₁=1,

2. На последующих итерациях применяются такие рекуррентные соотношения:

где j_k – тот номер j, на котором величина  достигла максимума.

Находим наименьшее значение g_i^k , которое определяет номер i_k+1 для следующей итерации:

Далее вычисляем  где i_k – тот номер i, на котором величина  достигла минимума.

Находим наибольшее значение h_j^k , которое определяет номер j_{k +1} для следующей итерации:

 

На каждой итерации (k – номер итерации) заполняется строка из табл. 4.1:

Таблица 4.1

Результаты расчетов в методе Брауна-Робинсона

k

jk

…

Mk

vk

…

ik

 

Замечание. Для получения решения с достаточной точностью требуется проделать большое число итераций. На последней итерации значение нижней цены игры будет близко к M_k, а верхней цены игры – к V_k. Смешанные стратегии игроков – векторы вероятностей выбора игроками чистых стратегий.

Пример. Имеется матрица:

На первой итерации (k=1) i₁=1, j₁=1. Тогда

 = а₁₁=6;  = а₂₁=4;  = а₃₁=5;

 = а₁₁=6;  = а₁₂=2; = а₁₃=5;

M ₁ = min{6; 4; 5}=4; V ₁ = max{6; 2; 5}=6.

На второй итерации (k=2) i₂=2, нам уже известно, т.к. величина М₁= , j₂ нам тоже известно, т.к. V₁= .

Остальные элементы получаем следующим образом:

= +а₁₁=12; = +а₂₁=8; =10;

= +а₂₁=10; = +а₂₂=5; =12;

M ₂ = min{12; 8; 10}/2=4; V ₂ = max{10; 5; 12}/2=6.

Следовательно, i ₃=2, j ₃=3.

На третьей итерации (k=3) i ₃=2, нам уже известно, т.к. величина М₂= /2, j ₃=3 нам тоже известно, т.к. V ₂= /2.

= +а₁₃=12+5=17; = +а₂₃=8+7=15; = +а₃₃ = 10+6=16;

= +а₂₁=10+4=14; = +а₂₂=5+3 =8; = +а₂₃=12+7=19;

M ₃ = min{17; 15; 16}/3=5; V ₃ = max{14; 8; 19}/3=19/3.

Следовательно, i ₄=2, j ₄=3 и т.д.

 

Игры с природой

Рассмотрим задачу принятия решений в условиях стохастической неопределенности, когда проведение экспериментов невозможно. Учет неопределенных факторы, закон распределения которых неизвестен, базируется на формировании специальных критериев, на основе которых принимаются решения – критерии Вальда, Сэвиджа , Гурвица и Байеса-Лапласа .

Модель проблемной ситуации имеет вид:

< U, V, W>,

где U={u_i} – множество стратегий (решений), ;

V={v_j} – множество состояний природы, ;

W=|w_ij| – матрица решений, элемент матрицы w_ij содержит доходы (или потери) от выбора стратегии u_i при реализации состояния природы v_j.

Требуется найти оптимальную стратегию.

 

4.2.1. Критерий Вальда

В соответствии с критериемВальда в качестве оптимальной выбирается стратегия, гарантирующая выигрыш не меньший, чем «нижняя цена игры с природой»:

.

Правило выбора решения в соответствии с критерием Вальда можно интерпретировать следующим образом: матрица решений W дополняется еще одним столбцом из наименьших результатов w_ir каждой строки. Выбрать надлежит тот вариант, в строке которого стоит наибольшее значение w_ir этого столбца.

Выбранное таким образом решение полностью исключает риск. Это означает, что принимающий решение не может столкнуться с худшим результатом, чем тот, на который он ориентируется. Какие бы условия v_j не встретились, соответствующий результат не может оказаться ниже P. Это свойство заставляет считать критерий Вальда одним из фундаментальных. Поэтому в технических задачах он применяется как сознательно, так и неосознанно. Однако в практических ситуациях излишний пессимизм этого критерия может оказаться очень невыгодным.

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

­ о вероятности появления состояния природы v_j ничего не известно;

­ с появлением состояния v_j необходимо считаться;

­ реализуется лишь малое количество решений;

­ не допускается никакой риск.

 

Критерий Байеса-Лапласа

Критерий Байеса-Лапласа в отличие от критерия Вальда, учитывает каждое из возможных следствий всех вариантов решений:

.

Соответствующее правило выбора можно интерпретировать следующим образом: матрица решений W дополняется еще одним столбцом, содержащим математическое ожидание значений каждой из строк. Выбирается тот вариант, в строках которого стоит наибольшее значение w_ir этого столбца.

Критерий Байеса-Лапласа предъявляет к ситуации, в которой принимается решение, следующие требования:

­ вероятность появления состояния v_j известна и не зависит от времени;

­ принятое решение теоретически допускает бесконечно большое количество реализаций;

­ допускается некоторый риск при малых числах реализаций.

 

Критерий Сэвиджа

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

Здесь величину P можно трактовать как максимальный дополнительный выигрыш, который достигается, если в состоянии v_j вместо варианта u_i выбрать другой, оптимальный для этого внешнего состояния, вариант.

Соответствующее критерию Сэвиджа правило выбора следующее: каждый элемент матрицы решений W вычитается из наибольшего результата W_j соответствующего столбца, W_j – максимальный элемент j-го столбца. Разности образуют матрицу остатков (рисков). Эта матрица пополняется столбцом наибольших разностей w_ir. Выбирается тот вариант, в строке которого стоит наименьшее значение.

 

Критерий Гурвица

Согласно критерию Гурвицавыбирается такая стратегия, которая занимает некоторое промежуточное положение между крайним пессимизмом и оптимизмом:

,

где r – коэффициент пессимизма, выбираемый в интервале [0, 1].

Правило выбора согласно этому критерию следующее: матрица решений W_ij дополняется столбцом, содержащим средние взвешенные наименьшего и наибольшего результатов для каждой строки. Выбирается тот вариант, в строках которого стоят наибольшие элементы w_r этого столбца.

При r=1 критерий Гурвица превращается в критерий Вальда (пессимиста), а при r=0 – в критерий азартного игрока. Отсюда ясно, какое значение имеет весовой множитель r. В технических приложениях правильно выбрать этот множитель бывает так же трудно, как правильно выбрать критерий. Поэтому чаоще всего весовой множитель r=0, 5 принимается в качестве средней точки зрения.

Критерий Гурвица предъявляет к ситуации, в которой принимается решение, следующие требования:

­ о вероятности появления состояния природы v_j ничего неизвестно;

­ с появлением состояния v_j необходимо считаться;

­ реализуется лишь малое количество решений;

­ допускается некоторый риск.

Общие рекомендации по выбору того или иного критерия дать затруднительно. Однако отметим следующее: если в отдельных ситуациях не допустим даже минимальный риск, то следует применять критерий Вальда; если определенный риск вполне приемлем, то можно воспользоваться критерием Сэвиджа. Можно рекомендовать одновременно применять поочередно различные критерии. После этого среди нескольких вариантов, отобранных таким образом в качестве оптимальных, приходится волевым решением выделять некоторое окончательное решение.

Такой подход позволяет, во-первых, лучше проникнуть во все внутренние связи проблемы принятия решений и, во-вторых, ослабляет влияние субъективного фактора. Кроме того, в области технических задач различные критерии часто приводят к одному результату.

 

Пример

На предприятии решается вопрос о создании ремонтной бригады. Основываясь на применении критериев Вальда, Лапласа, Сэвиджа и Гурвица, определить наиболее целесообразное число членов бригады. Исходные данные сведены в табл. 4.2, в ячейках которой занесены доходы при разных вариантах (стратегиях), x – стратегия – число членов бригады; R – состояние природы – количество станков, которые могут потребовать ремонта.

Таблица 4.2

Исходные данные

x\R	40	30	20	10
5	50	100	180	250
4	80	70	80	230
3	210	180	120	210
2	300	220	190	150

 

1. Критерий Вальда. Справа дописывается столбец минимумов по строкам.

 

x\R	40	30	20	10
5	50	100	180	250	50
4	80	70	80	230	70
3	210	180	120	210	120
2	300	220	190	150	150

Тогда . Таким образом, при данных условиях рациональным решением будет x=2.

2. Критерий Лапласа. Рассмотрим ситуацию, когда все состояния природы равновероятны. В этом случае критерий примет вид:

.

x\R	40	30	20	10
5	50	100	180	250	145
4	80	70	80	230	115
3	210	180	120	210	180
2	300	220	190	150	215

Тогда . Таким образом, наилучшим решением будет x=2.

3. Критерий Сэвиджа. Построим матрицу рисков. Ее элементы определяются по формуле , где .

x\R	40	30	20	10
5	300-50=250	120	10	0	250
4	220	150	110	20	220
3	90	40	70	40	90
2	0	110	100	100	100
	300	220	190	250

Тогда . Оптимальная стратегия согласно критерию Сэвиджа x=3.

4. Критерий Гурвица. В отличие от примененных выше «жестких» критериев, критерий Гурвица является «гибким», так как позволяет варьировать «степень оптимизма-пессимизма». Таким образом, этот критерий устанавливает баланс между случаями крайнего оптимизма или пессимизма, путем введения коэффициента веса r.

Применим данный критерий к нашим исходным данным, полагая r =0.5.

x\R	40	30	20	10			P
5	50	100	180	250	50	250	150
4	80	70	80	230	70	230	150
3	210	180	120	210	120	210	165
2	300	220	190	150	150	300	225

Таким образом, . Оптимальная стратегия x=2.

Вопросы и задания

1. Дайте определение задачи принятия решений в условиях неопределенности.

2. В чем суть различий между фиксированными стохастическими и неопределенными факторами?

3. В чем суть различий между неопределенными факторами стохастической и нестохастической природы?

4. Объясните термин «природные неопределенности».

5. Какое действие и почему снижает размерность платежной матрицы?

6. Всегда ли maxmin находится как максимум из минимумов в строках матрицы потерь?

7. Что является ценой игры в смешанных стратегиях?

 

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

Поделиться: