Разработанный МФТИ курс отличается тем, что все основные конструкции и принципы теории вводятся непосредственно на основе разбираемых "с нуля" конкретных этюдов. Каждый этюд начинается с понятной непрофессионалу проблемы. В одних случаях это просто "детская игра", в других - формализованное жизненное наблюдение, в третьих - обобщённая социальная закономерность. Сюжет затем разворачивается, исходя из логики содержащегося в нём конфликта, и сам порождает тот или иной принцип разрешения конфликта, который окончательно строго формализуется в виде решения игры. Этюдов всего рассмотрено чуть более десяти, и они в совокупности покрывают основные формальные конструкции базовой теории игр. В нескольких отступлениях приведены формулировки теорем существования игровых решений с набросками доказательств.
Игра "Белый Аист": окончание
Loading...
Do curso por Moscow Institute of Physics and Technology
Теория игр
33 classificações
Na lição
Смешанные равновесия
Conheça os instrutores
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
Итак, мы ищем вероятность послать SMS,
которая окажется равновесной, то есть стратегия — послать
вот с такой вероятностью SMS и не послать вот с такой — входит в
симметричное равновесие Нэша в той игре, которая нами рассматривалась, вот.
Значит, давайте посмотрим примерно, что у нас происходит на графике таком,
на котором мы изобразим вот здесь p от 0 до 1,
вот эту вероятность послать SMS — допустим, я верю в то,
что все остальные действуют согласно такой вероятности — и посмотрим, на то,
какая моя стратегия будет при тех или иных значениях p оптимальной.
И, соответственно, заодно мы...
это то, что называется изучение функции реакции, это общий прием для,
значит, поиска равновесия Нэша.
Итак, если — вот это p-ответ — если p очень низка,
предположим, что p очень-очень низка, скажем одна миллионная.
У нас, допустим, вот это вот n,
у нас n + 2 игрока, но вот, скажем, если n, допустим,
равно 1000 — мы потом разберем в цифрах конкретный пример,
— то тогда если будет одна миллионная вероятность у каждого, ну
тогда среди тысячи человек ну, может, одна тысячная какая-то, что один SMS полетит.
Ну, скорее всего, вообще ни один не полетит, и уж точно, что двух не будет,
это уж почти гарантировано.
Поэтому если так, то моя правильная реакция — это слать SMS,
быть тем самым одним из двух, попытаться по крайней мере стать.
То есть в этом случае я пишу единицу.
Если же вероятность сколько-нибудь отлична от нуля,
ну например, вероятность равна 20 % или 10 %, сколько их там?
Тысяча человек.
Если каждый из них посылает SMS с вероятностью 10 %,
то ясно, что их там будет десятки, сотни.
Поэтому ясно, что мне никакого смысла посылать SMS нет,
я ничего не выиграю, только деньги на SMS потрачу, поэтому здесь ответ — 0.
Ну и вот в некотором конкретном месте, которое мы ищем,
происходит перескок, потому что стратегия «послать SMS» и
стратегия «не послать SMS» дают одинаковый выигрыш,
и тем самым любая смешанная стратегия мне годится, в том числе и такая.
И в частности вот такая стратегия становится частью симметричного смешанного
равновесия.
Итак, ищем p,
при котором выигрыш от «послать SMS» будет такой же, как выигрыш от «не послать SMS».
Что такое выигрыш от «не послать SMS»?
0.
Как известно, не стучащим не открывают.
Не посылает, значит не посылает, выигрыш равен 0.
Если я посылаю SMS, то я сразу трачу 1, но с некоторой вероятностью,
которую мы сейчас будем высчитывать — это не вероятность p, конечно, нет.
С некоторой вероятностью я выиграю приз, получу бутылку
коньяка «Белый аист», и она для меня оценивается в N.
И то p, при котором наступает
равенство — это и есть искомое p, потому что q зависит от p.
Вероятность получить приз — этот q, а q — это функция от p.
Значит, осталось найти функцию от p, потому что в результате мы получаем,
что уравнение на p — это просто что q(p) должно быть = 1 / n,
вот и все, где n — стоимость приза, считаем, что она мне вполне известна,
стоимость этой бутылки коньяка в моих терминах моего выигрыша,
она для меня понятна.
И в симметричность игры вкладывается условие,
что эта стоимость тоже одинакова для всех.
Не то, что есть какие-нибудь абстиненты полные или, наоборот,
страшные любители коньяка — тогда игра уже не симметрична.
В симметричной игре для всех одинаковая стоимость, вот она прописана, она равна N.
Осталось посчитать q(p), это задача по теории вероятностей.
Смотрите, если каждый посылает SMS с вероятностью p,
то какая вероятность, что я со своим SMS выиграю приз?
Какие события приводят к выигрышу приза?
Первое событие — это что никто не послал, то есть реализация каждого
из таких случайных, каждой из таких случайных величин привела к 0.
Ну это понятно происходит, вот это происходит с вероятностью 1 / p,
это тоже с вероятностью 1 / p и так далее,
то есть независимые испытания в количестве n + 1 штуки — все, кроме меня.
И соответственно, у нас вероятность события, что никто не послал
SMS из оставшихся людей при условии,
что они используют одну и ту же стратегию p, она равна 1 − p в степени (n + 1).
Но это еще не все, потому что бутылки все-таки две.
И мне годится любая из реализаций, в которой есть ровно одна единичка.
Если у меня все нули и одна единичка, любая из таких реализаций мне годится.
Это значит, что здесь должна выпасть вероятность p,
а во всех остальных местах 1 − p.
И таких реализаций ровно n + 1, правильно?
Переходим на ту сторону и продолжаем.
Итого, q(p), то есть вероятность того,
что я выиграю приз — это сумма вот такой
величины и n +
1 вот такой.
Это можно немножко преобразовать, у меня получится (1 − p) в n-ной — за скобку,
скобка открывается, и в ней написано: 1 − p — это отсюда,
+ (n + 1) штука p.
Минус тут уходит, и остается такое выражение: (1 −
p) в степени n * (1 + pn).
И условие на равновесие по Нэшу — это что?
Это штука равна 1 / N.
Значит, это
уравнение — страшное довольно уравнение, его,
конечно, так просто не решить.
Но давайте его решим приблизительно.
Для этого поймем, что равновесное p — это очень-очень маленькая величина,
это понятно из этой картинки, что эта величина очень мала.
Ну и как бы если мы угадаем порядок ее малости, поступим как физики,
то есть напишем, что...
напишем, что β, которую мы будем вместо p искать — это примерно p n раз.
То есть давайте попробуем угадать, что вероятность p,
она примерно пропорциональна 1 разделить на количество людей, и посмотрим,
чему тогда равен этот коэффициент пропорциональности приблизительно.
Тогда смотрите, что у меня получится: (1 − β / n) в n-ной
степени * (1 + β) = 1 / N.
Надеюсь, что студенты математических специальностей знают,
чему это равно с очень большой точностью при n, равном количеству тех,
кто смотрит какую-нибудь телепрограмму, ну по крайней мере вот, например, при тысяче.
В общем, понятно, что это e в степени −β.
Поэтому мы перекидываем N налево, это направо, и получаем такое вот
приближенное трансцендентное уравнение N(1 + β) = e в степени β.
И должны найти β, ну, при том или ином N.
Ну я предлагаю при N = 1000 его примерно прикинуть.
Если N = 1000, получается такое уравнение: 1000 * (1 + β) = e в степени β.
Это...
извините, не из той точки, из точки 1.
Вот это график вот этой функции, соответственно,
это график вот этой функции, ну и там где-то нужно найти вот точку пересечения,
только тут, значит, из точки 1000, извините, стартует оно.
Экспонента стартует здесь, в какой-то момент экспонента догоняет, естественно,
линейную.
Ну в общем, e³ — это примерно 20, поэтому
если взять и просто наобум поставить β = 9, получится здесь справа 8000.
А здесь 10 000, то есть ясно, что это очень близко мы угадали, и в общем,
грубо говоря, примерно равно 9 или 10.
Ответ приблизительно такой,
и тем самым ответ для вероятности — что он примерно 1 %,
то есть равновесная вероятность — 1 %.
Каждый должен примерно в 1 из 100 случаев посылать SMS,
и примерно в 1 из 100 — не посылать.
В этом случае, при стоимости бутылки, равной 1000,
мне тоже все равно, посылать или нет.
То есть если я пошлю, то я уповаю на очень маленький шанс,
примерно равный одной тысячной, что таки никто не пошлет,
и тогда эта тысяча компенсирует этот шанс в одну тысячную.
Ну если я не посылаю, я просто получаю 0.
Что здесь важно?
То же, что в «дилемме заключенного».
Важно то, что в этом равновесии вероятность того,
что будет послано 0, 1 или 2 SMS — вероятность этого
события исчезающе мала, это тоже где-то в районе 1 % или даже меньше.
То есть, объявляя такую телеигру, телеведущий ничем не рискует — две
бутылки коньяка с вероятностью очень близкой к 100 % останутся у них.
Поэтому если люди играют здесь в симметричное равновесие,
им ничего не светит.
А вот если они скоординируются и решат, что какие-то Маша и Ваня сразу же,
вот именно они, будут посылать SMS, вот тогда другое дело,
то есть тогда они сыграют другое равновесие Нэша, не симметричное,
в чистых стратегиях, и тогда телеведущие останутся без бутылки.
Я проводил эксперимент в Пущинской школе.
В Зимней Пущинской школе в марте какого-то года я провел такой эксперимент:
я взял коробку конфет, раздал школьникам — полный зал школьников сидел, —
и показал две шоколадки, большие и вкусные шоколадки, конфетки маленькие-маленькие.
Каждому раздал по конфетке и сказал: я сейчас с пройду с коробкой,
мои ассистенты пройдут с коробкой, и каждый может ну как бы сделать вид,
что кладет конфету, а вот положить или нет — это уже как бы его личный выбор.
И если конфет...
да, и конфета как бы, конфета помеченная, ну вот человек вот если положил,
там написано чья.
И если конфет окажется одна или две, то обладатели,
счастливые обладатели этих конфет получат по огромной шоколадке.
Конфет было 7 или 8, так что никто ничего не получил, шоколадки остались при мне,
и игра блестяще подтвердилась, прогноз в этой игре блестяще подтвердился.
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
