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

Формальное определение

Для кооперативной игры рассмотрим некоторое упорядочение множества игроков N. Обозначим через подмножество, содержащее i первых игроков в данном упорядочении. Вкладом i-го по счету игрока назовем величину , где v — характеристическая функция кооперативной игры.

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

Вектором Шепли кооперативной игры называется такое распределение выигрыша, в котором каждый игрок получает математическое ожидание своего вклада в соответствующие коалиции , при равновероятном возникновении упорядочений:

где n — количество игроков, T — множество упорядочений множества игроков N, — распределение выигрыша, в котором игрок, стоящий на месте i в упорядочении , получает свой вклад в коалицию (точка Вебера).

Более распространенная формула для вычисления вектора Шепли, не требующая нахождения n! точек Вебера, имеет вид:

где n — количество игроков, k — количество участников коалиции K.

Аксиоматика вектора Шепли

Вектор Шепли удовлетворяет следующим свойствам:

1. Линейность. Отображение представляет собой линейный оператор, то есть для любых двух игр с характеристическими функциями v и w

и для любой игры с характеристической функцией v и для любого

2. Симметричность. Получаемый игроком выигрыш не зависит от его номера. Это означает, что если игра w получена из игры v перестановкой игроков, то ее вектор Шепли есть вектор с соответствующим образом переставленными элементами.

3. Аксиома болвана. Болваном в теории кооперативных игр называется бесполезный игрок, не вносящий вклада ни в какую коалицию, то есть игрок i, такой что для любой коалиции K, содержащей i, выполнено: .

Аксиома болвана состоит в том, что если игрок i — болван, то .

4. Эффективность. Вектор Шепли позволяет полностью распределить имеющееся в распоряжении тотальной коалиции благосостояние, то есть сумма компонент вектора равна .

Теорема Шепли. Для любой кооперативной игры v существует единственное распределение выигрыша, удовлетворяющее аксиомам 1 — 4, задаваемое приведенной выше формулой.

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

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

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

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

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

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

• Монотонность — свойство, при котором у больших (в смысле включения) коалиций выплаты больше: если .

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

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

Примеры игр

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

.

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: