Уважаемые пользователи Голос!
Сайт доступен в режиме «чтение» до сентября 2020 года. Операции с токенами Golos, Cyber можно проводить, используя альтернативные клиенты или через эксплорер Cyberway. Подробности здесь: https://golos.io/@goloscore/operacii-s-tokenami-golos-cyber-1594822432061
С уважением, команда “Голос”
GOLOS
RU
EN
UA
filinpaul
7 лет назад

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


Двигаюсь дальше. Сегодня мне предстоит сделать восьмой шаг по дороге "Теории игр"  проекта Академия от @ontofractal. Большая часть пути уже пройдена, но впереди по-прежнему - неизвестность и опасности долгой дороги. Доедаю свой бутерброд и стряхиваю крошки в придорожную пыль...


СМЕШАННЫЕ СТРАТЕГИИ: ТЕОРИЯ

Знаете ли вы, как рассчитать ожидаемые выплаты в лотерее, где выигрыш и проигрыш равны и вероятности их возникновения тоже равны? Найти сумму произведений каждой из вероятностей на ожидаемые выплаты. Например, если выигрыш-проигрыш равен 5 золотых, то выплаты будут равны нулю: 0,5*5+0,5*(-5)=0 золотых.

Если с вероятностью 1/2 выигрыш составит 10 золотых, с вероятностью 1/3 - 30 золотых и с вероятностью 1/6 - 1200 золотых, то ожидаемые выплаты, естественно, будут другими: 1/2*10+1/3*30+1/6*1200=5+10+200=215 золотых.

Представленные примеры приводят меня к определению дискретной случайной величины - математическому ожиданию.

Ещё одна лотерея (ну, прямо как на ГОЛОСЕ))). Вероятность выигрыша 2 золотых - 1/2, проигрыша 1 золотого - тоже 1/2. Вычислим математическое ожидание: 1/2*2+1/2*(-1)=1-1/2=1/2 золотых. Есть ли смысл играть в эту лотерею? Вроде бы да, ведь выигрыш больше нуля. На самом деле всё не так просто.

Пусть кому-то предложили сделать выбор: 

1) гарантированно получить 1 миллиард рублей или 

2) с вероятностью 1/2 получить 2 миллиарда 100 миллионов и с вероятностью 1/2 ничего не получить. 

В первом случае математическое ожидание равно 1 миллиарду, а во втором - 1/2*2100000000+1/2*0=1 миллиарду 50 миллионам. Во втором случае ожидание больше, но нормальный человек выберет гарантированный миллиард. Люди не хотят рисковать, вернее не хотят рисковать по-крупному. Например, банки пойдут на риск в отдельно взятой сделке, зная, что возникающий риск будет компенсирован рисками других сделок. Во всех рассматриваемых далее примерах я буду считать, что все игроки нейтральны к риску и поэтому будут стремиться максимизировать математическое ожидание своих выигрышей.

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

А теперь пусть игроки договариваются сыграть в эту игру 100 раз. Тогда в случае постоянного выбора одной и той же стратегии одного из игроков (например, Вася всё время пишет "орёл") , второй быстро догадывается об этом и меняет свою стратегию, чтобы выигрывать (пишет "решка"). Чтобы запутать Петю, Вася берёт игральный кубик и всякий раз перед написание слова подбрасывает его. Если выпадает число от 1 до 4, то он пишет "орёл", а если число 5 или шесть - "решка".

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

Итак, вероятность того, что Петя напишет "орёл" равна вероятности того, что он напишет "решка". Вероятность того, что Вася напишет "орёл" равна 4/6, а вероятность "решки" - 2/6. Каковы же будут вероятности разыгрывания каждого из четырёх возможных профилей?

Вероятность того, что игроки напишут одинаковые слова равна 1/6+1/3=1/6+2/6=3/6=1/2. Вероятность того, что игроки напишут разные слова тоже будет равна 1/2. Их ожидаемые платежи равны друг другу и равны нулю: 1/2*1+1/2*(-1)=0.

Стратегии, которые используют в этом примере Вася и Петя не являются чистыми. Петя смешивает две свои чистые стратегии с весами 1/2 и 1/2, а Вася смешивает чистую стратегию "орёл" с весом 4/6, а чистую стратегию "решка" - с весом 2/6.

Чистая стратегия s1 становится частным случаем смешанной, если а1=1, а а2=а3=...=аn=0. Можно представить себе, что значения а1, а2, ..., аn выдаёт некий генератор случайных чисел и прежде, чем сделать ход, игрок включает его и играет выбранную генератором стратегию.

Теперь я попробую разобраться в главном вопросе - как у Васи и Пети будут распределяться платежи? Начну с обобщения: пусть Вася играет смешанную стратегию, в которой вероятность стратегии "орёл" будет а, а вероятность стратегии "решка" будет 1-а, а Петя играет стратегию "орёл" с вероятностью b, а стратегию "решка" - с вероятностью 1-b.

Какие платежи у Васи? Чтобы ответить на этот вопрос я вероятности, с которыми эта игра может закончится в любом из четырех состояний, умножу на соответствующие платежи, которые получает Вася. И сложу полученные результаты: 

Выше я уже вычислил ожидаемые платежи для выбранного профиля стратегий:

А сможет ли Вася увеличить свой нулевой платёж, уклонившись от выбранной стратегии? Фиксирую стратегию Пети (1/2 - "орёл", 1/2 - "решка") и ищу более выгодную стратегию для Васи. Подсчитаю вероятности, с которыми игра закончится в том или ином профиле стратегий. Затем - вероятности, с которыми игроки напишут одинаковые слова и разные слова. 

Тогда ожидаемый платёж Васи будет снова равен нулю:

Это происходит из-за того, что обе чистые стратегии Васи приносят ему одинаковые платежи в ответ выбранную стратегию Пети:

Совсем другое дело, если я зафиксирую стратегию Васи, и попробую найти более выгодную стратегию для Пети. К примеру, при выборе им чистой стратегии "орёл", он получит платёж, больший нуля:

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


ПОИСК РАВНОВЕСИЙ НЭША В СМЕШАННЫХ СТРАТЕГИЯХ

Зафиксирую смешанную стратегию Васи - аО+(1-а)Р. Если теперь Петя сыграет чистую стратегию "орёл", его выигрыш будет равен:

Если же Петя сыграет чистую стратегию "решка", то его платёж будет равен:

Смешивать свои стратегии Пете выгодно, если эти платежи будут равны, то есть 1-2а=2а-1, откуда а=1/2. Значит Пете будет выгодно смешать свои стратегии только тогда, когда Вася их смешает с вероятностями 1/2 и 1/2. 

Если зафиксировать стратегию Пети, то я получу такую же ситуацию относительно Васи. Отсюда вытекает определение равновесия Нэша в смешанных стратегиях:

В рассмотренной игре есть только одно равновесие - когда игроки смешивают свои стратегии с вероятностями 1/2. А в чистых стратегиях равновесия нет. Вообще в смешанных стратегиях равновесие есть в любой конечной игре в нормальной форме. Это утверждение называется Теоремой Нэша, за которую он и получил Нобелевскую премию.

Согласен, что рассматриваемый материал воспринимается несколько сложно, поэтому предлагаю лучше бросить это гиблое дело и поговорить о чём-нибудь более интересном. Например, о футболе и, в частности, о пенальти. 

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

Попытаюсь найти равновесие Нэша для пенальти.Пусть нападающий бьёт вправо с вероятностью q, а влево - с вероятностью 1-q. Вратарь прыгает вправо с вероятностью р, а влево - с вероятностью 1-р. 

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

Аналогично поступаю и с вратарём:

Из представленных уравнений нахожу значения р=7/12=58% и q=37/60=62%. В реальности по статистике нападающие и вратари поступают следующим образом:

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


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

По матрице платежей игры можно понять, какую стратегию игрок не будет играть. В равновесии не будет играться строго доминируемая стратегия. Например, рассмотрю следующую матрицу игры:

Здесь нет строго доминирующих стратегий, и ни одна из чистых стратегий не доминируется другой чистой стратегией. Но стратегия t3 доминируется смешанной стратегией 1/2t1+1/2t2, а значит t3 точно не будет играться. Исключу её:

И опять нет строго доминирующих и доминируемых чистых стратегий. Но опять чистая стратегия s2 доминируется смешанной стратегией 3/4s1+1/4s3. Значит и s2 можно исключить.

Теперь чистая стратегия t1 доминирует чистую стратегию t2 - вычёркиваем!

А в этой матрице s1 доминируется s3. Остаётся единственный профиль, который является равновесием Нэша в смешанных стратегиях:


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

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

  “Конспект подготовлен для Академии Голоса @academy  

11
51.831 GOLOS
На Golos с February 2017
Комментарии (1)
Сортировать по:
Сначала старые