Если парная игра не имеет седловой точки, то она не имеет и решения, то есть, делая личные ходы (или, говоря иначе, в чистых стратегиях), игрок A гарантирует себе выигрыш, равный нижней цене игры, которая, вообще говоря, меньше верхней цены игры.
Если же игрок A будет чередовать свои стратегии случайным образом или, говоря иначе, придерживаться смешанной стратегии, то он получит оптимальную стратегию, которая в некоторых случаях будет гарантировать ему бόльший выигрыш.
Определение. Пусть игрок A имеет m стратегий, а игрок B – n стратегий. Смешанной стратегией игрока A называется набор вероятностей SA = (p1, p2, …, pm), где p1 + p2 +… + pm = 1, с которыми он чередует свои стратегии.
Аналогично определяется смешанная стратегия игрока B как набор SB = (q1, q2, …, qm), где q1 + q2 +… + qn = 1.
Имеет место следующая теорема.
Теорема (основная теорема теории игр). Любая m ´ n игра имеет решение в смешанных стратегиях и её решение может получено методами линейного программирования.
Доказательство. Пусть m ´ n игра имеет матрицу
требуется найти решение игры, то есть две оптимальные смешанные стратегии игроков SA = (p1, p2, …, pm) и SB = (q1, q2, …, qm), где p1 + p2 +… + pm = 1 и q1 + q2 +… + qn = 1.
Во-первых, можно считать, что цена игры n (пока неизвестная) больше нуля. Действительно, если n £ 0, то это означает, что некоторые элементы матрицы игры не положительные. Тогда найдём число M > 0, которое прибавим ко всем элементам матрицы игры и получим новую матрицу с положительными элементами. Это сложение сделает новую цену игры n + M положительной, но не изменит решения игры.
Во-вторых, предположим, что игрок A применяет свою оптимальную смешанную стратегию 
, а игрок B свою чистую стратегию Bj. В этом случае средний выигрыш игрока A будет равен
Стратегия является оптимальной, то есть при любой стратегии игрока B средний выигрыш игрока A будет больше или равен цены игры n, таким образом, получаем систему ограничений
Разделим обе части всех неравенств на положительное число n и обозначим
тогда система ограничений примет вид
Далее, так как p1 + p2 +… + pm = 1, то
Игрок A стремится максимизировать свой средний выигрыш n, то есть минимизировать отношение 
Таким образом, получаем задачу линейного программирования:
Заметим, что эта задача имеет решение, найдя которое 
найдём новую цену игры 
, вычтя из которой число M, получим искомую цену игры.
Аналогичные рассуждения дают оптимальную стратегию 
игрока B:
обозначим
тогда оптимальная стратегия 
игрока B есть решение следующей задачи линейного программирования:
причём 
Применим основную теорему теории игр для отыскания оптимальных стратегий игроков в игре "поиск".
1. Матрица игры "поиск" 
содержит отрицательные элементы, поэтому, прибавляя к её элементам число M= 1, получим
2. Для нахождения оптимальной стратегии игрока A решаем следующую задачу линейного программирования:
Так как последняя система ограничений эквивалентна системе
то минимум функции 
равен 1 и достигается при 
Так как 
то n = 1. Вычитая из n число M = 1, получим, что цена игры равна 0 = 1 – 1, а оптимальная стратегия 
Итак, чередуя свои обе стратегии с вероятностями 
, игрок A гарантирует себе средний выигрыш, равный 0, что больше нижней цены игры -1 при чистых стратегиях.
Аналогичные рассуждения приводят к тому, что игрок B, чередуя свои стратегии с вероятностями , получает средний выигрыш, равный 0.
6. ОТЧЕТ ДОЛЖЕН СОДЕРЖАТЬ:
6.1. Номер практической работы, ее название, номер выполняемого варианта.
6.2. Номер задания.
6.3. Условие решаемой задачи.
6.4. Математическая модель задачи.
6.5. Решение задачи теории игр.
7. КОНТРОЛЬНЫЕ ВОПРОСЫ:
7.1. Стратегия. Оптимальная стратегия.
7.2. Платежная матрица игры.
7.3. Нижняя и верхняя цена игры. Седловая точка.
7.4. Принцип минимакса.
7.5. Смешанные стратегии игроков.
ПРАКТИЧЕСКОЕ ЗАНЯТИЕ №8
