Скачать .docx Скачать .pdf

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

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

Если игра не имеет седловой точки, то применение чистых стратегий не дает оптимального решения игры. Так, в примере 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 .

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

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