Краткая игра

Смотрите также: Теория игр § Альтернативные представления игр.

Рассмотрим игру трех игроков I,II и III, столкнувшихся соответственно со стратегиями {T,B}, {L,R} и {l,r}. Без дальнейших ограничений, 3*2 3 Для описания такой игры потребуется =24 значения полезности.
	Л , л	Л , р	Р , л	Р , р
Т	4 , 6 , 2	5 , 5 , 5	8 , 1 , 7	1 , 4 , 9
Б	8 , 6 , 6	7 , 4 , 7	9 , 6 , 5	0 , 3 , 0
Для каждого профиля стратегии сначала указывается полезность первого игрока ( красный ), за ней следуют полезности второго игрока ( зеленый ) и третьего игрока ( синий ).

В алгоритмической теории игр сжатая игра или лаконично представимая игра — это игра, которая может быть представлена ​​в размере, намного меньшем, чем ее представление в нормальной форме . Не налагая ограничений на утилиты игрока, описывая игру $n$ игроки, каждый лицом к $s$ стратегии , требует листинга $ns^{n}$ утилитарные ценности. Даже тривиальные алгоритмы способны найти равновесие Нэша время за полиномиальное от длины такого большого входного сигнала. Сжатая игра имеет полиномиальный тип , если в игре, представленной строкой длины n, число игроков, а также количество стратегий каждого игрока ограничено полиномом от n (формальное определение, описывающее краткие игры как вычислительную задачу , дано Papadimitriou & Roughgarden 2008). ).

Виды кратких игр

Графические игры

Скажем, что полезность каждого игрока зависит только от его собственного действия и действия другого игрока — например, I зависит от II, II от III и III от I. Для представления такой игры потребовались бы всего три таблицы полезностей 2x2, содержащие все всего 12 значений полезности. л Р Т 9 8 Б 3 4 л р л 6 8 Р 1 3 Т Б л 4 4 р 5 7

Графические игры — это игры, в которых полезность каждого игрока зависит от действий очень небольшого числа других игроков. Если $d$ — наибольшее число игроков, действия которых затрагивают любого отдельного игрока (т. е. это степень графа игры), количество значений полезности, необходимых для описания игры, равно $ns^{d+1}$, что для небольшого $d$ это значительное улучшение.

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

Редкие игры

Когда большинство утилит равны 0, как показано ниже, легко получить краткое представление.
	Л , л	Л , р	Р , л	Р , р
Т	0 , 0 , 0	2 , 0 , 1	0 , 0 , 0	0 , 7 , 0
Б	0 , 0 , 0	0 , 0 , 0	2 , 0 , 3	0 , 0 , 0

Разреженные игры — это игры, в которых большая часть полезностей равна нулю. Графические игры можно рассматривать как частный случай разреженных игр.

Для игры двух игроков разреженная игра может быть определена как игра, в которой каждая строка и столбец двух матриц выигрыша (полезности) имеет не более постоянного количества ненулевых элементов. Было показано, что найти равновесие Нэша в такой разреженной игре сложно с точки зрения PPAD и что не существует полностью полиномиальной схемы аппроксимации, если PPAD не находится в P .

Симметричные игры

Предположим, что все три игрока одинаковы (мы раскрасим их всех в фиолетовый цвет ) и сталкиваются с набором стратегий {T,B}. Пусть #TP и #BP — количество игроков, выбравших T и B соответственно. Для описания этой игры требуется всего 6 значений полезности. #ТП=2 #BP=0 #ТП=1 #БП=1 #ТП=0 #БП=2 Т 5 2 2 Б 1 7 2

В симметричных играх все игроки одинаковы, поэтому при оценке полезности комбинации стратегий имеет значение только то, сколько из них $n$ игроки играют в каждую из $s$ стратегии. Таким образом, для описания такой игры необходимо указать лишь $s{\tbinom {n+s-2}{s-1}}$ утилитарные ценности.

В симметричной игре с двумя стратегиями всегда существует чистое равновесие по Нэшу, хотя симметричное чистое равновесие по Нэшу может не существовать. Задача нахождения чистого равновесия по Нэшу в симметричной игре (возможно, с более чем двумя игроками) с постоянным числом действий заключается в AC ⁰ ; однако когда количество действий растет с числом игроков (даже линейно), задача становится NP-полной. В любой симметричной игре существует симметричное равновесие . В симметричной игре n игроков, столкнувшихся с k стратегиями, симметричное равновесие может быть найдено за полиномиальное время, если k = $O(\log n/\log \log n)$. Нахождение коррелированного равновесия в симметричных играх может быть выполнено за полиномиальное время.

Анонимные игры

Если бы игроки были разными, но не делали различий между другими игроками, нам нужно было бы перечислить 18 значений полезности для представления игры — одну таблицу, подобную той, что приведена выше для «симметричных игр» для каждого игрока. #ТП=2 #BP=0 #ТП=1 #БП=1 #ТП=0 #БП=2 Т 8 , 8 , 2 2 , 9 , 5 4 , 1 , 4 Б 6 , 1 , 3 2 , 2 , 1 7 , 0 , 6

В анонимных играх игроки имеют разные утилиты, но не делают различий между другими игроками (например, им приходится выбирать между «пойти в кино» и «пойти в бар», заботясь только о том, насколько многолюдно будет каждое место, а не о том, с кем они встретятся). там). В такой игре полезность игрока снова зависит от того, сколько его коллег выберут какую стратегию, причем его собственную, поэтому $sn{\tbinom {n+s-2}{s-1}}$ необходимы значения полезности.

Если количество действий растет с числом игроков, найти чистое равновесие Нэша в анонимной игре будет NP-трудно . Оптимальное коррелированное равновесие анонимной игры может быть найдено за полиномиальное время. Когда количество стратегий равно 2, существует известная PTAS для нахождения ε-приблизительного равновесия по Нэшу .

Полиматричные игры

Если бы рассматриваемая игра была полиматричной игрой, для ее описания потребовалось бы 24 значения полезности. Для простоты рассмотрим полезности только игрока I (нам понадобится еще по две такие таблицы для каждого из остальных игроков). л Р Т 4 , 6 8 , 7 Б 3 , 7 9 , 1 л р Т 7 , 7 1 , 6 Б 8 , 6 6 , 4 л р л 2 , 9 3 , 3 Р 2 , 4 1 , 5 Если бы был выбран профиль стратегии (B,R,l), полезность игрока I была бы 9+8=17, полезность игрока II была бы 1+2=3, а полезность игрока III была бы 6+4=10.

В полиматричной игре (также известной как многоматричная игра существует матрица полезности ) для каждой пары игроков (i,j) , обозначающая компонент полезности игрока i. Конечная полезность игрока i представляет собой сумму всех таких компонентов. Число значений утилит, необходимых для представления такой игры, равно $O(n^{2}*s^{2})$.

Полиматричные игры всегда имеют хотя бы одно смешанное равновесие Нэша. Задача нахождения равновесия Нэша в полиматричной игре является PPAD-полной. Более того, задача нахождения постоянного приближенного равновесия Нэша в полиматричной игре также является PPAD-полной. Нахождение коррелированного равновесия в полиматричной игре может быть выполнено за полиномиальное время. Обратите внимание: даже если парные игры, в которые играют игроки, имеют чистое равновесие Нэша, глобальное взаимодействие не обязательно допускает чистое равновесие Нэша (хотя смешанное равновесие Нэша должно существовать). Проверка существования чистого равновесия по Нэшу является сильно NP-полной задачей.

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

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

Круговые игры

Давайте теперь приравняем различные стратегии игроков к логическим значениям «0» и «1», и пусть X обозначает выбор игрока I, Y — выбор игрока II и Z — выбор игрока III. Назначим каждому игроку схему: Игрок I: X ∧ (Y ∨ Z) Игрок II: X ⊕ Y ⊕ Z Игрок III: X ∨ Y Они описывают служебную таблицу ниже.
	0 , 0	0 , 1	1 , 0	1 , 1
0	0 , 0 , 0	0 , 1 , 0	0 , 1 , 1	0 , 0 , 1
1	0 , 1 , 1	1 , 0 , 1	1 , 0 , 1	1 , 1 , 1

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

Вычисление ценности схемы игры с нулевой суммой для двух игроков является EXP -полной задачей, а аппроксимация ценности такой игры с точностью до мультипликативного множителя, как известно, находится в PSPACE . Определить, существует ли чистое равновесие Нэша, сложно. $\Sigma _{2}^{\rm {P}}$-полная задача (см. Полиномиальная иерархия ).

Другие представления

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

поиска равновесия

Ниже приведена таблица некоторых известных результатов по сложности поиска определенных классов равновесий в нескольких представлениях игр. «NE» означает «равновесие по Нэшу», а «CE» — «коррелированное равновесие». n — количество игроков, а s — количество стратегий, с которыми сталкивается каждый игрок (мы предполагаем, что все игроки сталкиваются с одинаковым количеством стратегий). В графических играх d — это максимальная степень игрового графа. Ссылки см. в основном тексте статьи.

Представительство	Размер ( О (...))	Pure NE	Mixed NE	ЭТОТ	Оптимальный CE
Игра нормальной формы	$ns^{n}$	NP-полный	PPAD-полный	П	П
Графическая игра	$ns^{d+1}$	NP-полный	PPAD-полный	П	NP-жесткий
Симметричная игра	$s{\tbinom {n+s-2}{s-1}}$	NP-полный	Вычисление симметричного равновесия Нэша является PPAD-сложным для двух игроков. Вычисление несимметричного равновесия Нэша для двух игроков является NP-полным.	П	П
Анонимная игра	$sn{\tbinom {n+s-2}{s-1}}$	NP-жесткий		П	П
Полиматричная игра	$n^{2}s^{2}$	сильно NP-полный	PPAD-полный (полином для полиматрицы с нулевой суммой)	П	NP-жесткий
Схема игры		$\Sigma _{2}^{\rm {P}}$-полный
Игра с пробками		Пожалуйста, заполните		П	NP-жесткий

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

• Алгоритмическая теория игр: вычислительная сложность чистого Нэша