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

редактировать

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

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

Содержание

1 Формальное определение
2 Размер представления игры
3 Пример
4 Равновесие Нэша
5 Дополнительная литература

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

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

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

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

Пример

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

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

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

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

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

Дополнительная литература

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