Графическая теория игр

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

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

Формальное определение

Графическая игра представлена ​​графом $G$, в котором каждый игрок представлен узлом, а между двумя узлами есть ребро $i$ и $j$ тогда и только тогда, когда их функции полезности зависят от стратегии, которую выберет другой игрок. Каждый узел $i$ в $G$ имеет функцию $u_{i}:\{1\ldots m\}^{d_{i}+1}\rightarrow \mathbb {R}$, где $d_{i}$ степень вершины $i$. $u_{i}$ определяет полезность игрока $i$ в зависимости от его стратегии, а также стратегии его соседей.

Размер изображения игры

Для генерала $n$ игра игроков, в которой каждый игрок имеет $m$ возможных стратегий, размер представления в нормальной форме будет равен $O(m^{n})$. Размер графического представления этой игры составляет $O(m^{d})$ где $d$ — максимальная степень узла в графе. Если $d\ll n$, то графическое представление игры намного меньше.

Пример

В случае, когда функция полезности каждого игрока зависит только от одного другого игрока:

• 
  Графическая форма описываемой игры

Максимальная степень графа равна 1, и игру можно описать как $n$ функции (таблицы) размера $m^{2}$. Таким образом, общий размер ввода будет $nm^{2}$.

Равновесие Нэша

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

Дальнейшее чтение

• Майкл Кернс (2007) « Графические игры ». В Вазирани, Виджай В .; Нисан, Ноам ; Рафгарден, Тим ; Тардос, Ева (2007). Алгоритмическая теория игр (PDF) . Кембридж, Великобритания: Издательство Кембриджского университета. ISBN  0-521-87282-0 .
• Майкл Кернс, Майкл Л. Литтман и Сатиндер Сингх (2001) « Графические модели для теории игр ».