Метод расширяет понятие равновесия по Нэшу, разлагая асимметричную игру на несколько симметричных игр.
Недавно я запустил образовательный информационный бюллетень, посвященный ИИ, у которого уже более 125 000 подписчиков. TheSequence — это информационный бюллетень, ориентированный на машинное обучение, без BS (то есть без шумихи, без новостей и т. д.), чтение которого занимает 5 минут. Цель состоит в том, чтобы держать вас в курсе проектов машинного обучения, научных работ и концепций. Пожалуйста, попробуйте, подписавшись ниже:
Асимметричные игры представляют собой одну из самых важных областей теории игр и другую, которая напоминает многие сценарии реального мира. Концептуально асимметричная игра — это среда, в которой игроки имеют доступ к одним и тем же опциям, но вознаграждения различаются в зависимости от их предпочтений. Асимметричные игры сложны и бросают вызов некоторым фундаментальным конструкциям теории игр, таким как равновесие Нэша. Кроме того, асимметричные игры необходимы в различных областях машинного обучения, таких как многоагентное обучение с подкреплением. Поэтому неудивительно, что сообщество машинного обучения посвятило много исследований разработке новых методов в асимметричных игровых средах.
Каждый месяц появляются десятки статей от исследователей машинного обучения, посвященных методам асимметричных игр. Один из самых простых и инновационных подходов за последние несколько лет появился из статьи, опубликованной DeepMind, в которой они предлагают уникальный способ решения асимметричных игровых проблем. Прорыв DeepMind может иметь серьезные последствия для современных многоагентных систем искусственного интеллекта, которые часто моделируются как асимметричные игры. Прежде чем перейти к этому, давайте попробуем понять, что такого сложного в асимметричных игровых средах.
Симметричные и асимметричные игры
Симметричные игры являются любимыми примерами, используемыми для иллюстрации динамики теории игр, поскольку они математически элегантны и почти совершенны. Как мы объясняли ранее, асимметричная игра описывает динамику, в которой разные игроки используют одну и ту же стратегию и цели. Как правило, простота симметричных игр упрощает их моделирование с вычислительной точки зрения. К сожалению, большинству реальных игровых сред не хватает математической элегантности симметричных игр.
Асимметричные игры описывают среду с несколькими агентами, в которой у игроков разные и часто конфликтующие цели и стратегии. Возьмем в качестве примера вчерашний обвал рынка. В этой среде некоторые трейдеры отчаянно пытались избавиться от своих позиций, в то время как другие пытались накапливать новые позиции, планируя потенциальный отскок рынка (судя по фьючерсам, похоже, что сегодня этого не произойдет ;)) . Умножьте эту стратегию на миллионы трейдеров и инвесторов по всему миру, и вы получите невероятно хаотичную асимметричную игру.
В теории игр решение многих асимметричных игровых сред моделируется с использованием равновесия Нэша. Модель названа в честь Джона Форбса Нэша, американского математика, увековеченного Расселом Кроу в фильме Игры разума. По сути, равновесие по Нэшу описывает ситуацию, в которой каждый игрок выбрал стратегию, и ни один из игроков не может получить выгоду от изменения стратегии, в то время как другие игроки сохраняют свои стратегии без изменений.
Где нарушается равновесие Нэша
Равновесие Нэша — красивая и невероятно мощная математическая модель для решения многих проблем теории игр, но она также не работает во многих асимметричных игровых средах. Две основные причины:
· Во-первых, метод Нэша предполагает, что у игроков бесконечная вычислительная мощность, что редко бывает в реальных условиях.
· Также многие модели равновесия Нэша не учитывают понятие риска, которое повсеместно присутствует в большинстве асимметричных игр на экономических рынках.
В результате существует множество асимметричных игровых сценариев, которые трудно реализовать с использованием равновесия Нэша. Это особенно важно в многоагентных системах ИИ, которым необходимо найти правильный баланс между математической элегантностью решения и практичностью его реализации.
Симметричная декомпозиция асимметричных игр Deep Mind
В статье, опубликованной DeepMind два года назад, авторы предложили очень умную модель для поиска решений для очень сложных асимметричных игр путем их разложения на разные симметричные игры. С математической точки зрения, новые методы предполагают, что
если (x,y) является равновесием по Нэшу асимметричной игры (A, B), это означает, что y является равновесием по Нэшу в симметричной контригре, определяемой таблицей выигрышей A, а x является равновесием по Нэшу симметричная контригра, определяемая таблицей выплат B.
Чтобы проиллюстрировать новую технику, я позаимствую пример из оригинального поста на веб-сайте DeepMind. Пример основан на известной игре «Битва полов».
Здесь два игрока должны договориться о вечернем походе в оперу или кино. Один из игроков немного предпочитает оперу, а другой немного предпочитает кино. Игра асимметрична, потому что, хотя оба игрока имеют доступ к одним и тем же опциям, соответствующие награды для каждого из них различаются в зависимости от предпочтений игрока. Чтобы сохранить дружбу — или равновесие — игроки должны выбрать одно и то же действие (отсюда и нулевые выплаты за отдельные действия).
В этой игре есть три равновесия:
(i) оба игрока решают пойти в оперу
(ii) оба решили пойти в кино
(iii) окончательный смешанный вариант, когда каждый игрок будет выбирать предпочитаемый вариант в трех пятых случаях.
Последний вариант, который считается «нестабильным», может быть быстро обнаружен с помощью нового метода DeepMind путем упрощения или разложения асимметричной игры на ее симметричные аналоги. Эти параллельные игры по существу рассматривают таблицу вознаграждений каждого игрока как отдельную симметричную игру для двух игроков с точками равновесия, которые совпадают с исходной асимметричной игрой.
