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.
Key Takeaways
- The Nash equilibrium is a decision-making theorem within game theory that states a player can achieve the desired outcome by not deviating from their initial strategy.
- In the Nash equilibrium, each player’s strategy is optimal when considering the decisions of other players. Every player wins because everyone gets the outcome that they desire.
- The prisoner’s dilemma is a common game theory example and one that adequately showcases the effect of the Nash equilibrium.
- The Nash equilibrium is often discussed in conjunction with dominant strategy, which states 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.
- The Nash equilibrium does not always mean that the most optimal strategy is chosen.
The Nash Equilibrium
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.
All models of game theory only work if the players involved are “rational agents,” meaning that they desire specific outcomes, operate in attempting to choose the most optimal outcome, incorporate uncertainty in their decisions, and are realistic in their options.
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.
Julie Bang / Investopedia
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.
What is a Nash equilibrium in game theory?
Nash equilibrium in game theory is a situation in which a player will continue with their chosen strategy, having no incentive to deviate from it, after taking into consideration the opponent’s strategy.
How do you find Nash equilibrium?
To find the Nash equilibrium in a game, one would have to model out each of the possible scenarios to determine the results and then choose what the optimal strategy would be. In a two-person game, this would take into consideration the possible strategies that both players could choose. If neither player changes their strategy knowing all of the information, a Nash equilibrium has occurred.
Why is Nash equilibrium important?
Nash equilibrium is important because it helps a player determine the best payoff in a situation based on not only their decisions but also the decisions of other parties involved. Nash equilibrium can be utilized in many facets of life, from business strategies to selling a house, from war to social sciences, and so on.
How do you calculate Nash equilibrium?
There is not a specific formula to calculate Nash equilibrium. It can be determined by modeling out different scenarios within a given game to determine the payoff of each strategy and which would be the optimal strategy to choose.
What are the limitations of Nash equilibrium?
The primary limitation of Nash equilibrium is that it requires an individual to know their opponent’s strategy. A Nash equilibrium can only occur if a player chooses to remain with their current strategy if they know their opponent’s strategy.
In most cases, such as in war—whether that be a military war or a bidding war—an individual rarely knows the opponent’s strategy or what they want the outcome to be. Unlike dominant strategy, the Nash equilibrium doesn’t always lead to the most optimal outcome. It just means that an individual chooses the best strategy based on the information they have.
Furthermore, in multiple games played with the same opponents, the Nash equilibrium does not take into consideration past behavior, which often predicts future behavior.
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.
|
16.2. Статические игры с полной информацией |
633 |
Ситуации, когда в игре существует равновесие в доминирующих стратегиях, достаточно редки. И далеко не во всех играх можно найти решение, отбрасывая строго доминируемые стратегии. Соответствующий пример игры представлен в Таблице 16.8.
Второй игрок выберет стратегию A, если предполагает, что первый выберет стратегию Z; в то же время стратегия B для него предпочтительнее в случае, если первый выберет Y.
Таблица 16.8.
|
A |
B |
C |
|
|
X |
3 |
0 |
1 |
|
2 |
2 |
3 |
|
|
Y |
4 |
6 |
2 |
|
1 |
4 |
2 |
|
|
Z |
7 |
2 |
8 |
|
3 |
1 |
1 |
|
Естественно предположить, что при отсутствии у всех игроков доминирующих стратегий, выбор каждого игрока зависит от ожиданий того, какими будут выборы других. Далее мы рассмотрим концепцию решения, основанную на этой идее.
16.2.4Равновесие по Нэшу
Кроме ситуаций, рассмотренных в предыдущем разделе, бывают ситуации14, которые естественно моделировать, исходя из следующих предположений:
игроки при принятии решений ориентируются на предполагаемые действия партнеров;
ожидания являются равновесными (совпадают с фактически выбранными партнерами действиями).
Если считать, что все игроки рациональны, так что каждый выбирает стратегию, дающую ему наибольший выигрыш при данных ожиданиях, то эти предположения приводят к концепции решения, называемой равновесием Нэша. В равновесии у каждого игрока нет оснований пересматривать свои ожидания.
Формально равновесие Нэша определяется следующим образом.
Определение 90:
Набор стратегий x X является равновесием Нэша15, если
1)стратегия xi каждого игрока является наилучшим для него откликом на ожидаемые им стратегии других игроков xe−i :
ui(xi , xe−i) = max ui(xi, xe−i) i = 1, . . . , n;
xi Xi
14Можно представить себе популяцию игроков типа А (скажем, кошки) и игроков типа Б (скажем, мышки). Игрок типа А при встрече с игроком типа Б имеет оправданные своим или чужим опытом ожидания относительно поведения партнера типа Б, и заранее на них ориентируется (и наоборот). Однако это не единственный тип ситуаций, в которых рассматриваемый подход является адекватным.
15Американский математик Джон Нэш получил Нобелевскую премию по экономике в 1994 г. вместе с Дж. Харшаньи и Р. Зельтеном «за новаторский анализ равновесий в теории некооперативных игр». Концепция равновесия была предложена в следующих статьях: J. F. Nash: Equilibrium Points in N-Person Games,
Proceedings of the National Academy of Sciences of the United States of America 36 (1950): 48–49; J. F. Nash: NonCooperative Games, Annals of Mathematics 54 (1951): 286–295 (рус. пер. Дж. Нэш: Бескоалиционные игры, в кн. Матричные игры, Н. Н. Воробьев (ред.), М.: Физматгиз, 1961: 205–221).
Следует оговориться, что сам Нэш не вводил в определение ожиданий. Исходное определение Нэша совпадает с тем свойством, о котором говорится далее.
|
16.2. Статические игры с полной информацией |
634 |
2) ожидания совпадают с фактически выбираемыми стратегиями:
xe−i = x−i i = 1, . . . , n
Заметим, что при использовании равновесия Нэша для моделирования игровых ситуаций вопросы о том, знают ли игроки цели партнеров, знают ли они о рациональности партнеров, умеют ли их просчитывать, и т. д., отходят на второй план. Способ формирования ожиданий выносится за рамки анализа; здесь важно только то, что ожидания являются равновесными.
Но если при анализе равновесия Нэша не важно, знает ли игрок цели других игроков, то может возникнуть сомнение в правомерности рассмотрения концепции Нэша в контексте игр с полной информацией. Все дело в том, что термин «полная информация» в теории игр имеет довольно узкое значение. Он фактически подразумевает только полноту сведений о типах партнеров (термин «тип игрока», разъясняется в параграфе, посвященном байесовским играм).
Как легко видеть, приведенное определение равновесия Нэша эквивалентно следующему свойству, которое обычно и используется в качестве определения:
Набор стратегий x X является равновесием Нэша, если стратегия xi каждого игрока является наилучшим для него откликом на стратегии других игроков x−i :
ui(xi , x−i) = max ui(xi, x−i) i = 1, . . . , n
xi Xi
Это свойство можно также записать в терминах так называемых функций (отображений) отклика.
Определение 91:
Отображение отклика i-го игрока,
Ri : X−i 7→Xi
сопоставляет каждому набору стратегий других игроков, x−i X−i , множество стратегий i-го игрока, каждая из которых является наилучшим откликом на x−i . Другими словами,
ui(yi, x−i) = max ui(xi, x−i) x−i X−i, yi Ri(x−i) xi Xi
Введение отображений отклика позволяет записать определение равновесия Нэша более компактно: набор стратегий x X является равновесием Нэша, если
xi Ri(x−i) i = 1, . . . , n
Если отклик каждого игрока однозначен (является функцией), то множество равновесий Нэша совпадает с множеством решений системы уравнений:
xi = Ri(x−i) i = 1, . . . , n.
В Таблице 16.8 отображения отклика игроков изображены подчеркиванием выигрышей, соответствующих оптимальным действиям. Равновесие Нэша в данной игре — клетка (B, Y), поскольку выигрыши обоих игроков в ней подчеркнуты.
Проиллюстрируем использование функций отклика на примере игры, в которой игроки имеют континуум стратегий.
|
16.2. Статические игры с полной информацией |
635 |
Игра 5. «Международная торговля»
Две страны одновременно выбирают уровень таможенных пошлин, τi . Объем торговли между странами16, x, зависит от установленных пошлин как
x = 1 − τ1 − τ2
Цель каждой страны — максимизировать доходы ui = τix.
J
Максимизируем выигрыш 1-й страны,
τ1(1 − τ1 − τ2)
по τ1 считая фиксированным уровень пошлины, установленный 2-й страной. Условие первого порядка имеет вид
1 − 2τ1 − τ2 = 0
Поскольку максимизируемая функция строго вогнута, то условие первого порядка соответствует глобальному максимуму.
Условие первого порядка для задачи максимизации выигрыша 2-й страны находится аналогично:
1 − τ1 − 2τ2 = 0
Решив систему из двух линейных уравнений, найдем равновесие Нэша:
τ1 = τ2 = 1/3
Оптимальный отклик 1-й страны на уровень таможенной пошлины, установленной 2-й страной описывается функцией
τ1(τ2) = 1 − τ2
2
Аналогично, функция отклика 2-й страны имеет вид
τ2(τ1) = 1 − τ1 2
Чтобы найти равновесие Нэша, требуется решить систему уравнений
τ1(τ2 ) = τ1 ,
τ2(τ ) = τ .
1 2
Графически поиск равновесия Нэша показан не Рис. 16.3. Точки, лежащие на кривых оптимального отклика τ1(τ2) и τ2(τ1), характеризуются тем, что в них касательные к кривым безразличия игроков параллельны соответствующей оси координат. Напомним, что кривой безразличия называют множество точек, в которых полезность рассматриваемого индивидуума одна и та же (ui(x) = const). Равновесие находится как точка пересечения кривых отклика.
Преимущество использования концепции равновесия Нэша состоит в том, что можно найти решение и в тех играх, в которых отбрасывание доминируемых стратегий не позволяет этого сделать. Однако сама концепция может показаться более спорной, поскольку опирается на сильные предположения о поведении игроков.
Связь между введенными концепциями решений описывается следующими утверждения-
ми.
16В этой игре мы для упрощения не делаем различия между экспортом и импортом.
|
16.2. Статические игры с полной информацией |
636 |
|
1 |
τ2 |
|||
|
τ1 |
(τ2) |
|||
|
Точка |
равновесия |
|||
|
Нэша |
||||
|
1 |
||||
|
2 |
||||
|
1 |
τ2(τ1) |
|||
|
3 |
||||
|
τ1 |
||||
|
1 |
1 |
1 |
||
|
3 |
2 |
|||
Рис. 16.3. Равновесие Нэша в игре «Международная торговля»
Теорема 151:
Если x = (x1, . . . , xm) — равновесие Нэша в некоторой игре, то ни одна из составляющих его стратегий не может быть отброшена в результате применения процедуры последовательного отбрасывания строго доминируемых стратегий. 
Обратная теорема верна в случае единственности.
Теорема 152:
Если в результате последовательного отбрасывания строго доминируемых стратегий у каждого игрока остается единственная стратегия, xi , то x = (x1, . . . , xm) — равновесие Нэша в этой игре. 
Доказательства этих двух утверждений даны в Приложении B (с. 641). Нам важно здесь, что концепция Нэша не входит в противоречие с идеями рациональности, заложенной в процедуре отбрасывания строго доминируемых стратегий.
По-видимому, естественно считать, что разумно определенное равновесие, не может быть отброшено при последовательном отбрасывании строго доминируемых стратегий. Первую из теорем можно рассматривать как подтверждение того, что концепция Нэша достаточно разумна. Отметим, что данный результат относится только к строгому доминированию. Можно привести пример равновесия Нэша с одной или несколькими слабо доминируемыми стратегиями (см. напр. Таблицу 16.11 на с. 652).
16.2.5Равновесие Нэша в смешанных стратегиях
Нетрудно построить примеры игр, в которых равновесие Нэша отсутствует. Следующая игра представляет пример такой ситуации.
Игра 6. «Инспекция»
В этой игре первый игрок (проверяемый) поставлен перед выбором — платить или не платить подоходный налог. Второй — налоговой инспектор, решает, проверять или не проверять именно этого налогоплательщика. Если инспектор «ловит» недобросовестного налогоплательщика, то взимает в него штраф и получает поощрение по службе, более чем компенсирующее его издержки; в случае же проверки исправного налогоплательщика, инспектор, не получая поощрения, тем не менее несет издержки, связанные с проверкой. Матрица выигрышей представлена в Таблице 16.9.
J
|
16.2. Статические игры с полной информацией |
637 |
||||||||||
|
Таблица 16.9. |
|||||||||||
|
Инспектор |
|||||||||||
|
проверять |
не проверять |
||||||||||
|
нарушать |
1 |
0 |
|||||||||
|
−1 |
1 |
||||||||||
|
Проверяемый |
−1 |
0 |
|||||||||
|
не нарушать |
0 |
0 |
|||||||||
Если инспектор уверен, что налогоплательщик выберет не платить налог, то инспектору выгодно его проверить. С другой стороны, если налогоплательщик уверен, что его проверят, то ему лучше заплатить налог. Аналогичным образом, если инспектор уверен, что налогоплательщик заплатит налог, то инспектору не выгодно его проверять, а если налогоплательщик уверен, что инспектор не станет его проверять, то он предпочтет не платить налог. Оптимальные отклики показаны в таблице подчеркиванием соответствующих выигрышей. Очевидно, что ни одна из клеток не может быть равновесием Нэша, поскольку ни в одной из клеток не подчеркнуты одновременно оба выигрыша.
В подобной игре каждый игрок заинтересован в том, чтобы его партнер не смог угадать, какую именно стратегию он выбрал. Этого можно достигнуть, внеся в выбор стратегии элемент неопределенности.
Те стратегии, которые мы рассматривали раньше, принято называть чистыми стратегиями. Чистые стратегии в статических играх по сути дела совпадают с действиями игроков. Но в некоторых играх естественно ввести в рассмотрение также смешанные стратегии. Под смешанной стратегией понимают распределение вероятностей на чистых стратегиях. В частном случае, когда множество чистых стратегий каждого игрока конечно,
Xi = {x1i , . . . , xni i }
(соответствующая игра называется конечной, ), смешанная стратегия представляется вектором вероятностей соответствующих чистых стратегий:
µi = (µ1i , . . . , µni i )
Обозначим множество смешанных стратегий i-го игрока через Mi :
n o
Mi = µi µki > 0, k = 1, . . . , ni; µ1i + · · · + µni i = 1
Как мы уже отмечали, стандартное предположение теории игр (как и экономической теории) состоит в том, что если выигрыш — случайная величина, то игроки предпочитают действия, которые приносят им наибольший ожидаемый выигрыш. Ожидаемый выигрыш i-го игрока, соответствующий набору смешанных стратегий всех игроков, (µ1, . . . , µm), вычисляется по формуле
|
U(µi, µ−i) = |
n1 |
nm |
|
· · · |
µ1ki · · · µmkm ui(x1ki , . . . , xmkm ) |
|
|
X1 |
X |
|
|
k =1 |
km=1 |
Ожидание рассчитывается в предположении, что игроки выбирают стратегии независимо (в статистическом смысле).
Смешанные стратегии можно представить как результат рандомизации игроком своих действий, то есть как результат их случайного выбора. Например, чтобы выбирать каждую из двух возможных стратегий с одинаковой вероятностью, игрок может подбрасывать монету.
|
16.2. Статические игры с полной информацией |
638 |
Эта интерпретация подразумевает, что выбор стратегии зависит от некоторого сигнала, который сам игрок может наблюдать, а его партнеры — нет17. Например, игрок может выбирать стратегию в зависимости от своего настроения, если ему известно распределение вероятностей его настроений, или от того, с какой ноги он в этот день встал18.
Определение 92:
Набор смешанных стратегий µ = (µ1, . . . , µm) является равновесием Нэша в смешанных стратегиях, если
1)стратегия µi каждого игрока является наилучшим для него откликом на ожидаемые им стратегии других игроков µe−i :
U(µi , µe−i) = max U(µi, µe−i) i = 1, . . . , n;
µi Mi
2) ожидания совпадают с фактически выбираемыми стратегиями:
µe−i = µ−i i = 1, . . . , n.
Заметим, что равновесие Нэша в смешанных стратегиях является обычным равновесием Нэша в так называемом смешанном расширении игры, т. е. игре, чистые стратегии которой являются смешанными стратегиями исходной игры.
Найдем равновесие Нэша в смешанных стратегиях в Игре 16.2.5.
Обозначим через µ вероятность того, что налогоплательщик не платит подоходный налог,
ачерез ν — вероятность того, что налоговой инспектор проверяет налогоплательщика.
Вэтих обозначениях ожидаемый выигрыш налогоплательщика равен
U1(µ, ν) = µ[ν · (−1) + (1 − ν) · 1] + (1 − µ)[ν · 0 + (1 − ν) · 0] =
=µ(1 − 2ν),
аожидаемый выигрыш инспектора равен
U2(µ, ν) = ν[µ · 1 + (1 − µ) · (−1)] + (1 − µ)[µ · 0 + (1 − µ) · 0] = = ν(2µ − 1)
Если вероятность проверки мала (ν < 1/2), то налогоплательщику выгодно не платить налог, т. е. выбрать µ = 1. Если вероятность проверки велика, то налогоплательщику выгодно заплатить налог, т. е. выбрать µ = 0. Если же ν = 1/2, то налогоплательщику все равно, платить налог или нет, он может выбрать любую вероятность µ из интервала [0, 1]. Таким образом, отображение отклика налогоплательщика имеет вид:
|
µ(ν) = |
1, |
если ν < 1/2 |
|
[0, 1] , |
если ν = 1/2 |
|
|
0, |
если ν > 1/2. |
|
Рассуждая аналогичным образом, найдем отклик налогового инспектора:
0, если µ < 1/2
ν(µ) = [0, 1] , если µ = 1/2
1, если µ > 1/2.
17Если сигналы, наблюдаемые игроками, статистически зависимы, то это может помочь игрокам скоординировать свои действия. Это приводит к концепции коррелированного равновесия.
18Впоследствии мы рассмотрим, как можно достигнуть эффекта рандомизации в рамках байесовского равновесия.
|
16.2. Статические игры с полной информацией |
639 |
Графики отображений отклика обоих игроков представлены на Рис. 16.4. По осям на этой диаграмме откладываются вероятности (ν и µ соответственно). Они имеют единственную общую точку (1/2, 1/2). Эта точка соответствует равновесию Нэша в смешанных стратегиях. В этом равновесии, как это всегда бывает в равновесиях с невырожденными смешанными стратегиями (то есть в таких равновесиях, в которых ни одна из стратегий не выбирается с вероятностью 1), каждый игрок рандомизирует стратегии, которые обеспечивают ему одинаковую ожидаемую полезность. Вероятности использования соответствующих чистых стратегий, выбранные игроком, определяются не структурой выигрышей данного игрока, а структурой выигрышей его партнера, что может вызвать известные трудности с интерпретацией данного решения.
ν
ν(µ) 1 
µ(ν)
1
2
µ
Рис. 16.4. Отображения отклика в игре «Инспекция»
В отличие от равновесия в чистых стратегиях, равновесие в смешанных стратегиях в конечных играх существует всегда19, что является следствием следующего общего утверждения.
Теорема 153:
Предположим, что в игре G = hI, {Xi}i I , {ui}i I i у любого игрока множество стратегий Xi непусто, компактно и выпукло, а функция выигрыша ui(·) вогнута по xi и непрерывна. Тогда в игре G существует равновесие Нэша (в чистых стратегиях). 
Существование равновесия Нэша в смешанных стратегиях в играх с конечным числом чистых стратегий является следствием того, что равновесие в смешанных стратегиях является равновесием в чистых стратегиях в смешанном расширении игры.
Теорема 154 (Следствие (Теорема Нэша)):
Равновесие Нэша в смешанных стратегиях существует в любой конечной игре.
Заметим, что существование в игре равновесия в чистых стратегиях не исключает существования равновесия в невырожденных смешанных стратегиях.
Рассмотрим в Игре 16.2.1 «Выбор компьютера» случай, когда выгоды от совместимости значительны, т. е. a < c и b < c. В этом варианте игры два равновесия в чистых стратегиях: (IBM, IBM) и (Mac, Mac). Обозначим µ и ν вероятности выбора компьютера IBM PC первым и вторым игроком соответственно. Ожидаемый выигрыш 1-го игрока равен
U1(µ, ν) = µ[ν · (a + c) + (1 − ν) · a] + (1 − µ)[ν · 0 + (1 − ν) · c] = = µ[ν · 2c − (c − a)] + (1 − ν)c
19Этот результат был доказан Нэшем в статье 1950-го года, цитируемой в сноске 15.
|
16.2. Статические игры с полной информацией |
640 |
а его отклик имеет вид
0,
µ(ν) = [0, 1] ,
1,
Ожидаемый выигрыш 2-го игрока равен
если ν < (c − a)/2c
если ν = (c − a)/2c
если ν > (c − a)/2c.
U2(µ, ν) = ν[µ · c + (1 − µ) · 0] + (1 − ν)[µ · b + (1 − µ) · (b + c)] =
= ν[µ · 2c − (b + c)] + b + (1 − µ)c
а его отклик имеет вид
0,
ν(µ) = [0, 1] ,
1,
если µ < (b + c)/2c
если µ = (b + c)/2c
если µ > (b + c)/2c.
Графики отображений отклика и точки, соответствующие трем равновесиям изображены на Рис. 16.5. Как видно, в рассматриваемой игре кроме двух равновесий в чистых стратегиях имеется одно равновесие в невырожденных смешанных стратегиях. Соответствующие вероятности равны
µ = b + c и ν = c − a
2c 2c
ν
ν(µ) 1 
µ(ν)
c−a
2c
µ
Рис. 16.5. Случай, когда в игре «Выбор компьютера» существует три равновесия, одно из которых — равновесие в невырожденных смешанных стратегиях
Приложение A
??Теорема повторяется, номер обновляется, ссылки на это приложение нет. Можно поменять местами A и B
Теорема 155:
Предположим, что в игре G = hI, {Xi}i I , {ui0}i I i у любого игрока множество стратегий Xi непусто, компактно и выпукло, а функция выигрыша ui(·) вогнута по xi и непрерывна. Тогда существует равновесие Нэша. 
Доказательство: Докажем, что отображение отклика, Ri(·), каждого игрока полунепрерывно сверху и его значение при каждом x−i X−i непусто и выпукло. Непустота следует из теоремы Вейерштрасса (непрерывная функция на компакте достигает максимума).
16.2. Статические игры с полной информацией
Докажем выпуклость. Пусть z0 , z00 Ri(x−i). Очевидно, что u(z0, x−i) = u(z00, x−i вогнутости по xi функции ui(·) следует, что при α [0, 1]
u(αz0 + (1 − α)z00, x−i) > αu(z0, x−i) + (1 − α)u(z00, x−i) =
= u(z0, x−i) = u(z00, x−i)
Поскольку функция ui(·) достигает максимума в точках z0 и z00 , то строгое неравенство
невозможно. Таким образом,
αz0 + (1 − α)z00 Ri(x−i)
Докажем теперь полунепрерывность сверху отображения Ri(·). Рассмотрим последовательность xni сходящуюся к x¯i и последовательность xn−i сходящуюся к x¯−i , причем xni Ri(xn−i). Заметим, что в силу компактности множеств Xjx¯i Xi и x¯−i X−i . Нам нужно доказать, что x¯i Ri(x¯−i). По определению отображения отклика
u(xni , xn−i) > u(xi, xn−i) xi Xi, n
Из непрерывности функции ui(·) следует, что
u(¯xi, x¯−i) > u(xi, x¯−i) xi Xi
Тем самым, по введенному выше определению отображения отклика, x¯i Ri(x¯−i). Опираясь на доказанные только что свойства отображения Ri(·) и на теорему Какутани,
докажем существование равновесия по Нэшу, то есть такого набора стратегий x X , для
которого выполнено
xi Ri(x−i) i = 1, . . . , n
Определим отображение R(·) из X в X следующим образом:
R(x) = R1(x−1) × · · · × Rn(x−n)
Отметим, что это отображение удовлетворяет тем же свойствам, что и каждое из отображений Ri(·), так как является их декартовым произведением.
Отображение R(·) и множество X удовлетворяют свойствам, которые необходимы для выполнения теоремы Какутани. Таким образом, существует неподвижная точка отображения
R(·):
x R(x )
|
Очевидно, что точка x есть равновесие по Нэшу. |
Приложение B
В этом приложении мы формально докажем утверждения о связи между равновесием Нэша и процедурой последовательного отбрасывания строго доминируемых стратегий.
Сначала определим формально процедуру последовательного отбрасывания строго доминируемых стратегий. Пусть исходная игра задана как
G = hI, {Xi}I , {ui}I i.
Определим последовательность игр {G[t]}t=0,1,2,… , каждая из которых получается из последующей игры отбрасыванием строго доминируемых стратегий. Игры отличаются друг от друга множествами допустимых стратегий:
G[t] = hI, {Xi[t]}I , {ui}I i
|
16.2. Статические игры с полной информацией |
642 |
Процедура начинается с G[0] = G.
Множество допустимых стратегий i-го игрока на шаге t + 1 рассматриваемой процедуры берется равным множеству не доминируемых строго стратегий i-го игрока в игре t-го шага. Множества не доминируемых строго стратегий будем обозначать через NDi (см. определение строго доминируемых стратегий (Определение 89, с. 631)). Формально
NDi = xi Xi 
yi Xi : ui(yi, x−i) > ui(xi, x−i) x−i X−i
Таким образом, можно записать шаг рассматриваемой процедуры следующим образом:
Xi[t+1] = NDi[t]
где NDi[t] — множество не доминируемых строго стратегий в игре G[t] .
Приведем теперь доказательства Теорем 151 и 152 (с. 636). Теорема 151 утверждает следующее:
: Если x = (x1, . . . , xm) — равновесие Нэша в некоторой игре, то ни одна из стратегий не может быть отброшена в результате применения процедуры последовательного отбрасывания строго доминируемых стратегий.
Если использовать только что введенные обозначения, то Теорема 151 утверждает, что если x — равновесие Нэша в исходной игре G, то на любом шаге t выполнено
xi Xi[t], i I, t = 1, 2, . . .
или
x X[t], t = 1, 2, . . .
Доказательство (Доказательство Теоремы 151): Пусть есть такой шаг τ , что на нем должна быть отброшена стратегия xi некоторого игрока i I . Предполагается, что на предыдущих шагах ни одна из стратегий не была отброшена:
x X[t], t = 1, . . . , τ.
По определению строгого доминирования существует другая стратегия игрока i, x0i Xi[τ] , которая дает этому игроку в игре G[τ] более высокий выигрыш при любых выборах других
игроков:
ui(x0i, x−i) > ui(xi , x−i) x−i X−[τi]
В том числе, это соотношение должно быть выполнено для x−i , поскольку мы предположили, что стратегии x−i не были отброшены на предыдущих шагах процедуры (x−i X−[τi] ). Значит,
|
ui(xi0, x−i) > ui(xi , x−i) |
|
|
Однако это неравенство противоречит тому, что x — равновесие Нэша. |
|
|
Докажем теперь Теорему 152. Напомним ее формулировку: |
: Если в результате последовательного отбрасывания строго доминируемых стратегий у каждого игрока остается единственная стратегия, xi , то x = (x1, . . . , xm) — равновесие Нэша в этой игре.
Данная теорема относится к случаю, когда в процессе отбрасывания строго доминируемых
стратегий начиная с некоторого шага ¯ остается единственный набор стратегий, , т. е. t x
|
X |
[t] |
= |
x |
, i |
I, |
t = 1, . . . , t.¯ |
|
|
i |
{ i } |
Теорема утверждает, что x является единственным равновесием Нэша исходной игры.
|
16.2. Статические игры с полной информацией |
643 |
Доказательство (Доказательство Теоремы 152): Поскольку, согласно доказанной только что теореме, ни одно из равновесий Нэша не может быть отброшено, нам остается только доказать, что указанный набор стратегий x является равновесием Нэша. Предположим, что это не так. Это означает, что существует стратегия x˜i некоторого игрока i, такая что
ui(xi , x−i) < ui(˜xi, x−i)
По предположению, стратегия x˜i была отброшена на некотором шаге τ , поскольку она не совпадает с xi . Таким образом, существует некоторая строго доминирующая ее стратегия x0i Xi[τ] , так что
ui(x0i, x−i) > ui(˜xi, x−i) x−i X−[τi]
В том числе это неравенство выполнено при x−i = x−i :
ui(x0i, x−i) > ui(˜xi, x−i)
Стратегия x0i не может совпадать со стратегией xi , поскольку в этом случае вышеприведенные неравенства противоречат друг другу. В свою очередь, из этого следует, что должна существовать стратегия x00i , которая доминирует стратегию x0i на некотором шаге τ0 > τ , т. е.
|
u |
(x00 |
, x |
−i |
) > u |
(x0 |
, x |
−i |
) x |
X |
[τ0] |
|
i |
i |
i |
i |
−i |
−i |
В том числе
ui(x00i , x−i) > ui(x0i, x−i)
Можно опять утверждать, что стратегия x00i не может совпадать со стратегией xi , иначе вышеприведенные неравенства противоречили бы друг другу.
Продолжая эти рассуждения, мы получим последовательность шагов τ < τ0 < τ00 < . . .
и соответствующих допустимых стратегий x0i, x00i , x000i , . . ., не совпадающих с xi . Это противо-
|
¯ |
|
|
речит существованию шага t, начиная с которого множества допустимых стратегий состоят |
|
|
i |
|
|
только из x . |
Задачи
/667. Два игрока размещают некоторый объект на плоскости, то есть выбирают его координаты (x, y). Игрок 1 находится в точке (x1 , y1 ), а игрок 2 — в точке (x2 , y2 ). Игрок 1 выбирает координату x, а игрок 2 — координату y. Каждый стремиться, чтобы объект находился как можно ближе к нему. Покажите, что в этой игре у каждого игрока есть строго доминирующая стратегия.
/668. Докажите, что если в некоторой игре у каждого из игроков существует строго доминирующая стратегия, то эти стратегии составляют единственное равновесие Нэша.
/669. Объясните, почему равновесие в доминирующих стратегиях должно быть также равновесием в смысле Нэша. Приведите пример игры, в которой существует равновесие в доминирующих стратегиях, и, кроме того, существуют равновесия Нэша, не совпадающие с равновесием в доминирующих стратегиях.
Найдите в следующих играх все равновесия Нэша.
/670. Игра 16.2.1 (с. 625), выигрыши которой представлены в Таблице ??////??
/671. «Орехи»
Два игрока делят между собой 4 ореха. Каждый делает свою заявку на орехи: xi = 1, 2 или 3. Если x1 + x2 6 4, то каждый получает сколько просил, в противном случае оба не получают ничего.
|
16.2. Статические игры с полной информацией |
644 |
/ 672. Два преподавателя экономического факультета пишут учебник. Качество учебника (q) зависит от их усилий (e1 и e2 соответственно) в соответствии с функцией
q = 2(e1 + e2).
Целевая функция каждого имеет вид
ui = q − ei,
т. е. качество минус усилия. Можно выбрать усилия на уровне 1, 2 или 3.
/ 673. «Третий лишний» Каждый из трех игроков выбирает одну из сторон монеты: «орёл» или «решка». Если
выборы игроков совпали, то каждому выдается по 1 рублю. Если выбор одного из игроков отличается от выбора двух других, то он выплачивает им по 1 рублю.
/ 674. Три игрока выбирают одну из трех альтернатив: A, B или C . Альтернатива выбирается голосованием большинством голосов. Каждый из игроков голосует за одну и только за одну альтернативу. Если ни одна из альтернатив не наберет большинство, то будет выбрана альтернатива A. Выигрыши игроков в зависимости от выбранной альтернативы следующие:
u1(A) = 2, u2(A) = 0, u3(A) = 1,
u1(B) = 1, u2(B) = 2, u3(B) = 0,
u1(C) = 0, u2(C) = 1, u3(C) = 2.
/675. Формируются два избирательных блока, которые будут претендовать на места в законодательном собрании города N-ска. Каждый из блоков может выбрать одну из трех ориентаций: «левая» (L), «правая» (R) и «экологическая» (E). Каждая из ориентаций может привлечь 50, 30 и 20% избирателей соответственно. Известно, что если интересующая их ориентация не представлена на выборах, то избиратели из соответствующей группы не будут голосовать. Если блоки выберут разные ориентации, то каждый получит соответствующую долю голосов. Если блоки выберут одну и ту же ориентацию, то голоса соответствующей группы избирателей разделятся поровну между ними. Цель каждого блока — получить наибольшее количество голосов.
/676. Два игрока размещают точку на плоскости. Один игрок выбирает абсциссу, другой —
ординату. Их выигрыши заданы функциями:
а) ux(x, y) = −x2 + x(y + a) + y2 , uy(x, y) = −y2 + y(x + b) + x2 ,
б) ux(x, y) = −x2 − 2ax(y + 1) + y2 , uy(x, y) = −y2 + 2by(x + 1) + x2 , в) ux(x, y) = −x − y/x + 1/2y2 , uy(x, y) = −y − x/y + 1/2x2 ,
(a, b — коэффициенты).
/677. «Мороженщики на пляже»
Два мороженщика в жаркий день продают на пляже мороженое. Пляж можно представить как единичный отрезок. Мороженщики выбирают, в каком месте пляжа им находиться, т. е. выбирают координату xi [0, 1]. Покупатели равномерно рассредоточены по пляжу и покупают мороженое у ближайшего к ним продавца. Если x1 < x2 , то первый обслуживают (x1 + x2)/2 долю пляжа, а второй — 1 − (x1 + x2)/2. Если мороженщики расположатся в одной и той же точке (x1 = x2 ), покупатели поровну распределятся между ними. Каждый мороженщик стремиться обслуживать как можно большую долю пляжа.
/ 678. «Аукцион» Рассмотрите аукцион, подобный описанному в Игре 16.2.2, при условии, что выигравший
аукцион игрок платит названную им цену.
/ 679. Проанализируйте Игру 16.2.1 «Выбор компьютера» (с. 624) и найдите ответы на следующие вопросы:
|
16.2. Статические игры с полной информацией |
645 |
а) При каких условиях на параметры a, b и c будет существовать равновесие в доминирующих стратегиях? Каким будет это равновесие?
б) При каких условиях на параметры будет равновесием Нэша исход, когда оба выбирают IBM? Когда это равновесие единственно? Может ли оно являться также равновесием в доминирующих стратегиях?
/ 680. Каждый из двух соседей по подъезду выбирает, будет он подметать подъезд раз в неделю или нет. Пусть каждый оценивает выгоду для себя от двойной чистоты в a > 0 денежных единиц, выгоду от одинарной чистоты — в b > 0 единиц, от неубранного подъезда — в 0, а свои затраты на личное участие в уборке — в c > 0. При каких соотношениях между a, b и c в игре сложатся равновесия вида: (0) никто не убирает, (1) один убирает, (2) оба убирают?
/ 681. Предположим, что в некоторой игре двух игроков, каждый из которых имеет 2 стратегии, существует единственное равновесие Нэша. Покажите, что в этой игре хотя бы у одного из игроков есть доминирующая стратегия.
/ 682. Каждый из двух игроков (i = 1, 2) имеет по 3 стратегии: a, b, c и x, y, z соответственно. Взяв свое имя как бесконечную последовательность символов типа иваниваниван. . . , задайте выигрыши первого игрока так: u1(a, x) = «и», u1(a, y) = «в», u1(a, z) = «а», u1(b, x) = «н», u1(b, y) = «и», u1(b, z) = «в», u1(c, x) = «а», u1(c, y) = «н», u1(c, z) = «и». Подставьте вместо каждой буквы имени ее номер в алфавите, для чего воспользуйтесь Таблицей 16.10. Аналогично используя фамилию, задайте выигрыши второго игрока, u2(·).
1)Есть ли в Вашей игре доминирующие и строго доминирующие стратегии? Если есть, то образуют ли они равновесие в доминирующих стратегиях?
2)Каким будет результат последовательного отбрасывания строго доминируемых страте-
гий?
3)Найдите равновесия Нэша этой игры.
Таблица 16.10.
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
|
0 |
а |
б |
в |
г |
д |
е |
ё |
ж |
з |
|
|
1 |
и |
й |
к |
л |
м |
н |
о |
п |
р |
с |
|
2 |
т |
у |
ф |
х |
ц |
ч |
ш |
щ |
ъ |
ы |
|
3 |
ь |
э |
ю |
я |
/683. Составьте по имени, фамилии и отчеству матричную игру трех игроков, у каждого из которых по 2 стратегии. Ответьте на вопросы предыдущей задачи.
/684. Заполните пропущенные выигрыши в следующей таблице так, чтобы в получившейся игре. . .
(0)не было ни одного равновесия Нэша,
|
(1) |
было одно равновесие Нэша, |
1 |
? |
|
|
? |
2 |
|||
|
(2) |
было два равновесия Нэша, |
|||
|
? |
0 |
|||
|
(3) |
было три равновесия Нэша, |
|||
|
4 |
? |
(4)было четыре равновесия Нэша.
/685. 1) Объясните, почему в любом равновесии Нэша выигрыш i-го игрока не может быть меньше, чем
min max ui(xi, x−i).
x−i X−i xi Xi
2) Объясните, почему в любом равновесии Нэша выигрыш i-го игрока не может быть
|
меньше, чем |
|||||
|
max min |
u |
(x |
, x |
−i |
). |
|
xi Xi x−i X−i |
i |
i |
Что такое теория игр?
Теория игр — это область математики, которая занимается проблемами, в которых решение принимают несколько участников, называемых игроками. Название предполагает, что это связано с настольными или компьютерными играми. Первоначально теория игр использовалась для анализа стратегий настольных игр; однако в настоящее время он используется для решения множества реальных проблем.
В математической игре выигрыш игрока определяется не только его собственным выбором стратегии, но и стратегиями, выбранными другими игроками. Поэтому важно предвидеть действия других игроков. Теория игр пытается проанализировать оптимальную стратегию для нескольких типов игр.
Настольные игры
Кедр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 Джон