Основные теоремы в теории игр

Математик Алексей Савватеев о теории игр, управлении выборами и равновесии Нэша

Прежде чем разбираться с целями и задачами теории игр, я расскажу историю, которая близка каждому из нас. Утром вы думаете, как ехать на работу. Владельцы автомобилей решают вопрос с пробками и парковкой. Если автомобиль оставить около подъезда, то предсказать время на дорогу можно с точностью до нескольких минут. Точность работы нашего городского транспорта очень высока. Мы сядем за руль только в том случае, если есть надежда оказаться в нужном месте быстрее. С востока Москвы на юг я еду час на метро. Если ехать на метро и МЦК, путь займет час и пятнадцать минут. Если я сажусь за руль, я ожидаю, что доеду за 45 минут. Сам я не вожу автомобиль, поэтому речь идет не обо мне, а о типовом москвиче, у которого есть машина. Он думает, сесть за руль или нет. В итоге сел, проехал 40–45 минут и оказался быстрее. Реальность такого расклада зависит от пробок. Пробка возникает, когда много тысяч других людей поехали той же дорогой на машине — в вашу жизнь вмешиваются решения, принятые другими людьми. Когда человек решает, садиться за руль или нет, он взвешивает только свое собственное время. Если человек в итоге садится за руль, он создает негативное давление на окружающих — это отрицательная экстерналия. Он загружает дороги, и если много людей выберут ехать на машине, то 45 минут превратятся в два часа. Утром, принимая решение о выборе транспорта, вы решаете теоретико-игровую задачу, которую одновременно с вами решает все население города. Это большое событие с большим количеством игроков, и для описания таких процессов существует теория игр.

Теория игр описывает много разных процессов. Представим ситуацию выборов. Есть кандидаты A, B и C. Вы хотите, чтобы прошел кандидат C, но, исходя из опросов, которые проводились, мы понимаем, что кандидат C непроходной, 1–2% максимум. Вы понимаете, что если будете голосовать за него, то ваш голос в итоге выльется в то, что кандидат B не пройдет во второй тур. В итоге выиграет кандидат A, который вам не нравился. Поэтому вы решаете голосовать за B, раз C — непроходной вариант. В результате возможна дискоординация. Все хотели голосовать за C, но не верили, что C проходной. Или ситуация, когда никто не знал, проходной он или непроходной, но заказали опрос, на котором объявили результаты, что C непроходной. Такое в некоторых странах случается. Такими опросами люди хотят повлиять на ситуацию. Человек создает в голове некоторые представления о действиях других игроков и о том, какие у них функции выигрыша. Если любителей C много и они знают, что их много, то C может победить. Если любителей C много, но они считают, что они все в меньшинстве, то C не победит, потому что они будут голосовать за B против A. Возникает ситуация равновесия. Таких историй из нашей окружающей реальности можно много вспомнить, поэтому важно изучать теорию игр.

Теория игр — метод, когда мы берем и формализуем ситуацию с конкретным списком игроков. У каждого игрока чемоданчик, который он открывает, — там пульт управления его действиями. Он выбирает кнопку, которую должен нажать. Все остальные игроки тоже нажимают кнопки. В ситуации с транспортом решение, сесть за руль или нет, — это бинарный выбор: да или нет. Существуют ситуации сложнее. Например, выбор маршрута, когда вы уже сели за руль. Когда каждый игрок выбирает стратегию, складывается равновесие. В ситуации с транспортом каждый выбирает дорогу и средство передвижения. В результате этого равновесия возникают выигрыши игроков. В случае с транспортом выигрыш — сэкономленное время.

Равновесие — согласованный прогноз, который можно объявить вслух, и каждый игрок, сопоставив информацию, поймет, что сделал правильный выбор. Прогнозы, которые можно объявить, а после каждый решит, что он будет действовать так, как сказано, называются равновесными. Пример неравновесного прогноза: мэр города решил, что много пробок, и с утра разрешил садиться за руль тем, у кого фамилии начинаются на букву А. Представим себе, что некто, у кого фамилия начинается на букву Б или В, верит в то, что остальные действуют согласно словам мэра, значит, дороги будут пустые, поэтому этот некто садится за руль. Из этого следует только одно: такой прогноз не будет выполнен. Мы не знаем, кто будет отклоняться и в какую сторону, но ясно, что прогноз неравновесный.

Концепцию равновесия в 1838 году придумал Антуан Огюст Курно, анализируя рынок зерна во Франции. Курно рассматривал, какие объемы зерна привезут разные фермеры, угадывая действия друг друга, и как цена будет складываться в зависимости от количества зерна. Американский математик Джон Нэш доказал теорему существования, которая связана с равновесными прогнозами. Рассмотрим любую игру, где есть конечное количество n игроков. У каждого игрока конечный список стратегий и произвольные функции выигрыша — функции, которые определяют, сколько теряет или приобретает игрок в зависимости от выбранной стратегии. Математически это означает: задано n функций на прямом произведении множеств всех стратегий. Эта ситуация называется игрой. В некотором специальном смысле слова равновесие всегда существует. В прямом смысле слова существует прогноз, который можно объявить, и он выполнится. Каждый будет действовать согласно этому прогнозу, но это утверждение будет неверным. Рассмотрим самую простую игру — орлянка. Ты берешь монету и зажимаешь ее, а я пытаюсь угадать, орлом ты ее зажал или решкой. У меня две стратегии, и у тебя две стратегии. Четыре реализации: орел — орел, орел — решка, решка — орел, решка — решка. Если я угадал, я выигрываю бутылку кефира и полбатона. Проигрываю тоже бутылку кефира и полбатона. В этой игре равновесий в смысле объявленных прогнозов быть не может. У нас четыре ситуации, и в каждой из них ясно, что кто-то будет действовать не так, как сказано. Если сказано, что ты зажимаешь решкой и я должен говорить вслух слово «решка», то ты зажмешь орлом, чтобы выиграть, а не проиграть. Но если сказать, что ты зажимаешь решкой, а я скажу «орел», то я скажу «решка», чтобы выиграть. Равновесие здесь существует в другом смысле слова, более аккуратном.

Наши действия в этой ситуации можно сравнить с подбрасыванием монеты. Ты подбрасываешь ее и зажимаешь тем, чем получилось, и я подбрасываю и зажимаю, чем получилось. Если мне сообщить, что ты правда ее подбрасываешь, то мне бессмысленно пытаться угадать решку или орла. Любой расклад я угадаю только в одном из двух случаев. Поэтому я говорю, что мне все равно на выбор стратегии, поэтому я тоже буду бросать монету и говорить результат, который выпадет. В этом смысле ответом на стратегию выбрасывания монеты является стратегия выбрасывания монеты. Такая смешанная пара стратегий называется равновесием Нэша. В ситуациях с транспортным моделированием люди распадаются на страты, внутри которых одни садятся за руль, а другие нет. В таких транспортных моделях всегда есть равновесия, потому что это смешанные стратегии, в которых необязательно 50 на 50. Это и есть теорема, которую доказал Джон Нэш.

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

Источник: postnauka.ru

Комментарии: