Теория игр и стратегическое поведение

1.1. Введение в теорию игр

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

Эта относительно молодая ветвь была создана в 1930-е годы Джоном фон Нейманом и Оскаром Моргенштерном. Позже, в 1950-е годы, колоссальную роль в развитие теории игр внес американский математик, лауреат Нобелевской премии Джон Нэш. (Его неординарная жизнь легла в основу известного фильма «Игры разума»).

Индивид, принимая решения, догадывается о том, как будут вести себя другие участники. Говорят, что в этом случае индивид следует определённой игровой стратегии. Игровая стратегия — это полное описание действий игрока во всех возможных ситуациях, которые могут сложиться в игре.

1.2. Статические игры и Равновесие Нэша

Битва полов

Муж и жена решают, как провести вечер, выбирая между балетом и футболом. Выбор делается одновременно и независимо (никто не знает, что выбрал другой). Муж получает полезность 2, если идет с женой на футбол, и 1, если идет в балет. Жена — наоборот: 2 за балет, 1 за футбол. Если они идут порознь, оба получают 0. Представим игру в нормальной форме (матрица):

Дилемма заключенного и Парето-эффективность

Представьте, что вы с напарником ограбили банк. Полиция поймала вас и допрашивает в разных камерах. Каждому предлагают сделку: «Сдай напарника, и выйдешь на свободу, а он сядет на 5 лет». Если оба молчат — вина не доказана, оба получают по 1 году. Если оба «стучат» друг на друга — оба получают по 2 года. Подобные задачи на равновесие Нэша часто встречаются в олимпиадах.

Рассмотрим логику игрока А: «Если В молчит, мне лучше признаться (0 лет вместо 1). Если В стучит, мне тоже лучше признаться (2 года вместо 5)». Стратегия «Признаться» является строго доминирующей. Игрок В рассуждает так же. В итоге оба признаются и получают по 2 года. Это — Равновесие Нэша.

Однако исход (2; 2) не является Парето-эффективным. Преступники могли бы договориться молчать и получить (1; 1). Но эгоистические интересы и недоверие делают договор неустойчивым. Адам Смит считал, что «невидимая рука» эгоизма ведет к благу общества. Джон Нэш математически доказал, что это не всегда так.

1.3. Смешанные стратегии

Существуют ситуации, когда равновесия в чистых (однозначно определенных) стратегиях не существует. Вы прячете шарик за спиной, а я угадываю руку. Если вы всегда будете прятать в правую, я быстро это пойму и начну всегда выигрывать. Если вы будете чередовать — я тоже распознаю паттерн.

Единственный способ не проиграть — использовать смешанную стратегию, то есть делать выбор с помощью генератора случайностей (например, монетки). Это лишит оппонента возможности построить рациональную догадку.

Известный экономист Стивен Левитт (автор «Фрикономики») проанализировал сотни пробиваний пенальти в профессиональном футболе. Он доказал, что бьющие и вратари придерживаются смешанных стратегий, выбирая угол для удара и прыжка случайным образом (с определенными вероятностями).

1.4. Динамические игры и Коммитмент

В динамических играх вводится фактор времени — участники ходят по очереди. Игроки, делающие ход первыми, пытаются предугадать реакцию оппонентов с помощью обратной индукции (анализа игры с конца).

Иногда огромную выгоду приносит коммитмент (связывающее обязательство). Это парадоксальная ситуация: сознательное ограничение собственных возможных действий улучшает позицию игрока!

В фильме «Доктор Стрейнджлав» Кубрика СССР строит «Машину Судного дня», которая отвечает ядерным ударом автоматически и ее нельзя отключить. Смысл машины именно в невозможности изменить решение: зная, что удар неотвратим, США никогда не нападут первыми. Но чтобы это сработало, противник обязан знать о коммитменте!

1.5. Теория общественного выбора и Парадоксы

Возможно ли построить идеальную систему голосования, которая справедливо отразит мнение группы? Кеннет Эрроу в своей «Теореме о невозможности» математически доказал: не существует непротиворечивого общего мнения группы (при соблюдении ряда базовых логических условий, кроме абсолютной диктатуры).

Одним из проявлений этой невозможности является Парадокс Кондорсе. Предпочтения общества могут стать нетранзитивными: Общество предпочитает кандидата А кандидату В. Кандидата В предпочитает кандидату С. Но при этом кандидата С оно предпочитает кандидату А!

1.6. Теория мэтчингов (Поиск устойчивых пар)

Теория игр помогает решать реальные проблемы. Одной из них является теория «мэтчингов» (matching) — образования устойчивых пар без использования денег. (Например: распределение абитуриентов по вузам или доноров по реципиентам). В 2012 году Элвин Рот и Ллойд Шепли получили Нобелевскую премию за применение этой теории на практике.

Алгоритм отсроченного согласия (алгоритм Гейла-Шепли):

1. Инициаторы (например, абитуриенты) подают заявку своему самому предпочтительному кандидату (вузу).
2. Вуз временно удерживает заявку лучшего для себя студента, а остальным отказывает.
3. Отвергнутые студенты подают заявку в свой следующий по предпочтительности вуз. Процесс повторяется, пока не закончатся заявки.

Математически доказано, что этот алгоритм всегда находит стабильный мэтчинг (никто из распределенных не захочет сбежать друг к другу, разрушив текущие пары).