Симметричная декомпозиция асимметричных игр.

Содержание: [Показать]

Мы вводим новые теоретические идеи в асимметричные игры с двумя популяциями, позволяющие элегантно разложить их на две симметричные игры с одной популяцией. В частности, мы показываем, как асимметричная биматричная игра ( A, B) может быть разложена на ее симметричные аналоги, представляя и исследуя таблицы выплат ( Aи B), которые составляют асимметричную игру, как две независимые, симметричные игры с одной популяцией. Мы обнаруживаем несколько удивительных формальных взаимосвязей между асимметричной игрой с двумя популяциями и ее симметричными аналогами с одной популяцией, которые облегчают удобный анализ исходной асимметричной игры из-за уменьшения размерности разложения. Основной вывод показывает, что если(x, y)- это равновесие по Нэшу в асимметричной игре ( A, B), это означает, что y- это равновесие по Нэшу для симметричной партнерской игры, определяемой таблицей выплат A, а x- это равновесие по Нэшу для симметричной партнерской игры, определенной с помощью таблицы выигрышей B. Также имеет место обратное, и комбинации равновесий по Нэшу в играх-аналогах образуют равновесия по Нэшу в асимметричной игре. Мы проиллюстрируем, как эти формальные отношения помогают в идентификации и анализе структуры Нэша асимметричных игр, исследуя эволюционную динамику более простых двойных игр на нескольких канонических примерах.

Вступление

Мы заинтересованы в анализе структуры Нэша и эволюционной динамики стратегических взаимодействий в многоагентных системах. Традиционно такие взаимодействия изучались с использованием моделей динамики репликатора одной популяции, которые ограничены симметричными ситуациями, т. Е. Игроки имеют доступ к одному и тому же набору стратегий, а структура выплат также симметрична 1. Например, Уолш и др.. представить методологию эмпирической теории игр (также называемую методом эвристической таблицы выплат), которая позволяет анализировать многоагентные взаимодействия в сложных многоагентных играх 2,3. Этот метод был расширен другими и применялся, например, в непрерывных двойных аукционах, вариантах покера и системах с несколькими роботами 1,4,5,6,7,8,9. Подобные эволюционные методы были применены к моделированию человеческого сотрудничества, языка и сложных социальных дилемм 10,11,12,13,14,15,16. Хотя эти эволюционные методы были очень полезны для понимания типа и формы взаимодействий в таких системах, лежащей в основе структуры Нэша и эволюционной динамики, анализ ограничен симметричными ситуациями, т. Е. Игроки или агенты могут меняться местами и иметь доступ. к тому же набору стратегий,Другими словами, нет разных ролей для различных агентов, участвующих во взаимодействии (например, продавец против покупателя на аукционе). Как таковой, этот метод не применим напрямую к асимметричным ситуациям, в которых игроки могут выбирать стратегии из различных наборов действий с асимметричными структурами выплат. Многие интересные многоагентные сценарии включают асимметричные взаимодействия, примеры включают простые игры из теории игр, такие как, например, Ultimatum Game или Battle of the Sexes, и более сложные настольные игры, которые могут включать в себя различные роли, такие как Скотланд-Ярд, но также и торговать в Интернете для экземпляр можно считать асимметричным.Как таковой, этот метод не применим напрямую к асимметричным ситуациям, в которых игроки могут выбирать стратегии из различных наборов действий с асимметричными структурами выплат. Многие интересные многоагентные сценарии включают асимметричные взаимодействия, примеры включают простые игры из теории игр, такие как, например, Ultimatum Game или Battle of the Sexes, и более сложные настольные игры, которые могут включать в себя различные роли, такие как Скотланд-Ярд, но также и торговать в Интернете для экземпляр можно считать асимметричным.Как таковой, этот метод не применим напрямую к асимметричным ситуациям, в которых игроки могут выбирать стратегии из различных наборов действий с асимметричными структурами выплат. Многие интересные многоагентные сценарии включают асимметричные взаимодействия, примеры включают простые игры из теории игр, такие как, например, Ultimatum Game или Battle of the Sexes, и более сложные настольные игры, которые могут включать в себя различные роли, такие как Скотланд-Ярд, но также и торговать в Интернете для экземпляр можно считать асимметричным.Игра «Ультиматум» или «Битва полов» и более сложные настольные игры, которые могут включать в себя различные роли, такие как Скотланд-Ярд, но также и торговля в Интернете, например, могут считаться асимметричными.Игра «Ультиматум» или «Битва полов» и более сложные настольные игры, которые могут включать в себя различные роли, такие как Скотланд-Ярд, но также и торговля в Интернете, например, могут считаться асимметричными.

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

Анализ многоагентных взаимодействий с использованием эволюционной динамики или динамики репликаторов не только дает ценную информацию о (Нэш) равновесиях и их свойствах устойчивости, но также проливает свет на траектории поведения вовлеченных агентов и бассейны притяжения равновесного ландшафта 1, 4,15,17,18. Как таковой, он может быть очень полезным инструментом для анализа структуры и динамики нескольких взаимодействующих агентов в многоагентной системе. Однако при работе с асимметричными играми анализ быстро становится утомительным, так как в этом случае у нас есть связанная система уравнений репликатора, и изменения в поведении одного агента немедленно изменяют динамику в связанном уравнении репликатора, описывающем поведение другого агента. , наоборот. Эта статья проливает новый свет на асимметричные игры,и раскрывает ряд ранее неизвестных теорем, которые позволяют проводить более элегантный анализ асимметричных многоагентных игр. Основное нововведение заключается в том, что мы разделяем асимметричные игры на ихсимметричные аналоги, которые могут быть изучены симметричным способом с использованием симметричной динамики репликатора. Равновесия по Нэшу этих симметричных аналогов формально связаны с равновесиями по Нэшу исходной асимметричной игры и, как таковые, предоставляют нам средства для анализа асимметричной игры с использованием ее симметричных аналогов. Обратите внимание, что мы не рассматриваем асимметричную динамику репликатора, в которой происходят как внутривидовые (внутри популяции), так и межвидовые взаимодействия (между разными популяциями) 19, но мы рассматриваем только межвидовые взаимодействия, в которых взаимодействуют две разные роли, т. Е. , действительно асимметричные игры 20.

Один из наших основных выводов состоит в том, что стратегии x(игрок 1) и стратегии y(игрок 2) смешанного равновесия по Нэшу с полной поддержкой в ​​исходной асимметричной игре также составляют равновесия по Нэшу в симметричных играх-аналогах. Симметричный аналог игрока 1 ( x) определяется выигрышем игрока 2 и наоборот. Мы доказываем, что для полных поддерживающих стратегий равновесия по Нэшу асимметричной игры являются попарными комбинациями равновесий по Нэшу двух симметричных аналогов. Затем мы покажем, что это свойство остается в силе без предположения о полной поддержке. Хотя этот анализ не позволяет нам визуализировать эволюционную динамику самой асимметричной игры, он позволяет нам идентифицировать ее равновесие по Нэшу, исследуя эволюционную динамику аналогов. Таким образом, мы можем легко отличить равновесия по Нэшу от других точек привязки в асимметричной игре и получить понимание лежащей в основе структуры Нэша.

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

Связанных с работой

Самый простой и классический подход к асимметричным играм - рассматривать агентов как развивающиеся отдельно: одна популяция на игрока, где каждый агент в популяции взаимодействует, играя против агентов из другой популяции (групп), т. Е. Коэволюция 21. Это предполагает, что игроки этих игр всегда фундаментально привязаны к одной роли и никогда не должны знать / понимать, как играть в качестве другого игрока. Однако во многих случаях игрок может захотеть узнать, как играть за любого из них. Например, хороший шахматист должен уметь играть белыми или черными. Это рассуждение вдохновило на ролевую симметризацию асимметричных игр 22.

Ролевая симметризация произвольной биматричной игры определяет новую (расширенную) игру, в которой перед выбором действий роли двух игроков определяются равномерно случайным образом. Если доступны две роли, агенту назначается одна конкретная роль с вероятностью \ (\ frac \). Затем агент играет в игру под этой ролью и соответствующим образом собирает вознаграждение, зависящее от роли. Определяется новое пространство стратегий, которое является продуктом пространств стратегий обоих игроков, и новая матрица выплат, вычисляющая (ожидаемые) выплаты для каждой комбинации чистых стратегий, которые могут возникнуть при различных ролях. Существуют отношения между наборами эволюционно устойчивых стратегий и точками покоя динамики репликатора между исходной и симметризованной игрой 19,23.

Эта модель одной популяции вынуждает игроков быть общими: они могут разрабатывать стратегию для каждой роли, что может излишне усложнять алгоритмы, вычисляющие стратегии для таких игроков. В общем случае матрица выигрыша в результирующей ролевой симметризации равна n! ( n- количество агентов) раз больше из-за количества перестановок назначений ролей игроков. Существуют варианты с двумя популяциями, которые формулируют проблему несколько иначе: новая матрица, которая инкапсулирует полезности обоих игроков, присваивает 0 полезность комбинациям ролей, которые не находятся во взаимно однозначном соответствии с игроками 24. Однако это тоже приводит к излишне большей (хотя и разреженной) матрице.

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

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

Предварительные сведения и методы

В этом разделе мы кратко обрисовываем (эволюционные) теоретико-игровые концепции, необходимые для понимания оставшейся части статьи 23,26,27. Мы кратко даем определения игр нормальной формы и концепций решения, таких как равновесие по Нэшу, в игре с одной популяцией и в игре с двумя популяциями. Кроме того, мы вводим уравнения динамики репликатора (RD) для игр с одной и двумя популяциями и кратко обсуждаем концепцию эволюционных стабильных стратегий (ESS), введенную Смитом и Прайсом в 1973 г. 28,29,30.

Игры нормальной формы и равновесие по Нэшу

Определение. Двух игроков Нормальная форма игры( НФГ) G представляет собой 4- кортеж G= ( S1 , S2 , , Б), с чистыми наборами стратегии S1 и S2 для игрока 1, соответственно игрока 2, и соответствующего выигрыша таблицы а и В. Оба игрока выбирают свои чистые стратегии( также называются действиями) одновременно.

Выплаты для обоих игроков представлены биматрицей ( A, B), которая дает выигрыш для игрока строки в Aи игрока столбца в B(см. Таблицу 1 для примера двух стратегий). В частности, игрок строки выбирает одну из двух строк, игрок столбца выбирает один из столбцов, и результат их совместной стратегии определяет выигрыш для обоих.

В случае , если S1 = S2 и A= BТигроки являются взаимозаменяемыми , и мы называем игру симметричным. Если хотя бы одно из этих условий не выполняется, мы получаем асимметричную игру. В классической теории игр игроки считаются индивидуально рациональными в том смысле, что каждый игрок совершенно логичен, пытаясь максимизировать свой выигрыш, при условии, что другие поступают так же. При таком предположении концепция решения равновесия по Нэшу (NE) может быть использована для изучения того, что игроки разумно предпочтут делать.

Обозначим профиль стратегии двух игроков набором ( x, y) ∈ Δ S1 × Δ S2 , где Δ S1 , Δ S2 - множества смешанных стратегий, то есть распределения по множествам чистых стратегий или наборы действий. Стратегия x(соответственно y) представлена ​​как вектор в \ ( >>^ _ |>\) (соответственно \ ( >>^ _ |>\)), где каждая запись - это вероятность совершения соответствующего действия. Выигрыш, связанный с игроком 1, равен xTAy,а xTBy- это выигрыш, связанный с игроком 2. Профиль стратегии ( x, y) теперь формирует NE, если ни один отдельный игрок не может добиться большего за счет одностороннего переключения на другую стратегию. Другими словами, каждая стратегия в сетевом элементе является лучшим ответом на все другие стратегии в этом равновесии. Формально у нас есть

Определение. Профиль стратегии( x, y) является равновесием по Нэшу, если выполняется следующее:

Далее через NE( A, B) обозначим множество состояний равновесия по Нэшу игры G= ( S1 , S2 , A, B). Кроме того, равновесие по Нэшу называется чистым, если разыгрывается только одна стратегия из набора стратегий, и мы будем говорить, что оно полностью смешано, если все чистые стратегии разыгрываются с ненулевой вероятностью.

В эволюционной теории игр часто рассматриваются игры с одной популяцией. Другими словами, игрок играет против самого себя, и для определения игры необходима только одна таблица выплат A(обратите внимание, что это определение имеет смысл только тогда, когда | S1 | = | S2 | = n). В этом случае выигрыш, полученный игроком, равен xTAx,и следующее определение описывает равновесие по Нэшу:

Определение. В одной игре населения, стратегия х является равновесием Нэша, тогда и только тогда имеет место следующее:

В этом случае единственной популяции мы напишем, что xNE( A).

Репликатор Динамика

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

Каждый репликатор представляет одну (чистую) стратегию i. Эта стратегия наследуется всеми потомками репликатора. xiпредставляет собой плотность стратегии iв популяции, A- это матрица выигрыша, которая описывает различные значения выигрыша, которые получает каждый отдельный репликатор при взаимодействии с другими репликаторами в популяции. Состояние популяции хможет быть описано как вектор вероятности х= ( х1 , х2 ,. Хп) , который выражает различные плотности всех различных типов репликаторов в популяции. Следовательно ( Ax) i- это выигрыш, который репликатор iполучает в популяции с состоянием x,а xTAxописывает средний выигрыш в популяции. Опора Ixстратегии - это набор действий (или чистых стратегий), которые выполняются с ненулевой вероятностью Ix= < i| хя>0>.

По сути, это уравнение сравнивает выигрыш, который получает стратегия, со средним выигрышем для всего населения. Если оценка стратегии выше среднего, она сможет воспроизвести потомство, если оценка ниже среднего, ее присутствие в популяции уменьшится и потенциально приблизится к исчезновению. Население остается в симплексе (∑ ixi= 1), поскольку ∑ i( dxi) / ( dt) = 0.

Эволюционно стабильные стратегии

Первоначально стратегия эволюционной стабильности была введена в контексте симметричной игры с одним населением 28,32 (как было введено в предыдущем разделе), хотя ее можно распространить на игры с участием нескольких популяций, а также определить в следующем разделе 23,33. . Представьте себе группу простых агентов, играющих одну и ту же стратегию. Предположим, что в эту популяцию вторглась другая стратегия, которой изначально придерживается небольшая часть всего населения. Если репродуктивный успех новой стратегии меньше, чем исходная, она не будет отменять исходную стратегию и в конечном итоге исчезнет. В этом случае мы говорим, что стратегия эволюционно устойчива.(ESS) против этой недавно появившейся стратегии. В общем, мы говорим, что стратегия является ESS, если она устойчива против эволюционного давления со стороны любого появляющегося мутантного репликатора, еще не присутствующего в популяции (или только с очень небольшой долей).

Асимметричная динамика репликатора

Мы предположили, что репликаторы происходят из одной популяции, что делает модель применимой только к симметричным играм. Теперь можно задаться вопросом, как предыдущие введенные уравнения распространяются на асимметричные игры. Симметрия предполагает, что наборы стратегий и соответствующие выплаты одинаковы для всех участников взаимодействия. Примером асимметричной игры является знаменитая игра «Битва полов» (BoS), показанная в таблице 2. В этой игре оба игрока имеют одинаковый набор стратегий, то есть пойти в оперу или в кино, однако соответствующие выплаты для каждого из них различны, выражая разницу в предпочтениях, которые имеют оба игрока в своих ролях.

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

с таблицами выплат Aи B, соответственно, для игроков 1 и 2. В случае A= BTуравнения сводятся к модели единой популяции.

Симметричный аналог репликатора Dynamics

Теперь мы вводим новую концепцию, симметричнуюдинамику репликатора (SCRD) асимметричных репликаторных уравнений. Мы рассматриваем две таблицы выплат Aи Bкак две независимые игры, которые больше не связаны и в которых участвуют оба игрока. В первой игре-аналоге все игроки выбирают свою стратегию в соответствии с распределением y, исходной стратегией или распределением репликаторов для 2-й популяции или игрока 2, а во второй игре-аналоге все игроки выбирают свою стратегию в соответствии с распределением x, исходной стратегией или Распределение репликатора для 1-й популяции или игрока 1. Это дает нам следующие два набора уравнений репликатора:

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

Визуализация эволюционной динамики

Можно визуализировать динамику репликатора в поле направлений и графике траектории, который предоставляет полезную информацию о равновесиях, потоках динамики и бассейнах притяжения. Пока мы остаемся в сфере игр для двоих и двух действий, этого можно относительно легко добиться, построив на оси x вероятность, с которой игрок 1 совершит свое первое действие, и вероятность, с которой игрок 2 сыграет свое первое действие. действие по оси ординат. Поскольку у каждого игрока есть только 2 действия, это сразу дает полное представление о динамике всех стратегий, поскольку вероятность выбора второго действия a2 равна единице минус первое. В качестве примера мы показываем здесь диаграмму направленного поля для известной игры «Дилемма заключенного» (игра проиллюстрирована в Таблице 3).

График поля направлений и соответствующие траектории показаны на рис. 1. Для обоих игроков ось представляет вероятность, с которой они разыграют Дефект(D). Как можно заметить, вся динамика поглощается чистым равновесием по Нэшу ( D, D), в котором оба игрока проигрывают.

Направленный полевой сюжет игры Prisoner's Dilemma.

К сожалению, мы не можем использовать один и тот же тип графика, иллюстрирующий динамику, когда мы рассматриваем более двух стратегий. Однако, если мы перейдем к играм с одним населением, мы легко сможем полагаться на симплексный сюжет. В случае игры с двумя популяциями ситуация становится утомительной, о чем мы поговорим позже. В частности, множество вероятностных распределений над пэлементов может быть представлено множество векторов ( х1 ,. Хп) \ (\ в \, >>^ \), Удовлетворяющий й 1 ,. x n≥ 0 и ∑ i x i= 1. Это соответствует n- 1-мерной структуре, называемой симплексом Σ n(или просто Σ, когда nясно из контекста). На многих рисунках в статье мы используем Σ 3 , спроектированный как равносторонний треугольник. Например, рассмотрим игру « Камень-ножницы-бумага» дляодной популяции , описанную матрицей выигрышей, показанной на рис. 2а.

( а) Матрица выплат для игры «Камень-ножницы-бумага». Стратегии R, Sи Pсоответствуют игре соответственно Rock, Scissors, Paper. ( b) Σ 3 Сюжет траектории игры «Камень-ножницы-бумага». Равновесие по Нэшу отмечено сплошной желтой точкой.