Главная » Учебно-методические материалы » ВЫСШАЯ МАТЕМАТИКА, ТВ и МС, МАТ. МЕТОДЫ » Математические методы. Попова Н.В. |
22.12.2011, 14:31 | ||||||||||||||||
Если игра не имеет седловой точки, то применение чистых стратегий не дает оптимального решения игры. Так, в примере 3.2.1 α ≠ β, седловая точка отсутствует. В таком случае можно получить оптимальное решение, случайным образом чередуя чистые стратегии. Смешанной стратегией SA игрока А называется применение чистых стратегий A1, A2, ..., Am с вероятностями p1, p2, ..., pi, ..., pm причем сумма вероятностей равна 1: или в виде строки SA = (p1, p2, ..., pi, ..., pm) Аналогично смешанные стратегии игрока В обозначаются:
где сумма вероятностей появления стратегий равна 1: Чистые стратегии можно считать частным случаем смешанных и задавать строкой, в которой 1 соответствует чистой стратегии. На основании принципа минимакса определяется оптимальное решение (или решение) игры: это пара оптимальных стратегий S*A , S*B в общем случае смешанных, обладающих следующим свойством: если один из игроков придерживается своей оптимальной стратегии, то другому не может быть выгодно отступать от своей. Выигрыш, соответствующий оптимальному решению, называетсяценой игры v. Цена игры удовлетворяет неравенству:
где α и β — нижняя и верхняя цены игры. Справедлива следующая основная теорема теории игр — теорема Неймана. Каждая конечная игра имеет по крайней мере одно оптимальное решение, возможно, среди смешанных стратегий. Пусть S*A = (p*1, p*2, ..., p*i, ..., p*m) и S*B = (q*1, q*2, ..., q*i, ..., q*n) — пара оптимальных стратегий. Если чистая стратегия входит в оптимальную смешанную стратегию с отличной от нуля вероятностью, то она называется активной. Справедлива теорема об активных стратегиях: если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш остается неизменным и равным цене игры v, если второй игрок не выходит за пределы своих активных стратегий. Эта теорема имеет большое практическое значение — она дает конкретные модели нахождения оптимальных стратегий при отсутствии седловой точки. Рассмотрим игру размера 2×2, которая является простейшим случаем конечной игры. Если такая игра имеет седловую точку, то оптимальное решение — это пара чистых стратегий, соответствующих этой точке. Для того чтобы их найти, воспользуемся теоремой об активных стратегиях. Если игрок А придерживается своей оптимальной стратегии S'A, то его средний выигрыш будет равен цене игры v, какой бы активной стратегией ни пользовался игрок В. Для игры 2×2любая чистая стратегия противника является активной, если отсутствует седловая точка. Выигрыш игрока А (проигрыш игрока В) — случайная величина, математическое ожидание (среднее значение) которой является ценой игры. Поэтому средний выигрыш игрока А (оптимальная стратегия) будет равен v и для 1-й, и для 2-й стратегии противника. Пусть игра задана платежной матрицей Средний выигрыш игрока А, если он использует оптимальную смешанную стратегию
Решая эту систему, получим оптимальную стратегию
и цену игры
Применяя теорему об активных стратегиях при отыскании SВ*- оптимальной стратегии игрока В, получаем, что при любой чистой стратегии игрока А (А1 или А2) средний проигрыш игрока В равен цене игры v, т.е.
Тогда оптимальная стратегия определяется формулами:
Применим полученные результаты для отыскания оптимальных стратегий для игры, рассмотренной в примере 3.2.1. | http://matmetod-popova.narod.ru/ |