Сергей Ивановский. Всем добрый день! Продолжаем научную тематику. В гостях у нас Алексей Савватеев. Алексей, привет.
Алексей Савватеев. Привет. Привет снова.
Сергей Ивановский. Более подробно поговорим о теории игр.
Алексей Савватеев. Я хочу сказать, что теория игр, она всюду вокруг нас. Куда ни глянь. Если ты выходишь из дома, ты можешь, в принципе, сесть за руль, а можешь не садиться за руль. Решение, которое ты принимаешь, зависит от чего?
Сергей Ивановский. Раз теория игр связана, каким-то образом, с системой человеческих отношений, предсказание поведения в той или иной степени, то, значит, зависит от моего собственного решения и предсказания того, что я подумаю.
Алексей Савватеев. Предсказания того, что сделают другие. Представь, что гномик пришел и сказал: “Серега, сегодня никто не сядет за руль, они испугались плохой погоды”. Ты “фигачишь” по пустому Невскому проспекту. Проливной дождь или мокрый снег, но это неважно, если ты один, то тебя это не остановит.
Сергей Ивановский. То есть, теория игр связана с предсказанием поведения других. И моих действий относительно этого.
Алексей Савватеев. Да. Если ты знаешь как действуют другие... Если ты почему-то уверен, что они будут действовать тем или иным способом, то твое поведение какое? В теории игр есть такой постулат, что в этом случае ты ведешь себя, оптимизируя свой собственный выигрыш от взаимодействия. Это тонкий постулат, довольно сомнительный в моральном смысле. Если твой выигрыш означает большие беды для других, то далеко не каждый человек будет готов на этот выигрыш. Поэтому в теории игр есть много разных оговорок. Но в случае с пробками на дорогах очень все просто. Классическая модель работает превосходно. Все, что ты делаешь, это ты минимизируешь время нахождения в пути. Нормальный человек делает именно это. При этом ты напрямую никого этим не задеваешь. Что упускается при этом из виду? Вот ты думаешь поехать или нет. Если ты знаешь, что никто не поедет кроме тебя, ты поедешь в любую погоду. А, может, гномиком был Яндекс, который ты открыл, там все красное везде. Ты принял решение в соответствии с тем, как ты оцениваешь дорожную ситуацию. В случае, когда красное все, ты мог бы думать немножко по-другому. А как? “Все красное. Но не я же один вижу, что все красное. Все, кто со мной выезжают они видят, что все красное. Я рискну, они-то все не поедут, а я поеду. Когда эти пробки рассосутся, следующих не будет потому, что они все испугались”.
Сергей Ивановский. Как вариант. Он может быть. Частенько мы можем сталкиваться с тем, что Яндекс показывает в выходной день что-то красное, а ты едешь спокойно.
Алексей Савватеев. Ты еще должен подумать, что остальные подумали про других, какие они приняли решения. И перепрыгнуть через это. Как-то у меня была беседа с таксистом. Он жаловался. Он говорит: “Как только я вижу, что в этом районе утроенный коэффициент, я туда сразу еду. И в Яндексе сразу коэффициент понижают. Они за мной гоняются”. Говорю: “Успокойся и подумай. Представь, что в некоторой области показываются коэффициенты на три и на четыре. Что делает таксист, такой же как ты, в другом месте? Он туда едет”. Можно про это подумать? Одну секунду подумать и не ехать в этот район. Или проигнорировать эту информацию, подождать. Идея следующая. Теория игр, это не только просчет действий остальных, это еще и динамика. Динамики мы еще ни разу не касались. Это что завтра произойдет. Это интересный раздел теории игр. Называется “Динамическая теория игр“. Приведу примеры. Пример номер один. Мы с женой и с младшими детьми отдыхаем в Крыму. Взяли обед в Гурзуфе. Окна открыты, октябрь, жара. Котлету не доели. Положили котлету на подоконник, чтобы ее съели чайки. Подлетает чайка, следом за ней вторая, ей клювом в бок. Она начинают драться. Тут третья чайка хвать котлету и была такова. Я тут же вспомнил одну важную модель. Называется дуэль трех лиц. Она имеет лейтмотивное повторение и в истории человечества, и в нашей повседневной жизни. Это если есть три вояки, которые друг с другом воюют. Скорее всего победит слабейший. Первый раз эта модель появилась в 1945 году. Ее писали в Америке. Имелся в виду такой сценарий, что Гитлер со Сталиным друг друга “мочили”, а Америка поднималась на этом фоне, приняв лишь не очень глубокое участие в войне. Может быть, в экономическом смысле нам помогали, но жертвы американцев и русских сравнивать, это было бы кощунство. На самом деле было еще раньше. Мне было бы интересно спросить у историков. Я спросил у московских историков, они подтвердили. Керенский, Корнилов, Ленин. Керенский с Корниловым были вовлечены в конфликтное самоуничтожающее взаимодействие. И на этой волне смог вылезти Ленин, который в октябре заполучил власть. Я не настаиваю на этой интерпретации.
Сергей Ивановский. Можно посмотреть ролики с Егором. Он про это много рассказывает. Из того, что я помню, это задача достаточно многофакторная.
Алексей Савватеев. В принципе такая модель есть. В наше время была такая ситуация. Иркутск, 2010 год, выборы. Как у нас положено выборы проводить? Есть главный кандидат и тот, которого замордуют. Главный кандидат от одной партии. А второй, он от партии, которая должна красиво проиграть на выборах. Прекрасно. Но все идет не так. Я точно не помню фамилию у главного кандидата. Вдруг появляется кандидат Романов и говорит: “Это не он, а я представитель Путина на этой территории. Я тоже из той партии”. Тот был так удивлен. Эта вся битва была между Романовым и Серебряковым. В результате прошел третий, Кондрашов, с очень большим отрывом.
Сергей Ивановский. Теория игр в действии.
Алексей Савватеев. Потом была похожая история с Леброном Джеймсом, баскетболистом. Я не очень знаю баскетбол, я скорее слежу за футболом. Но была такая ситуация. Между двумя клубами была жесточайшая борьба, и Леброн Джеймс ушел в третий клуб. Историки баскетбола меня поправят. Суть в том, что это лейтмотивная история, в дуэли трех лиц побеждает слабейший. И это совершенно четко математически может быть сформулировано. Есть несколько вариантов. Один вариант, это одновременная игра, один – последовательная. Что на самом деле происходит? Модель, 1946 год, сразу после войны она сформулирована как задача. Есть три стрелка, они вышли... Вершины равностороннего треугольника. И каждый, когда наступает очередь стрелять, выбирает себе мишень. Вот этот бьет с вероятностью 0,5, то есть, 50 процентов. Этот с вероятностью 0,8. А этот с вероятностью 1, 100 процентов выбивает. И нужно предсказать какие шансы на выживание у этих трех. Если игра начинается отсюда. Если кто-то остался жив, очередность сохраняется. По сколько угодно выстрелов, в свой ход только один. Строго по очереди дуэль. Дальше. Если кто-то убит, то второй стреляет в этого. Дальше дуэль двух лиц идет.
Сергей Ивановский. И первый выстрел начинается со слабого?
Алексей Савватеев. Предлагается начать со слабого и сказать какие будут тогда шансы. На самом деле, когда мы будем решать задачу, начиная со слабого, нам все равно придется в уме решать ее и в такой, и в такой ситуации. “А” думает, что ему делать, он прикидывает свои шансы. Если он промахнется, наступит такая вот дуэль. Если “В” промахнется, наступит такая дуэль. Чтобы предсказать, что будет делать “А” здесь, нам нужно четко понимать, что делал бы “В” здесь, если бы был его ход. Это еще одно свойство теории игр. В теории игр всегда надо предсказывать действия игроков, даже если им не представится ход. Я предсказываю, что этот человек этому человеку не даст кредит. Ты судья этой ситуации, говоришь: “Почему ты так предсказываешь?” Говорю: “Я так предсказываю потому, что если представить, что даст, смотри какие у того стимулы. Он его “кинет”, можно доказать математически. Вот его стимулы”. Но тогда тот ему не будет давать кредит. Игра пойдет в другую сторону, он даст кому-то еще кредит. И вроде бы тот, кому могли дать кредит, он вне игры. Но чтобы объяснить, почему я решил, что этот человек не будет давать ему кредит, мне придется объяснять через его поведение в том случае, если бы ему кредит дали.
Сергей Ивановский. Сразу вопрос. Если у нас “С” бьет сто из ста, получается...
Алексей Савватеев. Ответь сам, что в этой ситуации “С” делает?
Сергей Ивановский. Он сразу убивает соседа.
Алексей Савватеев. Какого?
Сергей Ивановский. Слабого.
Алексей Савватеев. Если он убивает слабого, у него шанс выжить 0,2. Красота ситуации в том, что каждый имеет выбор. Он убивает “В”. Если он убивает “В”, у него шанс выжить 50 на 50. Потому, что если “А” промахнулся, “А” – труп. А если он убивает “А”, у него шансы 20 на 80. Поэтому мы совершенно точно можем сказать, что если ход дошел до “С”, то он сюда. Поэтому в этой ситуации шансы у “В” равны тождественному астрономическому нулю. А у этих двух по 50 процентов. Но в этом случае мы можем совершенно точно сказать в кого будет стрелять “В”. Он, в принципе, может стрелять и в “А”, и в “С”.
Сергей Ивановский. Он будет в более сильного стрелять.
Алексей Савватеев. Обязательно. Потому, что если он не будет стрелять в более сильного, его шанс на выживание равен стопроцентному нулю, не зависимо от того, попадет он в “А” или нет. Если он попал, они остаются вдвоем, “С” его сразу убил. Если не попал, они остались втроем, но мы знаем, что “С” его убивает сразу же. Если “С” остается жив после выстрела “В”, то “В” труп. И он это знает. Значит, он единственное, что может сделать, попытаться убить “С”. Если он убьет “С”, это довольно большая вероятность, начнется дуэль между “А” и “В”. Дуэли... Чистая теория вероятности, какие вероятности выжить в дуэлях. Пусть у меня “А” стреляет с вероятностью “p”, а “В” с вероятностью “q”. Решим задачу в общем виде. Какие шансы на выживание в этой дуэли. “p” плюс “q” не равно единице. Но даже если мы поделим на “p” плюс “q”, этот ответ будет неверный. Ответ более сложный, давай его попробуем найти. Давай обозначим за “х” шанс остаться в живых для “А”. Тогда для “В” он равен один минус “х”. И мне нужно найти “х” как функцию от “p” и “q”. Прекрасно. Вот я “А” стреляю в “В” и, в принципе, могу попасть. Если я попал, это происходит с вероятностью “p”, я получил... Будем считать, что выжить, это “1”, умереть, это “0”. Если не попал, то открывается новая скобка. Потому, что дальше ситуация зависит от того, попал ли “В”, когда он начнет стрелять. Если “В” попал, то каковы мои шансы? Я труп. А если “В” не попал... Тут надо дать правильный ответ каковы мои шансы. Если “В” не попал, то ход снова перешел ко мне. И мы обозначили вероятность выживания в этом случае за “х”. И это все тоже равно “х”. Вероятность выжить для “А”, равная “х”, должна быть в то же время равна вероятности, что “А” сразу попадет, и тогда выиграет, плюс вероятности того, что “А” и “В” промахнутся, умноженной на ту самую вероятность, которую мы считаем. Получилось уравнение с одним неизвестным. Получается, что “p” плюс “1 - p” на “1 - q”, на “х”, равно “х”. Откуда “х” равно “p” делить на один, минус “p” с чертой, “q” с чертой. Где я за “p” с чертой обозначил “1 - p”, а за “q” с чертой “1 - q”. Ну, и давай подставим это сюда. При 0,5 и 0,8. Единственная нетривиальная дуэль, которая здесь есть. Если “В”-“С” дуэль, то 0,8 против 0,2. Если “А”-“С” дуэль, то 0,5 против 0,5. Вероятность для “А” выжить в дуэли с “В” равна вероятности попадания “А” делить на 1 минус “1 - p” на “1 - q”. “1 - p” это 0,5. “1 - q” это 0,2. Если “А” начинает дуэль 0,5 против 0,8, то вероятность выжить пять девятых. А у “В” вероятность выжить четыре девятых.
Дальше у этой задачи была очень длинная и интересная история. “А” в кого должен стрелять, в “В” или в “С”? Если посчитать, то получается, что лучше в “С”. Если он убьет “С”, ему предстоит дуэль с “В”. В которой он, в принципе может выиграть. Вероятность одна девятая, но все-таки больше нуля. Когда мы высчитаем его шансы его выживания, когда он пытается стрелять в “С”, получается, они не очень большие, в районе одной трети. Потому, что у него есть 50 процентов, что он убьет “С”. И если он убьет “С”, “В” будет пытаться его убить. Шансов выжить очень мало. Возникает вопрос: “Зачем ему вообще в кого-то стрелять, если что то, что это плохо?” Он лучше в воздух стрельнет. Тогда ход перейдет к “В”, а про “В” и “С” мы уже знаем. Когда мы посчитаем, вероятность вместо одной трети появляется сорок девять девяностых. То есть, больше половины. Получается, что если правильно прикинуть дуэль трех лиц, с возможностью стрелять в воздух, то вероятность выживания слабейшего, который начинает, больше чем половина при данных цифрах. И она связана с ходом отказа от борьбы. Сидеть тихо, смирно, ни на кого не нападать.
Сергей Ивановский. Выстрелить в воздух, это равносильно тому, что специально промахнуться.
Алексей Савватеев. Да. Так вышло. Но эта статья подверглась критике, что неправильно посчитали вероятность. А потом вышла еще одна статья. Называется “Тройное дно тройной дуэли”. Это уже 1990-е годы. В ней говорилось, что мы вообще не понимаем, что там будет происходить. Потому, что “В” тоже может промахиваться. И “С” может промахиваться. Если цифры не 0,5, 0,8, 1, а, скажем, 0,8, 0,9, 1. Тогда у каждого есть отличный стимул отсидеться в сторонке. Если у нас такие вероятности, как можно эту игру решить? Выясняется, что это очень сложный вопрос. И тут дело не в математике, а в формализации. Сколько раз позволяется стрелять в воздух. Если мы договоримся, что, например, после двух выстрелов в воздух наступает ничья и никто не получает ничего, это одна история. Если после трех – другая. Если после четырех – третья. У нас получается, что завершение этой чисто математической задачи зависит от того, как мы договоримся о правилах игры. И совершенно по-разному предсказания происходят. В зависимости от того, как мы договоримся. У нас есть достижения некоторые чисто научные. Один случай разобрали до конца, правда, до сих пор не опубликовали. Суть в том, что если два раза в воздух стрелять можно, а на третий нужно стрелять в кого-то... Грубо говоря, если ты стрельнул в воздух, другой стрельнул в воздух, то третий обязан стрелять. В этой ситуации мы все досчитали. В ситуации, когда люди не используют смешанных стратегий, как до этого мы рассматривали, все так, как в первоначальной статье. “А” стреляет в воздух, “В” и “С” друг в друга. Но если допустить смешение... Придумали контрпример. Есть некий способ поведения, при котором “С” стреляет в воздух в определенных условиях. И, как бы, наказывает потом прицельным выстрелом того, кто откажется от некоторого шаблона. В общем, очень сложное нашли динамическое равновесие, в котором побеждает не слабейший, а сильнейший. Но в принципе правило, что слабейший побеждает, оно... Можно считать, что это лейтмотив все же. Какие-то особые ситуации бывают, когда можно себе представить иной исход, но в целом в дуэли трех лиц должен победить слабейший.
Сергей Ивановский. Что значит победить? Даже сорок девять девяностых. Все равно это не исключает того, что “С” стреляет таким образом, что выбивает кого-то. Это работает в условиях, которые мы создали. Если “С” стреляет первым, там задача...
Алексей Савватеев. Если “С” стреляет первым, у “А” прекрасные тоже шансы. Идея такая, что в этой игре хорошие шансы у “А”. Высокие, но не стопроцентные.
Сергей Ивановский. Сразу хочется пофантазировать. В реальной жизни...
Алексей Савватеев. Америка, Китай и Россия. Все просто. Америка и Китай друг друга “мочат” в экономическом смысле, а мы выигрываем у них.
Сергей Ивановский. Получается, что слабейший игрок должен очень хорошо думать об условиях.
Алексей Савватеев. На самом деле любые параллели с политикой являются спекулятивными. Интересна здесь именно математика. А с пробками есть много интересных парадоксов, теоретико-игровых. Вот пробки, это та область... Вообще транспортная теория игр, это область, в которой нет нареканий к теории игр. Почти везде есть нарекания: “Что вы представляете игроков, как каких-то индивидуалистов, которые только о себе думают?” В случае с транспортными проблемами такого нарекания нет. Но проблема в том, что человек не учитывает, что своей машинкой он чуть-чуть да ухудшил дорожную ситуацию для остальных. Когда все так действуют, они сильно ухудшают дорожную ситуацию для всех. Приведу один классический пример. Называется парадокс Браеса. Московская кольцевая автомобильная дорога, а здесь есть район, который называется Метрогородок. А здесь есть Щелковское шоссе, это такая артерия, которая соединяет... Здесь очень много городов. Мытищи, Королев... Магистраль, через которую въезжает много народа в Москву каждое утро. В 1990-е годы еще не было слишком много машин. В самом начале 1990-х годов магистраль ехала. Есть район, называется ВДНХ. Там довольно много мест сдавалось под офисы, там работало довольно много народу. Довольно серьезный поток машин так следует. Тут светофоры, светофоры... Допустим, один час. Есть малоизвестный проход, грубо говоря, между гаражами где-то. От Щелковского шоссе можно было попасть в Метрогородок. А из Метрогородка к ВДНХ идет узенькая, извилистая дорога. В те 1990-е годы без единого светофора. В общем, здесь быстро, здесь 20 минут. Ну, и здесь 10 минут. Теперь внимание. В эпоху, когда можно было сравнить эти пути, что стало происходить? Здесь час ехать, а здесь полчаса. Каждый водитель думает, что он самый умный и “фигачит” сюда. До какого момента это продолжается? Что должно произойти, чтобы времена сравнялись?
Сергей Ивановский. Должна образоваться некая пробка.
Алексей Савватеев. Да. Около ВДНХ. Вопрос: какой она должна быть длины в минутах? Математически точный ответ: полчаса. Доказательство от противного. Предположим, что меньше получаса. Если меньше получаса, тогда каждая машина, въезжающая сюда через эти широкие ворота, поедет здесь, а не здесь. Потому, что так будет быстрее. Предположим, что мы прогнозируем пробку больше получаса. Тогда зачем сюда сворачивать? Надо ехать вот так. Если она меньше получаса, то она больше получаса. Если она больше получаса, то она меньше получаса. Единственный вывод, что пробка приблизительно равна 30 минут. В равновесии, если мы знаем дорожную ситуацию, мы предсказываем в этой ситуации пробку длиной в районе получаса. Не меньше и не больше. А теперь внимание, финальный аккорд. Давай я здесь все разрушу. Уберу эту дорогу. Что произошло? Они все как час ехали, так и едут. А здесь пробки нет, и я за двадцать минут доезжаю от Метрогородка. Появление новой дороги не улучшает ситуацию для этих. А для всех, живущих в Метрогородке, добавляет полчаса. Эта ситуация называется парадокс Браеса. Когда строительство новой дороги приводит к ухудшению дорожной ситуации. Теперь идеальный вид парадокса Браеса устроен так. Есть пункт “А” и пункт “В”. Здесь спят, здесь работают. Здесь озеро, здесь тоже озеро. Есть пункт “С” между озерами. Ты не можешь проехать из пункта “А” в пункт “В”, минуя пункт “С”. Но и до и после есть альтернативная дорога в обход. По этой дороге может проехать не очень много машин. Грубо говоря, две трети всех желающих из “А” в “В” попасть. Но не больше двух третей. Здесь хоть все вообще. Широкая объездная дорога. Но здесь 40 минут, а здесь 20 минут. Здесь тоже 40 минут. И здесь 20 минут. До всякого дорожного регулирования. Что происходит? Отсюда выезжает машина и думает: “Как мне ехать? Так или так?” Пробка длиной 20 минут. И здесь такая же. Два куска ничем друг от друга не отличаются. Время езды. Вот так час двадцать. Вот так тоже час двадцать. Ехал двадцать минут, стоял двадцать минут. Время езды любого участника дорожного движения один час двадцать минут. Теперь приходит человек, Юрий Евгеньевич Нестеров. Один из величайших ученых, матпрограммистов в Европе. Наш современник. Что он сказал? Он говорит: “Один запрещающий знак на движение насквозь вперед”. Стоимость реформы ноль рублей. Поставить один запрещающий знак. Что теперь происходит?
Сергей Ивановский. Запрещающий, это какой?
Алексей Савватеев. Это значит, что если ты едешь вот так и дальше едешь, то штраф. Нельзя ехать прямо только этот участок. Вот можно. И так можно, и так можно. Но нельзя, если ты приехал из “А” в “С” по прямой дороге, продолжать по прямой дальше. Такой запрет. Ничего больше, только один запрет. Теперь смотрим, что происходит. Эти знают, что если они пойдут сюда, должны будут идти сюда. А если они пойдут сюда, они могут дальше ехать прямо. Если здесь много машин, то примерно половина будет стартовать сюда, а потом так. Половина сюда, а потом так. Но половину эта дорога выдержит без пробки. И эта тоже выдержит без пробки. Получается, что половина машин 20 минут едут здесь и 40 здесь. Половина машин 40 минут едут здесь и 20 здесь. Путем нулевой по стоимости реформы на 20 минут каждый участник дорожного движения сократил время. Это гениально. Если меня спрашивают: “Хоть что-то ваша теория игр куда-то привнесла?” Я сразу рассказываю про этот пример. В огромном количестве городов не заметили эту ситуацию. Нестеров сформулировал две аксиомы. Первая аксиома состоит в том, что время корреспонденции вначале не зависит от количества машин. А при достижении максимального уровня просто дальше растет время, а количество машин, которое может пропустить данная дорога, не меняется. Вот это рост пробки. Это первая аксиома. А вторая, что каждый человек выбирает кратчайший по времени путь из всех имеющихся. С этими двумя аксиомами можно записать любую транспортную систему города, как систему уравнений и решать. Здесь теория игр делает чудеса. Эти методы внедрены. Такая вот теория игр в применении к транспорту.
Сергей Ивановский. Я думаю, что мы оставим пару задач людям подумать. Специально делаем так, чтобы вы могли осмыслить это. Может быть, какие-то вопросы задать. Мы постараемся на них отреагировать. Попробуйте, может быть, на листочке нарисовать, подумать.
Алексей Савватеев. И задачка, которую каждый может решить или подсмотреть решение в интернете. В 2016 году большая часть голосующего населения Америки была против Дональда Трампа. Как он прошел? Не очень сложная, но интересная.
Сергей Ивановский. Я смотрел другую теорию, связанную с рекламой. Что определенным образом показывались объявления.
Алексей Савватеев. Трамп пользовался чрезвычайно продвинутой системой рекламирования. “Таргетировал”. Такому человеку то скажет, такому то. Но даже после этого больше половины была против него, а он прошел.
Сергей Ивановский. Не будем давать задачу, а просто решим ее.
Алексей Савватеев. Хорошо. Модель такая. Есть два штата. Здесь живет 12 миллионов человек, а здесь 8. В том, что я скажу, содержится ответ. В США голосуют не люди, а выборщики. То есть, в каждом штате проходит собственное внутреннее голосование “за” или “против” Трампа. От каждого штата количество выборщиков пропорционально населению. Если в этом штате живет 12 миллионов человек, то будет 3 выборщика. А если в этом 8, то 2. Поддержка Трампа здесь 8 “за”, 4 “против”. Трамп побеждает здесь. Соответственно, победив, он заставляет всех трех выборщиков голосовать за него на дальнейших выборах. Здесь 8 против него, поэтому эти два выборщика будут голосовать против Трампа. Здесь 3, а здесь 2. Именно из-за системы, что все выборщики голосуют одинаково. Выбирает штат, а не люди. Поэтому Трамп выигрывает в соотношении 3 к 2, хотя исходно он проигрывает в соотношении 2 к 3. Такая очень красивая модель. Это коалиционная теория игр. Это понимание того, как устроены выборы в принципе в Америке, что такое выборщики. Таких моделей довольно много в коалиционной теории игр. Это конечно не относится к стратегической теории игр.
Сергей Ивановский. Отлично. Ну, и на сегодня все. Всем до свидания.
Алексей Савватеев. Счастливо.
Новости
VIP
