Равновесие Нэша
- Автор метода
- John Nash
- Год
- 1950
- Тип
- algorithm
- Семейство
- Game-theoretic
Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском
Что он делает?
Равновесие Нэша — это концепция решения в теории игр, при которой ни один игрок не может в одностороннем порядке отклониться от своей стратегии, чтобы улучшить свой выигрыш.
Формализованный Джоном Нэшем в 1950 году, алгоритм Лемке-Хаусона позволяет вычислительно находить равновесия в биматричных играх путём идентификации полностью помеченных пар вершин в политопах стратегий.
Интуиция метода
В равновесии Нэша стратегия каждого игрока является наилучшим ответом на стратегии всех других игроков. Представьте ситуацию, когда оба игрока знают стратегии друг друга: ни один из них не захочет менять свою стратегию, потому что это только ухудшит его положение. Алгоритм Лемке-Хаусона использует геометрию игровых полиэдров, отслеживая метки (неудовлетворённые ограничения) и осуществляя повороты через вершины до тех пор, пока не будет найдена полностью помеченная пара — конфигурация, в которой у обоих игроков нет выгодных отклонений.
История
Джон Нэш доказал в своей диссертации 1950 года, что каждая конечная игра обладает по крайней мере одним равновесием Нэша в смешанных стратегиях. В 1964 году Лемке и Хаусон опубликовали первый конструктивный алгоритм для нахождения этих равновесий, превратив доказательство существования Нэша в практический вычислительный метод. Их работа стала основополагающей для вычислительной теории игр и алгоритмической экономики.
Когда применять
Используйте анализ равновесия Нэша при изучении игр с двумя игроками и дискретными пространствами стратегий или при поиске полностью смешанных равновесий. Подходит для моделирования конкуренции, переговоров и проблем координации, где стратегическое взаимодействие имеет первостепенное значение. Метод Лемке-Хаусона лучше всего работает для невырожденных биматричных игр; вырожденные случаи могут потребовать символьных вычислений или возмущений.
Ограничения и замечания
- Ограничен биматричными (играми с двумя игроками); расширение на игры с n-игроками является NP-трудной задачей.
- Не работает или становится неэффективным в вырожденных играх, где возможно несколько входящих поворотов.
- Может найти только одно равновесие; в играх с ненулевой суммой часто существует несколько равновесий.
- Не обрабатывает напрямую динамические или развёрнутые игры без переформулировки.
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Вычислительно эффективен для нахождения равновесий Нэша в конечных биматричных играх.
- Гарантирует сходимость к полностью помеченной паре вершин для невырожденных игр.
- Обеспечивает теоретическую основу, связывающую комбинаторную геометрию с теорией игр.
- Применим к равновесиям в смешанных стратегиях, которые часто более реалистичны, чем исходы в чистых стратегиях.
Применение
- Экономика: моделирование олигополистической конкуренции и ценообразования на рынках.
- Аукционы и проектирование механизмов: анализ стратегий торгов на аукционах первой цены и закрытых торгах.
- Кибербезопасность: прогнозирование равновесий между атакующим и защитником в играх по сетевой безопасности.
- Биология дикой природы: анализ эволюционно стабильных стратегий во взаимодействиях хищник-жертва.
Как это работает
Как это работает
Преобразуйте биматричную игру в две задачи линейного дополнения (LCP), по одной для каждого игрока, представляющие условия их наилучшего ответа.
Присвойте метки рёбрам и вершинам политопов стратегий на основе того, какие ограничения стимулов игрока нарушены.
Начиная с вершины, состоящей из всех единиц (полностью помеченной), выполните симплекс-подобные повороты для навигации по политопу, удаляя и добавляя метки до тех пор, пока не будет обнаружена полностью помеченная пара.
Подтвердите, что стратегии обоих игроков образуют взаимные наилучшие ответы, проверив, что ни один из них не может улучшить свой выигрыш, учитывая стратегию другого.
Частые ошибки
- Предполагает существование уникального равновесия; многие игры имеют несколько равновесий Нэша с различными последствиями для выигрыша.
- Смешение равновесий в смешанных стратегиях (вероятностная игра) с равновесиями в чистых стратегиях, что приводит к неверной интерпретации поведения агентов.
- Упущение различия между необходимыми и достаточными условиями равновесия; полностью помеченная пара удовлетворяет оптимальности, но может не быть реализована, если игроки не могут координировать свои действия.
Часто задаваемые вопросы
Может ли игра не иметь равновесия Нэша?
Равновесия Нэша в чистых стратегиях могут не существовать (например, «Камень-ножницы-бумага»), но каждая конечная игра имеет по крайней мере одно равновесие в смешанных стратегиях, где игроки рандомизируют свои действия с определёнными вероятностями.
Чем равновесие в смешанных стратегиях отличается от равновесия в чистых стратегиях?
В равновесии в чистых стратегиях каждый игрок с уверенностью выбирает конкретное действие. В равновесии в смешанных стратегиях каждый игрок использует вероятностное распределение по действиям. Смешанные равновесия часто более общие и существуют, когда чистые не существуют.
Почему алгоритм Лемке-Хаусона предпочтительнее полного перебора?
Алгоритм использует политопальную структуру пространств стратегий, экспоненциально сокращая пространство поиска и достигая сходимости за полиномиальное время для невырожденных игр, тогда как полный перебор становится невыполнимым по мере роста пространства стратегий.
Похожие методы
Источники
Nash, J. F. (1950). Equilibrium points in N-person games. Proceedings of the National Academy of Sciences, 36(1), 48-49.
Открыть ссылку DOIСкопировано.Lemke, C. E., & Howson Jr, J. T. (1964). Equilibrium points of bimatrix games. Journal of the Society for Industrial and Applied Mathematics, 12(2), 413-423.
Открыть ссылку DOIСкопировано.