 |
Игры без седловой точки в чистых стратегиях
|
|
|
|
Определение 12. Если платёжная матрица не имеет седлового элемента, то есть 
, то говорят, что игра не имеет решения в чистых стратегиях.
В этом случае для каждого игрока важно, чтобы соперник не угадал выбора его стратегии. В этом случае используются смешанные стратегии, при которых реализуется схема случайного выбора чистой стратегии.
Определение 13. Смешанной стратегией игрока А называется вероятностное распределение на множестве чистых стратегий этого игрока, задаваемого вектором 
, элементы которого удовлетворяют условиям: 1) 
(
), 2) 
, где 
() – вероятности, с которыми игрок А выбирает свои чистые стратегии 
.
Определение 14. Смешанной стратегией игрока В называется вероятностное распределение на множестве чистых стратегий этого игрока, задаваемого вектором 
, элементы которого удовлетворяют условиям:
1) 
(
),
2) 
, где 
() – вероятности, с которыми игрок В выбирает свои чистые стратегии 
.
При использовании смешанных стратегий игра приобретает случайный характер. Выбор каждой пары чистых стратегий 
является случайным событием и ввиду независимости случайных величин 
и 
реализуется с вероятностью 
. Величина 
выигрыша игрока А (проигрыша игрока В) становится случайной величиной. Эта величина является функцией смешанных стратегий и и определяется по формуле: 
.
Определение 15. Функцию 
называют функцией выигрыша или платёжной функцией.
Замечание 1. Формально функция представляет собой математическое ожидание выигрыша игрока А в ситуации в смешанных стратегиях и .
Замечание 2. На множестве смешанных стратегий игрок А, стремящийся достичь наибольшего из гарантированных выигрышей, выбирает вектор вероятностей так, чтобы получить максимум минимальных значений ожидаемых выигрышей, то есть решает задачу максимина математического ожидания 
, то есть поиск вектора 
такого, что
|
|
|
(6.1)
Соответственно, игрок В решает задачу минимакса математического ожидания – поиск вектора 
такого, что 
.
Определение 16. Смешанные стратегии 
и называются оптимальными, если они образуют седловую точку для платёжной функции 
, то есть удовлетворяют неравенству 
.
Определение 16’. Смешанные стратегии и называются оптимальными, если имеет место равенство:
.
Замечание. Определения 16 и 16’ равносильны.
Определение 17. Величину 
называют ценой игры.
Определение 18. Набор 
, состоящий из оптимальных смешанных стратегий и и цены игры 
, называется решением матричной игры.
Определение 19. Стратегия игрока А называется максиминной стратегией, стратегия называется минимаксной стратегией.
Возникают два ключевых вопроса:
1) какие матричные игры имеют решение в смешанных стратегиях?
2) как находить решение матричной игры, если он существует?
Теорема 2 (о минимаксе) (Дж. фон Нейман). Для матричной игры с любой платёжной матрицей 
1) величины 
, 
существуют и равны между собой: 
.
2) существует хотя бы одна ситуация в смешанных стратегиях 
, для которой выполняется соотношение:
.
Теорема 3 (о свойствах оптимальных стратегий). Пусть 
; 
– оптимальные смешанные стратегии и 
– цена игры. Тогда:
1) оптимальная смешанная стратегия игрока А может быть составлена только из тех чистых стратегий 
(), для которых 
;
2) оптимальная смешанная стратегия игрока В может быть составлена только из тех чистых стратегий 
(), для которых 
.
Следствие. Имеет место цепочка равенств:
Пример 2.5 [1]. Найти решение игры, имеющей платёжную матрицу 
.
Решение. Найдём седловую точку данной матрицы:
Таким образом, седловая точка данной матрицы отсутствует. Задача не имеет решения в чистых стратегиях. Решение игры нужно искать в
|
|
|
Пусть оптимальные стратегии игроков определяются, соответственно векторами вероятностей 
, 
, для которых 
, 
– условия нормировки. Функция выигрыша будет иметь вид:
.
Так как, согласно (6.1), требуется найти максимум функции выигрыша, то должно быть 
и, следовательно, должно выполняться равенство: 
. Система уравнений для определения оптимальных стратегий 
и 
имеет вид:
В ней содержится 3 уравнения и 5 неизвестных.
Для отыскания и воспользуемся следующим приёмом. Так как 
и 
, то имеем право записать: 
. Подставим полученное соотношение в первое уравнение системы, получим:
; или
.
Так как по теореме 3 значения 
и 
должны быть отличны от нуля (как оптимальные), то последнее равенство выполняется при произвольных положительных и только в том случае, когда
или 
.
Так как 
, то 
, следовательно,
.
Решая полученное уравнение, получаем 
, тогда 
. Таким образом, вероятности оптимальных стратегий первого игрока 
.
Аналогично для отыскания 
и 
из соотношений и имеем право записать: 
Подставим полученное соотношение в первое уравнение системы, получим:
или
.
Так как по теореме 3 значения и 
должны быть отличны от нуля (как оптимальные), то последнее равенство выполняется при произвольных положительных 
и 
только в том случае, когда
или 
.
Так как , то 
, и, следовательно, последнее уравнение примет вид: 
. Решая его, получаем 
, 
. Таким образом, вероятности оптимальных стратегий второго игрока определяются вектором 
.
Подставим найденные оптимальные вероятности смешанных стратегий в функцию выигрыша, найдём цену игры:
.
Ответ. 
; ; .
|
|
|
