Введение в теорию игр. Стратегические взаимодействия и их формализация в виде игр в нормальной и развернутой форме

ЛЕКЦИЯ 1. Введение в теорию игр. Стратегические взаимодействия и их формализация в виде игр в нормальной и развернутой форме План лекции: 1. Примеры стратегических взаимодействий. 2. Формализация одновременных стратегических взаимодействий в виде игр в нормальной форме. Матричная запись игр двух лиц. 3. Формализация последовательных стратегических взаимодействий в виде игр в развернутой форме. Цель лекции: научится переводить реальные ситуации на язык теории игр. 1 ВВЕДЕНИЕ Теория игр изучает принципы принятия решений в условиях стратегического взаимодействия нескольких агентов, то есть в таких ситуациях, когда решение кого-то одного оказывает влияние на всех остальных. Например, шахматист перед тем, как сделать свой ход, просчитывает возможные ответные ходы соперника и выбирает то продолжение, которое сулит ему самую хорошую позицию. Теннисист, выбирая направление подачи, старается сделать этот выбор непредсказуемым, чтобы затруднить прием мяча соперником. Всё это - примеры стратегического взаимодействия двух спортсменов. Однако, в теории игр слово «игра» трактуется более широко, чем в обычной жизни. Играми мы будем называть не только шахматы или теннис, но также и торг на рынке, голосование в Совете Безопасности ООН, распределение абитуриентов по высшим учебным заведениям и многое другое. Всё это игры, в которых каждый из участников стремится достичь оптимального для себя исхода, ориентируясь в том числе и на стратегии всех остальных. 2 Как это сделать - предмет изучения теории игр. В рамках нашего курса мы изучим базовые понятия и концепции теории игр, обсудим их практические применения, поговорим о современных исследованиях. Теория игр - молодая наука. Ее фундамент был сформирован в середине XX века. Тем не менее, на сегодняшний день аппарат теории игр является одним из основных инструментов анализа в экономической теории. За последние 20 лет четыре Нобелевские премии по экономике были присуждены за фундаментальные работы в области теории игр, а еще ряд лауреатов использовали аппарат теории игр в своих исследованиях. 3 1. Примеры стратегических взаимодействий Теория игр - наука о стратегических решениях агентов: людей, компаний, правительств. Стратегические решения - это такие решения, которые принимаются с учетом действий других агентов и которые влияют на полезность других агентов. Например, когда Ваня играет с друзьями в покер и принимает решение о том, сделать ли ему ставку или сбросить карты, он, естественно, принимает во внимание то, какие решения приняли или могут принять его соперники. С хорошей картой он будет чаще делать ставку. С плохой картой он будет чаще сбрасывать карты. Однако, если он все время будет играть таким образом, то соперники рано или поздно поймут его стратегию и смогут найти удачную стратегию против нее, то есть они смогут научиться предсказывать поведение Вани, поэтому Ваня должен задумываться о том, как сбить с толку своих соперников. Это стратегическое решение. Другой пример: Людмила Степановна собрала урожай помидоров и думает, по какой цене продавать эти помидоры на рынке. При принятии решения об уровне цены она, естественно, должна принимать во внимание то, какую цену установили соседи по рынку. Если она установит слишком высокую цену, то помидоры у нее никто не купит. С другой стороны, если она установит слишком низкую цену, то она лишится прибыли. Решение о том, какую цену установить, - это стратегическое решение Людмилы Степановны. Что же такое нестратегическое решение? Например, если Маша пришла в столовую во время обеденного перерыва и думает о том, какой пирожок купить: с яблоком, с капустой, с картошкой, - это нестратегическое решение. Это решение зависит исключительно от того, как устроены предпочтения Маши на множестве различных пирожков. Что ей больше нравится, то она и купит. 4 Ситуации, в которых действия одних агентов оказывают влияние на других агентов, мы будем называть стратегическими взаимодействиями. Давайте рассмотрим еще несколько примеров. Когда несколько легкоатлетов бегут дистанцию на 800 метров, они вступают друг с другом в стратегическое взаимодействие. Они принимают решение о том, как распределить свои силы по дистанции: выходить вперед или начать эту гонку сзади. Это решение, в том числе, зависит от того, какие действия, какие стратегии, какие решения приняли остальные участники этого забега. Другой пример. Когда мы выходим из магазина с тяжелыми сумками, подходим к таксисту и начинаем торговаться с ним о цене, по которой он довезет нас до дома, то мы вступаем с ним в стратегическое взаимодействие. Мы пытаемся договориться об уровне цены. При этом мы принимаем во внимание много разных факторов. 5 Во-первых, мы учитываем, что помимо этого таксиста рядом с ним стоят его коллеги. И если таксист будет называть слишком высокую цену, то мы не будем соглашаться на нее. Мы всегда можем уйти к его коллегам. Таксист также принимает это во внимание. Он хочет заключить с нами соглашение, довезти нас до дома, и поэтому он будет закладывать эти свои ожидания о том, на какую цену мы можем согласиться, в свое предложение. Мы вступаем с ним в стратегическое взаимодействие. Еще один пример, - это ценовая война фирм на олигополистическом рынке. Например, можно рассмотреть ценовую войну фирм на рынке сотовой связи. Если в некоторой стране есть три крупных оператора, то они, надеясь заполучить как можно большую долю рынка, могут захотеть чуть-чуть понижать цену по сравнению с другими фирмами. Если люди чувствительны к небольшому понижению цены, то такое поведение фирм может привести к ценовой войне, а именно к ситуации, когда одна фирма, понижая цену, будет провоцировать другую фирму на то, чтобы та также изменила цену на эту услугу. Ведь ни одной фирме не будет выгодно терять долю своих клиентов. Таким образом, эти фирмы вступают в стратегическое взаимодействие. Еще один пример стратегического взаимодействия - это дипломатические переговоры между правительствами. 6 Предлагая друг другу заключить некоторое соглашение, и называя свои условия, по которым стороны готовы заключить это соглашение, стороны вступают друг с другом в стратегическое взаимодействие. Все стратегические взаимодействия можно разделить на два типа: на одновременные и на последовательные. Одновременными стратегическими взаимодействиями мы будем называть такие взаимодействия, во время которых агенты принимают решение в один момент времени и независимо друг от друга. Они не знают, какой выбор делают другие агенты. Примером одновременного стратегического взаимодействия может служить, например, игра в «камень, ножницы, бумагу». Другой тип стратегического взаимодействия - это последовательные взаимодействия. В последовательных взаимодействиях агенты принимают решение по очереди. В каждый момент времени каждый агент знает о том, какие решения были приняты на предыдущих этапах, и, соответственно, он, принимая свое решение, может учитывать те действия, которые были совершены до этого момента времени. Примером последовательного стратегического взаимодействия являются шахматы. Игрок в каждый момент времени, раздумывая над ходом, знает все предыдущие ходы, которые были сыграны в этой партии. Теперь мы можем сформулировать, что такое игра. 7 Игрой мы будем называть любое стратегическое взаимодействие нескольких агентов, а игроками мы будем называть, собственно, этих агентов, которые являются участниками этого стратегического взаимодействия. Обратим внимание, что, вообще говоря, игры в бытовом понимании этого слова, как правило, тоже являются стратегическими взаимодействиями. Например, играя в теннис или в шашки, мы вступаем в стратегическое взаимодействие с нашим соперником. Принимая свое решение, мы стараемся затруднить положение соперника. В то же время многое из того, что бы мы не назвали игрой в привычном смысле этого слова, тоже является игрой в теоретико-игровом понимании. Например, торг на рынке, ценовая конкуренция фирм или политическая конкуренция во время предвыборной кампании, тоже являются играми. И о них мы будем подробно говорить в нашем курсе. Алгоритм работы со стратегическими взаимодействиями у нас будет таким: сначала нужно описать какую-то реальную жизненную ситуацию в виде модели, игры, то есть записать ее на формальном теоретико-игровом языке. После того как это сделано, мы абстрагируемся от этой реальной жизненной ситуации и работаем уже с этой игрой, с формальным ее описанием. 8 Применяя различные теоретико-игровые концепции, которые мы изучим в рамках нашего курса, мы сможем найти решение этой модели, то есть попытаться предсказать, как будут себя вести игроки в этой ситуации. Одновременные стратегические взаимодействия мы будем моделировать с помощью игр в нормальной форме. А последовательные стратегические взаимодействия - с помощью игр в развернутой форме. Давайте подробно рассмотрим еще один пример стратегического взаимодействия, касающегося поступления в высшие учебные заведения с помощью единого государственного экзамена. Давайте представим, что есть некоторый выпускник, назовём его Петя, который сдал единый государственный экзамен и теперь планирует поступить в вуз. Давайте представим, что Петя набрал не очень много баллов на ЕГЭ. Он точно знает, куда он хочет поступать, на какое направление, и у него есть предпочтения на множестве всех высших учебных заведений: чем сильнее вуз, тем больше он привлекает Петю. Таким образом, в голове у Пети есть некоторый рэнкинг вузов по привлекательности. Петю устраивает только бюджетное место: он ни за что не пойдёт учиться за деньги. Решение о том, в какие вузы Петя может отнести свои документы, - это стратегическое решение. Правила поступления в вузы устроены следующим образом: Петя может разослать свои документы по пяти университетам. Дальше университеты получают документы от всех абитуриентов, составляют списки лучших абитуриентов по сумме набранных баллов и делают предложение этим лучшим абитуриентам. Абитуриенты принимают это предложение или отказываются от него, и в случае, если остаются свободные места, наступает следующая итерация. 9 Давайте теперь подумаем, как выгодно себя вести Пете. Разумно ли Пете подавать документы только в лучший вуз? Петя может, вообще говоря, использовать своё право подать документы в пять различных высших учебных заведений. Вот если он подаст свои документы в пять лучших вузов в списке его предпочтений, будет ли это решение оптимальным? Нет. Мы знаем, что Петя набрал не очень много баллов на ЕГЭ, и это означает, что он очень сильно рискует вообще остаться без бюджетного места, потому что лучшие университеты скорее всего будут также являться лучшим выбором для других абитуриентов, в том числе для тех абитуриентов, которые набрали достаточно много баллов на ЕГЭ. Поэтому Петя вряд ли окажется высоко в этом списке, который построит каждый вуз. 10 Тогда Петя может просто оказаться без бюджетного места. Для того чтобы лучше предсказать поведение других абитуриентов, Петя начинает изучать итоги приёмных кампаний прошлых лет. Это может помочь ему понять, в какие вузы реально поступить с его суммой баллов. И в результате Петя подаёт документы в разные вузы: как в сильные, так и в те, в которые он имеет реальные шансы поступить. Такая стратегия является страховкой от того, что он не поступит вообще никуда. Если же ему повезёт и ему сделает предложение в том числе и сильный вуз, ничто не помешает Пете выбрать это высшее учебное заведение. 11 2. Формализация одновременных стратегических взаимодействий в виде игр в нормальной форме. Матричная запись игр двух лиц Мы рассмотрели достаточно подробно несколько примеров стратегического взаимодействия. Теперь давайте научимся формально описывать эти стратегические взаимодействия на языке теории игр. Сначала, начнем с игр в нормальной форме. Для того чтобы задать игру в нормальной форме, нужно сделать три вещи. Нужно, во-первых, указать множество всех игроков в этой игре. Во-вторых, указать множество возможных стратегий каждого игрока. И, в-третьих, указать платеж, который получает каждый игрок. Итак, мы задаем множество игроков. Будем обозначать это множество I. И оно состоит из имен этих игроков. Для простоты будем обозначать их один, два, три и так далее … n. Будем считать, что игроков по крайней мере двое. Иначе нет никакого взаимодействия между несколькими игроками. Теперь, у каждого игрока есть множество его возможных стратегий. Будем обозначать через S большое с индексом i множество возможных стратегий игрока номер i. 12 После того как каждый игрок посмотрел на множество своих возможных стратегий, он должен сделать выбор: какую из этих своих стратегий сыграть. Выбор игрока из множества всех своих возможных стратегий одной единственной стратегии будем обозначать ее s с индексом i маленькая. После того как каждый игрок выбрал, какую стратегию он сыграет, формируется набор этих стратегий. Его мы будем называть профилем стратегий. (s1, …, sn) - это профиль стратегий игроков. Теперь, когда зафиксирован профиль стратегий, мы должны определить платежи, которые получат игроки, если будет сыгран этот профиль стратегий. Таким образом, у каждого из игроков должна быть задана функция платежей. Обозначим ее через u с индексом i. Она определена на множестве всех возможных профилей стратегий. Что бы ни сыграли игроки, мы должны знать, сколько получит каждый из игроков в этом случае. 13 Давайте рассмотрим в качестве примера одну из самых известных в теории игр игр, которая называется «Битва полов». Муж и жена одновременно и независимо друг от друга решают, где им провести выходной день. Муж больше хочет на футбол, а жена предпочитает балет. При этом они хотят провести этот вечер вместе. Они принимают это решение независимо: у них нет возможности обменяться информацией. Мобильных телефонов еще нет. Множество игроков в этой игре - это муж и жена. У каждого из игроков есть две возможные стратегии. У мужа есть стратегия «пойти на футбол» и стратегия «пойти на балет». У жены есть стратегия «пойти на футбол» и «пойти на балет». Таким образом, в этой игре есть четыре возможных профиля стратегий: (Футбол, Футбол), (Футбол, Балет), (Балет, Футбол) и (Балет, Балет). 14 Здесь первая стратегия - это стратегия мужа. Вторая стратегия - стратегия жены. Теперь, когда мы описали множество возможных стратегий игроков, нам нужно определить платежи, которые они получат в каждом возможном профиле игры. Давайте представим, что оба игрока выбрали пойти на футбол. Тогда они проведут вечер вместе. Но при этом муж будет смотреть футбол, ему это нравится, а жена будет смотреть футбол, и это ей не очень нравится. Тогда муж получит платеж, равный пяти, а жена чуть меньший платеж - платеж, равный четырем. Если муж пойдет на футбол, а жена пойдет на балет, то они будут смотреть то, что им интересно, но будут делать это поодиночке. И тогда их платежи будут равны единице. Если муж пойдет на балет, а жена пойдет на футбол, то они и проведут выходной день по отдельности друг от друга, и будут смотреть не очень интересующее их мероприятие. Их платеж в этом случае будет равен нулю. Наконец, если и муж, и жена пойдут на балет, то тогда они снова проведут вечер вместе, но жене будет чуть лучше: она будет смотреть балет, а муж наслаждаться им не будет. Платеж мужа будет равен четырем, а платеж жены будет равен пяти. 15 «Битву полов», как и другие конечные игры в нормальной форме двух лиц, можно представить в виде матрицы. Давайте представим, что мы выписали по горизонтали все стратегии мужа, по вертикали - все возможные стратегии жены, и на пересечении строчки и столбца поставили платежи игроков в том случае, если они играют соответствующие стратегии. Муж играет ту стратегию, которая записана в указанной строчке, а жена играет ту стратегию, которая записана в указанном столбце. Будем первым платежом записывать платеж первого игрока, а вторым платежом - платеж второго игрока. Таким образом, матрица «Битвы полов» будет представлена следующим образом. Например, в профиле (Футбол, Футбол) платежи игроков равны соответственно пять - у мужа и четыре - у жены. Это левая верхняя ячейка в этой матрице. А. Например, если муж пойдет на балет, а жена пойдет на футбол, то платежи игроков будут равны нулю: как платеж мужа, так и платеж жены. Еще один пример одновременного стратегического взаимодействия - это аукцион Викри. На аукцион выставлена очень редкая почтовая марка. Ее хотели бы приобрести многие коллекционеры. Все коллекционеры по-разному оценивают стоимость этой марки. Марка продается по правилам закрытого аукциона второй цены. То есть участники аукциона одновременно подают свои ставки в закрытых 16 конвертах. После этого конверты вскрываются, и победителем становится участник, который предложил максимальную ставку. Покупка этой марки осуществляется по второй максимальной цене. То есть не по самой максимальной, а по той, которая следует за ней. Давайте формализуем этот аукцион в виде игры в нормальной форме. В этой игре есть n игроков - участников аукциона. И ценность марки будем обозначать через v с индексом i. Она больше нуля для каждого из игроков, но может различаться для каждого из них. Давайте пронумеруем этих игроков таким образом, что оценочная стоимость марки для первого игрока - самая высокая. Ее обозначаем через v1. Для второго игрока - чуть ниже. Ее обозначаем через v2. И так далее. У каждого из игроков есть множество возможных стратегий, состоящие из различных ставок, которые он может сделать. 17 Будем обозначать ставку игрока I через b с индексом i. Каждый игрок может выбрать абсолютно любое значение b с индексом i: от нуля до плюс бесконечности. Теперь, чем закончится аукцион? Давайте обозначим через b с чертой с индексом i максимальную из всех ставок игроков, за исключением i-го игрока. В каких случаях i-й игрок выигрывает аукцион? Он выигрывает его, во-первых, в случае, если он поставил больше, чем все остальные участники аукциона, а, во-вторых, в случае, если он поставил столько же, сколько и кто-то еще, но при этом номер игрока i - минимальный среди всех номеров участников, которые поставили такую же цену. 18 Будем считать, что первый игрок имеет небольшое преимущество перед всеми остальными, а именно: если все поставили одинаковую ставку, то первый игрок выиграет эту марку. То есть игрок с меньшим номером будет выигрывать в случае, если игроки поставили одинаковые ставки. Теперь нужно формально определить платежи игроков. Платеж i-го игрока определяется следующим образом. Если участники аукциона сделали ставки (b1, …, bn), то платеж, который получает i-й игрок, соответственно равен либо v с индексом i минус b с чертой с индексом I в случае, если i выиграл аукцион, и 0 в случае, если участник I проиграл этот аукцион. То есть если i-й игрок выиграл аукцион, то он получает разницу между ценностью марки со своей точки зрения и ценой, которую ему пришлось заплатить за эту марку. Если участник проиграл аукцион, то он не получает ничего. Это были игры в нормальной форме, с помощью которых мы будем моделировать одновременные стратегические взаимодействия. 19 3. Формализация последовательных стратегических взаимодействий в виде игр в развернутой форме Теперь давайте коротко поговорим и о втором типе стратегических взаимодействий - о последовательных играх. Их мы будем моделировать с помощью игр в развернутой форме. Давайте рассмотрим пример с экзаменом. Преподаватель проводит экзамен, и один из студентов никак не может решить задачу. У студента есть выбор: попытаться списать решение задачи из тетради или не списывать ее. Преподаватель всегда замечает, что студент списывает. Поэтому преподаватель сталкивается с необходимостью принять стратегическое решение. Если вдруг студент будет списывать, то что делать преподавателю: прогнать его, поставить неудовлетворительную оценку, или же пожалеть и закрыть глаза на это. Если студент не будет списывать, то тогда преподавателю тоже нужно принять стратегическое решение. Он будет видеть, что студент мучается, не может решить задачу, и преподаватель, если захочет, сможет подсказать этому студенту. 20 Платежи игроков формируются в соответствии с их предпочтениями. Студенту очень хочется решить эту задачу, но совсем не хочется быть изгнанным с экзамена с неудовлетворительной оценкой. А преподаватель больше всего хочет соблюсти положенную процедуру проведения экзамена. Таким образом, эту ситуацию можно представить в виде дерева игры. В начальной ситуации ход принадлежит студенту, и студент решает, что делать: списывать или не списывать на экзамене. В каждом из этих случаев ход переходит к преподавателю. В случае, если студент принял решение списывать, преподаватель столкнется с выбором: прогнать студента с неудовлетворительной оценкой или пожалеть его. Если студент не списывает, преподаватель будет решать: подсказать студенту или не подсказывать ему. Это дерево игры. В этом дереве каждой вершине приписано имя игрока, которому принадлежит ход в этой вершине. Разные вершины соответствуют различным состояниям игры. Ребрам, которые выходят из этих вершин, приписаны названия действий, которые могут совершить игроки, которым принадлежит ход в этих вершинах. 21 Наконец, вершины, из которых не исходит ни одного ребра, называются терминальными. И этим вершинам приписаны платежи, которые получают игроки в случае, если игра завершится в этих вершинах. Такое представление последовательного стратегического взаимодействия называется игрой в развернутой форме. Вопрос: Предположим, что студент решил не списывать, а преподаватель решил не подсказывать. Какой платеж получит в этом случае преподаватель? (0, 3, -2, -5) Другой пример последовательного стратегического взаимодействия - это взаимодействие с инспектором ДПС на дороге. Водитель нарушил правила дорожного движения, и теперь его остановил инспектор ДПС, грозится лишением прав. Водитель может попробовать договориться на месте и предложить инспектору взятку. Будем обозначать размер этой взятки через b. Или водитель может не давать взятку и смириться с лишением прав. Таким образом, множество возможных стратегий водителя - это либо не давать взятку, либо дать взятку в размере b. 22 Что может сделать инспектор ДПС? Если ему предложат взятку определенного размера, инспектор должен решить: брать ее или не брать. Заметим, что это решение может зависеть от того, какую взятку ему предложили. Есть один фактор, который сдерживает инспектора от того, чтобы взять взятку. Дело в том, что эту дачу взятки могут обнаружить. Будем считать, что если инспектор берет взятку, то ход делает такой искусственный игрок, которого в теории игр называют Природой. Это не стратегический игрок, который является фактически генератором случайных чисел. С вероятностью p факт дачи взятки обнаруживается. То есть Природа подкидывает монетку, которая с вероятностью p упадет на одно ребро, и с вероятностью 1-p — на другое ребро. И вот, с вероятностью p факт дачи взятки обнаружится, а с оставшейся вероятностью - не обнаружится. 23 Как устроены платежи игроков в этом взаимодействии? Если водитель решает не давать взятку, то он несет издержки в размере c. Эти издержки связаны с лишением прав. Инспектор получает платеж, равный нулю. Если водитель дает взятку, а инспектор от нее отказывается, игроки получают те же самые платежи. Игра заканчивается тем, что водитель получает платеж, равный -c, а инспектор ДПС получает платеж, равный нулю. Если водитель дает взятку, инспектор ее берет, и это не обнаруживается, то тогда водитель платит инспектору взятку в размере b, соответственно платеж водителя будет равен -b. Инспектор получает прибыль в размере b. И это и будут платежи, которые получат игроки в этой игре. Если водитель дает взятку, инспектор ее берет, и это обнаруживается, то тогда водитель лишается сначала той суммы, которую он предложил инспектору в размере b, затем он выплатит штраф, в 30 раз превышающий эту сумму, то есть платеж водителя будет равен -31b. А инспектор сначала получит b, затем заплатит штраф, в 30 раз превышающий размер взятки, -30b, и, наконец, понесет издержки, связанные с лишением работы. После того как факт взятки будет обнаружен, его уволят. Давайте считать, что эти издержки равны его зарплате w. Таким образом, итоговый платеж инспектора в этой ситуации составит -29b-w. 24 Мы нарисовали дерево игры, которое моделирует это последовательное стратегическое взаимодействие. Комментарий: Посмотрим внимательнее на это дерево: Видите дугу? Точки дуги соответствуют различным размерам взятки, которые может выбрать водитель. При каждом возможном размере взятки ход перейдет к инспектору, который будет решать, брать эту взятку или нет. Мы нарисовали в дереве лишь одно поддерево общего вида - аналогичное поддерево исходит из каждой точки дуги. Таким образом, мы с вами договорились, что будем моделировать одновременные стратегические взаимодействия с помощью игр в нормальной форме, а последовательные стратегические взаимодействия будем моделировать с помощью игр в развернутой форме. 25