Возможная игра

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

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

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

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

Определение [ править ]

Дадим некоторые обозначения, необходимые для определения. Пусть будет количеством игроков, набором профилей действий над наборами действий каждого игрока и функцией выигрыша.${\ displaystyle N}$${\ displaystyle A}$${\ displaystyle A_ {i}}$${\ displaystyle u}$

Игра это:${\ Displaystyle G = (N, A = A_ {1} \ times \ ldots \ times A_ {N}, u: A \ rightarrow \ mathbb {R} ^ {N})}$

• точный потенциал игры , если есть функция такая , что ,${\ displaystyle \ Phi: A \ rightarrow \ mathbb {R}}$${\ displaystyle \ 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: A \ rightarrow \ mathbb {R}}$${\ Displaystyle ш \ ин \ mathbb {R} _ {++} ^ {N}}$${\ displaystyle \ 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}))}$

• порядковое потенциал игры , если есть функция такая , что ,${\displaystyle \Phi :A\rightarrow \mathbb {R} }$${\displaystyle \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 :A\rightarrow \mathbb {R} }$${\displaystyle \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 \Phi :A\rightarrow \mathbb {R} }$${\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}}$

Простой пример [ править ]

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

Эта игра имеет на потенциальную функции P ( ₁ , ₂ ) = Ь _{- 1} + Ь _{- 2} + ш в _{1 2} .

Если игрок 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 а ₂ ) знак равно 2 б ₁ + 2 вес а ₂ = Δ u ₁ .

Решение для игрока 2 эквивалентно. Используя численные значения Ь ₁  = 2 , б ₂  = -1 , ш  = 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)]}$

См. Также [ править ]

• Игра с перегрузкой
• Эконофизика

Ссылки [ править ]

Внешние ссылки [ править ]

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