Свойства характеристической функции
Формальное определение
Для кооперативной игры рассмотрим некоторое упорядочение множества игроков 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 — это функция: 2N → R, из множества всех коалиций в множество вещественных чисел (так называемая характеристическая функция). Предполагается, что пустая коалиция зарабатывает ноль, то есть v(∅) = 0. Характеристическая функция описывает величину выгоды, которую данное подмножество игроков может достичь путем объединения в коалицию. Подразумевается, что игроки примут решение о создании коалиции в зависимости от размеров выплат внутри коалиции.
Свойства характеристической функции
- Монотонность — свойство, при котором у больших (в смысле включения) коалиций выплаты больше: если .
- Супераддитивность — свойство, при котором для любых двух непересекающихся коалиций A и B сумма их выгод по отдельности не больше их выгоды при объединении:
- Выпуклость — характеристическая функция является выпуклой:
Примеры игр
Простые игры — особый вид кооперативных игр, где все выплаты это 1 или 0, то есть коалиции либо «выигрывают», либо «проигрывают». Простая игра называется правильной, если:
.
Значение этого: коалиция выигрывает тогда и только тогда, когда дополняющая коалиция (оппозиция) проигрывает.
Не нашли, что искали? Воспользуйтесь поиском по сайту:
©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.
|