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

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

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

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

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

Определение

Мы определим некоторые обозначения, необходимые для определения. Позвольте быть количеством игроков, набором профилей действий над наборами действий каждого игрока и функцией выигрыша. ${\ 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 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: A \ rightarrow \ mathbb {R}}$${\ Displaystyle ш \ в \ 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}))}$

• порядковое потенциал игры , если есть функция такая , что ,${\ displaystyle \ Phi: A \ rightarrow \ mathbb {R}}$${\ 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: A \ rightarrow \ mathbb {R}}$${\ 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 \ 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 a ₂ ) знак равно 2 b ₁ + 2 w a ₂ = Δ u ₁ .

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

+1 –1 +1 + b 1 + w , + b 2 + w + b 1 - w , - b 2 - w –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, Пончиковый мир и архипелаг дуополии , Surfing Economics .