Теория игр для агентов

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

Definition

Теория игр изучает ситуации, в которых несколько рациональных агентов выбирают действия, чьи выигрыши зависят от выбора всех агентов, и характеризует стабильное или рациональное совместное поведение с помощью таких концепций решения, как равновесия.

Scope

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

Core questions

• Как стратегические взаимодействия представляются в виде игр в нормальной или развернутой форме?
• Какие концепции решения (доминирующие стратегии, равновесие Нэша) предсказывают поведение рациональных агентов?
• Когда гарантировано существование равновесия, возможно, в смешанных стратегиях?
• Насколько сложно вычислить равновесия и как это влияет на их использование агентами?

Key concepts

• игры в нормальной и развернутой форме
• выигрыши и стратегии
• доминирующая стратегия
• равновесие Нэша
• смешанные стратегии
• игры с нулевой суммой и минимакс
• дилемма заключенного
• вычисление равновесия

Key theories

Равновесие Нэша

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

Минимакс в играх с нулевой суммой

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

Доминирующие стратегии и дилеммы

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

Clinical relevance

Теоретико-игровой анализ лежит в основе разработки аукционов и рынков, стратегий безопасности и патрулирования, маршрутизации и перегрузки сетей, а также автоматизированных переговоров, предсказывая, как будут действовать стратегические агенты, и выявляя стабильные результаты в конкурентных условиях.

History

Теория игр была основана фон Нейманом и Моргенштерном (1944) и расширена концепцией равновесия Нэша (1950). Она стала центральной для экономики, а с 1990-х годов — для ИИ и информатики благодаря алгоритмической теории игр, которая изучает вычислительную сложность равновесий и их использование в многоагентных системах.

Key figures

• John von Neumann
• Oskar Morgenstern
• John F. Nash
• Yoav Shoham
• Kevin Leyton-Brown

Seminal works

• nash1950
• vonneumann1944
• shoham2009

Frequently asked questions

Что такое равновесие Нэша?

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

Почему дилемма заключенного важна для агентов ИИ?

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