WWW.DISSERS.RU

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

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


Pages:     | 1 |   ...   | 9 | 10 || 12 | 13 |   ...   | 15 |

Обычно игровые задачи ставятся в нормальной форме. Для Базовая модель кооперативной игры разрешает передачу вы- исследования кооперативных взаимодействий игру необходимо игрыша между игроками, а это значит, что предполагается нали- перевести в форму характеристической функции. При этом прочие линейно-трансферабельного товара, например, денег (см. цедура перехода существенно зависит от используемого принципа раздел 2.2). рационального поведения. Для классической постановки задачи теории кооперативных игр характерно отсутствие информированХарактеристической функцией игры n лиц называется вещености членов коалиции о стратегиях игроков, не входящих в коаственнозначная функция36 v(S), определенная на подмножествах лицию. У членов коалиции не предполагается даже знания о SN, такая, что v()=0.

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

если В этих условиях осторожные игроки должны использовать (14) S, T 2N : S T = v(S) + v(T ) v(S T ), принцип МГР для оценки выигрыша коалиции, к которой они то есть для любых непересекающихся коалиций их объединение собираются присоединиться. Применение принципа МГР для неможет получить полезность не меньшую, чем эти коалиции могли которой коалиции S состоит в минимизации выигрыша коалиции бы в сумме получить, действуя по отдельности. В этих условиях по стратегиям игроков, не входящих в коалицию S, и, затем, в макобъединение в коалицию, включающую всех игроков, представсимизации выигрыша по стратегии коалиции S (см. раздел 4.1).

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

участников, а под выигрышем коалиции – сумма их выигрышей.

Характеристическая функция определяется выражением (15) v(S) = max min [ Ki ( yS, yN \ S )], В настоящей главе используются обозначения, принятые в работах ySAS yN \ S AN \ S iS по кооперативным играм. Можно надеяться, что совпадения символов (например, характеристической функции и функции полезности – см.

раздел 1.1, и др.) не приведут к путанице.

95 5.3. Описание игры в терминах где yS = (yi )iS AS = Ai – вектор действий участников коа iS характеристической функции лиции S.

Определение 22: Игра в форме характеристической функции Можно заменить чистые стратегии на смешанные. Тогда v(S) задается множеством игроков N и характеристической функцией будет в точности совпадать с решением антагонистической игры v() на его подмножествах.

двух лиц – коалиции S и коалиции N\S [17, 48, 65].

Одним из часто встречающихся видов игр являются игры с Введенная таким образом характеристическая функция супостоянной суммой.

пераддитивна [65].

Определение 23: Кооперативная игра (N, v) называется игрой Несмотря на удобство использования максимина (то есть с постоянной суммой, если для любой коалиции S справедливо применения принципа МГР) для построения характеристической равенство функции, дополнительная информированность игроков может (16) v(S) + v(N \ S) = v(N ).

сделать более логичным использование других концепций равноМногими исследователями отмечалось, что вопрос о порядке весия. Обратим внимание на то, что переговорный процесс должен и способах взаимодействия игроков в теории кооперативных игр сопровождаться передачей игроками друг другу информации о разработан недостаточно полно. Однако целью введения характесвоих функциях выигрыша, поскольку подобные данные могут ристической функции, как основы описания игры, является именно оказывать существенное влияние на структуру коалиций. В связи с упрощение постановки задачи за счет того, что подробности этим можно предположить, что к моменту окончательного выбора функционирования, такие как: переговорный процесс, процесс коалиции каждый игрок (а, значит, и любая коалиция) будет образования коалиций, механизмы выработки совместной стратеобладать информацией о целевых функциях всех остальных иггии, и пр. скрыты «внутри» характеристической функции игры.

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

ствий, наихудших для коалиции S, как предписывает максимин Игроки в процессе игры выбирают, к какой коалиции им (напомним, что в играх с произвольной суммой минимаксная присоединиться, и каким образом будет распределяться выигрыш стратегия второго игрока может не совпадать с наихудшим, с этой коалиции. Затем, после образования коалиций, каждая из них точки зрения первого игрока, его поведением). Такие модификаполучает выигрыш v(S), равный значению ее характеристической ции процедуры построения характеристической функции могут функции. Полученный выигрыш распределяется между членами приблизить модель к реальному процессу переговоров, однако при коалиции согласно предварительной договоренности.

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



стниками.

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

ожиданного» дохода лежит за рамками исследования кооперативМножество дележей несущественной игры состоит из единной теории игр, так как этот «бонус» не влияет на рациональную, с ственного элемента точки зрения игроков, структуру коалиций. Считается, что процесс (20) xi = v({i}), i N.

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

определений дележа и несущественной игры (см. (18)-(20)).

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

вопрос о поиске решения среди дележей несущественной игры тривиален.

5.4. Определение дележа, доминирование дележей Пусть x и y – два дележа, и S – произвольная коалиция. ГоОпределение 24: Эффективным распределением супераддиворят, что x доминирует y по коалиции S (обозначается x y ), S тивной игры (N, v) называется вектор x = (x1, x2, …, xn), такой, что если (17) = v(N).

xi (21) xi > yi i S, iN Определение 25: Дележом для игры (N, v) называется эффек- (22) v(S).

xi iS тивное распределение, удовлетворяющее условию Если существует коалиция S, такая, что x y, говорят, что x (18) xi v({i}), i N.

S доминирует y (обозначается x y ).

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

Условие (17) ограничивает понятие дележа лишь случаем, коУсловие (21) означает, что дележ x лучше дележа y для членов гда игроки достигли достаточного взаимопонимания, чтобы обракоалиции S, а условие (22) отражает реализуемость дележа x коазовать коалицию, состоящую из всех игроков. Условие (18), назылицией S – если оно выполнено, то коалиция действительно может ваемое еще индивидуальной рациональностью (individual rationalпредложить своим участникам выигрыши xi.

ity), предлагает рассматривать только распределения полезности, Определение 26: Игры n лиц с характеристическими функциядающие каждому игроку значения выигрыша не меньшие, чем он ми u и v называются изоморфными, если существует функция f, получил бы, действуя в одиночку. Это условие позволяет сразу огвзаимно однозначно отображающая множество дележей игры u на раничится рассмотрением только множества индивидуально рамножество дележей игры v таким образом, что для любой пары циональных распределений дохода между игроками.

дележей x и y игры u и произвольной коалиции S из доминироваОпределение дележа приводит к понятию существенных игр. ния дележа x дележом y следует доминирование образа f(x) обраСупераддитивная игра называется существенной, если зом f(y). Иначе говоря, x y f (x) f (y), где f() – дележи S S (19) v(N ) > игры v.

v({i}).

iN При анализе свойств игры с помощью отношения доминироВ противном случае супераддитивная игра называется несувания полезно знать, у каких игр множества дележей имеют одищественной [62].

99 наковую структуру доминирования, то есть какие игры являются Некоторые концепции решения пришли в теорию игр из изоморфными. теорий общественного благосостояния и кооперативного выбоОпределение 27: Игры n лиц u и v называются S- ра [46, 79]. Темой исследования этих теорий является задача выэквивалентными, если существует положительное число r и n та- бора коллективных решений. Понятно, что коллективный выбор должен быть (или желательно, чтобы был) единственным. Для ких вещественных чисел 1,…,n, что для любой коалиции S N сужения круга возможных решений эти теории пользуются ак(23) v(S) = r u(S) +.

i сиоматическими предположениями о стратегии принятия коллекiS тивных решений. В этих аксиомах широко используется понятие Теорема 7 [62]. Если u и v являются S-эквивалентными, то «справедливого» распределения благ (то есть распределения выони изоморфны.

игрышей, полезности и т.д.).

Определение 28: Игра v называется игрой в (0, 1)С понятием справедливости в условиях принятия решения редуцированной форме, если i N v({i}) = 0, v(N ) = 1.

обществом связана отдельная проблематика. Аксиоматический Теорема 8 [62]. Любая существенная игра S-эквивалентна одподход предполагает, что при исследовании ситуации выбора, для ной и только одной игре в (0, 1)-редуцированной форме.

того, чтобы обосновать выбор общества, исследователь делает Таким образом, определение 27 вводит классы игр, изопредположения, более или менее очевидные, о моральных усморфных относительно операции доминирования, теорема 7 дает тановках данного общества, и, тем самым, определяет, что в данудобный способ проверки изоморфности игр, а теорема 8 утверном обществе понимается под справедливостью. Парадокс состоит ждает, что анализ игр с помощью отношения доминирования в том, что многие соответствующие здравому смыслу по отможно ограничить анализом игр в (0, 1)-редуцированной форме.





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

ными концепциями справедливого распределения благ являются эгалитаризм и утилитаризм [46]. Эгалитаризм утверждает, что 5.5. Концепции решения кооперативных игр при распределении благ в первую очередь следует обращать вниВ теории кооперативных игр, также как и вообще в теории мание на полезность наиболее «обделенных» членов общества.

игр, не существует единой концепции решения. Это связано с тем, Утилитаризм же считает справедливым «эффективное» распредечто на начальной стадии развития теории были разработаны ление, приводящее к наибольшему значению суммы полезностей достаточно простые модели игр, которые легко поддавались аначленов общества. Применение этих концепций к теории кооперализу, и, соответственно, простые концепции решений, такие, как тивных игр приводит к понятиям N-ядра и вектора Шепли соотC-ядро и НМ-решения (см. ниже). По мере развития теории встал ветственно (см. разделы 5.11 и 5.12).

вопрос о практической применимости полученных результатов.

Все концепции решения кооперативных игр, определяющие в Для того чтобы приблизить теорию к примерам игр, встречаюкачестве решения единственное распределение полезности между щихся в жизни, были разработаны более сложные модели, наигроками, называются значениями игры (см. раздел 5.10).

пример, игры с нетрансферабельной полезностью, игры «в разбиениях» и др. Параллельно появлялись как обобщения понятий решения на эти более сложные модели, так и новые концепции решений – см. ниже.

101 5.6. C-ядро Неравенства (25) делят симплекс на области, границы котоЕсли игроки пришли к такому дележу x выигрыша макси- рых параллельны одной из его сторон. С-ядро выделено на рисунмальной коалиции, что не существует дележа, доминирующего де- ке черным цветом. В зависимости от вида характеристической леж x, то дележ x устойчив в том смысле, что никакой коалиции S функции оно может быть множеством трех-, четырех-, пяти- и не выгодно отделяться от коалиции N и делить между членами шестиугольной формы, может вырождаться в линию или точку.

этой коалиции выигрыш v(S). Оно может быть и пустым множеством. • Определение 29: Множество недоминируемых дележей игры называется ее C-ядром.

Множество дележей, принадлежащих C-ядру, считается решением кооперативной игры.

Теорема 9 [46]. Для того чтобы дележ x принадлежал C-ядру, необходимо и достаточно выполнения для всех SN неравенств (24) v(S).

xi iS Доказательство очевидно. • Эта теорема дает удобный способ нахождения C-ядра путем решения системы неравенств. Решением этой линейной системы Рис. 9. С-ядро в игре с тремя игроками является выпуклый многогранник в пространстве |N|. Можно найти его крайние точки и описать любой дележ из ядра, как Итак, C-ядро существует не для всех игр. Например, все коовзвешенную линейную комбинацию крайних точек.

перативные игры с постоянной суммой имеют пустое C-ядро.

Пример 18. «Нахождение C-ядра игры трех лиц».

Необходимым и достаточным условием существования неРассмотрим игру трех лиц с характеристической функцией пустого ядра является свойство сбалансированности игры.

v(S): v({1}) = v({2}) = v({3}) = 0, v({1,2}) = 0.5, v({1,3}) = 0.6, Определение 30: Максимальной коалицией называется коалиv({2,3}) = 0.7, v(N ) = 1. Условие на дележи, принадлежащие C- ция, состоящая из всех игроков.

Определение 31: Собственной коалицией называется коалиядру, задается системой неравенств:

ция, отличная от максимальной коалиции.

x1 + x2 0. Определение 32: Для данного множества игроков N сбалансиx + x3 0. рованным покрытием называется такое отображение из 2N\{N} () (25) x + x3 0.в [0, 1], что x1 + x2 + x3 = 1.

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

3 неравенствами xi 0, i = 1,3, и равенством = v(N ) =xi Теорема 10 [7, 8]. С-ядро игры (N, v) не пусто тогда и только iN тогда, когда для любого сбалансированного покрытия () выпол(изображен на рисунке 9 серым цветом).

нено неравенство 103 v(S {i1}) - v(S) v(S {i1}) - v(T ), (27) v(S) v(N).

S S N v(S {i1,i2}) - v(S {i1}) v(S {i1,i2}) - v(T {i1}), Если для игры выполнено условие (27), то игра называется...

сбалансированной.

v(S {i1,...,ik }) - v(S {i1,...,ik-1}) Например, для супераддитивной игры трех лиц непустоту Cядра гарантирует следующее дополнительное (к условиям суперv(T {i1,...,ik }) - v(T {i1,...,ik-1}) аддитивности) условие v({1,2}) + v({1,3}) + v({2,3}) 2v(N). Для...

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

R' R верно следующее неравенство:

v(S R') - v(S) v(T R') - v(T ).

Pages:     | 1 |   ...   | 9 | 10 || 12 | 13 |   ...   | 15 |










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

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