Как найти равновесие по нэшу в игре

What Is Nash Equilibrium?

Nash equilibrium is a concept in game theory where the optimal outcome is when there is no incentive for players to deviate from their initial strategy. The players have knowledge of their opponent’s strategy and still will not deviate from their initial chosen strategies because it remains the optimal strategy for each player.

Overall, an individual can receive no incremental benefit from changing actions, assuming that other players remain constant in their strategies. A game may have multiple Nash equilibria or none at all.

Understanding Nash Equilibrium

Nash equilibrium is named after its inventor, John Nash, an American mathematician. It is considered one of the most important concepts of game theory, which attempts to determine mathematically and logically the actions that participants of a game should take to secure the best outcomes for themselves.

The reason why Nash equilibrium is considered such an important concept of game theory relates to its applicability. The Nash equilibrium can be incorporated into a wide range of disciplines, from economics to social sciences.

To quickly find the Nash equilibrium or see if it even exists, reveal each player’s strategy to the other players. If no one changes their strategy, then the Nash equilibrium is proven.

Nash Equilibrium vs. Dominant Strategy

Nash equilibrium is often compared alongside dominant strategy, both being strategies of game theory. The Nash equilibrium states that the optimal strategy for an actor is to stay the course of their initial strategy while knowing the opponent’s strategy and that all players maintain the same strategy.

Dominant strategy asserts that the chosen strategy of an actor will lead to better results out of all the possible strategies that can be used, regardless of the strategy that the opponent uses.

Both terms are similar but slightly different. Nash equilibrium states that nothing is gained if any of the players change their strategy while all of the other players maintain their strategy. Dominant strategy asserts that a player will choose a strategy that will lead to the best outcome regardless of the strategies that the other players have chosen. Dominant strategy can be included in Nash equilibrium, whereas a Nash equilibrium may not be the best strategy in a game.

Example of Nash Equilibrium

Imagine a game between Tom and Sam. In this simple game, both players can choose strategy A, to receive $1, or strategy B, to lose $1. Logically, both players choose strategy A and receive a payoff of $1.

If you revealed Sam’s strategy to Tom and vice versa, you see that no player deviates from the original choice. Knowing the other player’s move means little and doesn’t change either player’s behavior. Outcome A represents a Nash equilibrium.

Prisoner’s Dilemma

The prisoner’s dilemma is a common situation analyzed in game theory that can employ the Nash equilibrium. In this game, two criminals are arrested and each is held in solitary confinement with no means of communicating with the other. The prosecutors do not have the evidence to convict the pair, so they offer each prisoner the opportunity to either betray the other by testifying that the other committed the crime or cooperate by remaining silent.

If both prisoners betray each other, each serves five years in prison. If A betrays B but B remains silent, prisoner A is set free and prisoner B serves 10 years in prison, or vice versa. If each remains silent, then each serves just one year in prison.

In this example, the Nash equilibrium is for both players to betray each other. Even though mutual cooperation leads to a better outcome if one prisoner chooses mutual cooperation and the other does not, one prisoner’s outcome is worse.

The Bottom Line

The Nash equilibrium is a component of game theory that asserts that a player will continue with their chosen strategy while knowing their opponent’s strategy as they have no incentive to change course. The Nash equilibrium can be applied in a variety of real-life situations to determine what the best payoff in a scenario would be, based on your decisions as well as knowledge of your opponent’s decisions.

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

Равновесие Нэша
Концепция решения в теории игр
Связанные множества решений
Надмножества	Рационализируемость Коррелированное равновесие ε-равновесие
Подмножества	Равновесие, совершенное по подыграм Равновесие дрожащей руки Эволюционно стабильная стратегия Сильное равновесие
Факты
Авторство	Джон Нэш
Применение	Все некооперативные игры

Равнове́сие Нэ́ша — концепция решения, одно из ключевых понятий теории игр. Так называется набор стратегий в игре для двух и более игроков, в котором ни один участник не может увеличить выигрыш, изменив свою стратегию, если другие участники своих стратегий не меняют^[1]. Джон Нэш доказал существование такого равновесия в смешанных стратегиях в любой конечной игре.

История[править | править код]

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

До Нэша это было доказано только для игр с 2 участниками с нулевой суммой Джоном фон Нейманом и Оскаром Моргенштерном (1947).

Математическая формулировка[править | править код]

Допустим,  — некооперативная игра n лиц в нормальной форме, где S — набор чистых стратегий, а H — набор выигрышей. Когда каждый игрок выбирает стратегию в профиле стратегий игрок i получает выигрыш Заметьте, что выигрыш зависит от всего профиля стратегий: не только от стратегии , выбранной самим игроком i, но и от чужих стратегий , то есть всех стратегий при . Профиль стратегий является равновесием по Нэшу, если изменение своей стратегии с на не выгодно ни одному игроку , то есть для любого

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

Примеры использования понятия[править | править код]

Социология[править | править код]

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

	Актор B
1	2
Актор A	1	A: +1, B: +1	A: −1, B: +2
2	A: +2, B: −1	A: 0, B: 0

В таблице слева приведена структура действия в терминах теории игр, составленная для двух действующих субъектов (акторов). Каждый актор имеет два варианта действия, обозначенных цифрами 1 и 2. Коэффициенты вознаграждения получаемые ими при выборе определённых вариантов действия указаны в соответствующих ячейках таблицы. Предположим, что в данный момент оба актора используют действие 2, а их вознаграждения соответственно равны нулю. Выбрав действие 1, актор A ухудшит собственную ситуацию на одну позицию (A: −1, B: +2). Аналогично актор B самостоятельно выбрав вариант 1, в то время когда актор A продолжает использовать действие 2, только ухудшит свою ситуацию (A: +2, B: −1). Таким образом, несмотря на то, что оба актора понимают, что оптимальным для них была бы ситуация, когда оба они используют действие 1 (вознаграждение — A: +1, B: +1), ни у одного из них нет мотива к изменению ситуации, а равновесие становится результатом отсутствия таких мотивов. Если система уже находится в оптимальном состоянии (когда оба актора выбрали действие 1), то у обоих из них всегда будет искушение начать использовать действие 2, которое принесёт им вознаграждение за счёт другого игрока. Этот пример иллюстрирует возможность существования двух социальных состояний: устойчивого, но неоптимального (оба актора используют вариант 2); а также второго оптимального, но неустойчивого (оба актора используют вариант 1).^[2]

Политология[править | править код]

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

Экономика[править | править код]

В отрасли имеются две фирмы № 1 и № 2. Каждая из фирм может установить два уровня цен: «высокие» и «низкие». Если обе фирмы выберут высокие цены, то каждая будет иметь прибыль по 3 млн. Если обе выберут низкие, то каждая получит по 2 млн. Однако, если одна выберет высокие, а другая низкие, то вторая получит 4 млн, а первая только 1 млн. Наиболее выигрышный в сумме вариант — одновременный выбор высоких цен (сумма = 6 млн). Однако это состояние (при отсутствии картельного сговора) нестабильно из-за возможности относительного выигрыша, которая открывается перед фирмой, отступившей от этой стратегии. Поэтому обе компании с наибольшей вероятностью выберут низкие цены. Хотя этот вариант и не даёт максимального суммарного выигрыша (сумма = 4 млн), он исключает относительный выигрыш конкурента, который тот мог бы получить за счёт отступления от взаимно-оптимальной стратегии. Такая ситуация и называется «равновесием по Нэшу»^[3].

В модели олигополии Штакельберга для двух фирм-участников бескоалиционной игры можно принять, что существует две стратегии: 1. дуополист Курно (K) и дуополист Штакельберга (S), то есть S-стратег. Таким образом для двух игроков возможны следующие стратегии:

(K1;K2) (K1;S2);(K2;S1);(S1;S2). Как следует из построения модели прибыль при выборе стратегии S: , а при выборе стратегии K: , видно, что максимальный выигрыш первого игрока реализуется в ситуации (S1;K2), а второго (K1;S2). Так как эти ситуации несовместимы, то есть не могут реализоваться одновременно, то получить максимальный выигрыш оба игрока одновременно не могут. В данном случае оптимальным поведением обоих игроков будет выбор стратегии S, так как в этом случае стратегия S лучше стратегии K с точки зрения минимального возможного выигрыша. В данном случае выбор (S1;S2) является равновесием по Нэшу. Односторонее отклонение от данной стратегии автоматически уменьшает выигрыш любого из игроков, при этом суммарный выигрыш в данном типе равновесия меньше суммарного выигрыша при выборе стратегии (K1;K2) обоими игроками. Однако в условиях данной модели при отсутствии обмена информацией между игроками отклонение от равновесия по Нэшу не будет реализовано в виду повышенного риска того, что второй игрок может воспользоваться ситуацией и не выбрать стратегию K.

Военное дело[править | править код]

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

См. также[править | править код]

• Эффективность по Парето
• Парадокс Бертрана
• Эволюционно стабильная стратегия

Примечания[править | править код]

Литература[править | править код]

1. Васин А. А., Морозов  Теория игр и модели математической экономики. — М.: МГУ, 2005, 272 с. ISBN 5-317-01388-7.
2. Воробьёв Н. Н. Теория игр для экономистов-кибернетиков. — М.: Наука, 1985
3. Мазалов В. В. Математическая теория игр и приложения. — Изд-во Лань, 2010, 446 с.
4. Петросян Л. А., Зенкевич Н. А., Шевкопляс Е. В. Теория игр. — СПб: БХВ-Петербург, 2012, 432 с.

Что такое теория игр?

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

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

Настольные игры

Кедр101

Теория некооперативных игр

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

В теории некооперативных игр есть два типа игр:

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

Джон Форбс Нэш мл.

Эльке Ветциг (Elya) / CC BY-SA (http://creativecommons.org/licenses/by-sa/3.0/)

Джон Форбс Нэш мл.

Джон Форбс Нэш-младший был американским математиком, который жил с 1928 по 2015 год. Он был исследователем в Принстонском университете. Его работа была в основном в области теории игр, в которую он внес значительный вклад. В 1994 году он получил Нобелевскую премию по экономике за свои применения теории игр в экономике. Равновесие по Нэшу является частью всей теории равновесия, предложенной Нэшем.

Пример: дилемма заключенного

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

Если оба скажут правду о своей виновности, каждый получит по семь лет. Если один говорит правду, а другой лжет, то тот, кто говорит правду, получает один год тюрьмы, а другой – десять. Эта игра отображается в таблице ниже. В матрице стратегии игрока A отображаются вертикально, а стратегии игрока B – горизонтально. Выплата x, y означает, что игрок A получает x, а игрок B – y.

Матрица выплат для дилеммы заключенного

	Ложь	Говорить правду
Ложь	3,3	10,1
Говорить правду	1,10	7,7

Джулия Форсайт

Что такое равновесие по Нэшу и как его найти?

Определение равновесия по Нэшу является результатом игры, в которой ни один из игроков не хочет менять стратегию, если другие этого не сделают. Дилемма заключенного имеет одно равновесие по Нэшу, а именно 7,7, что соответствует обоим игрокам, говорящим правду. Если игрок А станет лгать, а игрок Б будет говорить правду, игрок А получит 10 лет тюрьмы, так что он не переключится. То же самое и с игроком B.

Похоже, что 3,3 – лучшее решение, чем 7,7. Однако 3,3 не является равновесием по Нэшу. Если у игроков остается 3,3, тогда, если игрок переключается с лжи на правду, он сокращает свой штраф до 1 года, если другой остается с ложью.

Игры с множественными равновесиями Нэша

Игра может иметь несколько равновесий по Нэшу. Пример показан в таблице ниже. В этом примере выплаты положительные. Так что большее число лучше.

Игра с множественными равновесиями Нэша

	Осталось	Правильно
верхний	5,4	2,3
Дно	1,7	4,9

В этой игре оба (вверху, слева) и (внизу, справа) являются равновесиями по Нэшу. Если A и B выберут (Top, Left), то A может переключиться на Bottom, но это уменьшит его выигрыш с 5 до 1. Игрок B может переключаться слева направо, но это уменьшит его выигрыш с 4 до 3.

Если игроки находятся в (Снизу, справа), игрок A может переключиться, но затем он снижает свой выигрыш с 4 до 2, а игрок B может только уменьшить свой выигрыш с 9 до 7.

Игры без равновесия по Нэшу

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

Игра без равновесия по Нэшу

	Осталось	Правильно
верхний	5,4	2,6
Дно	4,6	5,3

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

Смешанные стратегии

До сих пор мы рассматривали только чистые стратегии, то есть игрок выбирает только одну стратегию. Однако игрок также может разработать стратегию, в которой он выбирает каждую стратегию с определенной вероятностью. Например, он играет влево с вероятностью 0,4 и вправо с вероятностью 0,6.

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

Равновесия Нэша на практике

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

Теория игр в дорожном движении

	Водить машину	Стоп
Водить машину	-5, -5	2,1
Стоп	1,2	-1, -1

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

Светофор

Рафал Почтарски

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

Заключительные замечания о равновесии по Нэшу

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

© 2020 Джон

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

Пусть первый
участник имеет
стратегий, а второй –стратегий. Количество исходов равно.
Функция выигрышей первого участника
может быть задана платёжной матрицейсостоящую из элементов.
Аналогично функция выигрышей второго
участника будет задаваться матрицейсостоящую из элементовИгру можно также описать с помощью
таблицы.
В каждой клетке такой таблицы указывается
два числа, где первое число – это выигрыш
первого участника, а второе число –
выигрыш второго.

Рассмотрим пример.

Пример.
Игра «Двое
в горящем доме».
Два человека находятся в горящем доме
по разные стороны двери, которую нужно
открыть для спасения каждого из них.
Для того чтобы дверь открылась, им обоим
необходимо приложить общие усилия,
заключающиеся в том, что один должен
потянуть за ручку двери, а второй, в свою
очередь, должен её толкнуть. Запишем
эту игры в матричной форме:

первый игрок
	Толкать	Не толкать
второй игрок	Тянуть	100; 100	0; 0
Не тянуть	0; 0	0; 0

Выпишем платёжную
матрицу для первого игрока, в которой
первая строка доминирует вторую:

В платёжной матрице
второго игрока первый столбец доминирует
второй:

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

§2.2.3. Равновесие Нэша

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

Стратегии
иназываютсястратегиями
равновесными по Нэшу,
если выполняются следующие неравенства:

(2.3)

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

Пример.
Найти равновесные по Нэшу стратегии в
примере 2 (Таблица 1).

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

В игре имеется
два равновесия по Нэшу.
Как правило, равновесие по Нэшу не
является единственным.

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

Смысл смешанной
стратегии для биматричной игры будем
определять так же, как и для матричных
игр. Смешанная стратегия первого и
второго участников есть соответственно
вектора X={x₁,
x₂,…x_m}
и Y={y₁,
y₂,…,
y_n},
где
и(2.4)

Множества смешанных
стратегий будем обозначать так же, как
множества чистых стратегий – S_x
для 1-го игрока и S_y
для 2-го.

Функции выигрышей
первого и второго игроков при смешанных
стратегиях X
и Y определяются по формулам

Η₁(x,y)=∑a_ijx_iy_j,
Η₂(x,y)=∑b_ijx_iy_j

(2.5)

Равновесные по
Нэшу смешанные стратегии будем обозначать
X^*
и Y^*
соответственно. Вопрос существования
равновесия по Нэшу решается следующей
теоремой, доказанной Дж. Нэшем.

Теорема о
равновесии по Нэшу.
В любой биматричной игре существует,
по крайней мере, одно равновесие Нэша.
(Без доказательства).

Замечание.
Это могут быть равновесия в чистых или
смешанных стратегиях.

В общем случае
биматричной игры нахождение смешанных
равновесий является сложной задачей,
но для матриц размера 2×2
решение в смешанных стратегиях найти
несложно.

Рассмотрим
биматричную игру, в которой каждый игрок
имеет две чистые стратегии. Смешанные
стратегии игроков будем обозначать
x={x₁,
x₂}
и y={y₁,
y₂}
соответственно, где 0≤x_i≤1,
0≤y_j≤1,
x₁+x₂=1,
y₁+y₂=1.
Обозначая элементы платежных матриц
1-го и 2-го игроков a_ij
и b_ij
соответственно, получим Таблицу3 и
Таблицу 4 для расчета функций выигрыша.

Таблица3
Таблица 4

	y1	y2
x1	a11	a 12
x2	a 21	a 22

	y1	y2
x1	b11	b 12
x2	b 21	b 22

Функция выигрыша
1-го игрока будет равна

Η₁(x,y)=
x₁(a₁₁
y₁+
a
₁₂
y₂)+
x₂(a
₂₁
y₁+
a
₂₂
y₂),

подставляя x₂=1-
x₁
и y₂=1-
y₁,
получим

Η₁(x,y)=
x₁(y₁(a₁₁+
a
₂₂–
a
₁₂-a
₂₁)+
a
₁₂-a
₂₂)+
y₁(a
₂₁–
a
₂₂)+
a
₂₂.

Обозначим x^*={x₁^*,
x₂^*}
и y
^*={
y
₁^*,
y
₂^*}
равновесные по Нэшу стратегии игроков
и найдем функцию выигрыша 1-го игрока,
при условии, что 2-й игрок применит
равновесную по Нэшу стратегию y^*,
а 1-й игрок применит произвольную
смешанную стратегию x

Η₁(x,y^*)=
x₁(y₁^*(a₁₁+
a
₂₂–
a
₁₂-a
₂₁)+
a
₁₂-a
₂₂)+
y₁^*(a
₂₁–
a
₂₂)+
a
₂₂.
(2.6)

Если 2-й игрок
применит равновесную по Нэшу стратегию
y^*,
и 1-й игрок применит равновесную по Нэшу
стратегию x^*,
то функция выигрыша 1-го игрока будет
равна

Η₁(x^*,y^*)=
x₁^*(y₁^*(a₁₁+
a
₂₂–
a
₁₂-a
₂₁)+
a
₁₂-a
₂₂)+
y₁^*(a
₂₁–
a
₂₂)+
a
₂₂.
(2.7)

Согласно определению
равновесия по Нэшу для всех смешанных
стратегий x
должно выполняться неравенство

Η₁(x^*,y^*)≥
Η₁(x,y^*).

(2.8)

Подставляя в
неравенство Η₁(x^*,y^*)-
Η₁(x,y^*)≥0
функции из уравнений (4) и (5), получим
неравенство

(x₁^*–
x₁)(
y₁^*(a₁₁+
a
₂₂– a
₁₂-a
₂₁)+ a
₁₂-a
₂₂)
≥0, (2.9)

которое должно
выполняться для всех значений x₁
из отрезка [0;1].

Интерес представляет
случай, когда равновесная по Нэшу
стратегия x^*
не совпадает ни с одной чистой стратегией,
то есть, когда x₁^*
удовлетворяет строгому неравенству 0<
x₁^*<1.
В этом случае неравенство (2.9) будет
верно для всех x₁
из отрезка [0;1] тогда и только тогда,
когда

y₁^*(a₁₁+
a
₂₂– a
₁₂-a
₂₁)+ a
₁₂-a
₂₂=0.
(2.10)

Уравнение (2.10) дает
значение y₁^*,
при котором существует смешанная
стратегия x^*,
не совпадающая с чистыми стратегиями
1-го игрока.

Аналогично, для
всех смешанных стратегий y
2-го игрока должно выполняться неравенство

Η₂(x^*,y^*)≥
Η₂(x^*,y)

(2.11)

Определяя функции
Η₂(x^*,y)
и Η₂(x^*,y^*)
из таблицы 2, получим условие, при котором
2-й игрок имеет равновесную смешанную
стратегию y^*.
не совпадающую с его чистыми стратегиями

x
₁^*(
b ₁₁+
b ₂₂–
b ₁₂–
b ₂₁)+
b ₂₁–
b ₂₂=0.
(2.12)

Если уравнения
(2.10) или (2.12) не имеют решений на отрезке
[0;1], то в игре существуют только равновесия
в чистых стратегиях, существование
которых непосредственно следует из
неравенств (2.9) и аналогичного неравенства
для 2-го игрока.

Пример.Отыскать равновесие
Нэша в чистых, либо смешанных стратегиях
в игре «орёл-решка».

Таблица 5

	первый игрок
		орёл	решка
второй игрок	орёл	1; -1	-1; 1
решка	-1; 1	1; -1

Решение.
Запишем
матрицу игры:

Таблица
6

Очевидно, что
равновесия по Нэшу в чистых стратегиях
не существует. Будем искать решение в
смешанных стратегияхx={x₁,
x₂}
и y={y₁,
y₂}
соответственно, где 0≤x_i≤1,
0≤y_j≤1,
x₁+x₂=1,
y₁+y₂=1.
Найдем функцию выигрыша 1-го игрока

Η₁(x,y)=
x₁y₁–
x₁y₂–
x₂y₁+
x₂y₂=
4x₁y₁-2
x₁-2y₁+1=
x₁(4y₁-2)
-2y₁+1.

Для равновесных
по Нэшу стратегий x^*={x₁^*,
x₂^*}
и y^*={
y
₁^*,
y
₂^*}
найдем значение функции выигрыша будет
равно

Η₁(x^*,y^*)=
x₁^*(4y₁^*-2)
-2y₁^*+1

Если 2-й игрок
применит равновесную по Нэшу стратегию
y^*,
а 1-й игрок произвольную смешанную
стратегию x, то функция выигрыша 1-го
игрока составит значение

Η₁(x,y^*)=
x₁
(4y₁^*-2)
-2y₁^*+1.

Из условия равновесия
Η₁(x^*,y^*)≥
Η₁(x,y^*)
следует неравенство

(x₁^*–
x₁)
(4y₁^*-2)
≥0

для всех x₁
из отрезка [0;1]. Поскольку в игре нет
равновесия в чистых стратегиях, то x₁^*≠0
и x₁^*≠1,
то множитель (x₁^*–
x₁)
может быть и положительным и отрицательным
в зависимости от x₁.
Следовательно, последнее неравенство
выполняется лишь при условии, что второй
множитель равен нулю, то есть 4y₁^*-2=0.
Откуда находим y
₁^*=0,5
и y
₂^*=0,5.

Аналогично находим
равновесную по Нэшу стратегию 1-го игрока
x₁^*=
x₂^*=0,5.
Значения игры для 1-го и 2-го игроков
равны Η₁(x^*,y^*)=
Η₂(x^*,y^*)=0,5.

Пример.
«Семейный
спор». Муж
и жена собираются провести вместе
выходной день. Муж предпочитает пойти
на футбол, а жена на балет. Выигрыши мужа
и жены в зависимости от принятых стратегий
приведены в таблице:

Таблица 7

	жена
		Футбол	балет
муж	футбол	2; 1	0,5; 0,5
балет	0; 0	1; 2

Решение.
Выпишем общую матрицу игры.

В этой игре
существует два равновесия Нэша в чистых
стратегиях. Кроме того, можно показать,
что существует равновесие Нэша и в
смешанных стратегиях. Для этого найдем
платежную функцию 1-го игрока (мужа) для
смешанных стратегий x={x₁,
x₂}
и y={y₁,
y₂}.

Η₁(x,y)=2x₁y₁+0,5
x₁y₂+x₂y₂=1,5
x₁y₁-0,5
x₁+
y₁-1=
x₁(2,5
y₁-0,5)
+1- y₁.

Соответственно
получаем

Η₁(x^*,y^*)-
Η₁(x,y^*)=(x₁^*–
x₁)
(2,5y₁^*-0,5).

Неравенство
Η₁(x^*,y^*)≥
Η₁(x,y^*)
будет верно для всех x₁
из отрезка [0;1] и 0< x₁^*<1,
если 2,5y₁^*-0,5=0,
откуда y
₁^*=1/5
и y
₂^*=4/5.

Аналогично, для
2-го игрока (жены) получаем платежную
функцию

Η₂(x,y)=
x₁y₁+0,5
x₁y₂+2x₂y₂=2,5x₁y₁-2y₁-1,5x₁+2.

Тогда Η₂(x^*,y^*)-
Η₂(x^*,y)=(
y₁^*–
y₁)
(2,5 x
₁^*-2).

Неравенство
Η₂(x^*,y^*)≥Η₂(x^*,y)
будет верно для равновесной смешанной
стратегии y^*={y₁^*,y₂^*}
и произвольной стратегии y={y₁,
y₂}
при условии, что 2,5x₁^*-2=0,
откуда находим x₁^*=4/5,
x₂^*=1/5
(муж выбирает футбол с вероятностью 4/5
и балет с вероятностью 1/5).

Аналогично находим
y ₁^*=1/5,
y ₂^*=4/5.
Функции выигрыш игроков в смешанном
равновесии будут равны Η₁(x^*,y^*)=
Η₂(x^*,y^*)=4/5.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Открыть эту статью в PDF

Определение

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

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

Математическая запись равновесия Нэша

Математически равновесие Нэша можно записать следующим образом:

где:
S_i — набор всех возможных стратегий для игрока i,
Игрок i = 1, …, N,
s^* = (s^*_i, s^*_-i) — профиль стратегии или набор из одной стратегии для каждого игрока,
s^*_-i — обозначает (N – 1) стратегии всех игроков, кроме i-го игрока,
u_i (s^*_i, s^*_-i) — i-ый игрок с выигрышем в зависимости от стратегии.

Пример равновесия Нэша

Допустим, играют два игрока: X и Y. Каждый может выбрать стратегию А, чтобы получить 1 рубль, или стратегию Б, чтобы проиграть 1 рубль. Следуя логике оба игрока, захотят выбрать стратегию А и получить 1 рубль: (1; 1).

Если один игрок, например, игрок Y, выбирает стратегию Б, то он проигрывает 1 рубль, а игрок X выбирает стратегию А, то он выигрывает 1 рубль, и это можно будет записать, как (-1; 1). Точно также будет наоборот, если игрок Y выберет стратегию А, а игрок X выберет стратегию Б. Если оба игрока выбирают стратегию Б, то они оба проигрывают, то есть остаются в нулях: (0; 0).

Дилемма заключенного и равновесие Нэша

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

Если оба заключенных предают друг друга, то каждый из них получает 5 лет тюрьмы: (-5; -5).

Если заключенный № 1 предает заключенного № 2, а заключенный № 2 по-прежнему хранит молчание, то он окажется в худшем положении и получит 10 лет тюрьмы. А заключенный № 1 получит всего 1 год тюрьмы: (-10; -1).

Если оба заключенных молчат и не признаются, то каждый из них получит только 1 год тюрьмы: (-1; -1).

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

Важность равновесия Нэша

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

Ограничения равновесия Нэша

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

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

История равновесия Нэша

Термин «равновесие Нэша» появился в честь американского математика Джона Форбса Нэша-младшего. В 1950 году Джон Нэш защитил диссертацию на тему некооперативных игр, содержащую определение и свойства равновесия Нэша. В диссертации было всего 28 страниц, возраст диссертанта — 22 года. Позднее, в 1994 году, данный вклад в теорию игр принес Джону Нэшу Нобелевскую премию в области экономических наук.

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

Основные работы Джона Нэша, относящиеся к концепции равновесия Нэша:

• «Точки равновесия в играх n-персон», 1950
• «Проблема торга», 1950
• «Некооперационные игры», 1951
• «Кооперативные игры для двух человек», 1953