Композиционная теория игр ⇐ Васина Википедия

[wiki_en]

'''Композиционная теория игр''' — это раздел теории игр и информатики, целью которого является представление больших сложных игр как композиции простых маленьких игр.
== Мотивация ==
Основной темой информатики является способность создавать простые строительные блоки (например, функции или процедуры на языке программирования) и объединять их в более крупные структуры (например, более сложные функции или программы). Этот принцип еще называют модульностью.

Напротив, в классической теории игр даже сложные игры рассматриваются как отдельные монолитные объекты. Это затрудняет масштабирование анализа игр.

'''Композиционная теория игр''' '''(CGT)''' направлена ​​на применение принципа модульности к теории игр. Основная мотивация — упростить анализ больших игр с помощью программных инструментов.

== Игра высшего порядка ==
'''Одновременная игра высшего порядка'''
* Набор R «результатов».
* Для каждого игрока «i» набор «Xi» «выборов» (возможных действий).
** Мы определяем «Σ» как декартово произведение всех «Xi» и называем его набором «стратегических профилей».
* «Функция результата» от «Σ» до «R». Эта функция определяет для каждой комбинации действий игроков, каким будет результат.
* Для каждого игрока «i» существует «функция выбора», обозначенная «di». Функция выбора принимает в качестве входных данных «контекст», который является функцией от «Xi» до «R»; и возвращает набор «лучших ответов», который является подмножеством «Xi».

Термин «высший порядок» происходит от последнего элемента. Соответствие наилучшего ответа каждого игрока представляет собой функцию более высокого порядка, поскольку входные данные сами по себе являются функцией. Каждый профиль стратегии s1 в ''Σ'' определяет для каждого игрока ''i'' функцию от ''Xi'' до ''R' ': функция сопоставляет каждое возможное действие ''xi'' в ''Xi'' с результатом, который возникнет, если все игроки, кроме меня, будут играть, как в s 1, тогда как игрок «i» переключает свое действие на «xi». Другими словами, s1 определяет «контекст», в котором действует игрок «i».

Учитывая два кортежа стратегий s1 и s2 в ''Σ'', мы говорим, что s2 является «наилучшим ответом». '' на s1, если для каждого игрока ''i'' s2,i содержится в выводе ''di >'' в контексте, сгенерированном s1. «Отношение наилучшего ответа» — это бинарное отношение, содержащееся в «Σ x Σ», обозначаемое «B».

В стандартной игре вместо функции выбора существует «функция полезности» «ui» для каждого игрока «i». Функция полезности принимает на вход результат из ''R'' и возвращает действительное число. Такую игру можно представить как игру высшего порядка следующим образом. Для каждого игрока «i» функция выбора возвращает набор действий из «Xi», которые максимизируют полезность агента «i» с учетом контекста.

== Открытые игры ==
Основным объектом исследования в CGT является «открытая игра». Открытая игра имеет следующие элементы:

* Набор «X» «наблюдений»;
* Набор «Y» «результатов»;
* Набор «Σ» «стратегических профилей».
* «Функция воспроизведения» «P», которая представляет собой функцию от «Σ» x «X» до «Y»;
* «Функция совместной игры» «C», которая является функцией от «Σ x» X x R до S;
* «Функция наилучшего ответа» B, которая является функцией от X x (Y -> R) до отношения в «Σ x Σ».

Это абстракция игры высшего порядка.

Открытые игры можно разложить двумя способами:

* В последовательности - получение последовательной игры;
* Параллельно - ведение одновременной игры.

== См. также ==
* Байесовские открытые игры.

* [https://github.com/CyberCat-Institute/open-game-engine Открытый игровой движок] — код Haskell для построения и анализа открытых игр.

Теория игр
Теория категорий