Потенциальная игра

Игровой класс в теории игр

В теории игр игра называется потенциальной, если стимул всех игроков изменить свою стратегию можно выразить с помощью одной глобальной функции, называемой потенциальной функцией . Эта концепция возникла в статье 1996 года Дова Мондерера и Ллойда Шепли . ^[1]

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

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

Потенциальные игры можно изучать как повторяющиеся игры с состоянием, так что каждый сыгранный раунд имеет прямое последствие для состояния игры в следующем раунде. ^[2] Этот подход имеет применение в распределенном управлении, таком как распределенное распределение ресурсов, где игроки без центрального механизма корреляции могут сотрудничать для достижения глобального оптимального распределения ресурсов.

Определение

Пусть — количество игроков, набор профилей действий по наборам действий каждого игрока и — функция выигрыша для игрока . ${\displaystyle N}$ ${\displaystyle A}$ ${\displaystyle A_{i}}$ ${\displaystyle u_{i}:A\to \mathbb {R} }$ ${\displaystyle 1\leq i\leq N}$

Для игры мы говорим, что это потенциальная игра с точной (взвешенной, порядковой, обобщенной порядковой, наилучшей реакцией) потенциальной функцией, если это точная (взвешенная, порядковая, обобщенная порядковая, наилучшая реакцией, соответственно) потенциальная функция для . Здесь называется ${\displaystyle G=(N,A=A_{1}\times \ldots \times A_{N},u:A\rightarrow \mathbb {R} ^{N})}$ ${\displaystyle G}$ ${\displaystyle \Phi :A\rightarrow \mathbb {R} }$ ${\displaystyle G}$ ${\displaystyle \Phi }$

• точная потенциальная функция, если , ${\displaystyle \forall i,\forall {a_{-i}\in A_{-i}},\ \forall {a'_{i},\ a''_{i}\in A_{i}}}$

${\displaystyle \Phi (a'_{i},a_{-i})-\Phi (a''_{i},a_{-i})=u_{i}(a'_{i},a_{-i})-u_{i}(a''_{i},a_{-i})}$

То есть: когда игрок переключается с одного действия на другое , изменение потенциала равно изменению полезности этого игрока. ${\displaystyle i}$ ${\displaystyle a'}$ ${\displaystyle a''}$ ${\displaystyle \Phi }$

• взвешенная потенциальная функция, если существует вектор такой, что , ${\displaystyle w\in \mathbb {R} _{++}^{N}}$ ${\displaystyle \forall i,\forall {a_{-i}\in A_{-i}},\ \forall {a'_{i},\ a''_{i}\in A_{i}}}$

${\displaystyle \Phi (a'_{i},a_{-i})-\Phi (a''_{i},a_{-i})=w_{i}(u_{i}(a'_{i},a_{-i})-u_{i}(a''_{i},a_{-i}))}$То есть: когда игрок переключает действие, изменение равно изменению полезности игрока, умноженному на положительный вес игрока. Каждый точный PF является взвешенным PF с w _i =1 для всех i . ${\displaystyle \Phi }$

• порядковая потенциальная функция, если , ${\displaystyle \forall i,\forall {a_{-i}\in A_{-i}},\ \forall {a'_{i},\ a''_{i}\in A_{i}}}$

${\displaystyle u_{i}(a'_{i},a_{-i})-u_{i}(a''_{i},a_{-i})>0\Leftrightarrow \Phi (a'_{i},a_{-i})-\Phi (a''_{i},a_{-i})>0}$То есть: когда игрок переключает действие, знак изменения равен знаку изменения полезности игрока, тогда как величина изменения может отличаться. Каждый взвешенный ПФ является порядковым ПФ. ${\displaystyle \Phi }$

• обобщенная порядковая потенциальная функция, если , ${\displaystyle \forall i,\forall {a_{-i}\in A_{-i}},\ \forall {a'_{i},\ a''_{i}\in A_{i}}}$

${\displaystyle u_{i}(a'_{i},a_{-i})-u_{i}(a''_{i},a_{-i})>0\Rightarrow \Phi (a'_{i},a_{-i})-\Phi (a''_{i},a_{-i})>0}$То есть: когда игрок переключает действие, если полезность игрока увеличивается, то увеличивается и потенциал (но обратное не обязательно верно). Каждая порядковая ПФ является обобщенно-порядковой ПФ.

• потенциальная функция наилучшего ответа, если , ${\displaystyle \forall i\in N,\ \forall {a_{-i}\in A_{-i}}}$

${\displaystyle b_{i}(a_{-i})=\arg \max _{a_{i}\in A_{i}}\Phi (a_{i},a_{-i})}$где наилучшее действие для данного игрока . ${\displaystyle b_{i}(a_{-i})}$ ${\displaystyle i}$ ${\displaystyle a_{-i}}$

Обратите внимание, что хотя существуют функции полезности, по одной для каждого игрока, существует только одна потенциальная функция. Таким образом, через призму потенциальных функций игроки становятся взаимозаменяемыми (в смысле одного из определений выше). Из-за этой симметрии игры децентрализованные алгоритмы, основанные на общей потенциальной функции, часто приводят к сходимости (в некотором смысле) к равновесию Нэша. ${\displaystyle N}$

Простой пример

В игре с двумя игроками и двумя действиями с внешними эффектами выигрыши отдельных игроков определяются функцией u _i ( a _i , a _j ) = b _i a _i + w a _i a _j , где a _i — действие игрока i, a _j — действие противника, а w — положительный внешний эффект от выбора того же действия. Выбор действий равен +1 и −1, как показано в матрице выигрышей на рисунке 1.

Эта игра имеет потенциальную функцию P ( a ₁ , a ₂ ) = b ₁ a ₁ + b ₂ a ₂ + w a ₁ a ₂ .

Если игрок 1 переходит от −1 к +1, разница в выигрыше составляет Δ u ₁ = u ₁ (+1, a ₂ ) – u ₁ (–1, a ₂ ) = 2 b ₁ + 2 w a ₂ .

Изменение потенциала равно ΔP = P(+1, a ₂ ) – P(–1, a ₂ ) = ( b ₁ + b ₂ a ₂ + w a ₂ ) – (– b ₁ + b ₂ a ₂ – w a ₂ ) = 2 b ₁ + 2 w a ₂ = Δ u ₁ .

Решение для игрока 2 эквивалентно. Используя числовые значения b ₁  = 2 , b ₂  = −1 , w  = 3 , этот пример преобразуется в простую битву полов , как показано на рисунке 2. В игре есть два чистых равновесия Нэша, (+1, +1) и (−1, −1) . Они также являются локальными максимумами потенциальной функции (рисунок 3). Единственное стохастически устойчивое равновесие — это (+1, +1) , глобальный максимум потенциальной функции.

Игра для 2 игроков и 2 действий не может быть потенциальной игрой, если

${\displaystyle [u_{1}(+1,-1)+u_{1}(-1,+1)]-[u_{1}(+1,+1)+u_{1}(-1,-1)]=[u_{2}(+1,-1)+u_{2}(-1,+1)]-[u_{2}(+1,+1)+u_{2}(-1,-1)]}$

Потенциальные игры и игры с перегрузкой

Точные потенциальные игры эквивалентны играм с перегрузкой : Розенталь ^[3] доказал, что каждая игра с перегрузкой имеет точный потенциал; Мондерер и Шепли ^[1] доказали противоположное: каждая игра с точной потенциальной функцией является игрой с перегрузкой .

Потенциальные игры и пути улучшения

Путь улучшения (также называемый динамикой Нэша ) — это последовательность векторов стратегий, в которой каждый вектор достигается из предыдущего вектора одним игроком, переключающим свою стратегию на стратегию, которая строго увеличивает его полезность. Если игра имеет функцию обобщенного порядкового потенциала , то строго возрастает в каждом пути улучшения, поэтому каждый путь улучшения является ациклическим. Если, кроме того, в игре конечное число стратегий, то каждый путь улучшения должен быть конечным. Это свойство называется свойством конечного улучшения (FIP) . Мы только что доказали, что каждая конечная игра с обобщенным порядковым потенциалом имеет FIP. Обратное также верно: каждая конечная игра с FIP имеет функцию обобщенного порядкового потенциала. ^{[4] [ необходимо разъяснение ]} Конечное состояние в каждом конечном пути улучшения является равновесием Нэша, поэтому FIP подразумевает существование равновесия Нэша с чистой стратегией. Более того, это подразумевает, что равновесие Нэша может быть вычислено с помощью распределенного процесса, в котором каждый агент должен улучшить только свою собственную стратегию. ${\displaystyle \Phi }$ ${\displaystyle \Phi }$

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

Еще более слабым свойством является слабая ацикличность (WA) . ^[5] Это означает, что для любого начального вектора стратегии существует конечный путь наилучшего ответа, начинающийся с этого вектора. Слабая ацикличность недостаточна для существования потенциальной функции (поскольку некоторые пути улучшения могут быть циклическими), но она достаточна для существования равновесия Нэша чистой стратегии. Это подразумевает, что равновесие Нэша может быть вычислено почти наверняка с помощью стохастического распределенного процесса, в котором в каждой точке игрок выбирается случайным образом, и этот игрок выбирает наилучшую стратегию случайным образом. ^[4]

Смотрите также

• Игра в заторы
• Эконофизика
• Характеристика порядковых потенциальных игр. ^[6]

Ссылки

1. Monderer, Dov; Shapley, Lloyd (1996). «Потенциальные игры». Игры и экономическое поведение . 14 : 124–143. doi :10.1006/game.1996.0044.
2. Марден, Дж., (2012) Потенциальные игры на основе состояний http://ecee.colorado.edu/marden/files/state-based-games.pdf
3. Розенталь, Роберт В. (1973), «Класс игр, обладающих равновесием Нэша в чистой стратегии», Международный журнал теории игр , 2 : 65–67, doi : 10.1007/BF01737559, MR  0319584, S2CID  121904640.
4. Milchtaich, Igal (1996-03-01). «Игры с перегрузкой с функциями выплат, зависящими от игрока». Игры и экономическое поведение . 13 (1): 111–124. doi :10.1006/game.1996.0027. ISSN  0899-8256.
5. Янг, Х. Пейтон (1993). «Эволюция соглашений». Econometrica . 61 (1): 57–84. doi :10.2307/2951778. ISSN  0012-9682. JSTOR  2951778.
6. Voorneveld, Mark; Norde, Henk (1997-05-01). "Характеристика порядковых потенциальных игр". Игры и экономическое поведение . 19 (2): 235–242. doi :10.1006/game.1997.0554. ISSN  0899-8256. S2CID  122795041.

Внешние ссылки

• Конспект лекций Ишая Мансура о потенциальных и перегруженных играх
• Раздел 19: Вазирани, Виджай В .; Нисан, Ноам ; Рафгарден, Тим ; Тардос, Ева (2007). Алгоритмическая теория игр (PDF) . Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-87282-0.
• Нетехническое изложение Хью Диксона неизбежности сговора. Глава 8. Мир пончиков и архипелаг дуополии, экономика серфинга.