Основная теорема теории антагонистических игр — теорема Дж. фон Неймана. Смешанные стратегии. Фундаментальная проблема в теории игр

В общем случае 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 любая чистая стратегия игроков является активной. Если первый игрок использует оптимальную смешанную стратегию
, а второй игрок применит первую активную стратегию, то выигрыш первого игрока равен цене игры:

Если первый игрок использует оптимальную смешанную стратегию
, а второй игрок применит вторую активную стратегию, то выигрыш первого игрока снова будет равен цене игры:

Приравнивая левые части уравнений и учитывая, что =
,

получаем уравнение относительно :

, откуда находим оптимальную стратегию первого игрока:

, =

и цену игры:

Так как цена игры уже найдена, то для определения оптимальной стратегии второго игрока достаточно одного уравнения, которое получаем, если второй игрок применяет оптимальную стратегию, а первый – свою первую активную стратегию: