Аудит /
Институциональная экономика /
Информационные технологии в экономике /
История экономики /
Логистика /
Макроэкономика /
Международная экономика /
Микроэкономика /
Мировая экономика /
Операционный анализ /
Оптимизация /
Страхование /
Управленческий учет /
Экономика /
Экономика и управление народным хозяйством (по отраслям) /
Экономическая теория /
Экономический анализ
Главная
Экономика
Экономика
| С. Л. Печерский, А. А. Беляева. Теория игр для экономистов, 2001 | |
6.6. Дополнение. Выпуклые игры |
|
|
1. Пусть I = {1,..., п) - множество игроков, ав - выпуклая игра, т.е. для любых S, Т С (/) + + (6.1) Множество всех выпуклых игр мы будем обозначать через С . Оправданием такому названию может служить тот факт, что для выпуклой игры лпервые разности v(S + T)-v(S) (6.2) при фиксированном Т монотонно возрастают по S. (Заметим, что если / : R+ R+ выпуклая функция, т.е. f(ax + (1 - а) у) й af(x) + (1 - a)f(y) при всех х,у G R+ и 0 ^ а ^ 1, то лпервые разности этой функции f(x + y)-f(x) (х,уе R+) при фиксированном у монотонно возрастают по х .) Соотношение (6.2) наводит на мысль, что с-ядро выпуклой игры непусто. Действительно, можно заметить, что условие (-v(S+{t})-v(S))b (6.3) равносильно монотонности (6.2). Утверждение же (6.3) означает, что игроку i целесообразно присоединяться к все большим коалициям; отсюда вытекает стремление к образованию большой коалиции, охватывающей вообще всех игроков. Поэтому естественно ожидать, что образуется максимальная коалиция, а меньшие коалиции этому не будут препятствовать. Следовательно, можно ожидать, что с-ядро непусто. Теорема 6.6.1. Если v ? С , то C(v) ф 0 . Доказательство ведется по индукции. Для га = 1 доказывать нечего. Предположим, что теорема доказана для га - 1 игроков. Пусть / ={1,...,га},а Т - коалиция из га - 1 игроков. Тогда в силу индуктивного предположения функция имеет непустое с-ядро, т.е. существует такой вектор т ? v(S) = v(SnT) 1устое с-ядр IRT, что m0(S)b(S),VScT (6.4) т(Г) = т(7) = v(T) = v(I). Определим вектор m ? IR^, положив Г 777,9 Z (z Т m = Ui)-v(n ЦТ. (6-5) Тогда мы имеем т(!) = Еге/ тг = Егет тг + V(I) - V(T) = (6.6) = m(T)+v(I)-v(T) = v(I) и для S С Т в силу (6.4) 777(5) = m(S) ^ v(S) = v{S). Кроме того, для S ^ v(Sr\T) + ml0 =v(Sr\T)+v(I)-v{T) = = v(S\{i0}) + v(I)-v(I\{i0})Zv(S), причем последнее неравенство в цепочке следует из (6.3). Теорема доказана. Идея доказательства здесь достаточно прозрачна: выигрыш делится между членами коалиции Т соответственно некоторому дележу из C(v) , а вновь присоединяющемуся игроку го выплачивается все то, что он приносит большой коалиции. А это позволяет подойти к следующей конструкции. Теорема 6.6.2. Пусть 0 = So С Si С S2 С Х Х Х С Sn = I Ч (6.7) строго возрастающая последовательность коалиций из I, для которой ^ \ определяют некоторый дележ х ? C(v) . Доказательство аналогично доказательству предыдущей теоремы. Процесс, описываемый цепочкой (6.7), достаточно нагляден: пустая коалиция So за счет вступления в нее новых игроков последовательно увеличивается каждый раз на одного игрока. Этот порядок вступления определяет некоторую перестановку игроков ТГ . Перестановка ТГ, соответствующая (6.7), однозначно определяется равенством тг (Si \ Si-i) = i (i = l,...,n). (6.9) Пусть теперь тг :/Ч>ж/ - некоторая перестановка. Ясно, что она порождает некоторый порядок игроков. Обозначим множество первых (согласно этому порядку) i игроков через Sf = {к : тг (к) й г}. Если тг получено из соотношения (6.7) на основании (6.9), то из к G Si , к G Sj \ Sj-i (для некоторого j ^ i) вытекает тг (к) = тг (Sj \ SjЧi) Отсюда Q7T с. iJ i - iJ i . Поэтому справедлива следующая теорема. Теорема 6.6.3. (Shapley, 1979). Для любой перестановки тг : I Ч> I дележ ж71", задаваемый равенством xZ-4i) = v(Si)-v(Si-1), (6.10) принадлежит C(v). Замечание 6.6.1. Легко видеть, что xl = v(sv(k)) - w(5V(fc)-i)- (6-n) Теорема 6.6.4. (Shapley, 1979). Каждый дележ ж71", описываемый равенством вида (6.10), является крайней точкой множества C(v), и все крайние точки могут быть получены таким путем. Доказательство. Множество С является ограниченным замкнутым выпуклым многогранником в Rn . Известно (см., например, Рокафеллар, 1973), что крайние точки можно получить как единственные решения системы п уравнений, получаемых из неравенств, задающих многогранник. При этом необходимо еще проверить, принадлежат ли найденные таким образом точки многограннику. В силу равенства (6.8) для заданных ж71" = ж и Sf = Si мы имеем ж (Si) = x(Si \ Si^) + x(Si-! \ Si-2) Н Ь x(Si \ S0) = v(St), т.е. ж является решением системы п уравнений. Из равенства (6.10) следует, что ж является единственным решением этой системы. Наконец, по теореме 6.6.3 х ? С , так что х является крайней точкой с-ядра. Пусть, наоборот, х - некоторая крайняя точка с-ядра. Рассмотрим систему коалиций а = а(х) = {S С I\x(S) = v(S)}. (6.12) Эта система замкнута относительно операций объединения и пересечения. Действительно, пусть S,T ? <7 ; тогда v(SUT) й x(SUT) = x(S) + х(Т) - x(SnT) й (6.13) ^ v(S) + v(T) - v(SnT) < v(SUT) и, следовательно, S U T ? a . Точно так же доказывается, что и S П Т ? а . Пусть 0 = 5*0 С 5*1 С Х Х Х С Sm = I Ч (6.14) строго возрастающая последовательность коалиций из а , имеющая наибольшую длину. Если тп = п , то наша теорема доказана. Если тп < п, то найдется такое Sk , что \Sk+i \ Ввиду того, что х как крайняя точка является единствен-ным решением системы = (S ? сг), (6.15) ies существует хотя бы одно такое S ? а , что (не нарушая общ-ности) ies, jts. Множество Т= (SUSk) П Sk+i является элементом а ввиду замкнутости семейства а относительно операций объединения и пересечения. Кроме того, для Т имеет место включение Sk с т с Sk+i, а это невозможно в силу того, что (6.14) - последовательность наибольшей длины. Поэтому случай то < га невозможен, и теорема доказана. Теорема 6.6.5. Пусть функция v ? С такова, что для S,T ? В, для которых S \ Т ф 0 и Т \ S ф всегда имеет место v(S) + v(T) < v(SUT) + v(SnT). (6.16) Тогда все дележи ж71" различны. В этом случае С имеет ровно га! крайних точек. Доказательство. Пусть множества S и Т удовлетворяют условиям теоремы, а ж - некоторая крайняя точка С . Покажем, что если ж - крайняя точка С , a S,T ? <т(ж) , то либо S С Т, либо S Э Т . Действительно, из x(S) = v(S) и х(Т) = v(T) на основании свойств а(х) следовало бы, что x(S U Г) = v(S U Г) и x(S Г) Т) = v(S П Г) . Отсюда, в свою очередь, вытекало бы и(5) + v(T) = x(S) + ж (Г) = x(S U Г) + x(S П Г) = = л(SUT) + o(5nr), а это противоречит (6.16). Поэтому множества из <т(ж) можно упорядочить так: 0 = So С St С ж ж ж С Sm = I. Мы уже видели, что должно быть то = га и, следовательно, соответствие между крайней точкой ж и системой (6.7) является взаимно однозначным. Следствие 6.6.1. Если v ? С и выполнено (6.16), то значение Шепли игры v есть центр тяжести с-ядра C(v) . Доказательство немедленно следует из теоремы и формулы, определяющей значение Шепли. |
|
| << Предыдушая | Следующая >> |
| = К содержанию = | |
Похожие документы: "6.6. Дополнение. Выпуклые игры" |
|
|