Краткая игра

Игра в алгоритмической теории игр

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

Типы кратких игр

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

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

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

Редкие игры

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

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

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

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

В симметричной игре с 2 стратегиями всегда существует чистое равновесие Нэша, хотя симметричное чистое равновесие Нэша может и не существовать. ^[7] Задача нахождения чистого равновесия Нэша в симметричной игре (возможно, с более чем двумя игроками) с постоянным числом действий находится в AC 0 ; однако, когда число действий растет с числом игроков (даже линейно), задача является NP-полной. ^[8] В любой симметричной игре существует симметричное равновесие . Если задана симметричная игра из n игроков, сталкивающихся с k стратегиями, симметричное равновесие может быть найдено за полиномиальное время, если k= . ^[9] Поиск коррелированного равновесия в симметричных играх может быть выполнен за полиномиальное время. ^[2] ${\displaystyle O(\log n/\log \log n)}$

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

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

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

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

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

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

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

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

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

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

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

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

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

Резюме сложностей нахождения равновесий

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

Примечания

1. Пападимитриу, Христос Х. (2007). «Сложность поиска равновесия Нэша». В Нисане Ноам; Рафгарден, Тим; Тардос, Ева; и др. (ред.). Алгоритмическая теория игр . Издательство Кембриджского университета. стр. 29–52. ISBN  978-0-521-87282-9.
2. Пападимитриу, Христос Х.; Рафгарден, Тим (2008). «Вычисление коррелированных равновесий в многопользовательских играх». J. ACM . 55 (3): 1–29. CiteSeerX 10.1.1.335.2634 . doi :10.1145/1379759.1379762. S2CID  53224027.  
3. Голдберг, Пол В.; Пападимитриу, Христос Х. (2006). «Сводимость среди проблем равновесия». Труды тридцать восьмого ежегодного симпозиума ACM по теории вычислений . Сиэтл, Вашингтон, США: ACM. стр. 61–70. doi :10.1145/1132516.1132526. ISBN  1-59593-134-1. Получено 25.01.2010 .
4. Готтлоб, Г.; Греко, Г.; Скарчелло, Ф. (2005). «Чистые равновесия Нэша: сложные и легкие игры». Журнал исследований искусственного интеллекта . 24 (195–220): 26–37. arXiv : 1109.2152 . doi : 10.1613/jair.1683.
5. Daskalakis, Constantinos; Fabrikant, Alex; Papadimitriou, Christos H. (2006). "Игровой мир плоский: сложность равновесий Нэша в сжатых играх". Автоматы, языки и программирование . Конспект лекций по информатике. Том 4051. С. 513–524. CiteSeerX 10.1.1.111.8075 . doi :10.1007/11786986_45. ISBN   978-3-540-35904-3.
6. Чэнь, Си; Дэн, Сяоте; Тэн, Шан-Хуа (2006). «Разреженные игры сложны». Экономика Интернета и сетей . С. 262–273. doi :10.1007/11944874_24. ISBN  978-3-540-68138-0.
7. Ченг, Ши-Фен; Ривз, Дэниел М.; Воробейчик, Евгений; Уэллман, Майкл П. (2004). Заметки о равновесии в симметричных играх . Семинар AAMAS-04 по теории игр и теории принятия решений.
8. Брандт, Феликс; Фишер, Феликс; Хольцер, Маркус (2009). «Симметрии и сложность чистого равновесия Нэша». J. Comput. Syst. Sci . 75 (3): 163–177. doi : 10.1016/j.jcss.2008.09.001 .
9. Papadimitriou, Christos H.; Roughgarden, Tim (2005). "Вычисление равновесий в многопользовательских играх". Труды шестнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . Ванкувер, Британская Колумбия: Общество промышленной и прикладной математики. стр. 82–91. ISBN  0-89871-585-7. Получено 25.01.2010 .
10. Даскалакис, Константинос; Пападимитриу, Христос Х. (2007). «Вычисление равновесия в анонимных играх». arXiv : 0710.5582v1 [cs].
11. Хоусон, Джозеф Т. (январь 1972 г.). «Равновесия полиматричных игр». Management Science . 18 (5): 312–318. doi :10.1287/mnsc.18.5.312. ISSN  0025-1909. JSTOR  2634798.
12. Рубинштейн, Авиад (2015-01-01). «Неприближенность равновесия Нэша». Труды сорок седьмого ежегодного симпозиума ACM по теории вычислений . STOC '15. Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 409–418. arXiv : 1405.3322 . doi :10.1145/2746539.2746578. ISBN 9781450335362. S2CID  14633920.
13. Апт, Кшиштоф ; Саймон, Сунил; Войтчак, Доминик (4 октября 2021 г.). «Координационные игры на взвешенных направленных графах». Математика исследования операций . 47 (2): 995–1025. arXiv : 1910.02693 . doi : 10.1287/moor.2021.1159. S2CID  203836087.
14. Кай, Ю., Кандоган, О., Даскалакис, К., и Пападимитриу, К. (2016). Полиматричные игры с нулевой суммой: обобщение минимакса. https://people.csail.mit.edu/costis/zerosum_final3.pdf
15. О. Персона https://pypi.org/project/polymatrix/
16. Ран, Мона и Шефер, Гвидо (2015) Эффективные равновесия в играх с полиматричной координацией https://arxiv.org/pdf/1504.07518.pdf
17. Фейгенбаум, Джоан; Коллер, Дафна; Шор, Питер (1995). Теоретико-игровая классификация классов интерактивной сложности. Центр по дискретной математике \& Теоретическая компьютерная наука . Получено 25.01.2010 .
18. Фортнау, Лэнс; Импальяццо, Рассел; Кабанец, Валентайн; Уманс, Кристофер (2005). «О сложности кратких игр с нулевой суммой». Труды 20-й ежегодной конференции IEEE по вычислительной сложности . IEEE Computer Society. стр. 323–332. ISBN  0-7695-2364-1. Получено 2010-01-23 .
19. Schoenebeck, Grant; Vadhan, Salil (2006). "Вычислительная сложность равновесий Нэша в кратко представленных играх". Труды 7-й конференции ACM по электронной коммерции . Энн-Арбор, Мичиган, США: ACM. стр. 270–279. doi :10.1145/1134707.1134737. ISBN  1-59593-236-4. Получено 25.01.2010 .

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

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