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

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

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

Формальное определение [ править ]

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

Размер представления игры [ править ]

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

Пример [ править ]

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

• 

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

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

Равновесие Нэша [ править ]

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

Дальнейшее чтение [ править ]

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