WWW.DISSERS.RU

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

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


Pages:     | 1 |   ...   | 10 | 11 || 13 | 14 |   ...   | 15 |

5.7. Выпуклые игры Зафиксируем две произвольные коалиции S0 и T0 и применим Свойство сбалансированности в общем случае достаточно полученную формулу к S = S0 T0, T = T0 и R' = S0 \ T0. Это и сложно проверить (проверка сбалансированности игры сводится к дает искомое определение выпуклости. • решению задачи линейного программирования), поэтому встает Условие выпуклости иногда называют условием возрастания вопрос о построении достаточных условий непустоты ядра, опредоходов от кооперации, то есть игрок, присоединяясь к большей деляющих классы игр, для которых C-ядро гарантированно не коалиции, приносит ей дополнительный доход, больший, чем допусто.

полнительный доход, который он принес бы, присоединяясь к Определение 33: Игра (N, v) называется выпуклой, если для меньшей коалиции.

любых коалиций S, TN справедливо неравенство Выпуклость игры проверить гораздо проще, чем условие v(S) + v(T ) v(S T ) + v(S T ).

сбалансированности (просто проверив вышеуказанные 22N нераТеорема 11 [46]. Любая выпуклая игра имеет непустое C-ядро.

венств), и, если игра оказалась выпуклой, можно с уверенностью Другая формулировка выпуклости игры может быть дана в говорить о непустоте С-ядра.

виде следующего критерия:

Пример 19 [25]. «Кооперация центров в задаче распределенТеорема 12 [46]. Игра (N, v) выпукла тогда и только тогда, коного контроля».

гда для любых коалиций S, T N, таких, что S T и любого i T Исследуем возможности устойчивого существования коалисправедливо v(S {i}) - v(S) v(T {i}) - v(T ).

ции, состоящей из всех центров в задаче распределенного контроля Доказательство. Покажем, что из определения выпуклости (см. пример 3). Будем считать, что такая коалиция устойчива, если следует, что для любых коалиций S, TN, таких, что S T и люнепусто C-ядро соответствующей кооперативной игры.

бого i T справедливо v(S {i}) - v(S) v(T {i}) - v(T ).

В [25] приведены предположения, в рамках которых харакДействительно, эта формула является частным случаем оп- теристическую функцию игры центров в этой задаче можно представить в виде (см. обозначения примера 3):

ределения выпуклости для пары коалиций S{i} и T.

Для доказательства в обратную сторону рассмотрим две коа(28) v(S) = max[ ( y) - c( y)], где S N.

Hi y iS лиции S и T, такие, что ST. Обозначим R=N\T и рассмотрим поРассмотрим частный случай линейных функций доходов ценследовательность {i1, i2, …, ir}, покрывающую R. Последовательно тров, то есть будем считать, что H ( y) = i y, i > 0. Затраты применяя формулу в условии теоремы, получим:

i 105 агента, как и предполагалось в постановке задачи, будем считать Продифференцируем f(.) по S :

неотрицательной возрастающей выпуклой функцией действия y.

f '(S ) := g(S ) + S g'(S ) - c'(g(S ))g'(S ). Из (29) следует, что Обозначим S := – наклон функции дохода коалиции S, i c'(g(S )) = S. Значит, f ' (S ) = g(S ). Следовательно, f(.) выiS пукла. Кроме того, очевидно, что f (0) = 0, а значит условие лемyS – точка, в которой достигается максимум (28).

мы выполнено, и игра (28) выпукла. Значит, по теореме 11, эта Для произвольной коалиции S точка yS определяется из реигра имеет непустое C-ядро, и в ней устойчива коалиция, состояшения уравнения c'(y) =. Таким образом, i щая из всех центров. • iS 5.8. НМ-решения (29) yS = g(S ), g(S ) := [c']-1(S ).

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

Так как функция затрат выпукла, [c']-1(S ) – возрастающая Понятие НМ-решения было введено Дж. Фон-Нейманом и функция.

О. Моргенштерном [48]. Этот факт нашел отражение и в названии Игра с характеристической функцией (28) супераддитивна.

НМ-решений, которые обычно называют решениями по Нейману и Действительно, из (28) следует, что она супераддитивна, если спраМоргенштерну.

ведливо неравенство Они предложили рассматривать в качестве множества решеS yS - c(yS ) + T yT - c(yT ) (S + T )yS T - c(yS T ), (30) ний игры не отдельный дележ, и даже не множество дележей, а S,T N, S T =.

множество подмножеств множества дележей, обладающих опреПусть S T. Тогда из возрастания g(.) следует, что деленными свойствами. Каждое из этих подмножеств называется НМ-решением.

yS T yT yS, Идея, которая лежит в основе НМ-решений – это стремление к и, следовательно, внешней и внутренней устойчивости. Внутренняя устойчивость (S + T )yS T - c( yS T ) (S + T )yT - c(yT ).

гарантирует равноправность дележей одного НМ-решения, то есть Значит, для справедливости (30) достаточно выполнения нето, что в НМ-решении нельзя найти пару дележей, такую, что один равенства yT yS - c(yS ). Оно верно, так как yS yT, из них доминирует другой. Внешняя устойчивость состоит в том, i i iS iS что для любого произвольного дележа найдется доминирующий c() 0.

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

Для того чтобы показать, что игра (28) выпукла, воспользуемМножество VE(v) называется НМ-решением, если ся следующим результатом:

1) Не существует такой пары x, yV, что x y ;

Лемма 4 [25]. Если v(S) = f ( ), где f() – произвольная i 2) Если yV, то найдется такой xV, что x y.

iS Между НМ-решениями и C-ядром существует определенная выпуклая функция, f (0) = 0, а i, i N – набор неотрицательсвязь. Так, справедлива ных чисел, то игра v() выпукла. • Теорема 13 [62]. Если C-ядро не пусто, и существует НМПодставим (29) в (28). Тогда решение, то оно содержит в себе C-ядро.



v(S) = f (S ), f (S ) := S g(S ) - c(g(S )).

107 НМ-решения должны были решить проблему возможной пус- Определение 35: Конфигурацией для игры (N, v) и коалиционтоты C-ядра. Однако в 1967 году была найдена игра десяти лиц, не ной структуры P называется такое распределение дохода имеющая НМ-решений [78]. Обычно же игра имеет огромное x = {(xi,i S); S P} между участниками коалиций, что множество НМ-решений, что очень ограничивает применимость (31) = v(S), S P, xi этого понятия к практическим задачам. НМ-решения скорее iS представляют собой философскую категорию, чем практически (32) xi v({i}), i N.

применимую концепцию решения.

Здесь же определим понятия, которые понадобятся ниже при Заметим, что понятие НМ-решения оперирует дележом как описании решений в угрозах и контругрозах (см. раздел 5.13).

выигрышем максимальной коалиции, то есть в определении Определение 36: Индивидуально рациональной называется предполагается, что максимальная коалиция все-таки образоваконфигурация x, в которой для всех игроков i справедливо лась. Чтобы определить, каким же образом будет распределен xi v({i}) (все конфигурации, удовлетворяющие формуле (32), доход между участниками максимальной коалиции, игроки индивидуально рациональны по определению).

должны сначала определить, в рамках какого НМ-решения они Определение 37: Если в конфигурации x = {(xi,i S); S P} будут выбирать дележ, а потом выбрать дележ из множества дележей, принадлежащих этому НМ-решению. никакая подкоалиция T произвольной коалиции SP не может гарантировать себе больший доход, чем она получает в конфигураФон-Нейман и Моргенштерн предлагают следующую интерпретацию этого процесса. По их мнению, каждое НМ-решение ции x, (то есть если S P и T S v(T) ), то такая xi iT ограничивает множество дележей, удовлетворительных с точки конфигурация называется коалиционно рациональной.

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

некоторую этику поведения. Выбор же дележа, принадлежащему Определение 38: Конфигурация x = {(xi,i S); S P} доминивыбранному НМ-решению, зависит от переговорных способностей участников игры.

рует конфигурацию y = {(yi,i T); T R}, если найдется такая Поиск НМ-решений достаточно трудоемок ввиду их многокоалиция SP, что xi > yi, i S.

численности. Примеры построения НМ-решений можно найти в Легко видеть, что при этом коалиция S не может принадле[48, 62].

жать коалиционной структуре R.

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

гурации, которые учитывают образование коалиционной структуБыло доказано [72], что любая игра пяти лиц имеет решение в ры, отличной от максимальной коалиции.

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

непересекающихся коалиций, объединение которых дает N.

109 5.10. Значения игры 5.11. Вектор Шепли Общими недостатками рассмотренных выше концепций ре- Чтобы определить аксиомы, которые лягут в основу опредешения является, во-первых, то, что решение существует не для ления вектора Шепли, введем следующие определения.

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

построение концепции решения, которое всегда было бы опреде- Определение 41: Оператор значения маргинален, если его зналено и всегда давало бы единственный дележ в качестве решения. чение зависит только от маргинальных вкладов игроков в коалиТакие концепции решения называются операторами значения ции, то есть от величин v(S {i}) - v(S).

игры.

Определение 42: Носителем игры называется такая коалиция Определение 39: Оператором значения игры называется отоS, что для любой коалиции T выполнено v(T ) = v(T S).

бражение [v], ставящее в соответствие любой кооперативной игре Определение 43: Для двух игр n лиц с характеристическими единственный дележ из множества дележей, называемый значенифункциями u и v их суммой называется игра с характеристической ем игры.

функцией w(S) = u(S) + v(S) для любой коалиции S.





Этот подход к поиску решения разрабатывался, в основном, Аксиомы (Шепли) [46]:

аксиоматической теорией принятия решений [46]. Его основной 1. Если S – любой носитель игры v, то i ([v]) = v(S), где чертой является введение в виде аксиом определенных предполоiS жений о механизме принятия решения и поиск понятия решения, ([v])i – это компонента вектора Шепли, относящаяся к i-му удовлетворяющего данным аксиомам.

Уже само определение оператора значения несет в себе черты игроку.

вводимой аксиоматики. Так, по сути дела, априори предполагает2. [v] анонимен.

ся, что любая игра обязательно должна иметь решение, и решение 3. Для любой пары игр u и v выполнено [u + v]= [u] + [v].

это должно быть единственным.

Вектор Шепли есть оператор значения, задаваемый формуДальнейшие аксиомы вводятся в основном в рамках основных s!(n - s -1)! лами: xi = (v(S {i}) - v(S)), i N [46].

направлений теории кооперативного выбора – утилитаризма и n! 0sn-1 S N \{i} эгалитаризма [46], приводя к разным концепциям решения – |S|=s вектору Шепли и N-ядру соответственно.

Теорема 14 [46]. Аксиомы Шепли определяют единственный Значительным достижением аксиоматической теории приняоператор значения – вектор Шепли.

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

вом распределении благ, то есть оказывается, что некоторым усТеорема 15 [46]. Вектор Шепли – единственный анонимный и ловиям справедливости нельзя удовлетворить одновременно. Этот маргинальный оператор значения.

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

ется, так называемая, арбитражная схема Шепли. Пусть игроки договорились собраться в определенном месте. Из-за случайных 111 флуктуаций они будут прибывать в разное время. Будем предпола- симинного порядка. Это распределение называется N-ядром игры гать, что вероятность любого из n! порядков появления игроков (N, v).

одинакова и равна 1/n!. Предположим, что если игрок, прибывая Можно показать [46], что для супераддитивных игр N-ядро на место, находит там членов коалиции S и только их, то он полу- удовлетворяет принципу индивидуальной рациональности, то есть является дележом.

чает величину xi = v(S {i}) - v(S). Значение компоненты вектора По сути дела, механизм выбора N-ядра следующий. Для люШепли – это математическое ожидание выигрыша игрока в услобого эффективного распределения ранжируем коалиции по их виях описанной рандомизированной схемы.

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

селектором ядра не является. Однако для выпуклых игр справедлива Характеризация N-ядра основана на достаточно сложных определениях, поэтому в данной работе она опускается. Подробное Теорема 16 [46]. В выпуклых играх вектор Шепли принадлерассмотрение характеризации N-ядра и его модификаций провежит C-ядру.

дено в [46].

5.12. N-ядро Самый распространенный оператор значения, являющийся 5.13. Решения в угрозах и контругрозах селектором C-ядра – это N-ядро. Этот оператор реализует эгали- Еще одна концепция решения, которая, подобно решениям в тарный подход в распределении кооперативной прибыли. Эгали- конфигурациях, не ограничивается исследованием случая, когда таризм [46] считает справедливым распределение дохода, макси- реализуется максимальная коалиция, а рассматривает как резульмизирующее доход наименее удовлетворенного члена общества. тат игры и случаи неполного согласия игроков – это концепция решений в угрозах и контругрозах, которая основана на следуюДля вектора x будем обозначать L(x) вектор, составленный из щей идее. Пусть, например, в процессе игры трех лиц образовалась компонент вектора x, ранжированных по возрастанию.

коалиционная структура {{1, 2}, {3}}, содержащая коалицию Определение 44: Вектор x Rn превосходит вектор y Rn в T = {1, 2}, в которую входят игроки 1 и 2. При распределении досмысле лексиминного порядка, если найдется i {1,…, n–1} тахода коалиции v({1, 2}) игроки 1 и 2 получают суммы x1 и x2 сооткой, что L(x)k = L( y)k при k < i, L(x)i > L( y)i.

ветственно. Тогда, если игрок 1 недоволен таким распределением, Определение 45: Поставим в соответствие каждому эффективто он может сказать своему партнеру, что если его доля дохода не ному распределению x в игре (N, v) вектор эксцессов будет увеличена, то он сформирует коалицию S = {1, 3}, где смоN e(x)|2 \{N}| такой, что любой собственной коалиции S соответжет рассчитывать на больший выигрыш. Если такая коалиция S может образоваться, то есть если игроку 3 выгодно сменить конствует компонента этого вектора e(x)S и e(x)S = - v(S).

Pages:     | 1 |   ...   | 10 | 11 || 13 | 14 |   ...   | 15 |










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

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