Разработанный МФТИ курс отличается тем, что все основные конструкции и принципы теории вводятся непосредственно на основе разбираемых "с нуля" конкретных этюдов. Каждый этюд начинается с понятной непрофессионалу проблемы. В одних случаях это просто "детская игра", в других - формализованное жизненное наблюдение, в третьих - обобщённая социальная закономерность. Сюжет затем разворачивается, исходя из логики содержащегося в нём конфликта, и сам порождает тот или иной принцип разрешения конфликта, который окончательно строго формализуется в виде решения игры. Этюдов всего рассмотрено чуть более десяти, и они в совокупности покрывают основные формальные конструкции базовой теории игр. В нескольких отступлениях приведены формулировки теорем существования игровых решений с набросками доказательств.
Равновесие Нэша, итеративное доминирование
Loading...
From the course by Moscow Institute of Physics and Technology
Теория игр
20 ratings
Moscow Institute of Physics and Technology
Теория игр
20 ratings
From the lesson
Равновесия Нэша
В первой неделе вы познакомитесь с основными концепциями теории игр: игры в нормальной форме, (доминируемыми) стратегиями, равновесиями по Нэшу.
Meet the Instructors
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
Равновесие Нэша. [ЗВУК] Раз я его упомянул в предыдущем сюжете, то надо дать его строгое определение. Итак, рассмотрим игру, которая задается некоторым набором игроков, а также стратегическими множествами S₁, ...,
S*n называется равновесным по Нэшу, или просто равновесием Нэша, [ЗВУК] если [ЗВУК] для любого игрока i и для любой стратегии, которую он мог бы использовать, выполнено условие, что его выигрыш от ситуации S*, то есть от применения предписанной ему стратегии S*i, притом что остальные применяют именно эти предписанные стратегии, не меньше, чем его выигрыш от ситуации, когда он заменит свою стратегию на вот эту. Но остальные ничего не заменят. Всё. Вот это основное определение в теории игр, и давайте немножко его пообсуждаем. Итак, конкретный исход целиком называется равновесием Нэша, не какая-то одна стратегия. Типичной ошибкой, которую студенты совершают, является ошибка, когда говорят: «Вот эта стратегия у какого-то игрока является равновесием Нэша». Это бессмысленно, это абсурдно, не имеет никакого смысла. Смысл имеет говорить об исходе целиком как о равновесии Нэша. Каждая из этих стратегий может быть названа равновесной по Нэшу в таком-то равновесии, но никак сама по себе равновесием Нэша не может являться или же не являться. Вот. То есть к понятию исход игры применимо понятие равновесия Нэша. Некоторые исходы равновесны, некоторые нет. Вот это надо четко понимать. Значит, что за исходы являются равновесными по Нэшу? Такие исходы, что если я, i-й игрок, и верю, что остальные будут следовать тем стратегиям, которые здесь записаны, то тогда мне тоже нет смысла искать какого-то там счастья в поле, искать какую-то другую стратегию, которая лучше задана. Я не найду. Все остальные будут давать мне либо тот же выигрыш, либо более плохой. Значит, вера в то, что люди в реальном игровом взаимодействии играют согласно равновесию Нэша, еще более хрупкая и хлипкая, чем вера в то, что они применяют доминируемые стратегии или же не применяют те, которые строго доминируются какими-то другими. И здесь есть целый ряд дополнительных источников сомнения. Во-первых, равновесий Нэша может быть много. И это будет пример... следующий наш сюжет будет посвящен случаю, когда равновесий Нэша огромное количество. Во-вторых, равновесия Нэша может не быть. Вообще. Пустое множество. Ни один исход не является равновесным по Нэшу. И этому будет посвящен следующий наш сюжет потом, еще один сюжет. В-третьих, равновесие может быть плохим, это мы уже понимаем, потому что мы видели, что в дилемме заключенного даже исход по доминированию... Понятно, что если мы запишем здесь доминантные стратегии, то вот это условие будет выполнено, потому что это условие более слабое, чем условие на доминантность. Доминантность требует, чтобы вот эта стратегия была лучше вот этой при любом S − i, а здесь требуется, чтобы только при некотором конкретном, которое прописано в этом исходе. Поэтому понятно, что если у нас есть доминантные стратегии, то они образуют равновесие Нэша. Фактически мы сейчас только что это доказали. И даже набор доминантных стратегий может быть по Парето уступать какому-то другому набору стратегий, то есть может уступать другому исходу с точки зрения любого игрока. И уж тем более к равновесию Нэша это тоже имеет отношение. Ну и последнее возражение состоит в том, что как показывают некоторые примеры — их много в книжках, поэтому я даже не буду их здесь приводить, — примеры показывают, что равновесие Нэша может содержать слабо доминируемые стратегии. Так происходит для справок в так называемой олигополии Бертрана из экономики. Вот, то есть можете посмотреть в Интернете — олигополия Бертрана, и там равновесие, оно обладает тем свойством, что входящие в него стратегии все, собственно, слабо доминируемые. Поэтому это совсем уж абсурдно ожидать, что люди именно так себя будут вести. А как именно люди в этом случае себя будут вести, в общем, никто не знает на самом деле. То есть никаких универсальных правил нет. То есть есть концепция — теория игр. Мы можем считать ее для разных игр. Но быть уверенными в том, что люди будут именно так себя вести, мы не можем. Ну вот с этими всеми оговорками, тем не менее, запомните это навсегда. Это основа теории, это первый ее столп, самый главный. Ну и давайте подумаем, какая связь между равновесием Нэша и доминированием. Первая, я уже сказал. Если есть набор стратегий, каждая из которых доминантная, то есть самая лучшая в кавычках с точки зрения данного игрока, независимо от того, что делают остальные, приносящая ему наибольший выигрыш, то тогда соответствующий набор доминантных стратегий будет всегда равновесием Нэша. Можно усилить этот результат. Если стратегия какая-то сильно доминируется посредством какой-то другой, то она не может входить в равновесие, потому что вот на этот конкретный профиль она будет хуже, чем какая-то другая, так же, как и на любой другой. А значит, для нее не может быть условия, что она больше или равна. Тут выигрыш от применения этой стратегии при данном профиле не может быть больше или равен выигрышу от применения какой-то другой, потому что если она сильно доминируемая, значит, для нее есть какая-то стратегия Si с волной, которая лучше, независимо от того, что делают остальные. Ui от Si против S − i всегда больше, чем Ui от S*i при любых S − i. Ну в частности и больше при S* − i, тем самым сразу наступает противоречие с этим неравенством. Значит, сильно доминируемая стратегия не может входить ни в какое равновесие Нэша. Следовательно, если мы ставим себе задачу описать все равновесия Нэша в некоторой игре, то первым делом мы можем с чистой совестью вычеркнуть все сильно доминируемые стратегии у всех игроков. Про слабые я не говорю. Я говорю про сильные. Сильно доминируемые можно вычеркивать без потери равновесий по Нэшу. Если мы после этого получили урезанную игру, в которой у каждого игрока меньше стратегий, и в этой урезанной игре какие-то новые стратегии опять сильно доминируются, то, значит, мы их тоже можем выкинуть, их тоже не будет в равновесиях Нэша. И если вот таким посредством удаления по сильному доминированию мы можем свести стратегические множества к одноэлементным, то предсказываемый нами исход игры заведомо является равновесием Нэша. Потому что все другие не могут, но то, что если у нас осталось по одной стратегии у каждого, то есть выкинуть равновесную стратегию до этого мы не могли. Значит, конечный итог — одноэлементные множества — будут, если взять исход из вот этих вот элементов, он будет равновесным по Нэшу. Значит, что я не буду обсуждать здесь, потому что это обсуждается во многих книгах, это вопрос о том, какая связь слабого доминирования и равновесности по Нэшу.
Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.
© 2017 Coursera Inc. All rights reserved.
