Теория игр для начинающих: игроки, стратегии и матрицы выигрышей

Два лотка с кофе стоят напротив друг друга в переходе. Каждое утро владелец первого решает: держать цену 100 рублей или сбросить до 80. Второй решает то же самое — и решения принимаются одновременно, без сговора. Снизит цену один, а другой нет — первый соберёт почти всю очередь. Снизят оба — очередь поделится, а выручка упадёт. Перед каждым стоит не задача «как лучше для меня», а задача «что сделает он — и как мне ответить». Такие ситуации математика описывает одной моделью: игрой.

Что делает конфликт игрой?#

Игра в бытовом смысле — развлечение. В теории игр — модель конфликта, где результат каждого участника зависит от решений нескольких сторон. Чтобы превратить историю в игру, нужны четыре ингредиента.

• Игроки — стороны, принимающие решения. В парной игре их двое (обозначим A и B), в множественной — больше.
• Стратегии — планы действий каждого игрока. У кофе-лотка их две: «100» и «80».
• Выигрыши — числа, измеряющие интерес игрока: прибыль, годы свободы, вероятность победы. Их задают для каждого сочетания стратегий.
• Информированность — кто что знает в момент хода. Одновременные ходы и последовательные — это разные игры.

1. 1
   Назовите игроков. Двое — парная игра, трое и больше — множественная.
2. 2
   Выпишите стратегии каждого: конкретные варианты действий, а не «вести себя разумно».
3. 3
   Оцифруйте выигрыши для каждого сочетания стратегий — получите платёжную матрицу.
4. 4
   Зафиксируйте информированность: ходы одновременные или последовательные, кто что видит.
5. 5
   Классифицируйте игру по осям из таблицы ниже — от этого зависит, каким методом её решать.

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

Уберите любой пункт — и модели нет. Неизвестны выигрыши? Не с чем сравнивать варианты. Игрок один? Это задача оптимизации, а не игра. Ходы последовательные и всё видно? Получается дерево решений — отдельный раздел: развёрнутая форма игры зовётся деревом игры, решается она обратной индукцией от листьев к корню. А если «соперник» — погода или спрос, которые не выбирают ход из своих интересов, то это игра с природой, у неё свои критерии: критерии Вальда, Сэвиджа, Гурвица и Байеса.

Классификация: четыре оси, по которым различают игры#

Разобраться, с какой игрой вы имеете дело, — половина решения. Оси независимые, одна игра описывается комбинацией признаков.

Основной канал этого курса — матричные игры: парные, антагонистические, конечные. Они просты настолько, что считаются до конца, и содержательны настолько, что на них видны все главные идеи. Неантагонистические и кооперативные сюжеты (вроде кофе-лотков) появляются как разборы и интерпретации; полный их аппарат — тема продвинутых курсов.

Одна и та же история может попасть в разные клетки классификации — всё зависит от допущений. Два кофе-лотка, обязанные согласовать цены, — кооперативная игра; запрет сговора антимонопольной службой делает её некооперативной. Шахматы конечны, хотя число позиций таково, что полный перебор не существует ни в одном компьютере. Прежде чем считать, зафиксируйте допущения письменно: от них меняются и метод, и ответ. Дележи устойчивых коалиций описывает ядро игры.

Платёжная матрица: кто в строках, кто в столбцах?#

Парную конечную игру удобно записывать таблицей — платёжной матрицей. Игрок A выбирает строку, игрок B — столбец. В клетке стоит число $a_{ij}$ — выигрыш A, если A сыграл свою $i$-ю стратегию, а B свою $j$-ю. В антагонистической игре у пары одно число на двоих: проигрыш B равен выигрышу A.

Знак имеет значение: плюс — A выигрывает, минус — A платит. Классическая иллюстрация — орлянка. Каждый одновременно показывает орла или решку; совпали — A забирает рубль, разошлись — отдаёт.

Дилемма заключённого: почему рациональность ведёт в камеру#

Двух соучастников допрашивают в отдельных камерах. Каждому говорят: «Сознаешься и дашь показания — выйдешь сегодня. Молчите оба — получишь по году. Сознаются оба — по восьми лет». Выигрыш измерим: минус годы. Стратегии каждого — «молчать» или «сознаться». Матрица выигрышей игрока A:

Поставьте строку «сознаться» рядом со строкой «молчать». Если B молчит, A лучше сознаться: $0>-1$. Если B сознаётся, A снова лучше сознаться: $-8>-10$. Стратегия «сознаться» доминирует: она выгоднее при любом ответе соперника. Для B расчёт зеркальный — и оба сознаются, ведь у каждого из них своя доминирующая стратегия. Оба рациональны, и оба сидят восемь лет вместо одного. Забавно: тут нет предателя и глупца — плачевный исход заложен в саму структуру выигрышей.

Пара («сознаются», «сознаются») устойчива: одиночное отступление наказывает отступившего. Смени A «сознаться» на «молчать» — получит десять лет вместо восьми. А пара («молчат», «молчат») неустойчива: каждому отступление сулит ноль вместо минус единицы. Профиль стратегий, от которого никому не выгодно отклоняться в одиночку, называют равновесием по Нэшу. Проверка проста: «а что будет, если я один сверну?» — и на зачёте, и в жизни. Формальное определение и тонкости уточнения — в словарной статье равновесие Нэша. Уточнение, устойчивое даже к крошечным ошибкам игроков, зовут равновесием дрожащей руки.

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

Есть ли у игры цена?#

Вернёмся к орлянке. Какую строку A ни зафиксирует, B подстроится — и A останется с минус единицей. Может ли A гарантировать себе что-то лучше? Здесь появляется принцип осторожности: A смотрит на худший случай в каждой строке и выбирает строку с наилучшим худшим случаем; B делает то же зеркально. Выходят два числа — нижняя и верхняя цена игры. Совпадут — у игры есть цена и седловая точка; разойдутся — чистых стратегий не хватит, придётся тасовать вероятности. Весь следующий урок — про этот расчёт: чистые стратегии и седловая точка матрицы. Подробности про равновесие случайного выбора — в уроке про смешанные стратегии.

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

Где всё это работает?#

Экономика: олигополия решает, снижать ли цены; аукционы проектируют как игры; переговоры о зарплате — торги с оцифрованными выигрышами, а делёж совместного дохода считает вектор Шепли. Экология: страны решают, сокращать ли выбросы, — коллективная дилемма заключённого в масштабе планеты. Спорт: серия пенальти — игра вратаря и бьющего, и профессиональные клубы считают вероятности ударов по видеоархивам. Биологи прикладывают те же модели к животным: нападать или бежать — тоже стратегии с выигрышами.

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

Дальше по маршруту: осторожные цены, седловые точки, смешанные стратегии, игры с природой. Начните со следующего урока — там вы впервые посчитаете цену игры до конца, на честных числах.