Решение игры в смешанных стратегиях

Скачать материал

Решение игр в смешанных стратегиях.


Если игра не имеет седловой точки, то применение чистых стратегий не дает оптимального решения игры. Так, в примере 1 α ≠ β, седловая точка отсутствует. В таком случае можно получить оптимальное решение, случайным образом чередуя чистые стратегии.


Смешанной стратегией SA игрока А называется применение чистых стратегий A1, A2, ..., Am с вероятностями p1, p2, ..., pi, ..., pm причем сумма вероятностей равна 1:


Смешанные стратегии игрока А записываются в виде матрицы



или в виде строки SA = (p1, p2, ..., pi, ..., pm)

Аналогично смешанные стратегии игрока В обозначаются:


, или, SB = (q1, q2, ..., qi, ..., qn),


где сумма вероятностей появления стратегий равна 1:



Чистые стратегии можно считать частным случаем смешанных и задавать строкой, в которой 1 соответствует чистой стратегии. На основании принципа минимакса определяется оптимальное решение (или решение) игры: это пара оптимальных стратегий S*A , S*B в общем случае смешанных, обладающих следующим свойством: если один из игроков придерживается своей оптимальной стратегии, то другому не может быть выгодно отступать от своей. Выигрыш, соответствующий оптимальному решению, называется ценой игры v. Цена игры удовлетворяет неравенству:

α ≤ 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 = (p*1, p*2) и S*B = (q*1, q*2).


Для того чтобы их найти, воспользуемся теоремой об активных стратегиях. Если игрок А придерживается своей оптимальной стратегии S'A, то его средний выигрыш будет равен цене игры v, какой бы активной стратегией ни пользовался игрок В. Для игры 2×2 любая чистая стратегия противника является активной, если отсутствует седловая точка. Выигрыш игрока А (проигрыш игрока В) — случайная величина, математическое ожидание (среднее значение) которой является ценой игры. Поэтому средний выигрыш игрока А (оптимальная стратегия) будет равен v и для 1-й, и для 2-й стратегии противника.


Пусть игра задана платежной матрицей



Средний выигрыш игрока А, если он использует оптимальную смешанную стратегию


,


а игрок В — чистую стратегию B1 (это соответствует 1-му столбцу платежной матрицы Р), равен цене игры v: a11 p*1+ a21 p*2= v. Тот же средний выигрыш получает игрок А, если 2-й игрок применяет стратегию B2, т.е. a12 p*1+ a22 p*2= v. Учитывая, что p*1+ p*2= 1, получаем систему уравнений для определения оптимальной стратегии S'A и цены игры v:



Решая эту систему, получим оптимальную стратегию



и цену игры



Применяя теорему об активных стратегиях при отыскании S*B- оптимальной стратегии игрока В, получаем, что при любой чистой стратегии игрока А (А1 или А2) средний проигрыш игрока В равен цене игры v, т.е.


Тогда оптимальная стратегия определяется формулами:




Пример 1.


Игра «поиск»


Игрок А может спрятаться в одном из двух убежищ (I и II); игрок В ищет игрока А, и если найдет, то получает штраф 1 ден. ед. от А, в противном случае платит игроку А 1 ден. ед. Необходимо построить платежную матрицу игры.


Решение. Для составления платежной матрицы следует проанализировать поведение каждого из игроков. Игрок А может спрятаться в убежище I – обозначим эту стратегию через A1 или в убежище II — стратегия A2 .


Игрок В может искать первого игрока в убежище I — стратегия B1 , либо в убежище II — стратегия B2. Если игрок А находится в убежище I и там его обнаруживает игрок В, т.е. осуществляется пара стратегий (A1, B1), то игрок А платит штраф, т.е. a11 = - 1. Аналогично получаем a22 = - 1 (A2, B2). Очевидно, что стратегии (A1, B2) и (A2, B1) дают игроку А выигрыш 1, поэтому a12 = a21 = 1. Таким образом, для игры "поиск" размера 2×2 получаем платежную матрицу



Применим полученные результаты для отыскания оптимальных стратегий для игры, рассмотренной в примере 1.



Пример 2.


Найти оптимальные стратегии игры, приведенной в примере 1.


Решение. Игра "поиск" задана платежной матрицей без седловой точки:


Поэтому ищем решение в смешанных стратегиях; для игрока А средний выигрыш равен цене игры v (при B1 и B2); для игрока В средний проигрыш равен цене игры v (при A1 и B2). Системы уравнений в данном случае имеют вид:



Решая эти системы, получаем


Это означает, что оптимальная стратегия каждого игрока состоит в том, чтобы чередовать свои чистые стратегии случайным образом, выбирая каждое из убежищ с вероятностью 1/2, при этом средний выигрыш равен 0.



















РЕФЕРАТ ПО ДИСЦИПЛИНЕ «МАТЕМАТИКА»

НА ТЕМУ: «Решение игры в смешанных стратегиях».
























Нравится материал? Поддержи автора!

Ещё документы из категории математика:

X Код для использования на сайте:
Ширина блока px

Скопируйте этот код и вставьте себе на сайт

X

Чтобы скачать документ, порекомендуйте, пожалуйста, его своим друзьям в любой соц. сети.

После чего кнопка «СКАЧАТЬ» станет доступной!

Кнопочки находятся чуть ниже. Спасибо!

Кнопки:

Скачать документ
КУРСЫ ПОВЫШЕНИЯ КВАЛИФИКАЦИИ И ПЕРЕПОДГОТОВКИ Бесплатные олимпиады Инфоурок