Разработанный МФТИ курс отличается тем, что все основные конструкции и принципы теории вводятся непосредственно на основе разбираемых "с нуля" конкретных этюдов. Каждый этюд начинается с понятной непрофессионалу проблемы. В одних случаях это просто "детская игра", в других - формализованное жизненное наблюдение, в третьих - обобщённая социальная закономерность. Сюжет затем разворачивается, исходя из логики содержащегося в нём конфликта, и сам порождает тот или иной принцип разрешения конфликта, который окончательно строго формализуется в виде решения игры. Этюдов всего рассмотрено чуть более десяти, и они в совокупности покрывают основные формальные конструкции базовой теории игр. В нескольких отступлениях приведены формулировки теорем существования игровых решений с набросками доказательств.
Игра "Угадай число": решение
Loading...
From the course by Moscow Institute of Physics and Technology
Теория игр
32 оценки
From the lesson
Равновесия Нэша
В первой неделе вы познакомитесь с основными концепциями теории игр: игры в нормальной форме, (доминируемыми) стратегиями, равновесиями по Нэшу.
Meet the Instructors
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
Давайте попробуем найти все равновесия в этой игре.
Я бы мог это оставить в качестве упражнения, но упражнение это, во-первых,
не очень простое, ну и, кроме того,
анализ этой игры довольно характерен вообще для
анализа игровой ситуации, поэтому давайте его прямо вот в классе сейчас проведем.
Итак, давайте прежде всего попробуем выяснить,
существуют ли равновесные ситуации, в которых никто не выиграл.
То есть что значит «существуют ли равновесные»?
В реальной игре понятно, что люди не видят стратегии других.
Они видят только свою тетрадь и пытаются что-то угадать.
Но равновесие Нэша устроено так, что людям сообщаются стратегии остальных.
Грубо говоря, что такое равновесие Нэша?
Это вы объявили некоторый список действий.
Я делаю то, я беру репродуктор и говорю: «Миша пишет такое число,
Маша пишет такое число».
И прямо на весь зал объявляю.
И дальше это равновесное распределение,
если никто не может улучшить свою ситуацию.
Ну вот Маша смотрит: «Мне сказали написать 5, ну блин, ну а может быть,
мне лучше написать 4?» Так вот нет — не лучше.
Распределение остальных записей,
распределение остальных чисел объявленных таково,
что оно ничего не изменится для нее, если она напишет какое-то другое число.
Итак, вполне возможны ситуации, что никто не выиграл.
И это ситуации, когда каждое число записано более одного раза.
Ну так вышло, что несколько человек записали 0, несколько человек записали 1,
несколько человек записали 2, несколько человек записали 5.
И никто не записал эксклюзивного числа.
Вопрос: а возможна ли такая ситуация в равновесии?
То есть может ли быть равновесие, в котором никто не выиграл?
Давайте попробуем эту ситуацию проанализировать следующим
образом: давайте выпишем значения
возможных записей в тетрадках и будем здесь писать, сколько человек написали 0.
Может ли быть, что никто не написал 0?
Ответ: в равновесии, в котором никто не выиграл,
такой ситуации быть не может, потому что...
Рассмотрим любого игрока.
Он не выиграл, но если он изменит свою ситуацию и напишет 0,
а остальные ничего не будут менять, то он сразу же выиграет.
Значит, такая ситуация противоречит тому, что мы рассматриваем равновесие.
Хорошо.
Может ли быть в равновесии ситуация, когда 0 назвал ровно один человек?
Ответ: опять нет,
потому что мы сейчас рассматриваем равновесие, в котором никто не выиграл.
Но если 0 назвал только один человек, то, разумеется, именно он выиграл.
–1, –2, и так далее называть запрещено.
Значит, его число наименьшее и не названное больше никем,
оно как раз равно нулю.
И тогда этот человек выиграл, а значит неверно, что никто не выиграл.
Поэтому если мы рассматриваем равновесие, в котором никто не выиграл,
то логически минимум два человека должны назвать 0.
Вопрос: может ли быть так, что 0 назвали три,
четыре или более людей в равновесии, в котором никто не выиграл?
Ответ: не может этого быть по следующей причине: любой из этих
людей изменит свою стратегию на любое число (какое угодно,
там, не знаю: 2 в степени 2 в четвертой плюс 1 — какое-то там число Ферма).
Вот, назовет.
Ну, скорее всего, больше никто его не назвал, да?
Ну в общем, выберем здесь в натуральном ряду какое-нибудь число,
которое никто больше не назвал.
Натуральных чисел бесконечно много, а игроков конечное число.
Прикажем ему назвать столько, и он сразу же победит.
Почему?
Потому что после его ухода все равно остается не меньше двух человек,
назвавших 0, и все остальные числа тоже названы не менее чем одним человеком.
Следовательно, такая ситуация тоже невозможна ни в каком равновесии,
в котором никто не победил.
То есть для равновесия, в котором никто не победил, остается только одна опция.
Она состоит в том, что 0 назвало ровно два человека.
Абсолютно аналогично доказывается, что в таком равновесии 1 тоже
называют ровно два человека, и 2 — тоже два человека.
И вообще можно доказать (предоставляю это вам довести до ума),
что если никто не победил,
то n четно и композиция вот ровно такая.
То есть ровно двое назвали 0, ровно двое назвали 1, ровно двое назвали 2,
так далее, и ровно двое назвали n/2.
Эта ситуация действительно равновесная по Нэшу.
Посмотрите почему.
Рассмотрим любого игрока.
Он не победил.
Как он мог бы победить?
Ну изменить стратегию.
Но если он изменит стратегию (как угодно изменит стратегию), то тут же окажется,
что победит не он, а тот второй, который вместе с ним назвал это число.
Вот он изменил стратегию, и вот уже единственный человек,
назвавший 2, вот он и стал победителем.
Значит, этот человек меняет стратегию, он меняет ситуацию: никто не победил — было,
а стало — кто-то победил.
Но мы и договорились, что ему должно быть все равно, если это не он.
Поэтому у него нет стимулов менять стратегию, а значит,
рассматриваемая ситуация — это действительно равновесие Нэша.
Так, следующий вопрос: а как вообще выглядят все равновесия Нэша в этой игре?
Можно ли их подробно описать?
Давайте прежде всего заметим,
что если у нас ситуация такая,
что уровни вот так заполняются ровно по два,
то тогда, если у нас нечетное число игроков,
то любая стратегия последнего вот этого игрока (вот у нас все,
кроме одного игрока, и вот есть какой-то последний игрок), любая его стратегия,
отличная от написания: 0, 1, ..., n/2, гарантирует,
что он выиграет в этой игре.
И более того, вот такая ситуация, мало того,
что он выиграет в этой игре, она же и равновесная по Нэшу.
Потому что, опять, что могут эти люди, которые здесь находятся?
Ну этот ничего не хочет менять, понятное дело, потому что он уже и так выиграл.
Что ему менять?
Значит, улучшить потенциально свое положение могли бы вот эти люди,
если бы они могли, если бы они могли выиграть в игре, изменив свою стратегию.
Но что может любой из них?
Если он изменит стратегию на одну из вот этих,
да и вообще в принципе на любую другую стратегию,
если он уйдет вот с этого, так сказать, насеста, он изменит свою стратегию.
Он не выиграет.
Опять выиграет именно второй, вот который рядом с ним сидел на этой стратегии,
то есть никто не может изменить ход игры в свою пользу.
Он может свои...
Любой игрок может изменением своей стратегии привести игру к той ситуации,
что выиграет вместо этого человека какой-то другой, но не он сам.
Поэтому вот такая ситуация, где здесь произвольное количество пустых мест,
она является равновесной по Нэшу.
Но на самом деле найденные равновесия нетипичны.
Давайте попробуем...
Это нетипично в том смысле, что ну это как бы две конкретных конфигурации,
они действительно равновесны в зависимости от четности n,
но равновесий в этой игре по факту огромное количество.
Например, допустим, что ровно один человек назвал 0.
Тогда какие бы числа ни
называли все остальные (абсолютно любые комбинации чисел),
приводит к тому, что это равновесие Нэша.
Действительно, вот этот выиграл — ему ничего менять не хочется.
Может ли что-то изменить любой из них?
Нет, он может только что сделать?
Если он изменит стратегию не на 0, а на какую-то другую,
он вообще ничего не изменит.
А если он тоже напишет 0 — ну хорошо, значит, ни он не выиграет,
ни этот второй не выиграет.
Но он для себя ничего не изменит таким образом,
поэтому такая ситуация всегда равновесна по Нэшу.
Упражнение: доказать, что все остальные равновесия
Нэша в этой игре описываются следующей схемой: есть некоторый
уровень k, в котором ровно один игрок,
то есть число k написал один человек, больше никто.
Этот человек как раз сейчас у нас и выиграет.
До k все уровни, все абсолютно уровни до k,
заполнены не менее чем двумя (двумя или более) числами.
То есть люди все предыдущие числа они называли, и не один раз.
Вот.
А выше k — абсолютно произвольное соотношение любых чисел.
То есть равновесие, в котором выиграл человек, назвавший число k,
накладывает ограничение только на те уровни, которые ниже него.
И эти уровни должны быть заняты двумя или
тремя (не менее чем двумя людьми), а все выше могут быть совершенно произвольные.
Вот. Здесь есть некоторая...
Вот эта вот ситуация отличается от вот этой, где все по два, все ровно по два.
Если все ровно по два,
то позволяется поставить вообще в любую точку и здесь оставить пустые уровни.
Если бы хотя бы в одном месте было не два, а три, то вот такая ситуация равновесной
уже не была бы, потому что вот тот третий убежал вот сюда,
оставил бы их двоих и победил бы вместо этого.
Поэтому вот в этой общей ситуации мы позволяем заполнение уровней более
чем на два, но тогда победитель должен сразу следовать за ними,
а здесь уже произвольное соотношение.
Итак, все равновесия в этой игре описываются либо такой схемой, либо такой.
Доказать.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
