♟️ Теория игр

Кооперативная игра

англ. Cooperative game

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

Кооперативная игра — игра, где игроки могут заключать обязывающие соглашения и действовать коалициями. Описывается она не стратегиями, а характеристической функцией $v (S)$ — наибольшим суммарным выигрышем коалиции $S$ . Пример на трёх участниках: поодиночке $v ({1}) = 1$ , $v ({2}) = 2$ , $v ({3}) = 3$ ; парами $v ({1, 2}) = 6$ , $v ({2, 3}) = 7$ , $v ({1, 3}) = 5$ ; вместе $v ({1, 2, 3}) = 10$ . Объединение выгодно, потому что $v$ супераддитивна: $v ({1, 2}) = 6 \geq 1 + 2$ .

Главный вопрос — как делить $v (N)$ между участниками. Дележ устойчив, если ни одна коалиция не может отколоться и жить лучше: множество таких дележей называют ядром. Вектор Шепли делит по среднему предельному вкладу игрока во все порядки формирования большой коалиции. Некооперативный и кооперативный подходы дополняют друг друга; запрет картелей превращает кооперативную игру в некооперативную. Классификация игр и примеры соглашений — в уроке введение в теорию игр, понятие среднего вклада — через математическое ожидание.

v (S \cup T) \geq v (S) + v (T) при S \cap T = \emptyset

супераддитивность характеристической функции: коалиции вместе добывают не меньше, чем по отдельности, — математический смысл объединения

Частые вопросы

Чем кооперативная игра отличается от некооперативной?

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

Что такое вектор Шепли?

Правило дележа: каждому игроку достаётся его средний предельный вклад по всем возможным порядкам вхождения в коалицию. Например, входя, игрок поднял выигрыш коалиции с $5$ до $8$ — предельный вклад $3$ ; усредняем по всем порядкам. Шепли доказал, что это единственное деление с четырьмя аксиомами: эффективность, симметрия, нулевая доля игроку без вклада и аддитивность. Применяется в дележе издержек и голосованиях.