Композиционная теория игр
Композиционная теория игр — это раздел теории игр и информатики , целью которого является представление больших сложных игр как композиции простых маленьких игр. [1] [2] [3]
Мотивация [ править ]
Основной темой информатики является способность создавать простые строительные блоки (например, функции или процедуры на языке программирования) и объединять их в более крупные структуры (например, более сложные функции или программы). Этот принцип еще называют модульностью .
Напротив, в классической теории игр даже сложные игры рассматриваются как отдельные монолитные объекты. Это затрудняет масштабирование анализа игр.
Композиционная теория игр (CGT) направлена на применение принципа модульности к теории игр. Основная мотивация — упростить анализ больших игр с помощью программных инструментов.
Игра высшего порядка [ править ]
Одновременная игра высшего порядка [4] является обобщением одновременной игры , в которой игроки определяются функциями выбора, а не функциями полезности . Формально одновременная игра высшего порядка для n игроков содержит следующие элементы:
- Набор R результатов .
- Для каждого игрока i — набор X i вариантов выбора (возможных действий).
- Мы определяем Σ как декартово произведение всех X i и называем его множеством профилей стратегий .
- Функция результата от Σ до R. Эта функция определяет для каждой комбинации действий игроков, каким будет результат.
- Для каждого игрока i существует функция выбора , обозначенная d i . Функция выбора принимает на вход контекст , который является функцией от X i до R ; и возвращает набор лучших ответов , который является подмножеством X i .
Термин «высший порядок» происходит от последнего элемента. Соответствие наилучшего ответа каждого игрока — это функция высшего порядка , поскольку входные данные сами по себе являются функцией. Каждый профиль стратегии s 1 в Σ определяет для каждого игрока i функцию от X i до R : функция отображает каждое возможное действие x i в X i на результат, который возник бы, если бы все игроки, кроме i, играли, как в s 1 , как игрок i переключает свое действие на xi тогда . Другими словами, s1 определяет контекст , в котором действует игрок i .
Учитывая два кортежа стратегий s 1 и s 2 в Σ , мы говорим, что s 2 является лучшим ответом на s 1 , если для каждого игрока i s 2,i содержится в выходных данных d i в контексте, сгенерированном с 1 . Отношение наилучшего ответа — это бинарное отношение, в Σ x Σ , обозначаемое B. содержащееся
В стандартной игре вместо функции выбора i имеется функция полезности u i для каждого игрока . Функция полезности принимает на вход результат R и возвращает действительное число. Такую игру можно представить как игру высшего порядка следующим образом. Для каждого игрока i функция выбора возвращает набор действий из X i , которые максимизируют полезность агента i в данном контексте.
Открытые игры [ править ]
Основным объектом изучения в CGT является открытая игра . Открытая игра имеет следующие элементы:
- Набор X наблюдений ;
- Набор Y результатов ;
- Набор Σ профилей стратегий .
- Игровая функция P , которая является функцией от Σ x X до Y ;
- Функция совместной игры C , которая является функцией от Σ x X x R до S;
- Функция наилучшего ответа B, которая является функцией от X x (Y -> R) до отношения в Σ x Σ.
Это абстракция игры высшего порядка.
Открытые игры можно декомпозировать двумя способами: [2]
- В последовательности – получение последовательной игры ;
- Параллельно - ведение одновременной игры .
См. также [ править ]
- Байесовские открытые игры. [5]
Внешние ссылки [ править ]
- Движок открытой игры — код Haskell для создания и анализа открытых игр.
Ссылки [ править ]
- ^ Хеджес, Дж. М. (3 октября 2016 г.). К композиционной теории игр (Диссертация).
- ^ Jump up to: а б Гани, Нил; Хеджес, Жюль; Виншель, Виктор; Зан, Филипп (9 июля 2018 г.). «Композиционная теория игр» . Материалы 33-го ежегодного симпозиума ACM/IEEE по логике в информатике . ЛИКС '18. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 472–481. arXiv : 1603.04641 . дои : 10.1145/3209108.3209165 . ISBN 978-1-4503-5583-4 .
- ^ Атки, Роберт; Гавранович, Бруно; Гани, Нил; Купке, Клеменс; Ледент, Жереми; Нордвалль Форсберг, Фредрик (июль 2020 г.). «Композиционная теория игр, композиционно» . Электронные труды по теоретической информатике . 333 . Онлайн, США: 198–214. дои : 10.4204/eptcs.333.14 .
- ^ Хеджес, Жюль; Олива, Пауло; Спритс, Евгения; Виншель, Виктор; Зан, Филипп (3 июня 2015 г.). «Теория игр высшего порядка». arXiv : 1506.01002 [ cs.GT ].
- ^ Болт, Джо; Хеджес, Жюль; Зан, Филипп (04 октября 2023 г.). «Байесовские открытые игры» . Композиционность . 5 : 9.arXiv : 1910.03656 . doi : 10.32408/compositionality-5-9 .