Skip to content
Назад к результатам поиска

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

Автор метода
John Nash
Год
1950
Тип
algorithm
Семейство
Game-theoretic

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

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

Формализованный Джоном Нэшем в 1950 году, алгоритм Лемке-Хаусона позволяет вычислительно находить равновесия в биматричных играх путём идентификации полностью помеченных пар вершин в политопах стратегий.

Интуиция метода

В равновесии Нэша стратегия каждого игрока является наилучшим ответом на стратегии всех других игроков. Представьте ситуацию, когда оба игрока знают стратегии друг друга: ни один из них не захочет менять свою стратегию, потому что это только ухудшит его положение. Алгоритм Лемке-Хаусона использует геометрию игровых полиэдров, отслеживая метки (неудовлетворённые ограничения) и осуществляя повороты через вершины до тех пор, пока не будет найдена полностью помеченная пара — конфигурация, в которой у обоих игроков нет выгодных отклонений.

История

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

Когда применять

Используйте анализ равновесия Нэша при изучении игр с двумя игроками и дискретными пространствами стратегий или при поиске полностью смешанных равновесий. Подходит для моделирования конкуренции, переговоров и проблем координации, где стратегическое взаимодействие имеет первостепенное значение. Метод Лемке-Хаусона лучше всего работает для невырожденных биматричных игр; вырожденные случаи могут потребовать символьных вычислений или возмущений.

Ограничения и замечания

  • Ограничен биматричными (играми с двумя игроками); расширение на игры с n-игроками является NP-трудной задачей.
  • Не работает или становится неэффективным в вырожденных играх, где возможно несколько входящих поворотов.
  • Может найти только одно равновесие; в играх с ненулевой суммой часто существует несколько равновесий.
  • Не обрабатывает напрямую динамические или развёрнутые игры без переформулировки.

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

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

Применение

  • Экономика: моделирование олигополистической конкуренции и ценообразования на рынках.
  • Аукционы и проектирование механизмов: анализ стратегий торгов на аукционах первой цены и закрытых торгах.
  • Кибербезопасность: прогнозирование равновесий между атакующим и защитником в играх по сетевой безопасности.
  • Биология дикой природы: анализ эволюционно стабильных стратегий во взаимодействиях хищник-жертва.

Как это работает

Как это работает

1

Преобразуйте биматричную игру в две задачи линейного дополнения (LCP), по одной для каждого игрока, представляющие условия их наилучшего ответа.

2

Присвойте метки рёбрам и вершинам политопов стратегий на основе того, какие ограничения стимулов игрока нарушены.

3

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

4

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

Частые ошибки

  • Предполагает существование уникального равновесия; многие игры имеют несколько равновесий Нэша с различными последствиями для выигрыша.
  • Смешение равновесий в смешанных стратегиях (вероятностная игра) с равновесиями в чистых стратегиях, что приводит к неверной интерпретации поведения агентов.
  • Упущение различия между необходимыми и достаточными условиями равновесия; полностью помеченная пара удовлетворяет оптимальности, но может не быть реализована, если игроки не могут координировать свои действия.

Часто задаваемые вопросы

Может ли игра не иметь равновесия Нэша?

Равновесия Нэша в чистых стратегиях могут не существовать (например, «Камень-ножницы-бумага»), но каждая конечная игра имеет по крайней мере одно равновесие в смешанных стратегиях, где игроки рандомизируют свои действия с определёнными вероятностями.

Чем равновесие в смешанных стратегиях отличается от равновесия в чистых стратегиях?

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

Почему алгоритм Лемке-Хаусона предпочтительнее полного перебора?

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

Похожие методы

Источники

  1. Nash, J. F. (1950). Equilibrium points in N-person games. Proceedings of the National Academy of Sciences, 36(1), 48-49.

    Открыть ссылку DOI
    Скопировано.
  2. 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
    Скопировано.