16.03.2023. - Исследователь решил почти 60-летнюю дилемму теории игр

Исследователь решил почти 60-летнюю дилемму теории игр

Чтобы понять, как беспилотные автомобили могут преодолевать сложности дорог, исследователи часто используют теорию игр — математические модели, представляющие то, как рациональные агенты действуют стратегически для достижения своих целей. Деян Милутинович, профессор электротехники и вычислительной техники в Калифорнийском университете в Санта-Круз, долгое время работал с коллегами над сложным подмножеством теории игр, называемым дифференциальными играми, которые имеют дело с игроками в движении. Одна из таких игр называется «преследование стены» и представляет собой относительно простую модель ситуации, в которой более быстрый преследователь имеет целью поймать более медленного убегающего, который ограничен движением вдоль стены.

С тех пор, как эта игра была впервые описана почти 60 лет назад, внутри игры возникла дилемма — набор позиций, для которых считалось, что оптимального игрового решения не существует. Но теперь Милутинович и его коллеги в новой статье, опубликованной в журнале IEEE Transactions on Automatic Control, доказали, что этой давней дилеммы на самом деле не существует, и представили новый метод анализа, доказывающий, что всегда существует детерминированное решение проблемы. игра преследования стены. Это открытие открывает двери для решения других подобных проблем, существующих в области дифференциальных игр, и позволяет лучше рассуждать об автономных системах, таких как беспилотные транспортные средства.

Теория игр используется для рассуждений о поведении в самых разных областях, таких как экономика, политология, информатика и инженерия. В теории игр равновесие по Нэшу является одним из наиболее общепризнанных понятий. Эта концепция была введена математиком Джоном Нэшем и определяет оптимальные игровые стратегии для всех игроков, чтобы закончить игру с наименьшими сожалениями. Любой игрок, который решит не использовать свою оптимальную стратегию игры, в конечном итоге будет сожалеть больше, поэтому все рациональные игроки мотивированы использовать свою равновесную стратегию.

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

«Это беспокоило нас, потому что мы думали, что если убегающий знает, что существует сингулярная поверхность, существует угроза того, что убегающий может пойти на сингулярную поверхность и злоупотребить ею», — сказал Милутинович. «Убегающий может заставить вас отправиться на сингулярную поверхность, где вы не знаете, как действовать оптимально, — и тогда мы просто не знаем, как это повлияет на гораздо более сложные игры».

Итак, Милутинович и его соавторы придумали новый подход к проблеме, используя математическую концепцию, которой не существовало, когда изначально задумывалась игра преследования стены. Используя вязкостное решение уравнения Гамильтона-Якоби-Айзекса и введя анализ скорости потерь для решения сингулярной поверхности, они смогли обнаружить, что оптимальное решение для игры может быть определено во всех обстоятельствах игры, и решить дилемму. Вязкость решения уравнений в частных производных — это математическая концепция, которая не существовала до 1980-х годов и предлагает уникальную линию рассуждений о решении уравнения Гамильтона-Якоби-Айзекса. В настоящее время хорошо известно, что эта концепция актуальна для рассуждений об оптимальном управлении и задачах теории игр.

Использование решений вязкости, которые являются функциями, для решения задач теории игр включает в себя использование исчисления для нахождения производных этих функций. Относительно легко найти оптимальные решения для игры, когда решение вязкости, связанное с игрой, имеет четко определенные производные. Это не относится к игре преследования стены, и это отсутствие четко определенных производных создает дилемму. Как правило, когда возникает дилемма, практический подход заключается в том, что игроки случайным образом выбирают одно из возможных действий и принимают потери в результате этих решений. Но здесь кроется загвоздка: если есть проигрыш, каждый рациональный игрок захочет его минимизировать.

Поэтому, чтобы выяснить, как игроки могут минимизировать свои потери, авторы проанализировали вязкостное решение уравнения Гамильтона-Якоби-Айзекса вокруг сингулярной поверхности, где производные не определены четко. Затем они ввели анализ скорости потерь для этих сингулярных поверхностных состояний уравнения. Они обнаружили, что когда каждый актор минимизирует свой уровень потерь, существуют четко определенные игровые стратегии для их действий на сингулярной поверхности. Авторы обнаружили, что эта скорость минимизации потерь не только определяет оптимальные действия игры для сингулярной поверхности, но и согласуется с оптимальными действиями игры во всех возможных состояниях, где эти действия также можно найти с помощью классического анализа.

«Когда мы берем анализ скорости проигрыша и применяем его в другом месте, это не влияет на оптимальные игровые действия из классического анализа», — сказал Милутинович. «Мы берем классическую теорию и дополняем ее анализом скорости потерь, поэтому решение существует везде. Это важный результат, показывающий, что дополнение — это не просто исправление для поиска решения на сингулярной поверхности, а фундаментальный вклад к теории игр. Милутинович и его соавторы заинтересованы в изучении других задач теории игр с сингулярными поверхностями, где можно было бы применить их новый метод. Документ также является открытым призывом к исследовательскому сообществу аналогичным образом изучить другие дилеммы. «Теперь вопрос в том, какие еще дилеммы мы можем решить?» — сказал Милутинович.

Источник