Кооперативная игра (математика)

Кооперативная игра — термин теории игр. Кооперативной называется игра, в которой группы игроков — коалиции — могут объединять свои усилия. Этим она отличается от игр, в которых коалиции неприемлемы и каждый обязан играть за себя. Примером такой игры может являться карточная игра в дурака «двое на двое» или «трое на трое», либо разыгрывание «втёмную» виста в преферансе.

Развлекательные игры редко являются кооперативными, из-за отсутствия механизмов, которые могли бы навязывать координацию действий между членами коалиции. Однако такие механизмы нередки в повседневной жизни.

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

Математическое представление

Согласно определению, кооперативной игрой называется пара (N,v), где N - это множество игроков, а v - это функция: 2^N → R, из множества всех коалиций в множество вещественных чисел (так называемая характеристическая функция). Предполагается, что пустая коалиция зарабатывает ноль, т.е. v(∅) = 0. Характеристическая функция описывает величину выгоды, которую данное подмножество игроков может достичь путем объединения в коалицию. Подразумевается, что игроки примут решение о создании коалиции в зависимости от размеров выплат внутри коалиции.

Свойства характеристической функции

Монотонность —- свойство, при котором у больших (в смысле включения) коалиций выплаты больше: если $A \sube B \rArr v(A) \le v(B)$.

Супераддитивность —- свойство, при котором для любых двух непересекающихся коалиций A и B сумма их выгод по-отдельности не больше их выгоды при объединении:

$A \cap B= \emptyset \Rightarrow v(A \cup B) \ge v(A) + v(B)$

Выпуклость -- характеристическая функция является выпуклой, если

$v(A \cup B) + v(A \cap B) \ge v(A) + v(B)$

Примеры игр

Простые игры —- особый вид кооперативных игр, где все выплаты это 1 или 0, то есть коалиции либо «выигрывают», либо «проигрывают». Простая игра называется правильной, если:

$v(A)=1-v(N \setminus A)$.

Значение этого: коалиция выигрывает тогда и только тогда, когда дополняющая коалиция (оппозиция) проигрывает.

Решение кооперативных игр

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

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

Решение может быть как однозначным (в этом случае для каждой игры решением является единственное распределение выигрышей), так и многозначным (когда для каждой игры могут быть определены несколько распределений). Примерами однозначных решений служат N-ядро и вектор Шепли, примерами многозначных - C-ядро и K-ядро.

• С-ядро
• N-ядро
• K-ядро
• Вектор Шепли

Источники

Текст статьи на английском Cooperative game