Теория игр — раздел математики, изучающий стратегическое взаимодействие рациональных агентов. Основана Джоном фон Нейманом и Оскаром Моргенштерном в 1944 году (книга "Теория игр и экономическое поведение"). Теория анализирует ситуации, где результат для каждого участника зависит от действий других: конкуренция фирм, военные конфликты, аукционы, эволюционная биология.
Представьте игру в покер: ваш выигрыш зависит не только от ваших карт, но и от того, как играют соперники. Блефуете ли вы? Что думают о вас другие? Теория игр формализует такие ситуации: определяет оптимальные стратегии, равновесия (когда никому не выгодно менять решение), предсказывает исходы.
Основные понятия
Игра задаётся тремя компонентами: игроки (участники), стратегии (доступные действия), выигрыши (функции полезности, зависящие от выбора всех игроков).
Игра с нулевой суммой: Выигрыш одного = проигрыш другого. Сумма выигрышей всех игроков = 0. Пример: покер, шахматы (ничья = 0 обоим). Фон Нейман в 1928 году доказал теорему о минимаксе: в игре двух лиц с нулевой суммой существует оптимальная смешанная стратегия.
Игра с ненулевой суммой: Игроки могут выигрывать или проигрывать вместе. Пример: переговоры (сделка выгодна обоим), гонка вооружений (обе стороны тратятся). Большинство экономических и социальных ситуаций — ненулевая сумма.
Чистая стратегия: Детерминированное действие ("всегда выбирать A"). Смешанная стратегия: Случайный выбор действий с заданными вероятностями ("выбрать A с вероятностью 0,7, B — 0,3"). Смешанные стратегии расширяют множество равновесий.
Равновесие Нэша
Джон Нэш в 1950 году (Нобелевская премия 1994) доказал: в любой конечной игре существует равновесие (в смешанных стратегиях), где ни одному игроку не выгодно отклоняться в одиночку.
Определение: Профиль стратегий (s₁, s₂, ..., sₙ) — равновесие Нэша, если для каждого игрока i стратегия sᵢ — лучший ответ на стратегии остальных. Никому не выгодно менять решение, если другие не меняют.
Дилемма заключённого: Двух подозреваемых допрашивают раздельно. Варианты: молчать или предать. Если оба молчат — по 1 году каждому. Если оба предают — по 3 года. Если один предаёт, другой молчит — предатель свободен, молчавший получает 5 лет.
Равновесие Нэша: оба предают (каждому невыгодно молчать, если другой может предать). Но если бы сотрудничали — оба получили бы по 1 году (лучше для обоих). Парадокс: рациональное поведение приводит к худшему исходу.
Повторяющиеся игры
Если игра повторяется многократно, появляется возможность сотрудничества. Роберт Аксельрод в 1984 году провёл турнир стратегий для повторяющейся дилеммы заключённого. Победила "Tit for Tat" (Око за око): сотрудничай в первый ход, потом копируй действие соперника.
Народная теорема: В бесконечно повторяющихся играх любой исход, лучший чем равновесие одноходовой игры, может быть устойчивым равновесием. Игроки поддерживают сотрудничество угрозой наказания в будущем.
Применение: Картели (фирмы поддерживают высокие цены угрозой ценовой войны при нарушении), международные договоры (страны соблюдают соглашения под угрозой санкций).
Игры с неполной информацией
Джон Харсаньи (Нобелевская премия 1994, совместно с Нэшем) в 1967-1968 годах разработал теорию игр с неполной информацией: игроки не знают типы (характеристики) соперников, но имеют вероятностные убеждения.
Байесовское равновесие Нэша: Каждый игрок максимизирует ожидаемую полезность, учитывая убеждения о типах других. Применяется в аукционах (участники не знают оценки товара соперниками), переговорах (неизвестна готовность к уступкам).
Теория аукционов
Уильям Викри (Нобелевская премия 1996) в 1961 году проанализировал аукционы как игры. Четыре типа:
Английский аукцион: Цена растёт, пока есть ставки. Выигрывает последний. Стратегия: ставить до своей оценки.
Голландский аукцион: Цена падает, первый согласившийся выигрывает. Эквивалентен первому в стратегическом смысле.
Первоценовый закрытый: Каждый пишет ставку, выигрывает наибольшая, платит свою ставку. Стратегия: занижать ставку (баланс между вероятностью выигрыша и ценой).
Второценовый закрытый (Викри): Выигрывает наибольшая ставка, но платит вторую по величине. Доминирующая стратегия: ставить истинную оценку (занижение не выгодно — цена определяется вторым).
Теорема об эквивалентности доходов: При определённых условиях (симметричные независимо распределённые оценки) все четыре формата дают одинаковый ожидаемый доход продавцу.
Эволюционная теория игр
Джон Мейнард Смит в 1970-х годах применил теорию игр к эволюционной биологии. Эволюционно стабильная стратегия (ЭСС): Стратегия, которую не может вытеснить мутантная стратегия при малом проценте мутантов в популяции.
Игра Ястреб-Голубь: Животные конкурируют за ресурс. Ястреб дерётся до победы (риск травмы), Голубь отступает без драки. Если в популяции только Ястребы — высокая травматичность, выгодна мутация Голубь. Если только Голуби — выгоден Ястреб. ЭСС — смешанная популяция (определённое соотношение Ястребов и Голубей).
Применение: Альтруизм (взаимопомощь стабильна, если вероятность повторных встреч высока), половой отбор (павлиньи хвосты — дорогостоящая сигнализация здоровья).
Кооперативная теория игр
Изучает коалиции: игроки могут формировать группы и делить выигрыш. Вопросы: какие коалиции стабильны? Как справедливо распределить выигрыш?
Ядро игры: Распределение, от которого ни одна коалиция не может отклониться с выгодой для всех участников. Если ядро пустое — нет стабильного распределения (пример: три игрока, большинство из двух получает всё, третий ничего).
Вектор Шепли: Ллойд Шепли (Нобелевская премия 2012) в 1953 году предложил "справедливое" распределение выигрыша: вклад игрока = среднее увеличение выигрыша коалиции при его добавлении (по всем порядкам добавления).
Применение: Распределение прибыли в совместных проектах, формирование политических коалиций, оценка влияния акционеров (индекс Шепли-Шубика).
Применение в экономике
Олигополия: Модель Курно (1838, переосмыслена через теорию игр): фирмы выбирают объёмы производства, цена определяется рынком. Равновесие Нэша: каждая фирма выбирает оптимальный объём, учитывая выбор конкурентов.
Дизайн механизмов: Леонид Гурвиц, Эрик Маскин, Роджер Майерсон (Нобелевская премия 2007) разработали теорию: как спроектировать правила игры (аукцион, систему голосования), чтобы участники, действуя рационально, достигали желаемого результата.
Matching theory: Элвин Рот и Ллойд Шепли (Нобелевская премия 2012) изучали задачи сопоставления (распределение студентов по университетам, доноров органов реципиентам). Алгоритм Гейла-Шепли (1962) находит стабильное сопоставление (нет пары, предпочитающей обменяться партнёрами).
Применение в computer science
Алгоритмическая теория игр: Вычислительная сложность поиска равновесий. Класс PPAD (Polynomial Parity Arguments on Directed graphs) — задачи типа "найти равновесие Нэша" (полиномиально проверяемы, но неизвестно, решаемы ли за полиномиальное время).
Распределённые системы: Протоколы консенсуса в блокчейне (Bitcoin) — игра, где рациональным майнерам выгодно следовать правилам. Византийская задача о генералах (1982) — достижение консенсуса при наличии "предателей".
Машинное обучение: Генеративно-состязательные сети (GAN, Goodfellow, 2014) — игра между генератором (создаёт данные) и дискриминатором (отличает подделки). Равновесие Нэша = реалистичная генерация.