равновесие по Нэшу

Равновесие Нэша (сокращенно NGG или NGGW ) является центральным понятием в теории игр . В некооперативных играх он описывает комбинацию стратегий , при которой каждый игрок выбирает ровно одну стратегию, от которой для любого игрока нет смысла отклоняться от выбранной им стратегии как единственной. В равновесии по Нэшу каждый игрок соглашается со своей стратегией, даже ретроспективно, он ударил бы ее снова таким же образом. Таким образом, стратегии игроков являются взаимно лучшими ответами . Равновесие по Нэшу - это элементарное решение в теории игр. Определение и доказательство существования равновесия по Нэшу восходит к опубликованной в 1950 году диссертации математика Джона Форбса Нэша-младшего . Равновесие Нэша находит среди прочего. центральное значение в таких экономических областях, как микроэкономика , в распределении товаров и ценообразовании.

идея

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

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

определение

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

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

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

Чистые стратегии : игрок принимает очень конкретное решение.

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

Формальное определение для разных стратегий

Равновесие по Нэшу в чистых стратегиях

Это означает набор стратегий ( альтернативные курсы действий) в -й игроке и в декартово произведении этих множеств стратегий. ${\ displaystyle \ Sigma _ {i}}$${\ displaystyle i}$${\ Displaystyle \ Sigma: = \ Sigma _ {1} \ times \ dotsb \ times \ Sigma _ {n}}$

Под равновесием по Нэшу в чистых стратегиях понимается профиль стратегии, в котором стратегия каждого игрока является наилучшим ответом на выбранные стратегии других игроков. Если все остальные игроки придерживаются выбранных ими стратегий, равновесие по Нэшу в чистых стратегиях формально характеризуется тем, что для игроков нет ничего, что обещало бы игроку более высокую выплату: ${\ Displaystyle \ sigma ^ {*} = (\ sigma _ {1} ^ {*}, \ dotsc, \ sigma _ {n} ^ {*}) \ in \ Sigma}$${\ displaystyle i}$${\ displaystyle i}$${\ Displaystyle \ sigma _ {я} \ neq \ sigma _ {я} ^ {*}}$${\ displaystyle i}$

${\ displaystyle \ forall \ sigma _ {i} \ in \ Sigma _ {i}: u_ {i} (\ sigma _ {1} ^ {*}, \ dotsc, \ sigma _ {i} ^ {*}, \ dotsc, \ sigma _ {n} ^ {*}) \ geq u_ {i} (\ sigma _ {1} ^ {*}, \ dotsc, \ sigma _ {i}, \ dotsc, \ sigma _ {n } ^ {*})}$.

Также сказано, что одностороннее отклонение не улучшает выплату игрока . Равновесие по Нэшу характеризуется тем фактом, что ни один игрок не может улучшить себя , изменив свою стратегию в одностороннем порядке. Если равновесие по Нэшу состоит только из доминирующих стратегий, его также называют строгим равновесием . ${\ displaystyle i}$

Равновесие по Нэшу в смешанных стратегиях

В некоторых случаях это может быть , что игроки не связаны какой - либо конкретной стратегии, а распределение вероятностей , с которой из составляется случайным образом . Если оно конечное или хотя бы счетное , распределение вероятностей может быть описано вектором с вероятностью того, что стратегия выбрана. ${\ displaystyle \ sigma _ {я}}$${\ displaystyle \ Sigma _ {i}}$${\ displaystyle \ Sigma _ {i}}$ ${\ displaystyle s_ {i}}$${\ displaystyle s_ {i, j}}$${\ Displaystyle \ sigma _ {я, j} \ in \ Sigma _ {я}}$

Смешанная стратегия является равновесием Нэша тогда и только тогда , когда ни один игрок не может достичь лучшего выплаты по отклоняясь в одиночку, то есть , если и только если ${\ displaystyle s = (s_ {1} ^ {*}, \ dotsc, s_ {n} ^ {*})}$

${\ displaystyle \ forall i \ in \ {1, \ dotsc, n \} \; \; \ forall s_ {i} \ in S_ {i} \; \; u_ {i} (s_ {1} ^ {* }, \ dotsc, s_ {i-1} ^ {*}, s_ {i}, s_ {i + 1} ^ {*}, \ dotsc, s_ {n} ^ {*}) \ leq u_ {i} (s_ {1} ^ {*}, \ dotsc, s_ {i-1} ^ {*}, s_ {i} ^ {*}, s_ {i + 1} ^ {*}, \ dotsc, s_ {n } ^ {*})}$.

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

существование

С помощью теоремы Какутани о неподвижной точке можно показать, что по крайней мере одно равновесие по Нэшу должно существовать, если выполняются следующие условия:

1. Функции выплат являются непрерывными и квазивогнуты в .${\ Displaystyle Н_ {я} (\ сигма _ {1}, \ ldots, \ сигма _ {п})}$${\ displaystyle \ sigma _ {я}}$
2. Наборы стратегии являются выпукло и компактно .${\ Displaystyle \ Sigma _ {1}, \ ldots, \ Sigma _ {n}}$

Игры часто строятся таким образом, что они конечны, но конечные множества с более чем одним элементом не могут быть выпуклыми. Однако в этом случае количество смешанных стратегий через компактные и выпуклые и соответствующее расширение полилинейных. Хотя существование равновесия по Нэшу в чистых стратегиях не может быть гарантировано, по крайней мере одно равновесие по Нэшу существует в игре в смешанных стратегиях (если предполагается конечное число чистых стратегий). ${\ displaystyle \ Sigma _ {i}}$${\ displaystyle S_ {i}}$${\ displaystyle \ Sigma _ {i}}$${\ displaystyle H}$

Простой алгоритм определения равновесий по Нэшу

Если игра имеет стратегическую форму, все равновесия по Нэшу могут быть определены в чистых стратегиях, используя следующий алгоритм:

1. Оптимизируйте решение игрока с помощью (произвольно) фиксированных стратегий всех других игроков: отметьте самые высокие выплаты, которые могут быть достигнуты для игроков при данных обстоятельствах (так называемые «лучшие ответы» на комбинацию стратегий других игроков). Повторите это для всех возможных комбинаций стратегий других игроков.${\ Displaystyle я = 1, \ dotsc, п}$${\ displaystyle i}$
2. Выполните 1. для всех игроков.

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

пример

Пусть следующая игра будет дана в нормальной форме :

	Левый	центр	верно
выше	4 , 2	1 , 1	2 , 0
центр	2, 3	1 , 1	1, 4
ниже	3, 0	0, 2	1, 3
Выплата биматричная для игрока 1 и игрока , 2

Тогда алгоритм работает следующим образом (выделено жирным шрифтом):

• ${\ displaystyle i = 1:}$
  • данный игрок 2 играет правильно: для игрока 1 выше является оптимальным - метка 2 ( «выше , является лучшим ответом на право»)
  • если игрок 2 играет посередине: оптимально верхняя и средняя - отметьте две единицы
  • учитывая, что игроку осталось 2 ходов: выше оптимально - отметьте 4

• ${\ displaystyle i = 2:}$
  • данный игрок 1 играет выше: для игрока 2 оптимально левое - отметьте 2
  • учитывая, что игрок 1 играет посередине: оптимально справа - отметьте 4
  • если игрок 1 проигрывает: оптимально правильно - отметьте 3

Таким образом, единственное равновесие по Нэшу - это пара стратегий (вверху, слева), которые приводят к выигрышу (4, 2).

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

Алгоритм определения равновесий по Нэшу в смешанных стратегиях

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

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

пример

Дана следующая биматрица :

	Опера	Футбольный
Опера	3, 2	2, 3
Футбольный	1, 3	4, 1
Матрица выплат для игрока 1 и игрока 2

Тогда алгоритм работает следующим образом:

Игрок 2 играет с вероятностью Opera и с отдаленной вероятностью футбола, поэтому для игрока 1 возникает следующая ожидаемая полезность ( ожидаемая полезность ): ${\ displaystyle q}$${\ displaystyle (1-q)}$

${\ Displaystyle \ OperatorName {E} [U_ {1} (O)] = 3q + 2 (1-q)}$

${\ Displaystyle \ OperatorName {E} [U_ {1} (F)] = 1q + 4 (1-q)}$

Таким образом, игроку 1 безразлично, какая из его двух стратегий:

${\ Displaystyle {\ begin {array} {cl} & 3q + 2 (1-q) \; = \; 1q + 4 (1-q) \\\ Leftrightarrow & 3q + 2-2q \; = \; 1q + 4 -4q \\\ Leftrightarrow & 1q + 2 \; = \; 4-3q \\\ Leftrightarrow & 4q \; = \; 2 \\\ Leftrightarrow & q \; = \; 1/2 \ end {массив }}}$

Для игрока 2 аналогично можно определить, что ему безразлично, играет ли игрок 1 с вероятностью оперу и футбол. ${\ displaystyle p = 2/3}$${\ displaystyle (1-p) = 1/3}$

Поскольку все ответы оппонента на эти две стратегии являются наилучшими ответами, они также являются взаимно лучшими ответами. Таким образом, его можно определить как равновесие по Нэшу в смешанных стратегиях. ${\ Displaystyle [(2/3; 1/3), (1/2; 1/2)]}$

Особые случаи

Частным случаем теоремы Нэша о существовании равновесий является теорема Мин-Макса , действительная для игр двух лиц с нулевой суммой , которая была доказана Джоном фон Нейманом в 1928 году . В отличие от общего случая, каждая игра имеет уникальный вектор выплат , по которому вызывается значение игры. ${\ displaystyle (v, -v)}$${\ displaystyle v}$

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

Практические примеры

Рыночная экономика

Поиск стратегии, основанный на равновесии Нэша, может быть применен в равной степени к ценам и количеству . В рыночной экономике возможна ситуация, когда несколько поставщиков на рынке снизили цены на свои конкурирующие продукты до такой степени, что они едва могут работать экономически. Для отдельного поставщика не может быть возможна стратегия уклонения: если он снижает свою цену, чтобы увеличить свои продажи, он падает в рентабельность; если он ее увеличит, покупатели переключатся на конкурирующие товары, и его прибыль также уменьшится. Одним из выходов может быть внедрение инновационного продукта (почти) одновременно с конкурентом, чтобы оправдать более высокую цену. Такие сценарии более широко обсуждались в середине 1990-х годов под термином « сотрудничество» , и в качестве яркого примера приводился спор между авиакомпаниями США.

Дилемма заключенного

Другой пример - дилемма заключенного, проблема теории игр, в которой существует ровно одно равновесие по Нэшу.

	признается	не признается
признается	-5, -5	-1, -10
не признается	-10, -1	-2, -2
Матрица выплат для игрока 1 и игрока 2

Представьте себе следующую ситуацию: двое заключенных подозреваются в совместном совершении преступления. Максимальный срок наказания за преступление - 10 лет лишения свободы. Теперь обоим заключенным предлагают сделку, о которой оба проинформированы. Если один признается в одиночестве (ключевой свидетель) и, таким образом, также оговорит свою партнершу, он получает мягкий приговор в виде тюремного заключения сроком на 1 год - другой должен отбыть полные 10 лет. Если оба решат хранить молчание, останутся лишь косвенные улики, которых достаточно, чтобы заблокировать их обоих на 2 года. Но если оба признаются в этом деянии, каждого ожидает тюремное заключение сроком на 5 лет. Теперь заключенных допрашивают независимо друг от друга. Ни до, ни во время опроса у них двоих нет возможности поговорить друг с другом.

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

Смотри тоже

• Различные связанные концепции можно найти в разделе « Баланс (теория игры)».

веб ссылки

• Теория игр и Нэш - Вывод и примеры (английский)
• Стратегия минимакс на практике: простая игра с блефом двух человек против компьютера.

Индивидуальные доказательства

1. ^ Джон Форбс Нэш: Некооперативные игры. Диссертация, Принстонский университет, 1950 ( онлайн-версия ; PDF; 1,2 МБ).