В течение жизни мы постоянно взаимодействуем с другими людьми. Маленькие дети, пытаясь добиться того, чтобы родители купили понравившуюся конфетку, часто шантажируют родителей своими слезами. Принимая решение заплакать, ребенок рискует — он не знает, как поведут себя папа с мамой. В чуть более взрослом возрасте абитуриенты, выбирающие вуз, принимают сложное решение о том, в какие университеты подать документы. Ошибка может стоить дорого: при неправильной стратегии можно оказаться в слабом университете или вообще остаться без заветного студенческого билета. Окончив вуз, юноши и девушки начинают искать работу. Перед интервью с работодателем они штудируют статьи в интернете о том, что можно и чего нельзя говорить на интервью, — они пытаются найти наилучшую стратегию своего поведения, исходя из ожиданий компании, в которую они устраиваются. Все эти ситуации объединяет то, что решения, которые принимают одни люди, оказывают влияние на других людей. Такие взаимодействия называются стратегическими. Именно их изучает теория игр. Чтобы проанализировать ту или иную реальную жизненную ситуацию стратегического взаимодействия и найти оптимальный вариант поведения в ней, необходимо сделать две вещи. Во-первых, необходимо формально записать ситуацию на языке теории игр, то есть создать модель (игру). Во-вторых, после того как модель (игра) составлена, ее необходимо решить. Этому мы будем учиться в течение курса. Мы разберем основные виды игр (одновременные и последовательные, с совершенной и несовершенной информацией, коалиционные и некоалиционные), приведем способы их решения и обсудим их на многочисленных примерах. Курс будет интересен желающим разобраться в том, как конкурируют друг с другом несколько компаний и можно ли гарантированно выиграть в шашки, есть ли смысл угрожать на переговорах и с кем стоит объединяться в коалиции в парламенте. FAQ В: Требуется ли предварительная подготовка для прохождения курса? О: Курс является базовым, поэтому он не требует специальной подготовки. Для его успешного освоения достаточно уверенных знаний курса математики в объеме школьной программы. В одном-двух примерах могут пригодиться знания начал математического анализа (дифференцирование функций одной переменной, необходимое условие экстремума) и знания начал теории вероятностей (понятие математического ожидания случайной величины). В: Что требуется для успешного окончания курса? О: Итоговая оценка за курс складывается из результатов 10 оцениваемых тестов. Для успешного окончания курса необходимо дать не менее 80 % правильных ответов на каждый из этих тестов.
Определения
Loading...
來自 National Research University Higher School of Economics 的課程
Теория игр (Game Theory)
607 個評分
從本節課中
Игры с несовершенной информацией
Salut! Мы рады видеть вас уже на седьмой неделе нашего курса. Преодолен своеобразный рубеж: на первых шести неделях мы изучили джентльменский набор начинающего теоретико-игровика. Начиная с седьмой недели мы будем говорить о более высоких материях. Тема этой недели — несовершенство информации. Иногда бывает так, что при последовательном стратегическом взаимодействии один из игроков не знает, какие действия выбрал другой игрок. Можно ли анализировать поведение игроков в таких ситуациях? Оказывается, что да, и мы будем этому учиться.
與講師見面
Dmitry DagaevAssociate Professor, Deputy Vice Rector
Department of Higher Mathematics
Здравствуйте!
До сих пор, рассматривая игры в развернутой форме,
мы с вами предполагали, что каждый игрок в каждый момент времени знает,
какие стратегии, какие действия игрались другими игроками до этого.
Однако иногда встречаются игры,
в которых один из игроков не знает, в какой вершине он оказался.
Сегодня мы познакомимся именно с такими играми.
Давайте сначала обратимся к уже хорошо известной нам «Битве полов».
У каждого из супругов есть выбор из двух стратегий: пойти сегодня
вечером на футбол или на балет.
Матрица игры представлена на ваших экранах.
Теперь представим, что муж делает свой выбор чуть раньше жены.
Напомню, что раньше, когда мы обсуждали эту игру,
муж и жена делали всё время этот выбор одновременно.
Теперь игра становится последовательной.
Но во всех последовательных играх, которые мы рассматривали до этого,
игрок, делающий ход, знал,
какой ход сделали игроки до него.
Поэтому если бы мы описывали «Битву полов» в рамках
той модели, которую мы изучили на предыдущих лекциях,
то тогда жена должна была бы знать, какой ход сделал муж.
Проблема в том, что тогда это перестало бы быть одновременной игрой.
Давайте нарисуем то же самое дерево,
однако предположим, что жена не знает, в какой из двух вершин она оказалась.
Другими словами, она не может отличить то состояние,
в котором муж выбрал футбол, и то состояние, в котором муж выбрал балет.
На дереве пометим эти две вершины пунктиром.
Соединим их пунктиром.
Это будет означать, что игрок — в данном случае жена — не может однозначно понять,
в какой из этих двух вершин она находится.
Мы будем говорить, что некоторое множество вершин M дерева игры называется
информационным множеством игрока i, если выполняются три условия.
Во-первых, во всех вершинах множества М ход принадлежит игроку i.
Во-вторых, игрок i не может отличить друг
от друга вершины, входящие во множество М.
И в-третьих, игрок i может отличить любую из вершин,
входящую в множество М, от всех остальных вершин.
Если каждое информационное множество любого из игроков состоит
всего из одной вершины, то мы говорим,
что такая игра называется игрой с совершенной информацией.
А вот если существует по крайней мере у одного из игроков по крайней мере
одно информационное множество, в котором есть по крайней мере две вершины,
то тогда мы говорим, что это игра с несовершенной информацией.
Несовершенство информации означает, что по крайней мере
один из игроков по крайней мере иногда не может однозначно понять,
в какой из вершин дерева он находится.
В нашей игре у жены одно информационное множество.
Оно состоит из двух вершин: из вершины, в которой муж выбрал
футбол, и вершины, в которой муж выбрал балет.
Жена не знает, в какой из этих вершин она находится.
Она не знает выбор мужа.
Поэтому вот эти вот две вершины объединены в одно информационное множество.
У мужа тоже одно информационное множество, но оно состоит из одной вершины.
Муж доподлинно знает, в каком состоянии игры он находится.
В играх с несовершенной информацией игрок делает свой выбор в каждом своем
информационном множестве.
Он выбирает свое действие в этом информационном множестве.
И обратите внимание: в играх с совершенной информацией мы считали,
что игрок выбирает действие в каждой вершине, в которой ему принадлежит ход.
Теперь же мы считаем, что игрок выбирает свое
действие не в каждой вершине, а в каждом своем информационном множестве.
То есть жена, не будучи уверена, что выбрал муж,
не может сказать: я буду играть «футбол»,
если муж выбрал «футбол», и я буду играть «балет», если муж выбрал «балет».
У нее нет такой возможной стратегии.
Жена должна сказать: я буду играть «футбол» или я буду играть «балет».
То есть ее выбор совершенно однозначен и не может
различаться для двух вершин одного информационного множества.
Теперь мы можем дать определение стратегии игрока для более широкого класса игр.
То определение, которое мы сейчас дадим, будет работать как для игр
с совершенной информацией, так и для игр с несовершенной информацией.
Оно будет в случае игр с совершенной информацией,
обобщать то определение стратегии, которое мы дали раньше.
Итак, стратегией игрока называется набор действий
игрока во всех информационных множествах, в которых ему принадлежит ход.
То есть игрок должен сделать
выбор своего действия в каждом своем информационном множестве.
И вот этот вот набор указаний называется стратегией игрока.
Обратимся снова к нашей «Битве полов».
У мужа есть ровно одно информационное множество.
В нем у него есть выбор из двух действий: «пойти на футбол» или «пойти на балет».
И поэтому множество стратегий мужа имеет вид: «пойти на футбол» или «пойти на балет».
У жены есть одно информационное множество.
В этом одном информационном множестве у жены тоже есть два возможных
действия: «пойти на футбол» или «пойти на балет».
Поэтому у жены тоже есть ровно две стратегии: сыграть «футбол»
или сыграть «балет».
Обратите внимание, что, вообще говоря, дерево этой игры,
которое мы только что нарисовали, можно было бы нарисовать немножко по-другому.
Мы могли бы предположить, что жена ходит первой, а именно, она делает свой выбор,
после этого муж, не зная, какой выбор сделала жена,
принимает собственное решение, куда пойти: на футбол или на балет.
Тогда дерево игры получилось бы другим.
Однако в этом нет ничего страшного.
Вообще говоря, одну и ту же ситуацию могут описывать разные модели,
разные в данном случае деревья.
Давайте теперь уточним определение подыгры.
В играх с совершенной информацией мы называли подыгрой любую часть дерева,
которая начинается в одной из его нетерминальных вершин.
В играх с несовершенной информацией с таким определением возникла бы проблема.
Вот представьте, что мы находимся в какой-то части дерева.
Начинается это дерево в одной из вершин.
И теперь представьте, что один из игроков имеет информационное множество,
которое, с одной стороны, пересекается с этим поддеревом, с другой стороны,
имеет вершины, которые в этом поддереве не лежат.
Тогда получается, что это поддерево нельзя было бы рассматривать как
самостоятельную подыгру, потому что игрок не мог бы — по крайней
мере в некоторых ситуациях — быть уверенным в том,
находится он вообще в этой подыгре или не находится в ней?
Поэтому определение подыгры на случай игр
с несовершенной информацией несколько модернизируется.
Подыгрой в играх в развернутой форме с несовершенной информацией
называется любое такое поддерево, что любое информационное множество,
пересекающееся с этим поддеревом, полностью лежит в нем.
То есть мы называем теперь подыгрой вершину,
всю часть дерева, которая начинается в этой вершине,
но только в том случае, если любое информационное множество,
которое хоть как-то пересекается с этим поддеревом, полностью лежит в нем.
Вот в этом случае эта часть дерева называется подыгрой.
Например, в «Битве полов» есть всего одна подыгра,
в случае игры с несовершенной информацией.
Она совпадает со всей игрой.
Часть дерева, которая начинается в одной из вершин,
в которой ход принадлежит жене, подыгрой не является,
потому что, например, давайте рассмотрим верхнюю вершину,
в которой ход принадлежит жене, то есть когда муж выбрал «футбол».
Почему часть дерева, которая начинается в вершине B, не является подыгрой?
Потому что эту часть дерева нельзя рассматривать как самостоятельную игру.
Жена не может быть уверена, — она вообще
находится в этой подыгре или не находится в ней?
Она не может доподлинно знать, выбрал муж «футбол» или выбрал муж «балет»?
Поэтому мы требуем, чтобы любое информационное множество
содержалось в той части дерева, которое мы хотим назвать подыгрой.
А вот если мы рассмотрим подыгру, которая начинается в вершине А,
то это действительно подыгра, потому что любое информационное
множество — будь то информационное множество мужа или информационное
множество жены — целиком входит в эту часть дерева, то есть во все дерево.
Поэтому это подыгра по нашему определению.
Итак, что же мы сделали?
Теперь мы можем представлять в виде игры
в развернутой форме более широкий класс игр, чем мы умели делать это раньше.
В частности, например, все игры в нормальной форме теперь
можно представить в виде игры в развернутой форме.
Как это сделать?
Например, сначала можно зафиксировать первого игрока; рассмотреть
все его возможные стратегии; нарисовать дерево,
в котором, вот, у первого игрока, делающего первый ход,
есть набор его действий; получить соответствующие
вершины этого дерева; объединить их в одно информационное множество
второго игрока и из каждой из этих вершин выпустить ребра,
соответствующие возможным стратегиям второго игрока, и так далее.
Шаг за шагом, проделав эту операцию для каждого игрока,
мы в итоге построим дерево игры, соответствующее игре в нормальной форме.
Естественно, это соответствие не взаимно-однозначное.
По одной и той же игре в нормальной форме можно, вообще говоря,
построить много разных деревьев.
И в этом смысле переход от игры в нормальной форме к игре в развернутой
форме отличается от перехода от игры в развернутой форме
к игре в нормальной форме, то есть от перехода в обратную сторону.
Напомню, что когда у нас было дерево игры, мы по нему совершенно
однозначно могли построить матрицу игры.
До этого обратное действие мы совершить не могли, — то есть
по матрице игры построить дерево такой игры, — а вот теперь мы научились это делать.
Вводя несовершенство информации, мы можем представить любую игру в нормальной форме
в виде игры в развернутой форме.
