Добрый день! До сих пор мы с вами изучали игры, в которых игроки принимают решения одновременно. На этой неделе мы рассмотрим игры, в которых игроки ходят по очереди и, таким образом, каждый игрок знает информацию о том, какие решения принимали другие игроки, которым принадлежал ход до него. Давайте начнем нашу лекцию с красивого примера. В книге известного детского писателя Алана Милна «Винни-Пух и все-все-все» описана история о том, как у старого серого ослика Иа-Иа был день рождения, и плюшевый мишка Винни-Пух решил подарить Иа-Иа горшочек с медом. День был жаркий, а путь неблизкий. И не пройдя и полпути, Пух вдруг почувствовал какое-то странное щекотание. Сначала у него защекотало в носу, потом в горле, а потом засосало под ложечкой. И так постепенно дошло до самых пяток. Казалось, словно кто-то внутри у него говорил: «Знаешь, Пух, сейчас самое время чем-нибудь немножко...» Перед Винни-Пухом встал нелегкий выбор: съесть мед из горшочка, который он нес в подарок Иа-Иа, или все-таки доставить этот подарок в целости и сохранности. Винни-Пух не смог удержаться от соблазна и съел весь мед, сразу же пожалев об этом, ведь у него больше не было подарка для Иа-Иа. Сперва он прямо не знал, что и думать. А потом он подумал: «Все-таки это очень хорошенький горшочек, хотя в нем и нету меда. Если я его как следует вымою и попрошу кого-нибудь написать на нем «Поздравляю с Днем рождения!», Иа сможет держать в нем все, что хочешь. Это будет замечательный подарок!» Винни-Пух оказался прав. Иа-Иа с радостью принял его подарок. Таким образом, в этой истории разворачивается стратегическое взаимодействие между Винни-Пухом и Иа-Иа. Сначала Винни-Пух решает, съесть мед из горшочка или нет, а потом уже Иа-Иа, зная о том, какое решение принял Винни-Пух, в свою очередь решает, принимать этот подарок или не принимать его. Давайте подумаем, как устроены предпочтения игроков на множестве возможных исходов. С одной стороны, Винни-Пух очень голоден. С другой стороны, ему хочется порадовать Иа-Иа, подарив тому замечательный подарок. Лучше всего для Винни-Пуха было бы, если бы он съел мед, а Иа-Иа все равно бы согласился принять в подарок этот горшочек. Однако если сравнивать средние альтернативы, то Винни-Пуху было бы лучше все-таки не есть мед при условии, что Иа-Иа примет подарок, чем съесть мед, но потом получить отказ от Иа-Иа. Наконец, хуже всего Винни было бы, если бы он не ел мед, а Иа-Иа все равно бы отказался от его горшочка с медом. Предпочтения у ослика Иа-Иа устроены так. Для него принять подарок всегда лучше, чем отказаться от него. Ведь иметь что-то лучше, чем этого не иметь. Но при этом получить полный горшочек с медом для Иа-Иа было бы лучше, чем получить пустой. Описанное взаимодействие можно представить в виде дерева игры. Мы на первой лекции рассматривали пример построения игры в развернутой форме. Давайте немножечко вспомним про это. У нас вершинам соответствуют различные состояния игры, и каждой вершине приписано имя игрока, которому в этой вершине принадлежит ход. А ребрам приписаны действия, которые может совершить игрок, которому принадлежит ход в этой вершине, из которого эти ребра выходят. Получаем вот такое вот дерево игры, которое изображено на ваших экранах. Вершины, в которых игра заканчивается, называются терминальными. Они на нашем рисунке помечены черным цветом. И каждой из таких вершин приписаны платежи, которые получают игроки. То есть в разных состояниях игры игроки получают разные платежи. Первый платеж означает платеж в данном случае первого игрока, второй платеж — второго игрока, Винни-Пуха и Иа-Иа соответственно. Вот представление игры в таком виде называется игрой в развернутой форме. И последовательные стратегические взаимодействия мы будем описывать с помощью игр в развернутой форме. То есть это формальная модель, созданная специально для того, чтобы описывать последовательные стратегические взаимодействия. Еще одно определение. Давайте рассмотрим ту часть дерева, которая начинается не в самой начальной вершине у нас, а в какой-то другой, нетерминальной, вершине. Например, представим, что Винни-Пух съел мед, и мы оказались в ситуации, в которой Иа-Иа должен принять решение, что делать: принимать пустой горшочек или нет. Эта вершина здесь обозначена буквой В, и часть дерева, которая начинается в какой-то нетерминальной вершине, называется подыгрой. Таким образом, в этом дереве игры есть три подыгры: это подыгра В, которая соотвествует ситуации, в которой Иа-Иа должен принять решение о том, что делать с пустым горшочком: принимать его или нет. Это подыгра С, в которой Иа-Иа должен принять решение о том, что делать с полным горшочком: принимать его или нет. И подыгра А, которая совпадает со всей игрой. И теперь важное определение, которое отличает игру в развернутой форме от игры в нормальной форме. Стратегией игрока в игре в развернутой форме называется набор действий игрока в каждой вершине, в которой ему принадлежит ход. Обратите внимание: до сих пор я не говорил слово «стратегия». Когда мы говорили о том, что может сделать игрок в каждой вершине, в которой ему принадлежит ход, я говорил слово «действие». Так вот, стратегия игрока — это набор действий игрока в каждой вершине, в которой ему принадлежит ход. Например, в той игре, которую мы сейчас обсуждаем, у Винни-Пуха есть всего одна вершина, в которой ему принадлежит ход, поэтому, по определению, стратегия игрока — это указание Винни-Пуху, что делать в этой вершине, в которой ему принадлежит ход: либо съесть мед, либо не есть его. Таким образом, у него есть два возможных действия, две возможных стратегии. У Иа-Иа есть две вершины, в которых ему принадлежит ход. Соответственно, стратегия игрока Иа-Иа должна содержать информацию о том, что будет делать Иа-Иа в случае, если он оказался в такой ситуации, что должен принимать решение о принятии или непринятии пустого горшочка. Это первое, что должна предусматривать стратегия Иа-Иа. И второе, что должна предусматривать стратегия Иа-Иа, — это что делать в ситуации, когда Винни-Пух принес ему полный горшочек. И вообще говоря, действия Иа-Иа в первом случае и во втором случае могут различаться, а могут совпадать. Таким образом, у Иа-Иа есть четыре возможные стратегии. Первая стратегия Иа-Иа выглядит так: принимать подарок в любом случае. Если Винни-Пух принесет полный горшочек, или если он принесет пустой горшочек, все равно принимать. Эта стратегия на ваших экранах сейчас подсвечена. Вторая стратегия Иа-Иа заключается в следующем: принимать подарок, если Винни-Пух принесет пустой горшочек, то есть если съест мед, и не принимать подарок, если Винни-Пух принесет полный горшочек. На первый взгляд, эта стратегия может показаться очень странной. Как так: принимать подарок, если он не очень хороший, без меда, и не принимать его, если подарок хороший, с медом. На самом деле сейчас мы пока еще не анализируем игру. Мы пока описываем множество возможных стратегий каждого из игроков. Решение игры начнется позже. Сейчас наша задача — формализовать игру, то есть указать множество возможных стратегий каждого игрока. И та стратегия, которая сейчас указана на ваших экранах, — это возможная стратегия Иа-Иа. Итак, еще раз, у него есть возможная стратегия принимать подарок, если ему подарят пустой горшочек, и не принимать подарок, если ему подарят полный горшочек. Третья возможная стратегия Иа-Иа — наоборот, не принимать пустой горшочек и принимать полный. И, наконец, четвертая возможная стратегия — это вообще никогда не принимать подарок от Винни-Пуха.
