08. Чистые и смешанные стратегии

Если в игре каждый из противников применяет только одну и ту же стратегию, то про саму игру в этом случае говорят, что она происходит В чистых стратегиях, а используемые игроком А и игроком В пара стратегий называются Чистыми стратегиями.

Определение. В антагонистической игре пара стратегий (АI, ВJ) называется равновесной или устойчивой, если ни одному из игроков не выгодно отходить от своей стратегии.

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

В рассмотренном в §2.2 примере 1 максиминные чистые стратегии А4 и В5 неустойчивы по отношению к информации о поведении противника; они не обладают свойством равновесия.

Действительно, предположим, что мы узнали, что противник придерживается стратегии В3. Используя эту информацию, выберем стратегию А1 и получим больший выигрыш, равный 7. Но если противник узнал, что наша стратегия А1, он выберет стратегию В4, сведя наш выигрыш к 4.

Таким образом, в рассмотренном примере максиминные чистые стратегии оказались неустойчивы по отношению к информации о поведении другой стороны. Но это не всегда так.

Рассмотрим матричную игру G (3х4), платежная матрица которой приведена на рис 2.3.

Bj Ai	B1	B2	B3	B4	AI
A1	5	7	10	8	5
A2	10	9	11	10	9
A3	8	6	7	4	4
BJ	10	9	11	10

Рис. 2.3

В этом примере нижняя цена игры равна верхней: a=b=9, т. е. игра имеет седловую точку.

Оказывается, что в этом случае максиминные стратегии А2 и В2 будут Устойчивыми по отношению к информации о поведении противника.

Действительно, пусть игрок А узнал, что противник применяет стратегию В2. Но и в этом случае игрок А будет по-прежнему придерживаться стратегии А2, потому что любое отступление от стратегии А2 только уменьшит выигрыш. Равным образом, информация, полученная игроком В, не заставит его отступить от своей стратегии В2.

Пара стратегий А2 и В2 обладает свойством устойчивости, а выигрыш (в рассматриваемом примере он равен 9), достигаемый при этой паре стратегий, оказывается седловой точкой платежной матрицы.

Признак устойчивости (равновесности) пары стратегии - это равенство нижней и верхней цены игры.

Стратегии АI и ВJ (в рассматриваемом примере А2, В2), при котором выполняется равенство нижней и верхней цены игры, называются оптимальными чистыми стратегиями, а их совокупность - решением игры. Про саму игру в этом случае говорят, что она решается в чистых стратегиях.

Величина (2.5)

Называется ценой игры.

Если N>0, то игра выгодна для игрока А, если N<0 - для игрока В; при N=0 игра справедлива, т. е. является одинаково выгодной для обоих участников.

Однако наличие седловой точки в игре - это далеко не правило, скорее - исключение. Большинство матричных игр, не имеет седловой точки, а следовательно, не имеет оптимальных чистых стратегий. Впрочем, есть разновидность игр, которые всегда имеют седловую точку и, значит, решаются в чистых стратегиях. Это - игры с полной информацией.

Теорема 2. Каждая игра с полной информацией имеет седловую точку, а следовательно, решается в чистых стратегиях, т. е. имеется пара оптимальных чистых стратегий, дающая устойчивый выигрыш, равный N.

Если такая игра состоит только из личных ходов, то при применении каждым игроком своей оптимальной чистой стратегии она должна кончаться выигрышем, равным цене игры. Скажем, шахматная игра, как игра с полной информацией, либо всегда кончается выигрышем белых, либо всегда - выигрышем черных, либо всегда - ничьей (только чем именно - мы пока не знаем, так как число возможных стратегий в шахматной игре огромно).

Если матрица игры содержит седловую точку, то ее решение сразу находится по принципу максимина.

Возникает вопрос: как найти решение игры, платежная матрица которой не имеет седловой точки? Применение максиминного принципа каждым из игроков обеспечивает игроку А выигрыш не менее A, игроку - проигрыш не больше b. Учитывая что a<b, естественно для игрока А желание увеличить выигрыш, а для игрока В - уменьшить проигрыш. Поиск такого решения производит к необходимости применять смешанные стратегии: чередовать чистые стратегии с какими-то частотами.

Определение. Случайная величина, значениями которой являются чистые стратегии игрока, называется его Смешанной стратегией.

Таким образом, задание смешанной стратегии игрока состоит в указании тех вероятностей, с которыми выбираются его чистые стратегии.

Будем обозначать смешанные стратегии игроков А и В соответственно

SA=||p1, p2, ..., pm||,

SB=||q1, q2, ..., qn||,

Где pi - вероятность применения игроком А чистой стратегии АІ; ;

Qj - вероятность применения игроком В чистой стратегии Bj; .

В частном случае, когда все вероятности, кроме одной, равны нулю, а эта одна - единице, смешанная стратегия превращается в чистую.

Применение смешанных стратегий осуществляется, например, таким образом: игра повторяется много раз, но в каждой партии игрок применяет различные чистые стратегии с относительными частотами их применения, равными PI И QJ.

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

Если игрок А применяет смешанную стратегию SA=||p1, p2, ..., pm||, а игрок В смешанную стратегию SB=||q1, q2, ..., qn||, то средний выигрыш (математическое ожидание) игрока А определяется соотношением

. (2.6)

Естественно, что ожидаемый проигрыш игрока В равен такой же величине.

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

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

< Предыдущая		Следующая >