Академия. Теория игр. Неделя 2.

Итак, продолжаем изучать курс "Теория игр" (ВШЭ) в рамках проекта  Вторая академия от @ontofractal .

Мы уже знакомы с терминологией, видами стратегических взаимодействий и знаем, как можно построить формальные игровые модели для реальных жизненных ситуаций. Сегодня нам предстоит научиться "решать" игры.

РЕШЕНИЕ ИГР

Согласитесь - не совсем привычное словосочетание. Обычно нам приходится решать проблемы. Но игра  - это тоже некая проблема, поэтому всё нормально )) Что мы будем понимать под решением игры?

Это такой профиль стратегий, который будет сыгран участниками игры с наибольшей вероятностью.

Рассмотрим это понятие на конкретном примере одновременного стратегического взаимодействия. Пусть у двух игроков, делающих одновременный выбор, есть в наличии по две стратегии. Для определённости назовём первого игрока Таней (её стратегии обозначим через а1 и а2), а второго - Вовой (его стратегии - b1 и b2). Какую стратегию должна выбрать Таня? Возможны варианты: если Вова играет стратегию b1, то Таня из двух своих стратегий выберет ту, которая в этом случае гарантирует ей наибольший платёж. Например, это стратегия а1. Этот выбор Тани мы будем обозначать термином Best Responce («наилучший ответ») или функцией BR, где аргументом будет выбранная стратегия Вовы, а значением - стратегия Тани, то есть: 

BR(b1)=а1.

Однако, на самом деле Таня не знает, какую же стратегию будет играть Вова. Поэтому, чтобы понять, что сыграет Таня, нам нужны ещё какие-то предположения о её поведении. Иными словами нам нужна теоретико-игровая концепция. В зависимости от предположений, находящихся в рамках этой концепции, мы будем получать разные решения или разные стратегии поведения Тани.

Сегодня мы рассмотрим только две концепции:

-  равновесие в доминирующих стратегиях ,

-  исключение доминируемых стратегий. 

РАВНОВЕСИЕ В ДОМИНИРУЮЩИХ СТРАТЕГИЯХ

Для начала разберёмся в терминологии. Рассмотрим матричную модель игры, в которой участвуют два игрока. У первого есть набор возможных стратегий а1, а2, у второго - b1, b2, b3, b4. Также известны все возможные платежи, которые получат игроки в результате игры.

К примеру, если первый игрок выбирает стратегию а1, а второй стратегию b4, то платёж первого будет 5, а платёж второго будет 6.

Какую стратегию выбрать первому игроку? Если второй играет стратегию b1, то первому выгодно играть а1, поскольку в этом случае его платёж равен 2. В этом случае стратегия а1 - будет "наилучшим ответом" первого игрока на стратегию b1 второго игрока: 

BR1(b1)=а1.

Пометим наилучший ответ точкой:

Аналогично проанализируем матрицу до конца, перебирая все возможные стратегии второго игрока и выбирая "наилучший ответ" первого. Все "наилучшие ответы" также пометим точками:

Получается, что при любом выборе второго игрока, наилучшей стратегией первого будет всегда а1:

BR1(b1)=а1, 

BR1(b2)=а1, 

BR1(b3)=а1, 

BR1(b4)=а1.

Такие стратегии в теории игр получили название доминирующих (в данном курсе доминирующая и строго доминирующая стратегии являются синонимами).

У второго игрока тоже есть доминирующая стратегия. Какую бы стратегию не сыграл первый игрок, второму выгодно будет играть стратегию b1, так как в этом случае его платежи будут наибольшими:

BR2(а1)=b1,

BR2(a2)=b1.

То есть доминирующая стратегия первого игрока - а1, доминирующая стратегия второго игрока - b1.

Далее нам придётся немного поднапрячься, поскольку я попытаюсь дать формальное определение строго доминирующей стратегии. Пусть есть n игроков, и у каждого есть своя стратегия: s1, s2, ..., sn. Выберем наугад любого игрока и присвоим ему номер i, то есть его стратегия - si. Тогда множество всех стратегий, кроме стратегии игрока i обозначим через s-i (все, кроме i):

s-i=(s1, s2, ..., si-1, si+1, ..., sn) - видно, что элемент si из списка выброшен.

Если вернуться к рассматриваемому примеру, и стратегию первого игрока обозначить s1, а второго  - s2, то для любого конкретного профиля стратегий (s1, s2) стратегию s1 можно обозначить как s-2, а все стратегии первого игрока - как S-2:

S-2={а1, а2}.

Тогда определение строго доминирующей стратегии будет выглядеть следующим образом:

На первый взгляд выглядит пугающе, но давайте разберёмся. Под ui подразумевается платёж от конкретного профиля выбранных стратегий. Тогда платёж от профиля, в который входит доминирующая стратегия i-го игрока и любой набор стратегий других игроков, должен быть строго больше платежа от профиля, содержащего любую другую стратегию i-го игрока и тот же набор стратегий других игроков.

Существует похожее определение для слабо доминирующей стратегии:

Отличие, как видите, только в знаке сравнения: "строго больше" заменено на "больше или равно". Неравенство стало нестрогим.

Например, если в рассматриваемой матрице игры мы заменим в профиле стратегий (а1, b2) цифру 2 на цифру 7, то в этом случае BR2(a1)=b1 и BR2(а1)=b2, и стратегия b1 перестанет быть строго доминирующей.

Теперь стратегия b1 стала слабо доминирующей, поскольку при её выборе второй игрок играет не хуже, чем при выборе любой другой из своих стратегий.

Можно сказать, что любая строго доминирующая стратегия так же является и слабо доминирующей.

И вот мы подобрались к определению самой концепции:

Иными словами: профиль состоит из строго доминирующих стратегий всех игроков. В нашем исходном примере как раз и наблюдается такое равновесие, так как профиль (а1, b1) состоит из строго доминирующих стратегий. А в исправленном примере этот же профиль уже не является равновесием.

Аналогично даётся и определение равновесия в слабо доминирующих стратегиях:

Тогда профиль (а1, b1) будет равновесием в слабо доминирующих стратегиях и в исходном примере, и в исправленном.

Для чего нам нужно знать: играют ли игроки слабо доминирующие или строго доминирующие стратегии? Потому что, если у каждого игрока будет доминирующая стратегия, то решением игры будет равновесие, поскольку все, конечно же, сыграют именно доминирующие стратегии.

Но, как правило, "наилучший ответ" каждого игрока зависит от того, какую стратегию выбрал другой игрок, и тогда у них вообще может не быть доминирующих стратегий. Как решать игру в этой непростой ситуации?

ДИЛЕММА ЗАКЛЮЧЁННОГО 

Чтобы лучше понять, что такое доминирующая стратегия и как её использовать, рассмотрим одну из самых известных в теории игр под названием "Дилемма заключённого", описанную ещё в 1950 году американскими математиками  Мерилом Фладом и Мелвином Дрешером.

Полиция поймала двух преступников, ограбивших банк. Улик, доказывающих факт преступления у полиции нет. Подозреваемым можно предъявить в качестве обвинения только разбитое окно банка. В этом случае каждый получит год тюрьмы за хулиганство. Тогда полицейские разводят преступников в разные комнаты и предлагает каждому сдать напарника на условии смягчения приговора ему самому. Перед каждым из преступников возникает выбор. Если он молчит и молчит его напарник, то они получают по 1 году. Если он сдаёт напарника, то того сажают на 10 лет, а его самого отпускают на свободу. И если они оба сдают друг друга, то каждый получает по 5 лет. Построим матрицу игры:

Из неё видно, что у каждого из "игроков" есть доминирующая стратегия - "предать", поэтому равновесием будет профиль ("предать", "предать").

Здесь, чтобы лучше разобраться в профилях стратегий этой игры, нам понадобятся ещё два определения. Первое:

То есть профиль стратегий s парето-доминирует профиль стратегий s', если одновременно выполняются два условия:

1) платежи, которые получают игроки в профиле s не меньше платежей, которые получают игроки в профиле sʼ, 

2) хотя бы для одного игрока платеж, который он получает в профиле s, больше платежа, который он получает в профиле sʼ. 

И второе определение:

Вернёмся к дилемме. Профиль ("предать", "предать") не будет парето-оптимальным, поскольку есть профиль ("молчать", "молчать"), в котором платежи игроков больше. Он парето-доминирует профиль равновесия. Возникает странная ситуация, каждый игрок выбирает доминирующую стратегию, но получающийся профиль стратегий не является парето-оптимальным. Преступникам выгоднее молчать и получить по году тюрьмы. Но это ещё не всё. Профиль ("молчать", "предать") тоже парето-оптимальный, поскольку именно в нём второй игрок получает максимальный платёж - 0. Аналогично и профиль ("предать", "молчать") опять же парето-оптимальный. То есть все профили, за исключением равновесия, парето-оптимальны! Получается, что с точки зрения общественного благосостояния равновесие ничего не значит. Платежи, получаемые в нём, могут оказаться не наибольшими.

ОЛИГОПОЛИСТИЧЕСКАЯ КОНКУРЕНЦИЯ

Возможно, что история с преступниками кому-то показалась слишком надуманной и нереальной. Тогда специально для вас, ещё один пример, демонстрирующий, что наличие у игроков доминирующих стратегий не даёт им на самом деле максимальных платежей.

Есть две фирмы, продающие товар по одной цене. И вот независимо друг от друга и одновременно они задумываются о том, чтобы поднять цену на товар. Если они обе повышают, выставляя опять одну и ту же цену, то каждая получает прибыль +1000. Если одна повышает, а другая нет - то первая терпит убытки -200, а вторая получает прибыль +1400. И если они отказываются от этой затеи, то их платежи будут равны нулю. Построим матрицу игры:

Видно, что у каждой из фирм есть доминирующая стратегия - "не повышать". Однако, максимальная прибыль будет получена в случае профиля стратегий ("повышать", "повышать") с одинаковым ростом цены. То есть фирмы скорее всего вступят в сговор. Вот чтобы этого не было, в государстве должна проводиться антимонопольная политика, пресекающая ситуации, когда на каком-то рынке товаров присутствует небольшое количество производителей. Ведь тогда они смогут вести нечестную игру и извлекать сверхприбыли за счёт покупателей. Такие преступные рынки и называются олигополистическими.

РАВНОВЕСИЕ, ПОЛУЧАЕМОЕ ИСКЛЮЧЕНИЕМ ДОМИНИРУЕМЫХ СТРАТЕГИЙ

Перейдём к изучению второй теоретико-игровой концепции решения игр. 

Рассмотрим матрицу некоторой игры:

Проанализируем её. Выгодно ли второму игроку использовать стратегию b1? "Нет", если первый играет а1, поскольку стратегия b3 даст ему больший платёж, и "да", если первый играет а2. Выгодно ли ему играть стратегию b3? "Да", если первый играет а1, и "нет", если первый играет а2, поскольку в этом случае больший платёж принесёт стратегия b1. То есть ни b1, ни b3 не являются оптимальными стратегиями. Теперь рассмотрим стратегию b2. Она даёт ответ "нет" при любом раскладе. Более того, стратегия b3 всегда гарантирует лучшие платежи по сравнению с b2. Говорят, что b3 строго доминирует b2, говоря проще - она выгоднее, лучше.

С другой стороны:

Аналогичные определения формулируются и для слабого доминирования:

Опять же отличия только в замене строгих неравенств на нестрогие.

Вернёмся к матрице игры:

Стратегия а2 слабо доминирует стратегию а1, поскольку при любых стратегиях второго игрока, первый с а2 получает не меньшие платежи, чем с а1. Соответственно а1 слабо доминируется стратегией а2.

Стратегия b3 строго доминирует стратегию b2, поскольку при любых стратегиях первого игрока, второй с b3 получает большие платежи, чем с b2. Соответственно b2 строго доминируется стратегией b3.

И ещё пара определений:

Тогда в рассматриваемом примере стратегия а1 - слабо доминируемая стратегия первого игрока, а b2 - строго доминируемая стратегия второго игрока, то есть они менее предпочтительны чем остальные возможные стратегии играющих. Путём исключения этих слабых стратегий мы может придти к решению игры.

Поскольку второй игрок понимает, что его стратегия b2 - строго доминируемая, он её играть не будет. Исключим b2 из матрицы игры:

Теперь стратегия а1 первого игрока из слабо доминируемой стала строго доминируемой, и он так же не будет её играть. Исключим а1 из матрицы игры:

Можно заметить, что и в этом достаточно усечённом варианте исходной матрицы есть возможность убрать ещё одну стратегию - b3, так как она строго доминируема стратегией b1, и второй игрок не станет её играть:

Оставшийся единственным профиль стратегий (а2, b1) и называется равновесием, полученным путём исключения строго доминируемых стратегий.

Причём не важно, в каком порядке исключались доминируемые стратегии - мы по любому придём к матрице размера 1х1. Но, если мы будем исключать слабо доминируемые стратегии, то решение теряет однозначность, поскольку в зависимости от порядка исключения мы будем получать различные ответы.

К сожалению, и эта концепция не является универсальной, поскольку есть игры, в которых путём исключения строго доминируемых стратегий мы не придём к нужному равновесию.

СВЯЗЬ МЕЖДУ КОНЦЕПЦИЯМИ

Если в игре есть равновесие в строго доминирующих стратегиях, то у каждого из игроков есть строго доминирующая стратегия, и, значит, все остальные его стратегии - строго доминируемые. То есть путём исключения слабых стратегий мы придём к матрице 1х1 или к равновесию, полученному путём исключения доминируемых стратегий.

Если в игре есть равновесие первого типа, то есть и равновесие второго типа. Очевидно, что обратное утверждение неверно.

Поэтому, с одной стороны, равновесие, получаемое путём исключения строго доминируемых стратегий, позволяет нам решать более широкий класс игр, с другой - полученные решения будут проигрывать в силе своих свойств решениям, полученным с помощью равновесия в строго доминирующих стратегиях.

Итак, мы рассмотрели две концепции, которые могут привести к решению некоторых игр: 

ЧТО ДЛЯ МЕНЯ БЫЛО НАИБОЛЕЕ ИНТЕРЕСНЫМ ИЗ ЭТОЙ НЕДЕЛИ КУРСА

Стратегии, используемые в игре, можно строго классифицировать, и в зависимости от того или иного типа присутствующих стратегий игрок может использовать ту или иную концепцию решения игры. У каждой их рассмотренных концепция есть свои преимущества и недостатки. К сожалению, не всякую игру можно решить, используя изученные концепции.