Тема. Принятие решений в условиях неопределенности (стр. 3 )

Рис. 1. Пример поверхности с седловой точки

Достаточно посмотреть внимательно на матрицу (см. табл. 5), чтобы понять, что каждый из игроков должен придерживаться максиминной (минимаксной) стратегии. Эти стратегии являются оптимальными в игре с седловой точкой. Любое отклонение от них будет невыгодно для игрока, допустившего отклонение.

Если же игра не имеет седловой точки (см. табл. 4), то ни одна из стратегий Аi или Вi не является оптимальной.

Табл. 5. Платёжная матрица с седловой точкой

B A	В1	В2	В3	Минимумы строк, ai
А1	2	3	7	2
А2	5	4	6	4
А3	6	2	1	1
Максимумы столбцов, bj	6	4	7

Как быть, если игра не имеет седловой точки? Если каждый игрок вынужден выбирать одну-единственную чистую стратегию, то делать нечего: надо руководствоваться принципом минимакса. Другое дело, если можно свои стратегии "смешивать", чередовать случайным образом с какими-то вероятностями. Применение смешанных стратегий мыслится таким образом: игра повторяется много раз; перед каждой партией игры, когда игроку предоставляется личный ход, он "передоверяет" свой выбор случайности, "бросает жребий", и берёт ту стратегию, которая выпала.

Смешанные стратегии в теории игр представляют модель изменчивой, гибкой тактики, когда ни один из игроков не знает, как поведёт себя противник в данной партии. Такая тактика (правда, обычно безо всяких математических обоснований) часто применяется в карточных играх.

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

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

Необходимость случайного изменения стратегии в игре
без седловой точки

Допустим, что мы и наш противник многократно играем в игру, матрица которой дана на рис. 4. Если мы выберем определённую стратегию, например максиминную стратегию A1, и будем придерживаться её от игры к игре, то противник, поняв это, будет выбирать каждый раз стратегию B2, в результате чего наш выигрыш не превысит нижней цены игры, т. е. будет равен 3. Если, однако, мы внезапно (для противника) сменим стратегию A1 на стратегию A2, то получим выигрыш 10. Разгадав нашу новую стратегию, противник тут же сменит стратегию B2 на стратегию B3, уменьшив наш выигрыш до 1. И так далее. Здесь проявляется общее правило для игр без седловой точки: игрок, играющий по определённой (детерминированной) стратегии, оказывается в более худшем положении по сравнению с игроком, который меняет стратегию случайным образом.

Впрочем, случайные изменения стратегии надо делать не как попало, а с умом. Пусть A1, A2, …, An — возможные стратегии игрока A. Для получения наибольшего эффекта он должен использовать все или некоторые из этих стратегий случайным образом, но не с одинаковыми, а с разными (специально вычисленными) вероятностями. Пусть стратегия A1,используется с вероятностью p1, стратегия A2,с вероятностью p2 и т. д.

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

,

или в виде строки SA=(p1, p2, …, pn). В отличие от смешанных стратегий SA стратегии Aj называют чистыми. При надлежащем подборе вероятностей pj смешанная стратегия может оказаться оптимальной. При этом выигрыш игрока A будет не меньше некоторого значения v, называемого ценой игры. Это значение больше нижней цены игры, но меньше верхней.

Аналогичны образом должен вести себя игрок B. Его оптимальная стратегия также есть некоторая смешанная стратегия

или в виде строки SB=(q1, q2, …,qm), где qj — специально подобранные вероятности, с которыми игрок B использует стратегии Bj. Сумма вероятностей равна 1: При выборе игроком B оптимальной смешанной стратегии выигрыш игрока A будет не больше цены игры v.

Чистые стратегии можно считать частным случаем смешанных. На основании принципа минимакса определяется оптимальное решение (или решение) игры: это пара оптимальных стратегий 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.1.4. Приведение матричной игры к задаче линейного программирования

Обозначим через SA=(p1, p2, …, pn) оптимальную смешанную стратегию игрока A. Требуется найти вероятности и определить цену игры при условии, что известна платёжная матрица игры. Допустим, что игрок B выбирает чистую стратегию B1. Тогда средний выигрыш для игрока A будет равен a11p1+a21p2+…+an1pn. Этот выигрыш должен быть не меньше цены игры v, следовательно, a11p1+a21p2+…+an1pn≥v.

Если игрок B выберет стратегию B2, то и в этом случае средний выигрыш игрока A должен быть не меньше цены игры v, следовательно, a12p1+a22p2+…+an2pn≥v.

Какую бы стратегию ни выбирал игрок B, выигрыш игрока A всегда должен быть не меньше цены игры v. Поэтому мы можем записать следующую систему из m неравенств (напоминаем, что m — число чистых стратегий игрока B):

a11p1+a21p2+…+an1pn≥v;

a12p1+a22p2+…+an2pn≥v;

………………………… (1)

a1mp1+a2mp2+…+anmpn≥v.

При этом p1+p2+…+pn=1. (2)

Введя обозначения x1=p1/v, x2=p2/v, … xn=pn/v, перепишем (1) и (2) в виде

a11x1+a21x2+…+an1xn≥1;

a12x1+a22x2+…+an2xn≥1;

………………………… (3)

a1mx1+a2mx2+…+anmxn≥1;

x1+x2+…+xn=1/v. (4)

Нам желательно, чтобы цена игры была максимальной, следовательно, 1/v должна быть минимальной. Таким образом, поиск оптимальной смешанной стратегии свёлся к решению следующей задачи линейного программирования: надо найти неотрицательные величины xi такие, чтобы они удовлетворяли неравенствам (3) и обращали в минимум сумму x1+x2+…+xn, т. е.

L= x1+x2+…+xn→min,

при ограничениях

a11x1+a21x2+…+an1xn≥1;

a12x1+a22x2+…+an2xn≥1;

…………………………

a1mx1+a2mx2+…+anmxn≥1;

xi≥0, i=1, 2, …, n/

Задача. Самолёты против зениток. Найдём оптимальную смешанную стратегию некоторой конкретной игры. Предположим, что сторона A нападает на сторону B. У стороны A имеются два самолёта, несущие мощное поражающее средство. У стороны B имеются четыре зенитки, при помощи которых осуществляется оборона важного объекта. Чтобы объект оказался разрушенным, достаточно, чтобы к нему прорвался хотя бы один самолёт. Для подхода к объекту самолёты могут выбрать любой из четырёх воздушных коридоров (см. рис. 2).