назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [ 83 ] [84] [85] [86] [87] [88] [89] [90]


83

(случай, изображенный на рис. 4.15), то оно просто совпадает с Н-М-решением.

18.6. Для игры рынка с продавцом и двумя покупателями из п. 2.2 с-ядро бьшо описано в п. 14.3 (см. рис. 4.16). В соответствии с этим Н-М-решения для этой игры будут иметь вид, изображенный на рис. 4.33.

§ 19*. Н-М-РЕШЕНИЯ в ИГРАХ С ЧИСЛОМ ИГРОКОВ, БОЛЬШИМ ТРЕХ

19.1.В случае, когда число игроков в игре становится большим трех, разнообразие вариантов формировавния Н-М-решений начинает весьма быстро возрастать.

Наглядный пример дает анализ Н-М-игр четырех лиц с непустым с-ядром. Это с-ядро, как бьшо выяснено в § 15, является пересечением четырнадцати, замкнутых полупространств (которое удобно представлять себе как пересечение трех выпуклых многогранников). В случае, когда с-ядро непусто, всякое Н-М-решение должно содержать, кроме дележей изс-ядра, еще и дальнейшие дележи, принадлежащие тетраэдрам и клиновидным многогранникам, играющим в этом случае ту же роль, что и недоминируемые с-ядром треугольники в игре трех лиц, показанные на рис. 4.30. Оказывается, что таким путем удается построить Н-М-решения для любой игры четырех лиц с непустым с-ядром.

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

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

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

19.4.Ввиду того, что не все кооперативные игры имеют Н-М-решения, представляет интерес исследовать существование Н-М-решений для отдельных частных классов игр.

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



Теорема. Простейшая игра Vj имеет единственное Н-М-решение, совпадающее с ее с-ядром.

Доказательство. Внутренняя устойчивость с-ядра соблюдается автоматически. Покажем, что в условиях простейшей игры D/ множество C(vr) оказываетя и внешне устойчивым.

Возьмем для этого дележ у ф C(vj), Согласно п. 13.7 для этого дележа должно бытьy(R) < 1. Положим

1 -y(R) yi+ - для iGR,

Одля iGR.

Очевидно,х= (Xi ,. .. ,х„) GC(vr) их>у. П

§ 20. ВЕКТОР ШЕПЛИ. АКСИОМАТИКА

20.1.Теория игр рассматривает весьма разнообразные принципы оптимальности. Некоторые из них отражают интуитивные представления об оптимальности непосредственно. Таковы, например, принцип приемлемых ситуаций (принцип осуществимости цели) в бескоалиционных играх (см. § 2 гл. 1) с его важнейшим частным случаем - принципом максимина, а также рассмотренные в предыдущих параграфах принципы оптимальности, приводящие к с-ядру и Н-М-решению. Однако, кроме этих принципов оптимальности, которые можно назвать естественными, теория игр сама конструирует принципы оптимальности, задавая их теми свойствами, которыми они должны обладать. Такой подход к вопросу по существу является аксиоматическим.

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

Нашей целью будет указание способа, который ставит в соответствие каждой кооперативной игре (т.е. каждой характеристической функции) v над множеством игроков I = {!,...,п) некоторый вектор Ф(1;) = = (Ф1 (г;),..., Ф„(1;)), компоненты которого описывают справедливые в нектором смысле выигрьпни каждого из игроков в этой игре. При этом естественно желать, чтобы этот вектор Ф(1;) оказался дележом в условиях v.

20.2.Приступим к формулировке тех требований, которые естественно предьявлять к справедливому дележу. Прежде всего "справедливость требует" при разделении общего выигрыша носителя игры ничего не выделять на долю посторонних, не принадлежащих этому носителю болванов (см. п. 6.3), равно как и ничего не взимать с них. Формально это можно выразить в виде следующей аксиомы.

Аксиома эффективности. Если Л/- носитель v, то

Ъ Фi(v)v(N).(20.1)

iGN 250



20.3.Теорема. Если / - болван в v, то

Ф;(р)иОГ(20.2)

До казательство. Возьмем носителя N игры, v, не содержащего болвана /. Ясно, что множество NU / также является носителем v. Поэтому в нашем случае справедливо равенство (20.1), а также равенство

Z Ф,.(1;)-1;(Ли/).(20.3)

iN и /

Почленное вычитание (20.1) из (20.3) дает нам (20.2). □

20.4.Из этой теоремы следует, что в несущественной игре, в которой все игроки - болваны, формула (20.2) справедлива для каждого игрока.

205. Важной чертой справедливости является симметрия: игроки, одинаково входящие в правила игры, должны "по справедливости" получать одинаковые выигрьппи.

Аксиома симметрии. Для любого автоморфизма тг игры V Ф/(1;) =Ф,-(1;).

20.6.Наконец, естественно потребовать, чтобы операция перехода к справедливому дележу обладала некоторыми чертами аддитивности.

Пусть имеются две игры v ии " с одним и тем же множеством игроков /. Сумма v и D " , т.е. заданная на подмножествах / функция v-v" , для которой

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

Сложение характеристиеских функций можно понимать как одновременное участие каждого из игроков из / в двух играх.

"Справедливо считать", что при участии игроков в двух играх их выигрыши в отдельных играх должны складываться.

Аксиома агрегации. Если v и v" - две игры с множеством игроков /, то

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

20.7.Оказывается, что система, состоящая из трех приведенных аксиом, является непротиворечивой и полной в том смысле, что для всякой характеристической функции V а) существует, и притом б) единственный, вектор Ф(1)), удовлетворяющий этим трем аксиомам. Этот вектор называется вектором Шепли,

В связи с вектором Шепли перед нами встают следующие задачи.

Прежде всего нам нужно указать формулы, выражающие компоненты вектора Шепли в явном виде и позволяющие, по крайней мере в принципе, вычислять их для каждой игры. При этом, разумеется, необходимо доказать, что получаемый по этим формулам вектор действительно является вектором Шепли, т.е. удовлетворяет определяющим вектор Шепли аксиомам (непротиворечивость аксиоматики) и является среди таких векторов единственным (полнота аксиоматики). Это мы сделаем в § 21.

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [ 83 ] [84] [85] [86] [87] [88] [89] [90]