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

Среди конечных игр, имеющих практическое значение, сравнительно редко встречаются игры с седловой точкой; более типичным является случай» когда нижняя и верхняя цена - игры различны. Анализируя матрицы таких игр, мы пришли к заключению, что если каждому игроку предоставлен выбор

одной - единственной стратегии., то в расчете на разумно действующего противника этот выбор должен определяться принципом минимакса. Придерживаясь своей максиминной стратегии, мы при любом поведении противника заведомо гарантируем себе выигрыш, равный нижней цене -игры а. Возникает естественный вопрос: нельзя ли гарантировать себе средний выигрыш, больший а, если применять не одну-единственную «чистую» стратегию, а чередовать случайным образом несколько стратегий?

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

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

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

Высказанное утверждение составляет содержание так называемой основной теоремы теории игр. Эта теорема была впервые доказана фон Нейманом в 1928 г. Известные доказательства теоремы сравнительно сложны; поэтому приведем только ее формулировку.

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

Выигрыш, получаемый в результате решения, называется ценой игры. Из основной теоремы следует, что каждая конечная игра имеет цену. Очевидно, что цена игры v всегда лежит между нижней ценой игры а и верхней ценой игры :

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

стратегии, мы, во всяком случае, не ухудшаем своих возможностей; следовательно,

Аналогично, рассматривая возможности противника, покажем, что

откуда следует доказываемое неравенство (3.1).

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

Аналогично смешанную стратегию противника будем обозначать:

где - частоты, в которых смешиваются стратегии

Предположим, что нами найдено решение игры, состоящее из двух оптимальных смешанных стратегий S, S. В общем случае не все чистые стратегии, доступные данному игроку, входят в его оптимальную смешанную стратегию, а только некоторые. Будем называть стратегии, входящие в оптимальную смешанную стратегию игрока, его «полезными» стратегиями.

Оказывается, что решение игры обладает еще одним замечательным свойством: если один из игроков придерживается своей оптимальной смешанной стратегии 5 (5). то выигрыш остается неизменным и равным цене игры v, независимо от того, что делает другой игрок, если он. только не выходит за пределы своих «полезных» стратегий. Он, например, может пользоваться любой из своих «полезных» стратегий в чистом виде, а также может смешивать их в любых пропорциях.

Докажем это утверждение. Пусть имеется решение игры . Для конкретнрсти будем считать, что оптимальная смешанная стратегия состоит из смеси трех

«полезных» стратегий соответственно состоит из смеси трех «полезных» стратегий

причем Утверждается что если мы будем придерживаться стратегии S, то противник может применять стратегии в любых пропорциях, а выигрыш останется неизменным и по-прежнему будет равен цене игры

В общем случае V * ≠ V * - седловой точки не существует. Оптимальное решение в чистых стратегиях также не существует. Однако, если расширить понятие чистой стратегии введением понятия смешанной стратегии, то удаётся реализовать алгоритм нахождения оптимального решения не вполне определённой игровой задачи. В такой ситуации предлагается использование статистического (вероятностного) подхода к нахождению оптимального решения антагонистической игры. Для каждого игрока, наряду с данным набором возможных для него стратегий, вводится неизвестный вектор вероятностей (относительных частот), с которыми следует применять ту или иную стратегию.

Обозначим вектор вероятностей (относительных частот) выбора заданных стратегий игрока A следующим образом:
P = (p 1 , p 2 ,…, p m),
где p i ≥ 0, p 1 + p 2 +…+ p m = 1. Величина p i называется вероятностью (относительной частотой) применения стратегии A i .

Аналогично для игрока B вводится неизвестный вектор вероятностей (относительных частот) имеет вид:
Q = (q 1 , q 2 ,…, q n),
где q j ≥ 0, q 1 + q 2 +…+ q n = 1. Величина q j называется вероятностью (относительной частотой) применения стратегии B j . Совокупность (комбинация) чистых стратегий A 1 , A 2 , …A m и B 1, B 2, …B n в сочетании с векторами вероятностей выбора каждой из них называются смешанными стратегиями.

Основной теоремой в теории конечных антагонистических игр является Теорема фон Неймана : каждая конечная матричная игра имеет, по крайней мере, одно оптимальное решение, возможно, среди смешанных стратегий .
Из этой теоремы следует, что не вполне определённая игра имеет хотя бы одно оптимальное решение в смешанных стратегиях. В таких играх решением будет пара оптимальных смешанных стратегий P * и Q * , таких, что если один из игроков придерживается своей оптимальной стратегии, то и другому игроку не выгодно отклоняться от своей оптимальной стратегии.
Средний выигрыш игрока A определяется математическим ожиданием:

Если вероятность (относительная частота) применения стратегии отлична от нуля, то такая стратегия называется активной .

Стратегии P * , Q * называются оптимальными смешанными стратегиями, если M A (P, Q *) ≤ M A (P * , Q *) ≤ M A (P * , Q) (1)
В этом случае M A (P * , Q *) называется ценой игры и обозначается через V (V * ≤ V ≤ V *). Первое из неравенств (1)означает, что отклонение игрока A от своей оптимальной смешанной стратегии при условии, что игрок B придерживается своей оптимальной смешанной стратегии, приводит к уменьшению среднего выигрыша игрока A. Второе из неравенств означает, что отклонение игрока B от своей оптимальной смешанной стратегии при условии, что игрок A придерживается своей оптимальной смешанной стратегии, приводит к увеличению среднего проигрыша игрока B .

В общем случае подобные задачи успешно решаются этим калькулятором .

Пример .

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

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

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(a i) = 2, которая указывает на максимальную чистую стратегию A 1 .
Верхняя цена игры b = min(b j) = 7. Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах 2 ≤ y ≤ 7. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии).

2. Проверяем платежную матрицу на доминирующие строки и доминирующие столбцы .
В платежной матрице отсутствуют доминирующие строки и доминирующие столбцы.

3. Находим решение игры в смешанных стратегиях .
Запишем систему уравнений.
Для игрока I
4p 1 +7p 2 +2p 3 = y
7p 1 +3p 2 +p 3 = y
2p 1 +2p 2 +8p 3 = y
p 1 +p 2 +p 3 = 1

Для игрока II
4q 1 +7q 2 +2q 3 = y
7q 1 +3q 2 +2q 3 = y
2q 1 +q 2 +8q 3 = y
q 1 +q 2 +q 3 = 1

Решая эти системы методом Гаусса , находим:

y = 4 1 / 34
p 1 = 29 / 68 (вероятность применения 1-ой стратегии).
p 2 = 4 / 17 (вероятность применения 2-ой стратегии).
p 3 = 23 / 68 (вероятность применения 3-ой стратегии).

Оптимальная смешанная стратегия игрока I: P = (29 / 68 ; 4 / 17 ; 23 / 68)
q 1 = 6 / 17 (вероятность применения 1-ой стратегии).
q 2 = 9 / 34 (вероятность применения 2-ой стратегии).
q 3 = 13 / 34 (вероятность применения 3-ой стратегии).

Оптимальная смешанная стратегия игрока II: Q = (6 / 17 ; 9 / 34 ; 13 / 34)
Цена игры: y = 4 1 / 34

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

В этой игре и . Следовательно, первый игрок может гарантировать себе выигрыш, равный 4, а второй может ограничить свой проигрыш 5. Область между и является как бы ничейной и каждый игрок может попытаться улучшить свой результат за счет этой области. Каковы же должны быть в этом случае оптимальные стратегии игроков?

Если каждый из игроков применяет отмеченную звездочкой стратегию (и ), то выигрыш первого игрока и проигрыш второго будут равны 5. Это невыгодно второму игроку, так как первый выигрывает больше, чем оно может себе гарантировать. Однако если второй игрок каким-либо образом раскроет замысел первого о намерении использовать стратегию , то он может применить стратегию и уменьшить выигрыш первого до 4. Правда, если первый игрок раскроет замысел второго применить стратегию , то, используя стратегию , он увеличит свой выигрыш до 6. Таким образом, возникает ситуация, когда каждый игрок должен хранить в секрете ту стратегию, которую он собирается использовать. Однако, как это сделать? Ведь если партия играется многократно и второй игрок применяет все время стратегию , то первый игрок скоро разгадает замысел второго и, применив стратегию , будет иметь добавочный выигрыш. Очевидно, что второй игрок должен менять стратегию в каждой новой партии, но делать это он должен так, чтобы первый не догадался, какую стратегию применит он в каждом случае.

Для механизма случайного выбора выигрыши и проигрыши игроков будут случайными величинами. Результат игры в этом случае можно оценить средней величиной проигрыша второго игрока. Вернемся к примеру. Так, если второй игрок использует стратегию и случайным образом с вероятностями 0.5; 0.5, то при стратегии первого игрока среднее значение его проигрыша будет:

а при стратегии первого игрока

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

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

Дадим более строгое определение чистых и смешанных стратегий.

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

Обозначим частоту использования чистой стратегии первого игрока через , (вероятность использования i-ой стратегии). Аналогично обозначим частоту использования чистой стратегии второго игрока через , (вероятность использования j-ой стратегии). Для игры с седловой точкой существует решение в чистых стратегиях . Для игры без седловой точки существует решение в смешанных стратегиях, то есть когда выбор стратегии осуществляется на основании вероятностей. Тогда

Множество чистых стратегий 1-го игрока;

Множество смешанных стратегий 1-го игрока;

Множество чистых стратегий 2-го игрока;

Множество смешанных стратегий 2-го игрока.

Рассмотрим пример: пусть имеется игра

Второй игрок выбирает вероятность . Оценим средний проигрыш второго игрока при применении им стратегий и соответственно.

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

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

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

Рассмотрим матричную игру G (3х4)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

S A =||p 1 , p 2 , ..., p m ||,

S B =||q 1 , q 2 , ..., q n ||,

где p i - вероятность применения игроком А чистой с тратегии А і ; ; q j - вероятность применения игроком В чистой стратегии B j ; .

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

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

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

Если игрок А применяет смешанную стратегию S A =||p 1 , p 2 , ..., p m ||, а игрок В смешанную стратегию S B =||q 1 , q 2 , ..., q n ||, то средний выигрыш (математическое ожидание) игрока А определяется соотношением

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

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

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

Смешанной стратегией 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 ? ? (3.5) где? и? - нижняя и верхняя цены игры. Справедлива следующая основная теорема теории игр - теорема Неймана. Каждая конечная игра имеет по крайней мере одно оптимальное решение, возможно, среди смешанных стратегий. Пусть 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: (3.6) Решая эту систему, получим оптимальную стратегию (3.7) и цену игры (3.8) Применяя теорему об активных стратегиях при отыскании SВ*- оптимальной стратегии игрока В, получаем, что при любой чистой стратегии игрока А (А1 или А2) средний проигрыш игрока В равен цене игры v, т.е. (3.9) Тогда оптимальная стратегия определяется формулами: (3.10)