Теория графических игр
-
Основы графических игр
- Графическая форма игры представляет собой компактное представление, использующее взаимодействие между игроками.
- Игроки представлены узлами на графе, где функция полезности зависит от стратегии и соседей.
-
Размер представления
- Размер представления в нормальной форме равен O(m^n), в то время как графическое представление имеет размер O(m^d), где d — максимальная степень узла.
- При d << n графическое представление значительно меньше.
-
Пример графической игры
- В случае, когда полезность зависит только от одного соседа, размер представления равен O(m^2).
-
Равновесие Нэша и поиск
- Поиск равновесия Нэша в графической форме занимает экспоненциальное время, но в случае дерева может быть выполнен за полиномиальное время.
- Задача поиска равновесия в общем случае NP-полна.
-
Дополнительная литература
- Статья Майкла Кернса и его коллег (2001) о графических моделях для теории игр.
Полный текст статьи: