Оглавление
Лаконичная игра
-
Определение и сложность игр
- Игра – это математическая модель взаимодействия между игроками, где каждый игрок стремится максимизировать свою полезность.
- Равновесие по Нэшу – это набор стратегий, при котором ни один игрок не может увеличить свою полезность, изменяя свои стратегии.
- Сложность нахождения равновесия по Нэшу зависит от типа игры и количества игроков.
-
Типы игр и их сложность
- Игры с нормальной формой: сложность нахождения равновесия по Нэшу возрастает с увеличением количества игроков и стратегий.
- Графические игры: сложность нахождения равновесия Нэша NP-полная, но существуют полиномиальные алгоритмы для некоторых случаев.
- Редкие игры: сложно найти равновесие Нэша, если большинство функций полезности равны нулю.
- Симметричные игры: существуют полиномиальные алгоритмы для нахождения равновесия Нэша при определенных условиях.
- Анонимные игры: NP-сложно найти чистое равновесие Нэша, но существует полиномиальный алгоритм для нахождения коррелированного равновесия.
- Полиматричные игры: существуют полиномиальные алгоритмы для поиска равновесия Нэша и коррелированного равновесия.
-
Другие представления игр
- Круговые игры: сложны для вычисления стоимости и определения равновесия Нэша.
- Другие типы игр: существуют различные типы игр, которые имеют свои сложности в нахождении равновесия.
-
Сложности нахождения равновесия
- В таблице приведены известные результаты по сложности нахождения различных типов равновесий в играх.
Полный текст статьи: