Теория игр окутана тайной, и в то же время её название известно далеко за пределами математики и экономики. С её помощью полководцы выигрывают бои (начиная со Второй Мировой), а международные корпорации выстраивают стратегии продвижения товаров. Ей интересуются не только естественники, но и философы, в учебниках по теории игр есть главы, написанные философами.
Доцент кафедры «Математическое обеспечение информационных технологий» ЮУрГУ Константин Кудрявцев – уникальный для университета специалист в области теории игр. Его работа поддержана грантом РНФ «Разработка алгоритмов и методов управления сложными конфликтными системами в условиях неопределённости». Один из недавно опубликованных его результатов – определение условий Парето-оптимального решения в дифференциальной позиционной игре из шести лиц с двухкоалиционной структурой. Весомо звучит? Давайте попробуем понять, что это значит.
Победа или эквилибриум?
Теория игр возникла в годы Второй Мировой войны в США – по иронии почти одновременно со знаменитым романом Германа Гессе «Игра в бисер». Одним из её основателей стал знаменитый математик Джон фон Нейман, который где только не был известен – и в алгебре (теории клеточных автоматов), и в квантовой физике, и в кибернетике. Участвовал фон Нейман и в Манхэттенском проекте по созданию американской атомной бомбы. По легенде, именно он, по каким-то расчётам, выбрал среди 9 японских городов Хиросиму и Нагасаки, и этот роковой выбор стал причиной одной из самых известных трагедий планеты.
Другой основатель – ученик фон Неймана – Джон Нэш. Нобелевский лауреат по экономике и обладатель не менее известной среди математиков премии Абеля. Он известен далеко за пределами математики, в основном благодаря книге Сильвии Нэзер «Игры разума» и одноимённому фильму – о том, как учёный боролся с шизофренией, продолжая совершать открытия. Справедливости ради, тяжёлый диагноз был поставлен Нэшу гораздо позже, чем он опубликовал свой основной вклад в теорию игр. Свои открытия он совершил в 21 год, готовясь к защите диссертации Ph. D. Скончался Нэш на 87-м году жизни в автокатастрофе, причём, если бы он пристегнул ремень, это могло бы спасти его жизнь. Вот как важно в повседневности рассчитывать последствия!
Итак, теория игр – математическая наука о стратегиях и принятии оптимальных решений в условиях конфликта интересов. Для любой игры должны быть определены три вещи. Во-первых, список игроков. Во-вторых, набор доступных каждому из игроков действий, называемых в теории игр стратегиями. И, в-третьих, учитывая, что каждый из игроков, в зависимости от выбранной линии поведения, получает какой-то измеримый профит, должны быть определены функции выигрыша.
В функциях выигрыша как раз и скрыта основная проблема: выигрыш каждого игрока зависит не только от его собственного выбора, но и от стратегий остальных игроков. Поэтому, выбирая свою стратегию, игрок должен учитывать и возможные действия остальных участников игры.
Считается, что каждый игрок стремится к поиску оптимальной стратегии. Вот только что считать оптимальным? Чаще всего игрок желает получить максимальный выигрыш. Но кто-то может хотеть, чтобы «повезло» всем участникам, чтобы каждый выиграл столько, сколько возможно, не обидев других (альтруистическая стратегия). Напротив, может появиться игрок, задача которого – навредить другим игрокам или части из них.
Когда игра кончается – тоже неочевидный вопрос. Теория игр оперирует понятием «равновесия» (английский термин «эквилибриум»).
Равновесием по Нэшу называется ситуация, когда ни один из игроков не может увеличить своего выигрыша, если другие игроки не намерены менять своих стратегий. Как сказали бы сейчас, «стратегический тупик». И что делать дальше? Ждать перемен или заканчивать игру? Каждый решает сам за пределами математики.
Есть и другие типы равновесий. Например, равновесие по Бержу или альтруистическое, когда все, не договариваясь между собой, выстраивали стратегию так, чтобы каждому (а не кому-то одному) достался максимум возможной выгоды. Существуют ещё равновесие угроз и контругроз (когда игрок боится «наказания» со стороны других игроков) и многие другие.
Кстати, забавно звучащие термины имеют подчас не менее забавное происхождение. Опять же согласно легенде, Клод Берж – известный учёный в других областях – написал первый учебник по теории игр, который был жёстко раскритикован, после чего в теорию игр не возвращался. Но ведь, создавая пособие для студентов, он хотел, как лучше, не правда ли? Поэтому, с подачи советских математиков, его именем стало называться «альтруистическое» равновесие.
«Сугроб», «Орлянка» и другие игры
Проиллюстрируем это на примере игры «Сугроб», для начала – с двумя игроками. Два водителя застряли на лесной дороге ночью во время бурана. Они видят друг друга издалека, но не могут переговариваться из-за сильного снегопада. Сотовая связь ещё работает и можно вызвать из ближайшей деревни трактор, который расчистит дорогу. Вызов техники стоит 100 монет, деньги снимаются сразу. Расчистка дороги тоже 100 монет, оплачивается по выполнении.
Каждый водитель размышляет над стратегией: звонить или затаиться в надежде, что вызов сделает другой. Альтруистический вариант: оба сделают вызовы, а когда трактор расчистит дорогу, оплатят его работу вскладчину. В результате каждый потратит по 150 монет.
Эгоистический вариант: ждать, пока звонок сделает другой. Тогда тот, кто вызывает подмогу, оплатит и вызов, и расчистку дороги – 200 монет, а второй водитель сделает вид, что он тут ни при чём и просто проедет следом.
Наконец, вариант равновесия по Нэшу: оба водителя пытаются обхитрить друг друга, надеясь, что конкурент не выдержит и сделает вызов первым. Они не тратят монет – с точки зрения математики это и есть оптимальная стратегия. Но перспектива провести ночь в лесу, а может быть и до весны, пока не растает снег, очевидно не самая приятная и разумная.
Попробуем увеличить количество игроков – три, четыре, десять и так далее. Чем больше игроков поведут себя как альтруисты, тем меньшую сумму вскладчину за расчистку дороги им предстоит платить. При этом, разумеется, возрастают шансы и у эгоиста, который ничего платить не собирается (таким образом, получая не потраченную сумму в качестве выигрыша).
Если у игроков появляется возможность договариваться, некоторые из них объединяются в коалиции (например, два водителя решают сделать один звонок, а дорогу оплатить вскладчину или, наоборот, договариваются не звонить, чтобы вынудить на звонок третьего). Такие игры называются кооперативными. Сами коалиции называют устойчивыми, если ни одного игрока не тянет отделяться от них, переходить в другую коалицию или создавать свою.
Другие примеры игр известны многим с детства: «Орлянка» и «Камень, ножницы, бумага». Это игры с нулевой суммой: то, что проиграл один, становится выигрышем другого.
Ещё один важный для теории игр пример называется в математике «дилеммой заключённого», хотя можно сказать и подследственного. Двое преступников попались на месте, следователь рассадил их по разным камерам и в разное время вызывает на допрос. Каждому он предлагает дать показания, но не на себя, а на товарища.
Если оба преступника воздержатся от показаний, каждый получит минимальный срок. Если один обвиняет другого, а другой молчит, то первого освобождают как невиновного, а второй получает по максимуму. Если же оба дают показания друг на друга, наказание будет не максимальным (пошли на сделку со следствием), но и не минимальным (групповое преступление).
Эта игра с ненулевой суммой и она демонстрирует, как равновесие по Нэшу может быть вступать в противоречие с «эффективностью по Парето» (ни один игрок не может увеличить свой выигрыш, не ухудшая состояние другого игрока).
Эгоизм подсказывает: сознаться, тогда есть шанс сразу выйти на свободу.
Равновесие Нэша в этой игре, когда оба игрока сознаются, «закладывают» друг друга. Получить средние сроки – не очень приятный результат.
Принцип оптимальности по Парето устроен так: улучшение – это то, что никому не приносит вреда, а всем приносит пользу. В данном случае это значит – молчать. Конечно, не факт, что игра придёт к альтруистическому равновесию, когда оба смолчат и получат минимальные сроки.
Можно предположить и геополитическую трактовку для теории игр. Две граничащие друг с другом страны думают, вооружаться или нет. Если обе не станут вооружаться – сэкономят много денег. Если обе вооружатся – окажутся на равных, и вероятно не тронут друг друга. Если одна из стран не вооружится, а другая сделает это, первая потеряет независимость.
Мальчик и крокодил
В жизни всё сложнее: не всегда стратегии оптимального поведения можно описать словами, иногда эту роль играет функция, являющаяся одним из решений дифференциального уравнения, а выигрыш может определяться не числом, а числовым интервалом. Пример дифференциальной игры, известный многим студентам, – «Мальчик и крокодил». В центре круглого озера выныривает крокодил, видит на берегу мальчика и плывёт к нему прямо по радиусу, чтобы съесть его. Мальчик начинает бегать вдоль озера (свернуть в джунгли он не может по условиям), заставляя крокодила постоянно корректировать курс. Задача для обоих заключается в выборе скорости: крокодилу – чтобы добраться до мальчика, мальчика – чтобы заставить крокодила «кружиться». Ответ отнюдь не очевидный, в наше время учёные пишут об этом статьи, добавляя разные дополнительные условия.
Нечёткая романтика
Существуют факторы, которыми игроки управлять не могут, и тем не менее они влияют на выигрыш. Как их учесть? Только вероятностно (стохастически), собрав информацию и обработав её с помощью математической статистики. Но иногда вероятности определить не удаётся, а значит можно ожидать реализации любого, заранее игрокам не известного, значения из заданного интервала. Воздействие таких факторов представляет собой интервальную неопределенность.
Такой тип неопределенности Елена Вентцель – известнейший советский математик, а заодно и писательница, работавшая под псевдонимом И. Грекова (не «Ирина Грекова», а «игрекова», от латинской буквы «игрек») иллюстрировала капризами моды. Невозможно предсказать заранее длину юбки, которую будут носить через несколько сезонов. Но из наблюдения за ростом женщин можно сказать, что она не больше такой-то величины и не меньше такой-то, соответственно её размеру.
Это напоминает модель нечётких множеств – очень популярную сейчас математической концепции, которая лежит в основе работы нечётких сетей.
Нечеткий подход можно проиллюстрировать с помощью следующего наивного примера. Что значит «молодой человек»? Допустим, все согласятся, что это некто возрастом от 20 до 25. Но кто-то захочет расширить этот интервал влево, до 15 лет (в представлении других это дети, подростки) или вправо до 35 лет (в представлении других это зрелые). Таким образом, можно утверждать, что человек 24 лет «стопроцентно» молодой, 50 – «стопроцентно» нет, а вот 17 или 34 – молод «с определённой вероятностью».
Так и в игре выигрыш может задаваться с учётом вероятности, может интервалом, а может и нечётким числом.
Что же касается теории нечетких систем, здесь тоже существует забавная легенда. Изобретатель нечётких чисел Лофти Заде учился в американском университете Беркли в Калифорнии. И однажды вечером в баре угодил в драку из-за спора о красоте девушек. Проснувшись утром в полицейском участке, математик стал размышлять: а из-за чего же собственно спор? Джинни нравится всем, а Бетти – только некоторым. Так появилась концепция нечётких множеств и «мягких» вычислений.
И хотя строго математически было доказано, что с любой точностью более простая «нечёткая» система может аппроксимировать обычную, долгое время теорию нечётких множеств многие считали чудачеством. Все изменилось в 1970-е годы, когда в Японии на основе нечеткой логики реализовали систему автоматического управление движением поездов в токийском метро. Сегодня контроллеры с нечёткой логикой можно встретить везде – начиная с обычной бытовой техники (они управляют микроволновками, стиральными машинами, кофеварками) и тракторов «Джон Дир» и заканчивая ракетами, которым необходимо в зависимости от ситуации, корректировать курс.
Челябинским учёным, работающим под руководством Константина Кудрявцева над грантом РНФ 23-21-00539 «Разработка алгоритмов и методов управления сложными конфликтными системами в условиях неопределённости» предстоит иметь дело как раз с такими играми: дифференциальными, с возможностью заключать коалиции между игроками, с нечёткими выигрышами. Как и вообще в теории игр, их результаты на первый взгляд покажутся абстрактными: для каждой из игр им нужно будет определить типы равновесий, условия их существования, единственности или не-единственности. Но сфера применений этих результатов огромна: от «умной техники», интегрированной с нейросетями до построения стратегий крупных промышленных компаний, а может быть, и военных кампаний. Всё зависит от того, какую стратегию, альтруистическую или «по Нэшу», выберет в будущем мир.