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

редактировать

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

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

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

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

Содержание

1 Определение
2 Простой пример
3 См. Также
4 Ссылки
5 Внешние ссылки

Определение

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

Игра $G = (N, A = A 1 ×… × AN, u: A → RN) {\ displaystyle G = (N, A = A_ {1} \ times \ ldots \ раз A_ {N}, u: A \ rightarrow \ mathbb {R} ^ {N})}$ $G = (N, A = A _ {{1}} \ times \ ldots \ times A_ {{N}}, u: A \ rightarrow \ mathbb {R} ^ {N})$ это:

точная потенциальная игра, если есть функция $Φ: A → R {\ displaystyle \ Phi: A \ rightarrow \ mathbb {R}}$ $\ Phi: A \ rightarrow \ mathbb {R}$ такой, что $∀ a - i ∈ A - i, ∀ ai ′, ai ″ ∈ A i {\ displaystyle \ forall {a _ {- i} \ in A _ {- i}}, \ \ forall {a '_ {i}, \ a' '_ {i} \ in A_ {i}}}$ $\forall {a_{{-i}}\in A_{{-i}}},\ \forall {a'_{{i}},\ a''_{{i}}\in A_{{i}}}$ ,

Φ (ai ′, a - i) - Φ (ai ″, a - i) = ui (ai ′, a - i) - ui (ai ″, 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})}

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

То есть: когда игрок

i {\ displaystyle i}

i

переключается с действия

a ′ {\ displaystyle a '}

a'

к действию

a ″ {\ displaystyle a' '}

a''

, изменение потенциала равно изменению полезности этого игрока.

a взвешенный потенциал игра, если есть функция $Φ: A → R {\ displaystyle \ Phi: A \ rightarrow \ mathbb {R}}$ $\ Phi: A \ rightarrow \ mathbb {R}$ an вектор da $w ∈ R + + N {\ displaystyle w \ in \ mathbb {R} _ {++} ^ {N}}$ $w \ in \ mathbb {R} _ {{++}} ^ {N}$ такой, что $∀ a - i ∈ A - я, ∀ ai ′, ai ″ ∈ A i {\ displaystyle \ forall {a _ {- i} \ in A _ {- i}}, \ \ forall {a '_ {i}, \ a' '_ {i} \ in A_ {i}}}$ $\forall {a_{{-i}}\in A_{{-i}}},\ \forall {a'_{{i}},\ a''_{{i}}\in A_{{i}}}$ ,

Φ (ai ′, a - i) - Φ (ai ″, a - i) = wi (ui (ai ′, a - i) - ui (ai ″, a - я)) {\ 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}))}

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

порядковая потенциальная игра, если существует функция $Φ: A → R {\ displaystyle \ Phi: A \ rightarrow \ mathbb {R}}$ $\ Phi: A \ rightarrow \ mathbb {R}$ такая, что $∀ a - i ∈ A - i, ∀ ai ′, ai ″ ∈ A i {\ displaystyle \ forall {a _ {- i} \ in A _ {- i}}, \ \ forall {a '_ {i}, \ a' '_ {i} \ in A_ {i }}}$ $\forall {a_{{-i}}\in A_{{-i}}},\ \forall {a'_{{i}},\ a''_{{i}}\in A_{{i}}}$ ,

ui (ai ′, a - i) - ui (ai ″, a - i)>0 ⇔ Φ (ai ′, a - i) - Φ (ai ″, a - i)>0 { \ 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}

$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$

a обобщенная порядковая потенциальная игра если существует функция $Φ: A → R {\ displaystyle \ Phi: A \ rightarrow \ mathbb {R}}$ $\ Phi: A \ rightarrow \ mathbb {R}$ такая, что $∀ a - i ∈ A - i, ∀ ai ′, Ai ″ ∈ A i {\ displaystyle \ forall {a _ {- i} \ in A _ {- i}}, \ \ forall {a '_ {i}, \ a' '_ {i} \ in A_ { i}}}$ $\forall {a_{{-i}}\in A_{{-i}}},\ \forall {a'_{{i}},\ a''_{{i}}\in A_{{i}}}$ ,

ui (ai ′, a - i) - ui (ai ″, a - i)>0 ⇒ Φ (ai ′, a - i) - Φ (ai ″, a - i)>0 {\ 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}

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

a потенциальная игра с наилучшим ответом, если есть функция $Φ: A → R {\ displaystyle \ Phi: A \ rightarrow \ mathbb {R}}$ $\ Phi: A \ rightarrow \ mathbb {R}$ такой, что $∀ i ∈ N, ∀ a - i ∈ A - i {\ displaystyle \ forall i \ in N, \ \ forall {a _ {- i} \ in A _ {- i}}}$ $\ forall i \ in N, \ \ forall {a _ {{- i}} \ in A_ {{-i}}}$ ,

bi (a - i) = arg ⁡ max ai ∈ A я Φ (ai, a - i) {\ displaystyle b_ {i} (a _ {- i}) = \ arg \ max _ {a_ {i} \ in A_ {i}} \ Phi ( a_ {i}, a _ {- i})}

b_ {i} (a _ {{- i}}) = \ arg \ max _ {{a_ {i} \ in A_ {i}}} \ Phi (a_ {i}, a _ {{- i}})

где $bi (a - i) {\ displaystyle b_ {i} (a _ {- i})}$ $b_ {i } (a _ {{- i}})$ - лучшее действие для игрока $i {\ displaystyle i}$ $i$ с учетом $a - i {\ displaystyle a _ {- i}}$ $a _ {{- i}}$ .

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

при игре вдвоем, Игра с двумя стратегиями с внешними эффектами, выигрыши отдельных игроков задаются функцией u i(si, s j) = b isi+ ws isj, где s i - стратегия игрока i, s j - стратегия противника, и w - положительное внешнее воздействие от выбора той же стратегии. Варианты стратегии: +1 и -1, как показано в матрице выигрыша на рисунке 1.

Эта игра имеет потенциальную функцию P (s 1, s 2) = b 1s1+ b 2s2+ ws 1s2.

Если игрок 1 перемещается с -1 на +1, разница выплат будет Δu 1 = u 1 (+1, s 2) - u 1 (–1, s 2) = 2 b 1 + 2 ws 2.

Изменение потенциала равно ΔP = P (+1, s 2) - P (–1, s 2) = (b 1 + b 2s2+ ws 2) - (–b 1 + b 2s2- ws 2) = 2 b 1 + 2 ws 2 = Δu 1.

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

	+1	–1
+1	+b1+ w, + b 2+w	+b1–w, –b 2–w
–1	–b1–w, + b 2–w	–b1+ w, –b 2+w
Рис. 1: Пример потенциальной игры

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

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

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

[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)] {\ 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)]}

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