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

Равновесие Нэша Дмитрий Дагаев НИУ Высшая школа экономики Решение игр ▶ На прошлой неделе мы научились находить равновесия в строго (слабо) доминирующих стратегиях, а также равновесия, получаемые последовательным исключением строго (слабо) доминируемых стратегий. ▶ На этой неделе мы познакомимся с еще одной концепцией, которая позволит нам решать гораздо более широкий класс игр. Дмитрий Дагаев НИУ ВШЭ 2 / 65 Битва полов Постановка игры ▶ Муж и жена независимо друг от друга решают, куда пойти вечером: на футбол или на балет. ▶ Связь между ними отсутствует, поэтому никто из них не может ничего узнать о том, куда решил пойти другой. Дмитрий Дагаев НИУ ВШЭ 3 / 65 Битва полов Предпочтения игроков ▶ Предпочтения супругов таковы, что вечером они хотели бы оказаться в одном месте, но жене больше нравится балет, а мужу –– футбол. ▶ Мужу лучше оказаться вместе с женой на балете, чем одному на футболе. ▶ Жене лучше пойти на футбол с мужем, чем пойти одной на балет. Дмитрий Дагаев НИУ ВШЭ 4 / 65 Битва полов Стратегии ▶ У каждого из супругов есть выбор из 2 стратегий: пойти на футбол (Ф) или пойти на балет (Б). Платежи ▶ Предпочтения супругов можно задать с помощью следующей матрицы платежей: Муж Дмитрий Дагаев Ф Б Жена Ф Б 5; 4 1; 1 0; 0 4; 5 НИУ ВШЭ 5 / 65 Битва полов Сравним платежи мужа и заметим, что у него нет ни доминирующих, ни доминируемых стратегий: ▶ Ф = BRм (Ф) ▶ Б = BRм (Б) Таким образом, в ответ на разные стратегии жены, мужу также выгодно играть разные стратегии. Жена Ф Б • Ф 5; 4 1; 1 Муж Б 0; 0 • 4; 5 Дмитрий Дагаев НИУ ВШЭ 6 / 65 Битва полов То же самое верно и для жены: ▶ Ф = BRж (Ф) ▶ Б = BRж (Б) Если муж пошел на футбол, то ей тоже лучше пойти на футбол, а если на балет, то ей выгоднее пойти на балет. Муж Дмитрий Дагаев Ф Б Жена Ф Б ∗ 5; 4 1; 1 0; 0 4; 5 ∗ НИУ ВШЭ 7 / 65 Битва полов В нашей матрице платежей получились две клеточки, в которых лучший выбор мужа при фиксированной стратегии жены совпал с лучшим выбором жены при фиксированной стратегии мужа. Жена Ф Б • ∗ Ф 5; 4 1; 1 Муж Б 0; 0 • 4; 5 ∗ Дмитрий Дагаев НИУ ВШЭ 8 / 65 Битва полов Что если муж и жена вместе пришли на футбол? ▶ Захочет ли кто-нибудь из них изменить свое решение и сыграть стратегию «Б» при условии, что другой останется смотреть футбол? ▶ Нет, так как тогда его платеж уменьшится. Жена Ф Б • ∗ Ф 5; 4 1; 1 Муж Б 0; 0 • 4; 5 ∗ Дмитрий Дагаев НИУ ВШЭ 9 / 65 Битва полов Что если муж и жена вместе пришли на балет? ▶ Захочет ли кто-нибудь из них изменить свое решение и уйти смотреть футбол при условии, что другой останется на балете? ▶ Нет, так как в этом случае его платеж уменьшится. Жена Ф Ф Муж Б Дмитрий Дагаев • 5; 4 ∗ 0; 0 НИУ ВШЭ Б 1; 1 • 4; 5 ∗ 10 / 65 Битва полов Пусть муж решил пойти на футбол, а жена выбрала балет. Что тогда? ▶ Лучший ответ мужа на стратегию жены «Б» –– тоже пойти на балет, так как тогда его выигрыш больше, чем в случае когда он идет на футбол. ▶ При условии того, что жена пошла на балет, мужу будет выгодно отклониться и сыграть стратегию «Б» вместо стратегии «Ф». ▶ Тогда он сможет увеличить свой выигрыш с 1 до 4. Жена Ф Б Ф • 5; 4 ∗ 1; 1 Муж Б 0; 0 • 4; 5 ∗ Дмитрий Дагаев НИУ ВШЭ 11 / 65 Битва полов ▶ C другой стороны, при условии, что муж пошел на футбол, жене было бы лучше тоже пойти на футбол, а не на балет. ▶ То есть жена тоже захочет отклониться и сыграть стратегию «Ф» вместо стратегии «Б» при фиксированной стратегии мужа «Ф». ▶ Тогда ее выигрыш увеличится с 1 до 4. Жена Ф Б Ф • 5; 4 ∗ 1; 1 Муж Б 0; 0 • 4; 5 ∗ Дмитрий Дагаев НИУ ВШЭ 12 / 65 Битва полов Пусть муж решил пойти на балет, а жена выбрала футбол. Что тогда? ▶ То же самое, что и в ситуации, когда муж пошел на футбол, а жена –– на балет. ▶ Обоим будет выгодно отклониться при фиксированной стратегии другого. Жена Ф Ф Муж Б Дмитрий Дагаев • 5; 4 ∗ 0; 0 НИУ ВШЭ Б 1; 1 • 4; 5 ∗ 13 / 65 Битва полов ▶ Таким образом, профили стратегий (Ф, Ф) и (Б, Б) в каком-то смысле лучше профилей стратегий (Ф, Б) и (Б, Ф). ▶ Если муж и жена оказались вместе на футболе или на балете, то никому из супругов по отдельности не выгодно уйти в другое место при неизменном решении второго остаться. ▶ Если супруги оказались вечером в разных местах, то каждому из них выгодно отклониться от выбранной первоначально стратегии. Дмитрий Дагаев НИУ ВШЭ 14 / 65 Равновесие Нэша ▶ Полученные нами профили стратегий (Ф, Ф) и (Б, Б) являются «хорошими» в том смысле, что, оказавшись в одном из них, никому из игроков уже не выгодно изменить свою стратегию при фиксированной стратегии другого игрока. ▶ Такие профили стратегий называют равновесиями Нэша. Дмитрий Дагаев НИУ ВШЭ 15 / 65 Равновесие Нэша Определение Профиль (s∗1 ,…, s∗n ) называется равновесием Нэша (NE), если для любого игрока i и любой его стратегии si ∈ Si выполняется неравенство ui (s∗i , s∗−i ) ⩾ ui (si , s∗−i ). Иными словами, равновесием Нэша называется такой профиль стратегий, что никому из игроков не выгодно отклониться и сыграть другую стратегию при фиксированных стратегиях других игроков. Дмитрий Дагаев НИУ ВШЭ 16 / 65 Равновесие Нэша Равновесие Нэша названо так в честь известного математика Джона Нэша, лауреата Нобелевской премии по экономике 1994 года «За анализ равновесия в теории некооперативных игр» (совместно с Райнхардом Зельтеном и Джоном Харсаньи). John Nash, Jr by Peter Badge (CC BY-SA 3.0) Дмитрий Дагаев НИУ ВШЭ 17 / 65 Алгоритм нахождения равновесий Нэша Мы можем сформулировать алгоритм нахождения равновесий Нэша в конечных играх двух игроков: 1. Для каждой стратегии второго игрока пометим точками наилучшие ответы первого игрока. 2. Для каждой стратегии первого игрока пометим звездочками наилучшие ответы второго игрока. 3. Профили, которые оказались помечены как точками, так и звездочками, являются равновесиями Нэша. Дмитрий Дагаев НИУ ВШЭ 18 / 65 Алгоритм нахождения равновесий Нэша Может ли получиться так, что профиль стратегий, который не помечен либо звездочкой, либо точкой, окажется равновесием Нэша? ▶ Нет, не может. ▶ Пусть профиль (a, b) не помечен, например, звездочкой, но тогда стратегия b второго игрока не является его BR2 (a). ▶ Тогда существует стратегия второго игрока c = BR2 (a). ▶ Второму игроку выгодно отклониться и выбрать стратегию c вместо стратегии b. ▶ Значит, профиль (a, b) не является равновесием Нэша. Дмитрий Дагаев НИУ ВШЭ 19 / 65 Алгоритм нахождения равновесий Нэша Может ли получиться так, что профиль стратегий, который помечен и звездочкой, и точкой, все же не является равновесием Нэша? ▶ Нет, не может. ▶ Пусть профиль (a, b) помечен и звездочкой, и точкой. ▶ Тогда a = BR1 (b), а b = BR2 (a). ▶ Тогда никому из игроков не выгодно отклониться при фиксированной стратегии другого, так как они уже сыграли свои наилучшие ответы на стратегии друг друга. ▶ Значит, профиль (a, b) является равновесием Нэша. Дмитрий Дагаев НИУ ВШЭ 20 / 65 Конкуренция между университетами Постановка игры ▶ В некотором городе M есть два хороших университета, студенты которых после выпуска конкурируют между собой на рынке труда. ▶ У работодателей есть лишь один критерий оценки навыков и знаний выпускников –– их средний балл в университете. ▶ Чем он выше, тем выше вероятность, что данного студента возьмут на работу. ▶ Каждый университет заинтересован в том, чтобы как можно больше его выпускников устроились на работу. Дмитрий Дагаев НИУ ВШЭ 21 / 65 Конкуренция между университетами Стратегии ▶ У каждого университета есть две стратегии: завышать оценки своих студентов (З) и не завышать (Н). Платежи ▶ Предпочтения университетов можно задать с помощью следующей матрицы платежей: Университет Б З Н З 1; 1 2; 0 Университет А Н 0; 2 1; 1 Дмитрий Дагаев НИУ ВШЭ 22 / 65 Конкуренция между университетами Что будет делать университет А, если университет Б станет завышать оценки? ▶ Тогда университету А будет выгодно тоже начать завышать оценки. Что будет делать университет А, если университет Б не будет завышать оценки? ▶ Университету А все равно будет выгодно начать завышать оценки. Дмитрий Дагаев НИУ ВШЭ 23 / 65 Конкуренция между университетами ▶ Отметим точками платежи университета А, которые он получает, отвечая на каждую стратегию университета Б наилучшим для себя образом. Университет Б З Н • 2; 0 З • 1; 1 Университет А Н 0; 2 1; 1 ▶ Стратегия «З» является строго доминирующей для университета А. Дмитрий Дагаев НИУ ВШЭ 24 / 65 Конкуренция между университетами ▶ Отметим звездочками платежи университета Б, которые он получает, отвечая на каждую стратегию университета А наилучшим для себя образом. Университет Б З Н З • 1; 1 ∗ • 2; 0 Университет А Н 0; 2 ∗ 1; 1 ▶ Стратегия «З» является строго доминирующей для университета Б. Дмитрий Дагаев НИУ ВШЭ 25 / 65 Конкуренция между университетами ▶ Мы уже знаем, что профиль стратегий (З, З) является равновесием в строго доминирующих стратегиях. ▶ Но давайте теперь посмотрим на него с точки зрения равновесия Нэша. Университет Б З Н • ∗ • З 1; 1 2; 0 Университет А Н 0; 2 ∗ 1; 1 Дмитрий Дагаев НИУ ВШЭ 26 / 65 Конкуренция между университетами Предположим, что оба университета решили завышать оценки своим студентам. Выгодно ли кому-нибудь из них отклониться и перестать завышать оценки студентам? ▶ Нет, так как тогда его платеж уменьшится. ▶ Профиль стратегий (З, З) будет являться равновесием Нэша. Университет Б З Н • ∗ • З 1; 1 2; 0 Университет А Н 0; 2 ∗ 1; 1 ▶ В этой игре всего одно равновесие Нэша. Дмитрий Дагаев НИУ ВШЭ 27 / 65 Равновесие в доминирующих стратегиях и NE Всегда ли равновесие в строго (слабо) доминирующих стратегиях будет являться и равновесием Нэша? ▶ Да, всегда! ▶ В равновесии в строго (слабо) доминирующих стратегиях ни одному из игроков не будет выгодно отклониться и сыграть другую стратегию, так как ни одна другая стратегия по определению не принесет ему большего выигрыша. Дмитрий Дагаев НИУ ВШЭ 28 / 65 Равновесие в доминирующих стратегиях и NE Правда ли, что равновесие в строго доминирующих стратегиях будет единственным равновесием Нэша? ▶ Да, правда! ▶ Это следует из определения строго доминирующей стратегии. ▶ Докажем это. Дмитрий Дагаев НИУ ВШЭ 29 / 65 Равновесие в доминирующих стратегиях и NE Предположим противное ▶ Пусть стратегия a1 первого игрока и стратегия b1 второго игрока являются строго доминирующими, и существует профиль стратегий (ai , bj ), отличный от профиля стратегий (a1 , b1 ), также являющийся равновесием Нэша. ▶ Тогда если i ̸= 1, то первому игроку выгодно отклониться и сыграть стратегию a1 , так как тогда он получит строго больший платеж, ведь стратегия a1 строго доминирует стратегию ai . Дмитрий Дагаев НИУ ВШЭ 30 / 65 Равновесие в доминирующих стратегиях и NE ▶ Если i = 1, тогда j ̸= 1, иначе (ai , bj ) совпадал бы с (a1 , b1 ). ▶ Тогда второму игроку выгодно отклониться и сыграть b1 . ▶ Получили противоречие. ▶ Значит, профиль стратегий (a1 , b1 ) –– единственное равновесие Нэша. Дмитрий Дагаев НИУ ВШЭ 31 / 65 Равновесие в доминирующих стратегиях и NE Всегда ли равновесие в слабо доминирующих стратегиях будет единственным равновесием Нэша? ▶ Нет! Это неверно! Контрпример a1 a2 b1 • 0; 0 ∗ • 0; 2 ∗ b2 • 2; 0 ∗ 1; 1 ▶ Стратегия a1 слабо доминирует стратегию a2 . ▶ Стратегия b1 слабо доминирует стратегию b2 . Дмитрий Дагаев НИУ ВШЭ 32 / 65 Равновесие в доминирующих стратегиях и NE Однако равновесий Нэша в данной игре будет 3. ▶ (a1 , b1 ) будет равновесием Нэша, так как никто из игроков не может поменять свою стратегию так, чтобы улучшить свое положение при фиксированной стратегии другого игрока. ▶ То же самое верно и для профилей (a1 , b2 ) и (a2 , b1 ). a1 a2 ▶ b1 • 0; 0 ∗ • 0; 2 ∗ b2 • 2; 0 ∗ 1; 1 Равновесие в слабо доминирующих стратегиях не всегда единственное равновесие Нэша в игре. Дмитрий Дагаев НИУ ВШЭ 33 / 65 Доминируемые стратегии и равновесие Нэша Всегда ли равновесие, полученное последовательным исключением строго (слабо) доминируемых стратегий, будет равновесием Нэша? ▶ Да, всегда! ▶ Алгоритм последовательного исключения строго (слабо) доминируемых стратегий таков, что из него напрямую следует, что полученное с его помощью равновесие будет равновесием Нэша. Дмитрий Дагаев НИУ ВШЭ 34 / 65 Равновесие Нэша Правда ли, что в любой игре в нормальной форме есть равновесия Нэша (в чистых стратегиях)? ▶ Нет, это неверное утверждение. ▶ Рассмотрим в качестве контрпримера игру «Орлянка». Дмитрий Дагаев НИУ ВШЭ 35 / 65 Игра «Орлянка» Постановка игры ▶ Играют двое: Вася и Петя. ▶ Каждый из игроков независимо от другого пишет на бумаге либо слово «Орел», либо слово «Решка». ▶ Затем написанное на двух бумажках сравнивается. ▶ Если на бумажках написаны одинаковые слова, то побеждает Вася, а если разные, то Петя. Дмитрий Дагаев НИУ ВШЭ 36 / 65 Игра «Орлянка» Стратегии ▶ У каждого из игроков 2 стратегии: написать слово «Орел» (О) или написать слово «Решка» (Р). Платежи ▶ Матрица платежей устроена следующим образом: Петя O Вася P Дмитрий Дагаев O 1; −1 − 1; 1 НИУ ВШЭ P − 1; 1 1; −1 37 / 65 Игра «Орлянка» ▶ Отметим точками оптимальный ответ Васи на каждую из стратегий Пети. ▶ А звездочками –– оптимальный ответ Пети на каждую из стратегий Васи. Петя O P • 1; −1 − 1; 1 ∗ O Вася ∗ • P − 1; 1 1; −1 ▶ Нет ни одной такой клеточки, в которой оптимальный ответ Васи на данную стратегию Пети совпадал бы с оптимальным ответом Пети на данную стратегию Васи. Дмитрий Дагаев НИУ ВШЭ 38 / 65 Игра «Орлянка» ▶ Если исход игры таков, что ребята написали разные слова и выиграл Петя, тогда Васе было бы выгодно отклониться и написать такое же слово, что и Петя, и победить. ▶ Если ребята написали одинаковые слова, тогда уже Петя хотел бы отклониться и написать слово, отличное от Васиного. ▶ В данной игре нет ни одного равновесия Нэша. Петя O P O • 1; −1 − 1; 1 ∗ Вася P − 1; 1 ∗ • 1; −1 Дмитрий Дагаев НИУ ВШЭ 39 / 65 Количество равновесий Нэша ▶ Только что мы рассмотрели пример игры, в которой не было ни одного равновесия Нэша. ▶ Мы также обсудили игры, в которых были одно, два и три равновесия Нэша. ▶ Оказывается, бывают игры, в которых все профили стратегий являются равновесиями Нэша. Дмитрий Дагаев НИУ ВШЭ 40 / 65 Количество равновесий Нэша ▶ Например, игра с нулевой матрицей платежей. ▶ При любом из 4 исходов игры никто из игроков не захочет отклоняться и менять свою стратегию, так как никто из них все равно не сможет улучшить свое положение. a1 a2 Дмитрий Дагаев b1 • 0; 0 ∗ • 0; 0 ∗ НИУ ВШЭ b2 • 0; 0 ∗ • 0; 0 ∗ 41 / 65 Финансирование избирательных кампаний Выборы мэра ▶ На выборах мэра в городе N соперничают два кандидата. ▶ Исход выборов будет зависеть от того, какой объем финансирования каждый кандидат привлечет к своей избирательной кампании. ▶ Избирательные кампании будут финансироваться исключительно за счет собственных средств кандидатов. Дмитрий Дагаев НИУ ВШЭ 42 / 65 Финансирование избирательных кампаний Кто победит на выборах? 1. На выборах побеждает тот кандидат, который привлекает наибольшее количество средств на избирательную кампанию. 2. В случае, если кандидаты привлекают одинаковое количество средств на свои кампании, они побеждают с равной вероятностью. Дмитрий Дагаев НИУ ВШЭ 43 / 65 Финансирование избирательных кампаний Стратегии кандидатов ▶ Каждый кандидат выбирает то количество денег, которое он хочет привлечь для своей избирательной кампании. ▶ Обозначим за c1 количество денег, которое привлекает первый кандидат. ▶ А за c2 –– количество денег, которое привлекает второй кандидат. Дмитрий Дагаев НИУ ВШЭ 44 / 65 Финансирование избирательных кампаний Платежи кандидатов ▶ Каждому кандидату хотелось бы гарантированно победить на выборах. ▶ Несколько хуже –– победить с вероятностью 1/2. ▶ Совсем плохо –– проиграть выборы. ▶ При прочих равных каждому кандидату хотелось бы потратить как можно меньше денег. Дмитрий Дагаев НИУ ВШЭ 45 / 65 Финансирование избирательных кампаний Что произойдет, если c1 окажется больше, чем c2 ? ▶ Тогда на выборах гарантированно победит первый кандидат. ▶ Но будет ли такая ситуация равновесием Нэша? Дмитрий Дагаев НИУ ВШЭ 46 / 65 Финансирование избирательных кампаний ▶ Нет, не будет! ▶ Первому кандидату будет выгодно отклониться и потратить на избирательную кампанию чуть меньше. C2 C1+C2 C1 2 ▶ Например, если он потратит на выборы победит на выборах. Дмитрий Дагаев НИУ ВШЭ c1 +c2 2 , то все равно гарантированно 47 / 65 Финансирование избирательных кампаний Что произойдет, если c2 окажется больше, чем c1 ? ▶ Тогда на выборах гарантированно победит второй кандидат. ▶ Но будет ли такая ситуация равновесием Нэша? Дмитрий Дагаев НИУ ВШЭ 48 / 65 Финансирование избирательных кампаний ▶ Нет, не будет! ▶ Второму кандидату будет выгодно отклониться и потратить на избирательную кампанию чуть меньше. C1+C2 C1 C2 2 ▶ Например, если он потратит на выборах. Дмитрий Дагаев c1 +c2 2 , то все равно гарантированно победит НИУ ВШЭ 49 / 65 Финансирование избирательных кампаний Что произойдет, если c2 окажется равно c1 ? ▶ Тогда кандидаты побеждают на выборах с равной вероятностью. ▶ Но будет ли такая ситуация равновесием Нэша? Дмитрий Дагаев НИУ ВШЭ 50 / 65 Финансирование избирательных кампаний ▶ Нет, не будет! ▶ Обоим кандидатам будет выгодно отклониться и потратить на свою избирательную кампанию чуть больше денег и победить на выборах гарантированно. ▶ В этой игре нет равновесий Нэша. Дмитрий Дагаев НИУ ВШЭ 51 / 65 В сумме 100 Постановка игры ▶ Играют двое: каждый независимо от другого пишет на бумажке некоторое неотрицательное число. ▶ Если сумма двух чисел оказывается меньше либо равна 100, то каждый получает то число, которое написал. ▶ Если же сумма оказывается больше 100, то тогда оба ничего не получают. ▶ Найдем все равновесия Нэша в данной игре. Дмитрий Дагаев НИУ ВШЭ 52 / 65 В сумме 100 Пусть первый игрок написал на бумажке некоторое число x, а второй –– некоторое число y. ▶ В этой игре равновесиями Нэша будут все такие пары (x, y), что x + y = 100. ▶ Например, (x = 50, y = 50) или (x = 5, y = 95). ▶ Никому из игроков не выгодно написать число поменьше, так как тогда он получит меньший выигрыш. ▶ Никому не выгодно также написать число побольше, так как тогда сумма двух чисел превысит 100, и платеж игрока составит 0. Дмитрий Дагаев НИУ ВШЭ 53 / 65 В сумме 100 ▶ Исход, в котором x + y < 100, не будет равновесным, так как тогда каждому из игроков будет выгодно отклониться и чуть-чуть увеличить свое число. ▶ Например, если (x = 45, y = 50), то первый игрок может увеличить свой выигрыш, написав на бумажке число 10 вместо числа 5. Дмитрий Дагаев НИУ ВШЭ 54 / 65 В сумме 100 ▶ Ситуация, когда x > 100, y < 100 или x < 100, y > 100, также не будет равновесной. ▶ Игроку, написавшему число, большее 100, будет выгодно отклониться и написать такое число, чтобы сумма двух чисел оказалась не больше 100, тогда он сможет получить положительный, а не нулевой выигрыш. ▶ Например, если (x = 90, y = 120), то второму игроку выгодно отклониться и написать 10 вместо 120, тогда он увеличит свой выигрыш с 0 до 10. Дмитрий Дагаев НИУ ВШЭ 55 / 65 В сумме 100 ▶ Равновесиями Нэша в данной игре также будут являться все такие пары (x, y), что x ⩾ 100 и y ⩾ 100. ▶ Например, если (x = 105, y = 110), тогда оба игрока получают платеж 0, и никто не может (не хочет) поменять свою стратегию так, чтобы получить больший выигрыш, так как при фиксированной стратегии другого игрока сумма двух чисел все равно окажется больше 100. Дмитрий Дагаев НИУ ВШЭ 56 / 65 В сумме 100 ▶ Может показаться нелогичным со стороны кого-либо из игроков писать на бумажке число, большее 100, так как тогда он заведомо не сможет получить выигрыш, больший 0. ▶ Тем не менее все исходы, в которых x ⩾ 100 и y ⩾ 100, вполне соответствуют концепции равновесия Нэша. Есть ли еще примеры «неоптимальных» равновесий Нэша? Дмитрий Дагаев НИУ ВШЭ 57 / 65 Дилемма заключенного Дилемма заключенного ▶ Мы уже знакомы с игрой, называемой дилеммой заключенного, в которой двое сообщников преступления, взятые под стражу, независимо друг от друга решают выдать своего подельника или промолчать. Дмитрий Дагаев НИУ ВШЭ 58 / 65 Дилемма заключенного Платежи Молчать Предать Молчать −1; −1 • 0; −10 Предать − 10; 0 ∗ • − 5; −5 ∗ ▶ В этой игре у обоих игроков есть доминирующая стратегия «Предать». ▶ Единственным равновесием Нэша в этой игре является профиль стратегий (Предать, Предать). Дмитрий Дагаев НИУ ВШЭ 59 / 65 Дилемма заключенного ▶ Заметим, что если бы оба преступника промолчали, то платеж каждого был бы равен (−1). ▶ В то время как в равновесии Нэша платеж каждого равен (−5). ▶ Проблема в том, что профиль (Молчать, Молчать) не является равновесным, и каждому из игроков всегда будет выгодно отклониться и предать другого. Молчать Предать Дмитрий Дагаев Молчать −1; −1 • 0; −10 НИУ ВШЭ Предать − 10; 0 ∗ • − 5; −5 ∗ 60 / 65 Дилемма заключенного ▶ Концепция равновесия Нэша имеет мало общего с оптимальностью с общественной точки зрения. ▶ Идея равновесия Нэша в том, что, однажды попав в него, уже трудно из него выбраться. ▶ Ведь никому из игроков по отдельности не выгодно менять свои стратегии при фиксированных стратегиях других игроков. ▶ Об этом говорят и реальные жизненные примеры равновесия Нэша. Дмитрий Дагаев НИУ ВШЭ 61 / 65 QWERTY ▶ Если вы печататали какой-то текст на английском, то, скорее всего, делали это на раскладке клавиатуры, которая называется QWERTY (по буквам в ее левой верхней части). ▶ Расположение букв на раскладке QWERTY обусловлено тем, что в печатных машинках конца XIX века нужно было избежать частого сцепления рычагов друг с другом в процессе печати. ▶ Поэтому буквы, которые чаще всего встречаются стоящими в тексте рядом друг с другом, на раскладке QWERTY расположены довольно далеко друг от друга. Дмитрий Дагаев НИУ ВШЭ 62 / 65 QWERTY Однако теперь печатными машинками почти никто не пользуется. Поэтому были придуманы раскладки, которые позволяют печатать быстрее, например: ▶ Dvorak ▶ Colemak Почему же QWERTY по-прежнему так распространена? Дмитрий Дагаев НИУ ВШЭ 63 / 65 QWERTY Это пример «неоптимального» равновесия Нэша. ▶ Если бы все использовали раскладку Dvorak, то печатание текстов занимало бы у людей меньше времени. ▶ Тем не менее ни одной из фирм, производящей компьютеры, не выгодно начинать выпускать свои компьютеры с раскладкой Dvorak, так как абсолютное большинство потребителей привыкли к QWERTY. ▶ Каждому отдельному пользователю компьютера также не выгодно перeучиваться до тех пор, пока отыскать компьютер с раскладкой, отличной от QWERTY, довольно сложно. В итоге, ситуация, в которой (почти) все пользуются раскладкой QWERTY, является равновесной. Дмитрий Дагаев НИУ ВШЭ 64 / 65 Пример интерпретации равновесия Нэша ▶ В городе N на рынке мобильных услуг конкурируют три мобильных оператора. ▶ В одну ночь они должны решить, какую цену установить на новую услугу. ▶ После того, как все операторы приняли решение, промышленные шпионы докладывают, какие цены выбрали другие компании. ▶ Если после этого кто-то из операторов захочет пересмотреть свое решение, то это не равновесие. Дмитрий Дагаев НИУ ВШЭ 65 / 65