Основная теорема теории антагонистических игр — теорема Дж. фон Неймана. Смешанные стратегии. Фундаментальная проблема в теории игр
В общем случае V * ≠ V * - седловой точки не существует. Оптимальное решение в чистых стратегиях также не существует. Однако, если расширить понятие чистой стратегии введением понятия смешанной стратегии, то удаётся реализовать алгоритм нахождения оптимального решения не вполне определённой игровой задачи. В такой ситуации предлагается использование статистического (вероятностного) подхода к нахождению оптимального решения антагонистической игры. Для каждого игрока, наряду с данным набором возможных для него стратегий, вводится неизвестный вектор вероятностей (относительных частот), с которыми следует применять ту или иную стратегию.
Обозначим вектор вероятностей (относительных частот) выбора заданных стратегий игрока A следующим образом:
P = (p 1 , p 2 ,…, p m),
где p i ≥ 0, p 1 + p 2 +…+ p m = 1. Величина p i называется вероятностью (относительной частотой) применения стратегии A i .
Аналогично для игрока B вводится неизвестный вектор вероятностей (относительных частот) имеет вид:
Q = (q 1 , q 2 ,…, q n),
где q j ≥ 0, q 1 + q 2 +…+ q n = 1. Величина q j называется вероятностью (относительной частотой) применения стратегии B j . Совокупность (комбинация) чистых стратегий A 1 , A 2 , …A m и B 1, B 2, …B n в сочетании с векторами вероятностей выбора каждой из них называются смешанными стратегиями.
Основной теоремой в теории конечных антагонистических игр является Теорема фон Неймана
: каждая конечная матричная игра имеет, по крайней мере, одно оптимальное решение, возможно, среди смешанных стратегий
.
Из этой теоремы следует, что не вполне определённая игра имеет хотя бы одно оптимальное решение в смешанных стратегиях. В таких играх решением будет пара оптимальных смешанных стратегий P * и Q * , таких, что если один из игроков придерживается своей оптимальной стратегии, то и другому игроку не выгодно отклоняться от своей оптимальной стратегии.
Средний выигрыш игрока A определяется математическим ожиданием:
Если вероятность (относительная частота) применения стратегии отлична от нуля, то такая стратегия называется активной .
Стратегии P * , Q * называются оптимальными смешанными
стратегиями, если M A (P, Q *) ≤ M A (P * , Q *) ≤ M A (P * , Q) (1)
В этом случае M A (P * , Q *) называется ценой
игры и обозначается через V (V * ≤ V ≤ V *). Первое из неравенств (1)означает, что отклонение игрока A от своей оптимальной смешанной стратегии
при условии, что игрок B придерживается своей оптимальной смешанной стратегии, приводит к уменьшению среднего выигрыша
игрока A. Второе из неравенств означает, что отклонение игрока B от своей оптимальной смешанной стратегии
при условии, что игрок A придерживается своей оптимальной смешанной стратегии, приводит к увеличению среднего проигрыша игрока B
.
В общем случае подобные задачи успешно решаются этим калькулятором .
Пример .
4 | 7 | 2 |
7 | 3 | 2 |
2 | 1 | 8 |
1. Проверяем, имеет ли платежная матрица седловую точку . Если да, то выписываем решение игры в чистых стратегиях.
Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.
Игроки | B 1 | B 2 | B 3 | a = min(A i) |
A 1 | 4 | 7 | 2 | 2 |
A 2 | 7 | 3 | 2 | 2 |
A 3 | 2 | 1 | 8 | 1 |
b = max(B i) | 7 | 7 | 8 |
Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(a i) = 2, которая указывает на максимальную чистую стратегию A 1 .
Верхняя цена игры b = min(b j) = 7. Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах 2 ≤ y ≤ 7. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии).
2. Проверяем платежную матрицу на доминирующие строки и доминирующие столбцы
.
В платежной матрице отсутствуют доминирующие строки и доминирующие столбцы.
3. Находим решение игры в смешанных стратегиях
.
Запишем систему уравнений.
Для игрока I
4p 1 +7p 2 +2p 3 = y
7p 1 +3p 2 +p 3 = y
2p 1 +2p 2 +8p 3 = y
p 1 +p 2 +p 3 = 1
Для игрока II
4q 1 +7q 2 +2q 3 = y
7q 1 +3q 2 +2q 3 = y
2q 1 +q 2 +8q 3 = y
q 1 +q 2 +q 3 = 1
Решая эти системы методом Гаусса , находим:
y = 4 1 / 34
p 1 = 29 / 68 (вероятность применения 1-ой стратегии).
p 2 = 4 / 17 (вероятность применения 2-ой стратегии).
p 3 = 23 / 68 (вероятность применения 3-ой стратегии).
Оптимальная смешанная стратегия игрока I: P = (29 / 68 ; 4 / 17 ; 23 / 68)
q 1 = 6 / 17 (вероятность применения 1-ой стратегии).
q 2 = 9 / 34 (вероятность применения 2-ой стратегии).
q 3 = 13 / 34 (вероятность применения 3-ой стратегии).
Оптимальная смешанная стратегия игрока II: Q = (6 / 17 ; 9 / 34 ; 13 / 34)
Цена игры: y = 4 1 / 34
Если нижняя и верхняя цены игры в смешанных стратегиях совпадают, то их общее значение V= =v называется ценой игры в смешанных стратегиях , а стратегии и , для которых выполняется равенство называются оптимальными смешанными стратегиями соответственно игроков А и В. Оптимальные смешанные стратегии и обладают тем свойством, что если один из игроков придерживается своей оптимальной стратегии, то противнику невыгодно отклоняться от своей оптимальной стратегии. Обозначим через множества оптимальных стратегий игроков А и В. Очевидно, что множество оптимальных стратегий каждого из игроков является подмножеством множества смешанных стратегий:
, то есть цена игры в смешанных стратегиях не меньше нижней цены игры в чистых стратегиях α и не больше верхней цены игры в чистых стратегиях β.
Полным решением игры в смешанных стратегиях называется совокупность множеств оптимальных стратегий игроков и цены игры. Любая пара оптимальных стратегий и и цена игры образуют частное решение в смешанных стратегиях.
Основная теорема матричных игр фон Неймана . Любая матричная игра имеет решение в смешанных стратегиях, то есть существует цена игры в смешанных стратегиях и оптимальные смешанные стратегии и игроков А и В соответственно.
Критерий оптимальности смешанной стратегии игрока А в терминах, задаваемых цены игры в смешанных стратегиях, выигрыш-функции и множества смешанных стратегий игрока В
Пусть V-цена игры, Н(Р,Q) – выигрыш-функция, S B – множества смешанных стратегий игрока В.
Для того чтобы стратегия Р 0 игрока А была оптимальной, необходимо и достаточно, чтобы выполнялось нер-во Н(Р 0 ,Q) V для любого Q S B , (1)
т.е. выбор игроком А оптимальной стратегии Р 0 гарантирует ему выигрыш Н(Р 0 ,Q), не меньший цены игры V, при любой стратегии Q игрока В .
Док-во:
Необходимость. Пусть Р 0 - опт стратегия игрока А. тогда по т. Фон Неймана показатель эфф-ти α(Р) стратегии Р 0 равен цене игры V: (2)
Рассматривая как пок-ль эф-ти стратегии Р 0 относит множ-ва S B смеш стр-гий игрока В, будем иметь по опр-нию: (3)
Р 0 игрока А выполнется нер-во (1)
Для док-ва оптимальности стратегии Р 0 достаточно показать справедливость равенства: (4)
Т.к. нер-во(1) выполняется для любой стратегии Q S B игрока В, то (5)
Но цена игры V равна нижней цене игры , по опр кот. (6)
Критерий оптимальности смешанной стратегии игрока В в терминах задаваемых цены игры в смешанных стратегиях, выигрыш-функции и множества смешанных стратегий игрока А
Теорема (Критерий оптимальных стратегий.)
Пусть V-цена игры, Н(Р,Q) – выигрыш-функция, S A – множества смешанных стратегий игрока А.
Для того чтобы стратегияQ 0 игрока В была оптимальной, необходимо и достаточно, чтобы выполнялось неравенство
Н(Р 0 ,Q) V для любого Р S A , (1)
т.е. выбор игроком В оптимальной стратегии Q 0 гарантирует ему проигрыш Н(Р, Q 0), не больший цены игры V, при любой стратегии Р игрока А.
Док-во:
Необходимость. Пусть Q 0 - опт стратегия игрока B. тогда по т. Фон Неймана показатель эфф-ти β(Q)стратегии Q 0 равен цене игры V: (2)
Рассматривая как пок-ль эф-ти стратегии Q 0 относит множ-ва S A смеш стр-гий игрока A, будем иметь по опр-нию: (3)
Из равенств (2)-(3)получаем (1)
Достаточность. Пусть для некоторой стр-гии Q 0 игрока B выполнется нер-во (1)
Для док-ва оптимальности стратегии Q 0 достаточно показать справедливость равенства: (4)
Т.к. нер-во(1) выполняется для любой стр-гии Q S B иг-ка В, то (5)
Но цена игры V равна верхней цене игры , по опр кот. (6)
Совокуп (5) и (6) эквивалентна рав-ву (4).
Достаточность доказана. Теорема доказана.
Критерий оптимальности смешанной стратегии игрока А в терминах, задаваемых цены игры в смешанных стратегиях, выигрыш-функции и множества чистых стратегий игрока В
Существование оптимальных стратегий смешанного расширения игры доказывается следующей теоремой.
Теорема 2. (основная теорема матричных игр, теорема фон Неймана-Нэша). Всякая матричная игра имеет ситуацию равновесия в смешанных стратегиях.
Доказательство
1.
Пусть
– игра со строго положительной матрицей
,
где
.
Докажем справедливость теоремы для
игры с такой матрицейA
.
Рассмотрим задачу линейного программирования следующего вида:
,
В векторно-матричной форме задача преобразуется к следующему виду:
(6)
где
.
Двойственная к (6) задача имеет следующий вид:
которая имеет следующую векторно-матричную форму:
(6д)
где
.
Так
как элементы матрицы A
строго
положительны, то существует вектор
,
для которого
,
то есть задача (6) имеет допустимую точку.
С другой стороны, точка y =0 является допустимым решением (6д). Тогда по теореме двойственности существуют и– оптимальные решения задач (6) и (6д) соответственно и значения целевых функций в оптимальных точках совпадают, то есть
. (7)
Рассмотрим
векторы:
,
.
Покажем,
что
,– оптимальные смешанные стратегии ви цена игры
.
Первоначально докажем, что ,– смешанные стратегии.
Из
соотношений (7):
,
то есть
.
Из допустимости векторовив задачах (6) и (6д) следует, что
,
,
то есть пара
– ситуация в смешанных стратегиях.
Докажем, что ,– оптимальные смешанные стратегии.
Вычислим
выигрыш первого игрока P1
в ситуации
:
Причем,
с одной стороны,
,
а с другой –
.
Тогда
,
а
.
Пусть ,– произвольные смешанные стратегии Р1 и Р2. Тогда выполняются неравенства:
Таким
образом,
,
,
,
то есть
– ситуация равновесия, а
– цена игрысо строго положительной матрицейA.
2.
По лемме о масштабе теорема верна для
игры с произвольной матрицей A
,
т. к. всегда существует матрица
,
где
,
такая, что элементы матрицы
положительны. Теорема доказана.
Упражнения к § 3.3–3.5
№1. Найти, опираясь на определение ситуации равновесия, ситуацию равновесия в игре со следующей матрицей:
1)
;
2)
.
№2
.
Проверить, что
и пара
,
где
и
,
соответственно цена и ситуация равновесия
в игре с матрицей
.
№3 . Методом сведения игры к системе неравенств найти оптимальные стратегии и цену игры, задаваемой матрицей:
.
№4
.
Дана игра с квадратной матрицей
,
где
.
С помощью свойства
2 оптимальных смешанных стратегий
показать, что оптимальные стратегии
игроков равны и вычисляются по формулам:
,
а цена игры
.
№5
.
Матрица порядка
называется латинским квадратом, если
каждая строка и каждый столбец ее
содержит все целые числа от 1 доm.
(Например, матрица
–
латинский квадрат). Показать, что
.
№6 . Решить графически игру со следующими матрицами:
1)
;
2)
;
3)
;
4)
.
№ 7 . Найти оптимальные стратегии и цену игры сведением игры к задаче линейного программирования, если матрица имеет вид:
1)
;
2)
,
3)
.
№ 8. К туристу (игрок Р1) подходит незнакомец (игрок Р2) и предлагает сыграть в игру «Орел-решка». Если у туриста «орел», а у незнакомца «решка», то турист получит 30 ден.ед. в местной валюте; если у туриста «решка», а у незнакомца «орел», то всего 10 ден. ед. Если выборы совпадут, то «для справедливости», как говорит незнакомец, турист заплатит ему 20 ден. ед. Действительно ли эта игра «честная»? Станете ли Вы в нее играть (ответьте вначале без обращения к методам теоретико-игрового анализа)? Как будет влиять на Ваше решение количество партий в этой игре? Если Вы принимаете игру, какую стратегию выберете? Рассмотрите два варианта игры: а) выбор стратегий определяется игроками самостоятельно; б) выбор стратегий определяется случайно (по броску монеты). Сделайте выводы.
Смешанной
стратегией
первого игрока называется применение
его чистых стратегий
по
случайному закону с частотами
причем сумма частот (вероятностей) равна
1:
.
Смешанная стратегия первого игрока
записывается в виде матрицы:
Аналогично смешанную стратегию второго игрока будем обозначать
где
сумма частот
его
стратегий
равна 1:
.
Средняя цена игры V(,) со стратегиями игроков и равна:
(1)
V(,)
=
Любая чистая стратегия является частным случаем смешанной стратегии, в которой все стратегии, кроме одной, применяются с нулевыми частотами, а данная – с частотой 1.
На
основании принципа минимакса определяется
решение игры: это пара оптимальных
стратегий
,
в общем случае смешанных, обладающих
свойством: если один из игроков
придерживается своей оптимальной
стратегии, то другому не может быть
выгодно отступать от своей. Выигрыш,
соответствующий решению игры, называется
ценой игры и обозначаетсяV.
Так
как чистые стратегии являются частным
случаем смешанных, то цена игры
удовлетворяет неравенству:
.
В 1928 году американский математик Джон Нейман доказал теорему:
Теорема 2 (Неймана ): Каждая конечная игра имеет по крайней мере одно решение, возможно, среди смешанных стратегий.
Для нахождения решения конечных игр без седловой точки требуется ввести еще одно понятие «активной» стратегии:
Активной стратегией называется стратегия игрока, входящая в его смешанную стратегию с отличной от нуля частотой.
Теорема 3 (об активных стратегиях): если один из игроков придерживается своей оптимальной стратегии, то выигрыш остается неизменным и равным цене игры V , если другой игрок не выходит за пределы своих активных стратегий.
Пример.
Позднее мы докажем, что оптимальной
стратегией Фионы в игре с пальцами
является смешанная стратегия с частотами
. Цена игрыV
= –.
Так как игра без седловой точки, то
обестратегии
Эдварда – активные. По теореме 3 при
любых частотах стратегий Эдварда цена
игры не изменится, если Фиона придерживается
своей оптимальной стратегии. Пусть,
например, частоты стратегий Эдварда
таковы:
.Средняя цена игры
по формуле (1) равна:
V.
Теорема 3 имеет большое практическое значение, так как она в некоторых случаях позволяет найти решение игры без седловой точки.
4. Аналитическое решение игры размера 2×2
Рассмотрим игру размера 2×2 с платежной матрицей
Для игры размера 2×2, в которой отсутствует седловая точка, решением игры по теореме Неймана будет пара смешанных стратегий
и
,
,
.
Чтобы
их найти, воспользуемся теоремой 3. Если
первый игрок придерживается своей
оптимальной смешанной стратегии
,
то его средний выигрыш будет равен цене
игры V
при любой активной стратегии второго
игрока. Для данной игры размера 2×2
любая чистая стратегия игроков является
активной. Если первый игрок использует
оптимальную смешанную стратегию
,
а второй игрок применит первую активную
стратегию, то выигрыш первого игрока
равен цене игры:
Если
первый игрок использует оптимальную
смешанную стратегию
,
а второй игрок применит вторую активную
стратегию, то выигрыш первого игрока
снова будет равен цене игры:
Приравнивая
левые части уравнений и учитывая, что
=
,
получаем уравнение относительно :
,
откуда находим оптимальную стратегию
первого игрока:
,
=
и
цену игры:
Так как цена игры уже найдена, то для определения оптимальной стратегии второго игрока достаточно одного уравнения, которое получаем, если второй игрок применяет оптимальную стратегию, а первый – свою первую активную стратегию:
,
откуда, учитывая, что
,
получаем:
=
,
Найдем по этим формулам решение игры Эдварда и Феоны.
Платежная
матрица игры:
,
поэтому
,
=
;
;
=
,
=;
Оптимальные стратегии игроков:
и
Игра для Эдварда невыгодная: в среднем за каждую игру он будет проигрывать доллара.