<< Предыдушая Следующая >>

Характеристическая функция игры

Теорию кооперативных игр интересует в основном то, какие коалиции образуются в процессе игры и какие условия необходимы для устойчивого существования коалиций.
Игра в нормальной форме, как достаточно подробное описание конфликтной ситуации, оказалась слишком сложной моделью для исследования кооперативных взаимодействий игроков. Чтобы описать с помощью игры в нормальной форме даже самый простой переговорный процесс между игроками, требуется немыслимое усложнение множества их стратегий, включающее в себя как элементы, соответствующие передаче информации другим игрокам, так и элементы, описывающие реакцию на их сообщения. Основная идея теории кооперативных игр состоит в том, чтобы, не рассматривая переговорный процесс как таковой, анализировать возможные его исходы и делать выводы о реализуемости того или иного результата переговоров. Поэтому и элементами описания игры в форме характеристической функции - базовой модели теории кооперативных игр - являются не стратегии игроков, а выигрыши, которые может себе гарантировать та или иная коалиция.
Игра в форме характеристической функции может быть построена на основе игры в нормальной форме. Так обычно и приходится делать, потому что реальные конфликты обычно формулируются сперва в нормальной форме - перечислением множества игроков, их стратегий и функций выигрыша. Характе-ристическая функция определяет выигрыш, получаемый коалицией S (если в процессе игры такая коалиция образовалась) при
рациональных действиях ее участников [70]. Решение о том, что понимать в каждом конкретном случае под рациональными действиями игроков, принимается из анализа игры в нормальной форме и выбранной модели рационального поведения.
Базовая модель кооперативной игры разрешает передачу выигрыша между игроками, а это значит, что предполагается наличие линейно-трансферабельного товара [72], например, денег. Это предположение типично для экономических моделей, к которым относятся и модели управления ОС.
Характеристической функцией игры п лиц называется такая вещественнозначная функция v(S), определенная на подмножествах S с 7V множества игроков N, что v(0) = 0 [67]. Характеристическая функция называется супераддитивной, если (1) MS,T = 0 v(S) + V(T)то есть для любых непересекающихся коалиций их объединение может получить полезность не меньшую, чем эти коалиции могли бы в сумме получить, действуя по отдельности [67]. В этих условиях объединение в коалицию, включающую всех игроков, представляет собой самое эффективное с точки зрения суммарной полезности поведение участников игры, однако устойчивость этой коалиции требует дополнительного исследования (см. ниже).
Супераддитивные игры представляют собой в некотором смысле типичный случай. Действительно, пусть имеются коалиции S и 7 с их выигрышами v(.V) и v(7). Что мешает образующейся коалиции S U Т действовать так, как если бы такого объединения не существовало? Тогда полезность этой коалиции будет как минимум равна сумме полезностей коалиций S и Т, обеспечивая супераддитивность. Эти нестрогие рассуждения, как показано ниже, верны лишь при некоторых предположениях.
Классическая теория [54, 67] рассматривает в основном супераддитивные игры. Главные вопросы, которые встают при их исследовании - это вопросы об условиях реализуемости максимальной коалиции N и справедливом распределении выигрыша v(N) между игроками.
Обычно игровые задачи, в том числе и задачи управления ОС, ставятся в нормальной форме. Для исследования коалицион-
ного взаимодействия игру необходимо перевести в форму характеристической функции. При этом процедура перехода существенно зависит от используемого принципа рационального поведения игроков.
Для классической постановки задачи теории кооперативных игр характерно отсутствие информированности членов коалиции о стратегиях игроков, не входящих в коалицию и о структуре других образовавшихся коалиций. В этих условиях осторожные игроки должны использовать принцип максимального гарантированного результата (МГР) для оценки выигрыша коалиции, к которой они собираются присоединиться. Применение принципа МГР для некоторой коалиции S состоит в минимизации выигрыша коалиции по стратегиям игроков, не входящих в коалицию S, и, затем, в максимизации выигрыша по стратегии коалиции S.
Под стратегией коалиции понимается вектор стратегий ее участников, а под выигрышем коалиции - сумма их выигрышей. Характеристическая функция определяется выражением (2) v(S) = max min E/JOWms)],
ys^AS yN\SGAN\S iGS
где = (.уДея e = ДД - вектор действий участников
i<=S
коалиции S, afi(.) - их целевые функции.
В выражении (2) можно заменить чистые стратегии на смешанные. Тогда v(.V) будет в точности совпадать с нижним значением [54, 68] антагонистической игры двух лиц - коалиции S и коалиции N\S. Введенная таким образом характеристическая функция всегда супераддитивна [70].
Несмотря на удобство применения принципа МГР для построения характеристической функции, дополнительная информированность игроков может сделать более логичным использование других концепций равновесия. Обратим внимание на то, что переговорный процесс должен сопровождаться передачей игроками друг другу информации о своих функциях выигрыша, поскольку подобные данные могут оказывать существенное влияние на структуру коалиций. В связи с этим можно предположить, что к моменту окончательного выбора коалиции каждый игрок (а значит и любая коалиция) будет
обладать информацией о целевых функциях всех остальных игроков (а, значит, и всех возможных коалиций).
Тогда коалиция S должна ожидать от остальных игроков действий, направленных на максимизацию их функций полезности, а не действий, наихудших для коалиции S, как предписывает МГР.
<< Предыдушая Следующая >>
= Перейти к содержанию учебника =
Информация, релевантная "Характеристическая функция игры"
  1. Описание игры в форме характеристической функции
    Определение 1 [67]: Игра в форме характеристической функции задается множеством игроков N и характеристической функцией v(-) на его подмножествах. Многими исследователями отмечалось [65, 67, 70, 83], что вопрос о порядке и способах взаимодействия игроков в теории кооперативных игр разработан недостаточно полно. Однако целью введения характеристической функции, как основы описания игры, является
  2. Кооперативное взаимодействие центров в ОС с распределенным контролем
    Для исследования возможностей кооперации центров в рассматриваемой игре построим характеристическую функцию v(S), ставящую в соответствие каждой коалиции суммарный выигрыш, на который могут рассчитывать ее участники, играя совместно. Будем считать, что характеристическая функция определяется как равновесный по Нэшу выигрыш коалиции S в игре с коалицией N\S, состоящей из всех остальных центров.
  3. Вектор Шепли
    Определение 14 [52]: Оператор значения анонимен, если он коммутирует с перестановкой агентов, то есть при перестановке двух игроков местами соответственно переместятся и компо-ненты значения игры. Определение 15 [52]: Оператор значения маргинален, если его значение зависит только от маргинальных вкладов игроков в коалиции, то есть от величин v(S U !'!) - v'(.V). Определение 16 [52]: Носителем
  4.   § 7. О - 1-РЕДУЦИРОВАННАЯ ФОРМА
      7.1. По многим соображениям, и в том числе для возможностей сравне&ния значений различных характеристических функций на одной и той же коалиции, представляется удобным произвести своего рода нормировку характеристических функций. Определение. Характеристическая функция v над / назьюается 0 — 1 -редуцированной (имеет 0 — 1-редуцированную форму) , если v(i) = 0 для любого
  5. Модель принятия решений
    Рассмотрим ОС, состоящую из центра и п агентов, обладающих свойством активности, то есть собственными предпочтениями и способностью самостоятельно предпринимать некоторые действия [34]. Опишем модель принятия решений агентом. Для того чтобы определить, как задаются предпочтения агентов, введем следующее описание взаимодействия каждого агента с его обстановкой, в которую могут входить другие
  6.   § 8. ПЕРЕЧИСЛЕНИЕ ХАРАКТЕРИСТИЧЕСКИХ ФУНКЦИЙ С МАЛЫМ ЧИСЛОМ ИГРОКОВ
      В соответствии со сказанным в п. 7.4 мы будем для любого числа и игроков фиксировать наличие нулевой характеристической функции как представителя класса несущественных характеристических функций, а также перечислять все 0 - 1-редуцированные характеристические функции как представителей классов существенных характеристических функций. Из сказанного в п. 4.1 следует, что каждая
  7.   ОСНОВНЫЕ ОБОЗНАЧЕНИЯ
      Основной рассматриваемый в данной книге объект — игра — представляет со&бой теоретико-игровую конструкцию, в образовании которой участвуют мно&жества с элементами различной природы. Для элементов большинства вводи&мых далее множеств мы будем использо&вать следующие обозначения: і, j, к - игроки в бескоалиционной игре; Xj, x'j, yj,... - чистые стратегии игро&ка і в бескоалиционной
  8.   § 15*. с-ЯДРО В ИГРАХ ЧЕТЫРЕХ ЛИЦ
      Ввиду разнообразия возможностей доминирования дележей в играх четырех лиц (см. пп. 12.5—12.7) перечисление всех вариантов формы расположения с-ядра представляется для таких игр достаточно громоздким. Однако наглядное геометрическое представление о с-ядре, построение его для каждой конкретной игры и, тем более, суждение о принадлежности с-ядру того или иного дележа выглядят достаточно просто.
  9.   § 21. СУЩЕСТВОВАНИЕ И ЕДИНСТВЕННОСТЬ ВЕКТОРА ШЕПЛИ
      21.1. Найдем сначала вектор Шепли для характеристической функции вида cvR, где vR — простейшая характеристическая функция (см. п. 4.2), ас > 0. Теорема. Для вектора Шепли Ф(сі>д) характеристической функции cvR (где с > 0) должно быть с IR I Ф/(с^) = (21.1) если і ЄR, 0,              если і Є
  10.   § 24. ВЕКТОР ШЕПЛИ ДЛЯ ИГР ТРЕХ ЛИЦ
      В отдельных случаях формула (21.4) для компонент вектора Шеп&ли допускает более "замкнутое" их описание. Помимо простейших игр (см. п. 21.1), это удается сдедать, например, для игр трех лиц. Ввиду сказанного в п. 20.4 мы можем ограничиться существенными иг&рами, а ввиду сказанного в п. 21.8 — играми в 0—1-редуцированной форме. Теорема. Если v- характеристическая функция
  11. Несущественные игры
    Несущественность игры зачастую можно проверить еще на той стадии исследования, когда известна только ее нормальная форма. Пусть полезность игроков линейно-трансферабельна. Определение 7 [70]: Ситуация у* = (у*,...,у*) называется сильным равновесием Нэша игры п лиц с функциями выигрыша fi(yl,...,yn) и стратегиями уг. е Д¦, ieN, если для любой коалиции S с N и для любого ее действия ys е Y\Ai
  12.   § 13. с-ЯДРО
      Как указывалось, доминирование дележом х дележа у можно понимать как предпочтение дележа х дележу у со стороны одной из коа&лиций. Это можно понимать так, что всякая попытка предложить "общест&ву" дележ у может встретить со стороны этой коалиции контрпредложение дележа х. Значит, дележ, который не доминируется никаким другим де&лежом, можно считать в известном смысле "вполне устойчивым".
  13.   § 5. КООПЕРАТИВНАЯ ТЕОРИЯ
      5.1. Каждая бескоалиционная игра Г = </, { х,} /є/, {Я,},.е/>              (51) описывает некоторый, вообще говоря, достаточно сложный конфликт, не всегда поддающийся не только детальному изучению, но и даже точному описанию. Поэтому представляется естественным выбирать в этом кон&фликте отдельные его аспекты и подвергать их специальному анализу. Быть может, самым простым
  14.   § 3. РЕАЛИЗАЦИЯ ХАРАКТЕРИСТИЧЕСКИХ ФУНКЦИЙ
      3.1. Конструкция характеристической функции бескоалиционной игры является для общей теории характеристических функций в некотором смысле универсальной. Теорема. Какова бы ни была функция v: 2Z-*R              (3.1) с конечным множеством игроков /, обладающая свойствами персоналъ- ности и супераддитивности, существует конечная бескоалиционная игра r = </,{x,}.er
  15.   § 10. ДЕЛЕЖИ И ХАРАКТЕРИСТИЧЕСКИЕ ФУНКЦИИ
      Присоединение к заданию характеристической функции множества допустимых дележей, т.е. ее превращение в кооперативную игру, можно рассматривать как своего рода оптимальное решение задачи, которая описывается характеристической функцией. Это значит, что характеристи&ческая функция бескоалиционной игры находит в соответствующей ей кооперативной игре некоторое свое оптимизационное уточнение. Однако
  16.   § 2. АБСТРАКТНЫЕ ХАРАКТЕРИСТИЧЕСКИЕ ФУНКЦИИ
      Говоря абстрактно, характеристическая функция бескоалиционной игры состоит в постановке в соответствие каждому подмножеству некоторо&го множества (игроков) вещественного числа. Поэтому о ней можно го&ворить и вне какой-либо связи с бескоалиционными играми. На этом пути возникает весьма плодотворное понятие кооперативной игры, о которой речь будет идти ниже. Определение.
Портал "ФИНАНСЫ-КРЕДИТ" © 2014
sci@all-sci.net

Рейтинг@Mail.ru