Что такое смешанная стратегия

СОДЕРЖАНИЕ

Набор стратегий

В противном случае набор стратегий бесконечен. Например, игра по резке торта имеет ограниченный континуум стратегий в наборе стратегии <Вырезать где-нибудь между 0 и 100 процентами торта>.

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

Выбор набора стратегий

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

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

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

Смешанная стратегия

Иллюстрация

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

Значимость

Интерпретации смешанных стратегий

В течение 80-х годов концепция смешанных стратегий подверглась резкой критике как «интуитивно проблематичная», поскольку они представляют собой слабые равновесия по Нэшу, и игроку безразлично, следует ли ему следовать вероятности своей равновесной стратегии или отклоняться в сторону какой-либо другой вероятности. Теоретик игр Ариэль Рубинштейн описывает альтернативные способы понимания этой концепции. Первый, предложенный Харшаньи (1973), называется очищением и предполагает, что интерпретация смешанных стратегий просто отражает наше незнание информации игроков и процесса принятия решений. Очевидно, случайный выбор тогда рассматривается как следствие неуказанных, нерелевантных экзогенных факторов. Вторая интерпретация предполагает, что игроки выступают за большую популяцию агентов. Каждый из агентов выбирает чистую стратегию, и выигрыш зависит от доли агентов, выбирающих каждую стратегию. Таким образом, смешанная стратегия представляет собой распределение чистых стратегий, выбранных каждой популяцией. Однако это не дает никаких оснований для случая, когда игроки являются отдельными агентами.

Стратегия поведения

Эквивалентность результата

Стратегия с идеальным отзывом

Идеальное воспоминание определяется как способность каждого игрока в игре запоминать и вспоминать все прошлые действия в игре. Для эквивалентности требуется совершенный отзыв, поскольку в конечных играх с несовершенным воспроизведением будут существовать смешанные стратегии Игрока I, в которых нет эквивалентной стратегии поведения. Это полностью описано в игре « Рассеянный водитель», сформулированной Пиччоне и Рубинштейном. Короче говоря, эта игра основана на принятии решения водителем с несовершенной памятью, которому нужно свернуть на второй съезд с шоссе, чтобы добраться до дома, но он не помнит, на каком перекрестке они находятся, когда добираются до него. Рисунок [2] описывает эту игру.

Источник

Смешанные стратегии. Основная теорема теории игр

Целесообразность случайного выбора стратегии в игре без седловой точки

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

Вернемся к примеру 2:

В этой игре нет седловой точки, так как нижняя и верхняя цена игры не совпадают. Если мы (игрок A) не имеем никакой информации о том, какую стратегию выберет противник В, то для минимизации проигрыша (максимизации выигрыша в худшем случае) нам следует руководствоваться принципом минимакса и выбирать стратегию A₁. В этом случаем мы гарантируем себе выигрыш не ниже нижней цены игры α (в данном примере не ниже –3).

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

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

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

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

Введем обозначения для смешанных стратегий. Пусть у нас (игрока A) имеется m возможных стратегий A₁, A₂, …, A_m, а у противника (игрока B) – n возможных стратегий B₁, B₂, …, B_n. Будем обозначать

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

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

Пара оптимальных стратегий образует в игре некое положение равновесия: мы хотим обратить наш выигрыш в максимум, противник – в минимум, каждый тянет в свою сторону и, при разумном поведении обоих, устанавливается равновесие и устойчивый выигрыш ν. Если ν > 0, то игра выгодна для нас, если ν

Игры с седловой точкой также подчиняются основной теореме теории игр и являются ее частным случаем. Поэтому можно сформулировать общее правило:

· Если игра имеет седловую точку, то следует придерживаться чистой оптимальной стратегии, определяемой принципом минимакса. В этом случае наш выигрыш будет равен чистой цене игры ν.

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

Решение игры с седловой точкой в чистых стратегиях находится очень просто – по матрице игры с использованием принципа минимакса.

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

Источник

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

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

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

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

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

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

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

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

Bj

Источник

Игры с нулевой суммой и условия Каруша-Куна-Таккера

В этой статье я подробностях разбираюсь с задачей поиска равновесных смешанных стратегий на примере антагонистических игр.

Пусть есть два игрока, A и B, которые многократно разыгрывают некоторую игру. Каждый игрок в каждом розыгрыше придерживается одной из нескольких стратегий — для простоты будем считать, что количество стратегий для обоих игроков совпадает и равняется . При выборе -й стратегии первым игроком и -й стратегии вторым игроком первый игрок получит выигрыш , а второй игрок получит такой же проигрыш — так уж устроены антагонистичные игры. Эти выигрыши можно записать в виде квадратной матрицы :

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

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

Вот поиском таких равновесий мы сейчас и займёмся.

1. Равновесия

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

Например, рассмотрим такую матрицу выигрышей:

В этом случае ни одна из пар чистых стратегий не является равновесием. Пусть, скажем, первый игрок выбирает первую стратегию. Тогда второй игрок хочет захочет также всегда выбирать первую стратегию: это приведёт к меньшему проигрышу (2 против 3). Но, если второй игрок выбирает первую стратегию, первый игрок предпочтёт ответить стратегией номер два: так его выигрыш будет больше (4 против 1). Однако, если первый игрок выбирает вторую стратегию, второй игрок также ответит второй: его проигрыш таким образом уменьшится (1 против 4). Но при выборе вторым игроком второй стратегии первый игрок выберет первую стратегию, и так далее. Итого, при любом выборе чистых стратегий хотя бы один из игроков может изменить свой выбор так, чтобы увеличить собственную выгоду.

Однако в пространстве смешанных стратегий равновесие найдётся. Нетрудно проверить, что равновесием в данном случае будет пара смешанных стратегий , . В таком случае математическое ожидание выигрыша для первого игрока будет равно 2.5.

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

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

При этом на сами стратегии распространяются очевидные ограничения:

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

Рассмотрим, например, следующую матрицу выигрышей:

Не вдаваясь в технические детали, скажу, что применение метода множителей Лагранжа с учётом только лишь ограничений в виде равенств

в данном случае приведёт к решению

Это происходит из-за того, что метод множителей Лагранжа не может учесть ограничения в виде неравенств. Тут-то нам и помогут условия Каруша-Куна-Таккера.

2. Условия Каруша-Куна-Таккера

Также эти условия известны как условия Куна-Таккера, а всё потому, что впервые опубликованы они были в работе 1951-го года за авторством Куна и Таккера, и лишь впоследствии обнаружилось, что Каруш уже в 1939-м году сформулировал их в неопубликованной работе.

На время отвлечёмся от теории игр и сформулируем более общую задачу оптимизации следующим образом: необходимо найти минимум некоторой функции

при условии ограничений как в виде равенств, так и в виде неравенств:

Доказывается, что тогда каждая точка, являющаяся решением оптимизационной задачи, удовлетворяет условиям Каруша-Куна-Таккера:

Здесь первое условие очень похоже на соответствующие условие в методе множителей Лагранжа; последние два условия фактически дублируют ограничения исходной оптимизационной задачи.

Второе и третье условия — хитрые. Вместе с условием четыре они означают следующее:

Теперь возникает вопрос о том, а как, собственно, решать такую систему уравнений. Как правило, можно поступать следующим образом:

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

3. Условия ККТ для антагонистических игр

Выше я записал условия ККТ для задачи минимизации. Поэтому нужно сформулировать все условия в терминах задачи минимизации, плюс нужно соблюсти формальность и переписать условия в виде неравенств так, чтобы они были записаны в виде «меньше либо равно нулю».

Условия для :

Условия для :

Теперь выпишем лагранжианы:

Теперь запишем оставшиеся условия Каруша-Куна-Таккера, местами преобразовав в более удобный вид. Для :

Для :

Приравнивая производные лагранжианов нулю, получим следующую систему уравнений:

Здесь переменных и уравнений. Используем теперь условия:

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

Из всех решений нужно будет выбрать только те, которые удовлетворяют оставшимся ограничениям Каруша-Куна-Таккера:

В полученном множестве решений обязательно окажется искомое равновесие.

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

Мы знаем, что может равняться нулю, в таком случае уравнение принимает вид

Если же в соответствии с выбором не равняется нулю, эта неизвестная просто выражается через значения вектора и значение :

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

А ограничения становятся тривиальными:

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

5. В поисках равновесия

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

Но проверять это свойство для всех возможных альтернативных смешанных стратегий, конечно, не получится. Нам на помощь приходит тот факт, что среди множества найденных решений обязательно находится равновесие. Это значит, что проверить равновесность можно лишь сравнениями с другими полученными решениями. Подробнее: пусть — все найденные решения. Пара является равновесием тогда и только тогда, когда

6. Реализация

Весь код реализации я сложил к себе на GitHub: https://github.com/ashagraev/zero_sum_game

В matrix.h лежит простой утилитарный код: прочитать матрицу, транспонировать матрицу, решить СЛАУ. Для решения СЛАУ я использую простейший метод Гаусса с выбором ведущего элемента и тривиальной проверкой на вырожденность. Эту можно было бы реализовать и получше, но суть не в ней.

Реализация описанного алгоритма для решения набора СЛАУ находится в файле kkt.cpp. Для генерации подмножеств используются коды Грея. Чтобы подружить рекурсивный метод генерации кодов Грея с последовательной их обработкой, пришлось немного покуражиться с callback’ами.

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

Источник