Возможная игра - Potential game

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

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

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

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

Определение

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

Игра ${displaystyle G = (N, A = A_ {1} imes ldots imes A_ {N}, u: Aightarrow mathbb {R} ^ {N})}$ является:

• ан точная потенциальная игра если есть функция ${displaystyle Phi: Aightarrow mathbb {R}}$ такой, что ${displaystyle forall {a _ {- i} в A _ {- i}}, forall {a '_ {i}, a' '_ {i} в 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: Aightarrow mathbb {R}}$ и вектор ${displaystyle win mathbb {R} _ {++} ^ {N}}$ такой, что ${displaystyle forall {a _ {- i} в A _ {- i}}, forall {a '_ {i}, a' '_ {i} в 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: Aightarrow mathbb {R}}$ такой, что ${displaystyle forall {a _ {- i} в A _ {- i}}, forall {a '_ {i}, a' '_ {i} в A_ {i}}}$,

${displaystyle u_ {i} (a '_ {i}, a _ {- i}) - u_ {i} (a' '_ {i}, a _ {- i})> 0Стрелка влево Фи (a' _ {i} , a _ {- i}) - Phi (a '' _ {i}, a _ {- i})> 0}$

• а обобщенная порядковая потенциальная игра если есть функция ${displaystyle Phi: Aightarrow mathbb {R}}$ такой, что ${displaystyle forall {a _ {- i} в A _ {- i}}, forall {a '_ {i}, a' '_ {i} в A_ {i}}}$,

${displaystyle u_ {i} (a '_ {i}, a _ {- i}) - u_ {i} (a' '_ {i}, a _ {- i})> 0Rightarrow Phi (a' _ {i} , a _ {- i}) - Phi (a '' _ {i}, a _ {- i})> 0}$

• а потенциальная игра с лучшим откликом если есть функция ${displaystyle Phi: Aightarrow mathbb {R}}$ такой, что ${displaystyle forall iin 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}}$.

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

В а Игра на двоих, игра на двоих с экстерналиями, выигрыши отдельных игроков задаются функцией ты_я(s_я, s_j) = б_я s_я + ш s_я s_j, куда s_я стратегия игроков i, s_j стратегия оппонента, и ш является а положительный внешность от выбора той же стратегии. Варианты стратегии: +1 и -1, как показано на матрица выплат на рисунке 1.

В этой игре есть а потенциальная функция П(s₁, s₂) = б₁ s₁ + б₂ s₂ + ш s₁ s₂.

Если игрок 1 переходит с -1 на +1, разница в выплатах равна Δты₁ = ты₁(+1, s₂) – ты₁(–1, s₂) = 2 б₁ + 2 ш s₂.

Изменение потенциала ΔP = P (+1, s₂) - P (–1, s₂) = (б₁ + б₂ s₂ + ш s₂) – (–б₁ + б₂ s₂ – ш s₂) = 2 б₁ + 2 ш s₂ = Δты₁.

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

+1 –1 +1 +б1+ш, +б2+ш +б1–ш, –б2–ш –1 –б1–ш, +б2–ш –б1+ш, –б2+ш Рис.1: Возможный пример игры

+1 –1 +1 5, 2 –1, –2 –1 –5, –4 1, 4 Рис.2: Битва полов (выплаты)

+1 –1 +1 4 0 –1 –6 2 Рис.3: Битва полов (потенциалы)

Игра для 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, Пончиковый мир и архипелаг дуополии,Экономика серфинга.