Разработанный МФТИ курс отличается тем, что все основные конструкции и принципы теории вводятся непосредственно на основе разбираемых "с нуля" конкретных этюдов. Каждый этюд начинается с понятной непрофессионалу проблемы. В одних случаях это просто "детская игра", в других - формализованное жизненное наблюдение, в третьих - обобщённая социальная закономерность. Сюжет затем разворачивается, исходя из логики содержащегося в нём конфликта, и сам порождает тот или иной принцип разрешения конфликта, который окончательно строго формализуется в виде решения игры. Этюдов всего рассмотрено чуть более десяти, и они в совокупности покрывают основные формальные конструкции базовой теории игр. В нескольких отступлениях приведены формулировки теорем существования игровых решений с набросками доказательств.
Игра "Гарвард", доминируемые стратегии
Loading...
En provenance du cours de Moscow Institute of Physics and Technology
Теория игр
32 notes
À partir de la leçon
Равновесия Нэша
В первой неделе вы познакомитесь с основными концепциями теории игр: игры в нормальной форме, (доминируемыми) стратегиями, равновесиями по Нэшу.
Rencontrer les enseignants
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
Но далеко не всегда существует доминантная стратегия,
и можно так просто предсказать исход.
Когда есть доминантная стратегия, ну по крайней мере с
точки зрения классической теории игр, исход предопределен.
Человек будет ее играть.
Бывает так, что доминантной стратегии нет,
но если подумать долго, игру все-таки решить можно, и исход можно предсказать.
Давайте рассмотрим следующий пример.
Игра, которая в простонаречии носит название «Гарвард».
Сейчас я объясню, по каким причинам это происходит.
Игра такая.
Есть аудитория, например, слушатели курса «Теория игр».
И им предлагается каждому выбрать число от 1 до 100,
натуральное целое положительное число от 1 до 100, любое.
0 запрещен, значит, от 1 до 100 — сто вариантов,
то есть можно так сказать у нас есть произвольное
количество игроков, ну, например, 50.
И у каждого игрока стратегическое множество — это множество,
состоящее из 100 первых натуральных чисел, не считая нуля.
Значит, теперь, каковы правила игры?
Правила такие: выигрывает тот,
чье число окажется ближе всего к среднему из всех чисел.
Но не просто к среднему из всех чисел, а его половине.
Давайте я это выпишу.
Выигрывает тот,
чье число
ближе всего — окажется ближе всего,
когда соберется информация про то, кто какое число записал,
— к среднему пополам,
то есть к x1 +...
+ xn / 2n.
Например, если 50 человек в зале было,
то сумму всех чисел нужно поделить на 100.
Давайте проанализируем эту игру.
Есть ли в ней какая-то стратегия, которая лучше всех остальных,
независимо от действий всех остальных.
Ну более-менее понятно, что не может быть такой стратегии, потому что то,
какое будет среднее, очень сильно зависит от того, что будут делать остальные.
Среднее может быть от 1 до 100.
И соответственно среднее пополам тоже может быть в каком-то диапазоне,
который совершенно нетривиальный диапазон, занимающий половину этих чисел.
И соответственно, априори нельзя сказать,
что какое-то число будет ближе к этому среднему.
Конечно, нет.
Ну давайте немножко подумаем над этой задачей.
Давайте рассмотрим самое большое возможное значение вот этого выражения.
Предположим, что все назвали число 100.
Тогда какое значение принимает вот это выражение?
Оно принимает значение 50.
[ЗВУК] [ЗВУК] Значит,
если выбраны произвольные стратегии,
то есть произвольные числа от 1 до 100,
то значение среднего пополам не превосходит 50.
Какой вывод из этого можно сделать?
Из этого можно сделать вывод, что число 50 — это максимальное число,
которое, грубо говоря, имеет смысл называть.
Потому что назвать 51,
52 и так далее вплоть до 100 — любая из
вот этих стратегий заведомо будет дальше
от числа среднее пополам, чем число 50.
То есть пишу: 50 лучше, заведомо лучше — ну скажем так, не хуже,
— не хуже, потому что будет ближе к среднему пополам.
Шансы оказаться самым близким к среднему пополам у
числа 50 не меньше, чем у чисел 51, 52 и так далее.
Вот это подсказывает нам следующее определение,
которое продолжает предыдущее определение,
а именно определение доминируемой стратегии.
Не доминирующей, которая лучше всех, а доминируемой, то есть стратегия,
которая хуже некоторой другой, независимо от того, что делают другие игроки.
Значит, прежде чем давать это определение, я хочу договориться о некоторых
обозначениях, которые для теории игр совершенно универсальны.
И поэтому нам тоже имеет смысл их придерживаться.
Набор стратегий S₁, S₂, ..., Si − 1,
Si + 1, ..., Sn в теории
игр обозначается следующим образом: S−i.
Запоминайте во всех книгах по теории игр.
Более того, S − i — это
обозначение для декартового произведения всех стратегических множеств,
кроме стратегического множества i-того игрока, то есть вот для этого объекта.
Если мы договоримся таким образом,
то выражение (Si,
S − i) — это просто обозначение некоторого исхода игры,
в котором Si вставлен вот в это вот место этого профиля.
Вот. После того,
как мы сделали такие обозначения, давайте дадим определение.
Стратегия S*i
игрока и
строго доминируемая
— или строго строго доминируется
— посредством
стратегии Si
с волной того же самого игрока,
если независимо от того,
как действуют остальные, выигрыш
i-того игрока от
применения * вот в этом окружении,
как говорят, в окружении — это значит при применениями остальными вот этого набора
их стратегий — строго меньше, чем Ui от применения
Si с волной против того же самого набора действий остальных игроков.
Итак, строгое доминирование.
Некоторая стратегия — одна конкретная стратегия — объявляется плохой,
если существует какая-то другая стратегия,
дающая строго больший выигрыш во всех вообще мыслимых ситуациях.
Ну и постулат.
Постулат, постулат теории игр состоит в том,
что такие стратегии никогда не используются игроками.
Постулат: в этой ситуации стратегию
S*i можно выкинуть из списка стратегий игрока.
То есть не рассматривать ситуаций никаких,
в которых эта стратегия бы применялась.
Из списка Si.
Я не обсуждаю, насколько этот постулат
разумный с житейской точки зрения, потому что как мы уже видели,
даже в дилемме заключенных, где есть просто доминантная стратегия и вроде бы
надо ее всегда применять, в реализациях в классе происходит не так.
В половине случаев люди ведут себя иначе.
То есть то, как ведут себя люди, и то, как теория игр предсказывает их поведение,
— это две вещи, которые очень сильно расходятся.
К сожалению или к счастью — я не знаю, я не хочу обсуждать философских аспектов.
Но факт состоит в том, что теория игр плохо предсказывает поведение людей.
То есть с точки зрения математики здесь всё безупречно,
я вас научу этой математике, но я хочу сразу предупредить всех,
что эта математика далеко не всегда относится к жизни.
Но давайте, тем не менее, продолжим исследование этой игры с точки зрения
постулата, который мы сделали.
Значит, если мы вводим такое определение и исходим из этого постулата,
то вот эти стратегии использоваться не будут.
Единственное, нужно дополнить это определение,
что слабое доминирование слабо доминируется,
слабо доминируется, если всё то же самое,
и здесь стоит знак меньше или равно вместо знака меньше.
Значит, стратегия слабо доминируется, если выигрыш, который будет получен от нее,
он никогда не больше, чем выигрыш, который получается от некоторой другой стратегии.
Иногда меньше, иногда такой же, но никогда не больше.
В частности, если я говорю 51, вместо 50,
то я никогда не окажусь ближе к тому числу,
к которому я должен приблизиться ближе всех остальных.
Но при этом если кто-то другой будет ближе к нему, то и в этом случае,
и в этом я просто ничего не выиграю.
Мой выигрыш будет равен нулю.
Поэтому здесь нельзя написать строгого равенства,
но нестрогое равенство написать можно.
Значит, постулат о том, что игроки не используют слабо доминируемых стратегий
он еще в меньшей степени выполняется в реальности, чем постулат о сильных.
И тому есть некоторые даже теоретические причины.
Не тем не менее, давайте попробуем работать в рамках того, что этот постулат
выполнен, и соответственно игрок не будет использовать стратегии 51, 51,
..., 100 просто потому, что сказав 50,
он заведомо окажется ближе к числу, к которому он хочет приблизиться.
Может быть, это ему не позволит выиграть,
но по крайней мере во всех случаях шансы не уменьшатся.
Поэтому мы объявляем, что игроки,
если они сколько-нибудь умные, они этих стратегий применять не будут.
Вот.
Ну и в следующем сюжете мы посмотрим, что следует из
этой логики, если согласно нее идти до конца.
Explorer notre catalogue
Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.
Coursera propose un accès universel à la meilleure formation au monde,
en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.
© 2018 Coursera Inc. Tous droits réservés.
