Графическая теория игр - Graphical game theory
В теория игры, общие способы описания игры - это нормальная форма и обширная форма. Графическая форма представляет собой альтернативное компактное представление игры с использованием взаимодействия между участниками.
Рассмотрим игру с игроки с стратегии каждый. Мы представим игроков как узлы в графе, в котором каждый игрок имеет вспомогательная функция это зависит только от него и его соседей. Поскольку функция полезности зависит от меньшего числа других игроков, графическое представление будет меньше.
Формальное определение
Графическая игра представлена графиком , в котором каждый игрок представлен узлом, а между двумя узлами есть ребро и если и только если их полезные функции зависят от стратегии, которую выберет другой игрок. Каждый узел в имеет функцию , куда степень вершины . указывает полезность плеера как функция его стратегии, а также стратегии его соседей.
Размер представления игры
Для генерала игра игроков, в которой каждый игрок возможные стратегии, размер представления нормальной формы будет . Размер графического представления этой игры составляет куда - максимальная степень узла в графе. Если , то графическое представление игры намного меньше.
Пример
В случае, когда функция полезности каждого игрока зависит только от одного другого игрока:
Графическая форма описываемой игры
Максимальная степень графа равна 1, и игру можно описать как функции (таблицы) размера . Итак, общий размер ввода будет .
равновесие по Нэшу
Нахождение равновесия по Нэшу в игре занимает экспоненциальное время по размеру представления. Если графическое представление игры представляет собой дерево, мы можем найти равновесие за полиномиальное время. В общем случае, когда максимальная степень узла равна 3 и более, проблема заключается в НП-полный.
дальнейшее чтение
- Майкл Кернс (2007) "Графические игры ". В Вазирани, Виджай В.; Нисан, Ноам; Roughgarden, Тим; Тардос, Ива (2007). Алгоритмическая теория игр (PDF). Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-87282-0.
- Майкл Кернс, Майкл Л. Литтман и Сатиндер Сингх (2001) "Графические модели для теории игр ".