- •И.Н.Булгакова, ю.В.Бондаренко, г.Д.Чернышова
- •§ 1. Основные понятия исследования операций. Математическая модель операции
- •§ 2. Понятие игры. Классификация игр
- •§ 3. Антагонистические игры в нормальной форме
- •3.1 Определение антагонистической игры в нормальной форме. Матричные игры
- •Примеры
- •3.2 Ситуация равновесия в чистых стратегиях: понятие и существование
- •Упражнения к § 3.1. – 3.2
- •3.3 Смешанное расширение игры
- •3.4 Методы решения матричных игр
- •3. Сведение игры к задаче линейного программирования
- •3.5 Существование оптимальных стратегий. Теорема фон Неймана-Нэша
- •Упражнения к § 3.3–3.5
- •3.6. Доминирование стратегий
- •Примеры
- •Упражнения к § 3.6
- •3.7 Игры с частными случаями платежных матриц
- •§ 4. Игры в условиях неопределенности и риска (игры с природой)
- •Принятие решений в условиях полной неопределенности
- •Принятие решений в условиях риска
- •Примеры
- •Упражнения к § 4
- •§ 5 Позиционые игры
- •Упражнения
- •Список литературы
- •I. Основная литература
- •II. Дополнительная литература
3.5 Существование оптимальных стратегий. Теорема фон Неймана-Нэша
Существование оптимальных стратегий смешанного расширения игры доказывается следующей теоремой.
Теорема 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 ден. ед. Действительно ли эта игра «честная»? Станете ли Вы в нее играть (ответьте вначале без обращения к методам теоретико-игрового анализа)? Как будет влиять на Ваше решение количество партий в этой игре? Если Вы принимаете игру, какую стратегию выберете? Рассмотрите два варианта игры: а) выбор стратегий определяется игроками самостоятельно; б) выбор стратегий определяется случайно (по броску монеты). Сделайте выводы.