WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 | 2 || 4 | 5 |   ...   | 17 |

другим игрокам, так и элементы, описывающие реакцию на их Супераддитивные игры представляют собой в некотором сообщения. Основная идея теории кооперативных игр состоит в смысле типичный случай. Действительно, пусть имеются коалитом, чтобы, не рассматривая переговорный процесс как таковой, ции S и T с их выигрышами v(S) и v(T). Что мешает образующейся анализировать возможные его исходы и делать выводы о коалиции S T действовать так, как если бы такого объединения реализуемости того или иного результата переговоров. Поэтому и не существовало Тогда полезность этой коалиции будет как элементами описания игры в форме характеристической функминимум равна сумме полезностей коалиций S и T, обеспечивая ции – базовой модели теории кооперативных игр – являются не супераддитивность. Эти нестрогие рассуждения, как показано стратегии игроков, а выигрыши, которые может себе гарантирониже, верны лишь при некоторых предположениях.

вать та или иная коалиция.

Классическая теория [54, 67] рассматривает в основном Игра в форме характеристической функции может быть супераддитивные игры. Главные вопросы, которые встают при их построена на основе игры в нормальной форме. Так обычно и исследовании – это вопросы об условиях реализуемости максиприходится делать, потому что реальные конфликты обычно мальной коалиции N и справедливом распределении выигрыша формулируются сперва в нормальной форме – перечислением v(N) между игроками.

множества игроков, их стратегий и функций выигрыша. ХарактеОбычно игровые задачи, в том числе и задачи управления ристическая функция определяет выигрыш, получаемый коалициОС, ставятся в нормальной форме. Для исследования коалиционей S (если в процессе игры такая коалиция образовалась) при 16 ного взаимодействия игру необходимо перевести в форму обладать информацией о целевых функциях всех остальных характеристической функции. При этом процедура перехода игроков (а, значит, и всех возможных коалиций).

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

о стратегиях игроков, не входящих в коалицию и о структуре Описание игры в форме характеристической функции других образовавшихся коалиций. В этих условиях осторожные Определение 1 [67]: Игра в форме характеристической функции игроки должны использовать принцип максимального гарантирозадается множеством игроков N и характеристической функцией ванного результата (МГР) для оценки выигрыша коалиции, к которой они собираются присоединиться. Применение принципа v() на его подмножествах.

МГР для некоторой коалиции S состоит в минимизации Многими исследователями отмечалось [65, 67, 70, 83], что выигрыша коалиции по стратегиям игроков, не входящих в вопрос о порядке и способах взаимодействия игроков в теории коалицию S, и, затем, в максимизации выигрыша по стратегии кооперативных игр разработан недостаточно полно. Однако коалиции S. целью введения характеристической функции, как основы Под стратегией коалиции понимается вектор стратегий ее описания игры, является именно упрощение постановки задачи за участников, а под выигрышем коалиции – сумма их выигрышей. счет того, что подробности функционирования, такие как:

Характеристическая функция определяется выражением переговорный процесс, процесс образования коалиций, механизмы выработки совместной стратегии, и т.д. скрыты «внутри» (2) v(S) = max min [ fi (yS, yN \S )], ySAS yN \SAN \S iS характеристической функции игры. Такое смысловое наполнение где yS = (yi )iS AS = Ai – вектор действий участников характеристической функции может быть достаточно сложным, iS однако на уровне постановки задачи поведение игроков описывакоалиции S, а fi(.) – их целевые функции.

ется относительно просто.

В выражении (2) можно заменить чистые стратегии на Игроки в процессе игры выбирают, к какой коалиции им смешанные. Тогда v(S) будет в точности совпадать с нижним присоединиться и каким образом будет распределяться выигрыш значением [54, 68] антагонистической игры двух лиц – коалиции S этой коалиции. Затем, после образования коалиций, каждая из и коалиции N\S. Введенная таким образом характеристическая них получает выигрыш v(S), равный значению ее характеристичефункция всегда супераддитивна [70].

ской функции. Полученный выигрыш распределяется между Несмотря на удобство применения принципа МГР для членами коалиции согласно предварительной договоренности.

построения характеристической функции, дополнительная Обычно считается, что выигрыш коалиции равен значению информированность игроков может сделать более логичным характеристической функции для этой коалиции. Однако можно использование других концепций равновесия. Обратим внимание заметить, что характеристическая функция определяет гарантина то, что переговорный процесс должен сопровождаться рованный выигрыш, но, в общем случае, в результате игры передачей игроками друг другу информации о своих функциях коалиция может получить и выигрыш, больший гарантированвыигрыша, поскольку подобные данные могут оказывать ного, определяющего лишь минимальное значение выигрыша при существенное влияние на структуру коалиций. В связи с этим самых неблагоприятных условиях. Проблема распределения можно предположить, что к моменту окончательного выбора такого «неожиданного» дохода лежит за рамками исследования коалиции каждый игрок (а значит и любая коалиция) будет кооперативной теории игр, поскольку считается, что процесс 18 коалиционного взаимодействия опирается только на имеющуюся (7) i S xi > yi, информацию, в роли которой выступает характеристическая (8) xi v(S).

функция игры.

iS Если существует такая коалиция S, что x y, говорят, что S Определение дележа, доминирование дележей дележ x доминирует дележ y (обозначается x y ) [67]. Условие Определение 2 [67]: Эффективным распределением суперадди(7) означает, что дележ x лучше дележа y для всех участников тивной игры (N, v) называется такой вектор x = (x1, x2, …, xn), что коалиции S, а (8) отражает реализуемость дележа x коалицией S – (3) xi = v(N).

если оно выполнено, то коалиция действительно может предiN ложить своим участникам выигрыши xi.

Определение 3 [67]: Дележом для игры (N, v) называется Понятия дележа и доминирования дележей играют немалоиндивидуально-рациональное эффективное распределение, то есть важную роль в формулировках представленных ниже концепций эффективное распределение, для которого выполнены условия решения.

индивидуальной рациональности:

(4) xi v({i}), i N.

Концепции решения кооперативных игр Множество дележей игры (N, v) будем обозначать E(v).

В настоящее время в теории кооперативных игр, так же как и Условие (3) ограничивает понятие дележа лишь случаем, вообще в теории игр, не существует единой концепции решения когда игроки достигли достаточного взаимопонимания, чтобы [70, 83, 85]. Связано это, по всей видимости, с тем, что в начальобразовать коалицию, состоящую из всех игроков. Условие (4) ной стадии развития теории были разработаны достаточно предлагает рассматривать только распределения полезности, простые модели игр, которые легко поддавались анализу, и, дающие каждому игроку значения выигрыша не меньшие, чем он соответственно, простые концепции решений, такие, как C-ядро и получил бы, действуя в одиночку. Супераддитивная игра НМ-решения (см. ниже). По мере развития теории встал вопрос о называется существенной, если практической применимости полученных результатов. Для того, (5) v(N) > v({i}).

чтобы приблизить теорию к примерам встречающихся в жизни iN конфликтов, были разработаны более сложные модели, например, В противном случае супераддитивная игра называется игры с нетрансферабельной полезностью [67], игры «в разбиенинесущественной [67]. Несущественность игры означает нулевой ях» [67] и др. Параллельно появлялись как обобщения понятий эффект от кооперации. Действительно, выигрыш любой коалиции решения на эти более сложные модели, так и новые концепции в несущественной игре равен просто сумме индивидуальных вырешений.

игрышей ее участников. Множество дележей несущественной Некоторые концепции решения пришли в теорию игр из игры состоит из единственного элемента теорий общественного благосостояния и коллективного выбора (6) xi = v({i}), i N [18].

[50, 52, 74, 78]. Предметом исследования этих теорий является Обычно рассматриваются лишь существенные игры, так как задача выбора коллективных решений в обществе. Понятно, что вопрос о поиске решения среди дележей несущественной игры коллективный выбор должен быть (или желательно, чтобы был) тривиален.

единственным. Для сужения круга возможных решений эти Пусть x и y – два дележа, а S – произвольная коалиция.

теории пользуются аксиоматическими предположениями о Говорят, что дележ x доминирует дележ y по коалиции S стратегии принятия коллективных решений. В этих аксиомах (обозначается x y ), если S широко используется понятие «справедливого» распределения 20 благ (распределения выигрышей, полезности и т.д.). Применение Теорема Бондаревой [5]. С-ядро игры (N, v) не пусто тогда и аксиоматического подхода к теории кооперативных игр привело к только тогда, когда для любого сбалансированного покрытия () появлению понятий N-ядра [52] и вектора Шепли [1].

выполнено неравенство (11) v(S) v(N).

S C-ядро SN Если для некоторой кооперативной игры выполнено условие Если игроки пришли к такому дележу x выигрыша макси(11), то игра называется сбалансированной.

мальной коалиции, что не существует дележа, доминирующего Если характеристическая функция v игры имеет вид дележ x, то дележ x устойчив в том смысле, что никакой коалиции v(S) = u(S) + w(S) и игры u и w сбалансированы, то и игра v S не выгодно отделяться от коалиции N и делить между членами этой коалиции выигрыш v(S).

также сбалансирована [67].

Определение 4 [67]: Множество недоминируемых дележей игры Если для игры с характеристической функцией v найдется называется ее C-ядром1.

такая сбалансированная игра w, что Множество дележей, принадлежащих C-ядру, считается v(N) = w(N), S N v(S) w(S), решением кооперативной игры.

то игра v также сбалансирована [67].

Определение 5: Собственной коалицией называется коалиция, Несущественные игры отличная от максимальной коалиции (коалиции, состоящей из всех игроков).

Несущественность игры зачастую можно проверить еще на Теорема VII.4.2 [67]. Чтобы дележ x принадлежал C-ядру, той стадии исследования, когда известна только ее нормальная необходимо и достаточно выполнения для всех собственных форма.

коалиций S N неравенств Пусть полезность игроков линейно-трансферабельна.

(9) v(S) xi. * * Определение 7 [70]: Ситуация y* = (y1,..., yn ) называется сильiS ным равновесием Нэша игры n лиц с функциями выигрыша Решение этой системы линейных неравенств – это выпуклый fi (y1,..., yn ) и стратегиями yi Ai, i N, если для любой коалимногогранник в пространстве |N|. Можно найти его крайние ции S N и для любого ее действия yS Ai выполнено нераточки и описать любой дележ из C-ядра, как их взвешенную iS линейную комбинацию [39].

венство fi ( y* ) fi (yS, y* \S ), где y* \S – вектор компонент Необходимым и достаточным условием существования N N iS iS непустого С-ядра является свойство сбалансированности игры.

равновесной ситуации, относящихся к игрокам множества N \ S.

Определение 6 [5]: Для данного множества игроков N сбалансироИначе говоря, ситуация является сильным равновесием ванным покрытием называется такое отображение () из Нэша, если никакая коалиция не может выиграть, отклоняясь множества собственных коалиций 2N\{N} в отрезок [0, 1], что от равновесной ситуации.

(10) = 1 для всех игроков i N, S Можно заметить также, что суммарный выигрыш fi (.) S: iS iN где суммирование ведется по всем собственным коалициям, всех игроков в двух различных сильно равновесных ситуациях содержащим игрока i.

одинаков, иначе ситуация с меньшим доходом была бы неустойчивой относительно отклонения от нее максимальной коалиции.

От английского core – ядро.

22 Множество сильных равновесий Нэша может оказаться НМ-решения должны были решить проблему возможной пустым, однако если в некоторой игре с трансферабельной пустоты C-ядра. Однако в 1967 году была найдена игра десяти полезностью имеется единственное сильное равновесие Нэша, то лиц, не имеющая НМ-решений [79]. Обычно же игра имеет соответствующая кооперативная игра будет несущественной: огромное множество НМ-решений, что очень ограничивает Лемма [70]. Если в игре единственное равновесие Нэша, дающее применимость этого понятия к практическим задачам. НМрешения скорее представляют собой философскую категорию, игрокам выигрыши fi*, является сильным равновесием, и для чем практически применимую концепцию решения.

построения характеристической функции используется Заметим, что понятие НМ-решения оперирует дележом, как равновесие Нэша, то характеристическая функция получившейся выигрышем максимальной коалиции, то есть в определении игры будут иметь вид v(S) = fi* и будет несущественной.

предполагается, что максимальная коалиция все-таки образоваiS лась. Чтобы определить, каким же образом будет распределен НМ-решения доход между участниками максимальной коалиции, игроки должны сначала определить, в рамках какого НМ-решения они Поскольку C-ядро кооперативной игры слишком часто окабудут выбирать дележ, а потом выбрать дележ из множества зывается пустым, приходится искать другие концепции решения.

дележей, принадлежащих этому НМ-решению.

Понятие НМ-решения было введено Дж. фон-Нейманом и Поиск НМ-решений достаточно трудоемок ввиду их многоО. Моргенштерном [54].

численности. Примеры построения НМ-решений можно найти в Они предложили рассматривать в качестве множества [54, 67].

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

мости их модификаций. Так, Р. Ауман и М. Машлер [75], Идея, которая лежит в основе НМ-решений – это стремление предложили в качестве исхода игры использовать не дележи, а к внешней и внутренней устойчивости. Внутренняя устойчивость конфигурации, которые учитывают образование коалиционной гарантирует равноправность дележей одного НМ-решения, то структуры, отличной от максимальной коалиции.

Pages:     | 1 | 2 || 4 | 5 |   ...   | 17 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.