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


[Старт] [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] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [ 224 ] [225] [226] [227] [228] [229] [230] [231] [232]


224

(где в отличие от композиции сложение понимается в булевском смысле). Аналогично произведением этих же игр называется игра

T{PbWd®T(P24 W2) = T(P, W),

где также P = Pi[]P2l а для любого S cz Р

v(S) = vt (S[]Pi)v2(S[]P2).

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

Некоторый выход за пределы простых игр осуществляется в конструкции Оуэна [1], которая названа им тензорной композицией игр.

Исследовались и отдельные классы простых игр. Так, еще фон Нейман и Моргенштерн (в гл. X) рассматривали различные виды мажоритарных игр.

Ботт.[1] вводит мажоритарные (п, &)-игры, где п/2 < к < п, полагая

/ ЧН если \S\<k, VW - п \$\, если \S\k,

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

8. Наряду с решением игры «разумный» класс дележей представляет рассмотренное Джиллисом [2] с-ядро (core), состоящее из всех дележей, не доминируемых какими-либо другими дележами. «Разумность» с-ядра определяется тем его свойством, что оно состоит из всех дележей (аь ... . . ., ап), для которых

2 at>v(S)

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

Ясно, что с-ядро является замкнутым ограниченным выпуклым множеством, содержащимся в любом решении игры. Однако для многих игр с-ядро оказывается пустым. Джиллис [2] показал, что для наличия; у игры совпадающего с с-ядром решения достаточно, чтобы все значения характеристической функции игры были меньше чем 1/лг, где п - число игроков. В дальнейшем этот результат был усилен О. Н. Бондаревой [1], которая начала систематически использовать в теории кооперативных игр аппарат линейного программирования.

9. Существенно иной подход к кооперативным играм был предложен Ауманом и Машлером в заметке [1], которая положила начало новому направлению в теории кооперативных игр. Этот подход основан на рассмотрении в известном смысле устойчивых исходов игры, к которым игроки приходят в результате переговоров при полном обмене информацией, угрозах, контругрозах и т. п. Множество получающихся при этом устойчивых исходов называется договорным множеством игры и может быть найдено в результате решения систем линейных неравенств. Основные факты складывающейся при этом теории см. в работе Аумана и Маш-лера [2]. Дальнейшие результаты содержатся в статьях Дэвиса и Маш-



лера [1] и Пелега [1]. Некоторые соображения об этом направлении теории игр см. в предисловии О. Моргенштерна к данной книге.

10. Исследования по кооперативной теории без трансферабельной полезности, но с побочными платежами немногочисленны. Первая попытка построения такой теории на описательном уровне была предпринята Шепли и Шубиком [1] (см. также § 10.4 книги Льюса и Райфы [1] и обзорную статью Аумана [2]).

11. Переход от классической кооперативной теории к теории игр без побочных платежей формально сводится к обобщению понятия характеристической функции (см. обзорную статью Аумана [2]).

Пусть / - множество игроков, каждому из которых поставлена в соответствие координата евклидова пространства Et. Для любой коалиции S через -Eg обозначается координатное подпространство Е1г натянутое на координатные оси, соответствующие игрокам из S. Точки Es называются векторами выигрышей S.

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

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

Пусть и (S) - множество векторов выигрышей, которые может обеспечить себе коалиция S. Это множество и будет называться значением характеристической функции для коалиции S. Естественно потребовать, чтобы характеристическая функция удовлетворяла следующим аксиомам:

v (S) является выпуклым, замкнутым и непустым множеством (выпуклость отражает возможность смешивания стратегий, замкнутость - естественное свойство возможностей, а непустота - факт участия в игре).

Если х £ v (S), у £ Es и у х, то у £ v (S) (т. е. множество v (S) имеет только «северо-восточную» границу; содержательно это достаточно естественно: способная на большее коалиция способна и на меньшее).

(3) Для непересекающихся коалиций S и Т

v{S)xv{T)czv{S[)T)

(это условие обобщает классическую аксиому супераддитивности характеристической функции: возможности объединения во всяком случае не уже, чем комбинации возможностей коалиций, действующих порознь).

Выделим теперь в v (I) некоторую часть, примыкающую к ее «северовосточной» границе, т. е. для которой выполняется следующее соотношение:

v(I) = {x£Ej\ существует вектор уН, для которого у>х}.

Н состоит из всех тех векторов выигрышей, которые допустимы по «внешним» обстоятельствам.

Пара (у, Н) и называется игрой без побочных платежей.



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

xi=z max v (г);

Не существует вектора у £ v (I), для которого у > х.

Понятие доминирования дележей переносится с классического случая на рассматриваемый почти буквально: дележ х доминирует дележ у относительно каолиции S, если х £ v (S) и xt > yt для каждого i £ S; дележ х доминирует дележ у, если х доминирует у относительно некоторой коалиции.

Доминирование порождает понятия решения, ядра и т. д., а также всю относящуюся к ним проблематику. Так как возможности игр без побочных платежей существенно шире, чем возможности классических игр, построение многих «опровергающих» примеров оказывается более легким делом. Так, например, вопрос о всеобщей разрешимости игр без побочных платежей был решен в отрицательном смысле раньше, чем для классических кооперативных игр: как показал Стерне (см. стр. 9 обзорной статьи Аумана [2]), существует игра 7 лиц, не имеющая решения.

13. При воспроизведении игры без побочных платежей из ее нормальной, стратегической формы, кроме ее обычной характеристической функции (которую мы будем здесь обозначать через va), описывающей векторы выигрышей, которые участники коалиции могут себе обеспечить, возникает еще другая функция, описывающая те векторы выигрышей, получению которых остальные игроки не могут воспрепятствовать. Эта вторая функция также удовлетворяет аксиомам характеристической функции и обозначается через ур. Функции иа и v$ в известном смысле аналогичны максиминному и минимаксному выигрышам.

В классической кооперативной теории (т. е. при побочных платежах и трансферабельной полезности) обе функции va и v$ совпадают. Иенч в своей единственной, но весьма содержательной работе [1] исследовал более широкие возможности совпадения функций va и v$. Те игры, для которых va = ур, он называет чистыми, приводит примеры игр, не являющихся чистыми, и устанавливает, что для чистоты любой игры с данным множеством участников каждая коалиция должна обладать некоторой «социальной функцией полезности» для побочных платежей. Иенч замечает (не приводя доказательства), что к такой социальной функции полезности приводит предложенная Бернулли логарифмическая шкала индивидуальной полезности.

14. Как и в классическом случае, множественность дележей в решении (как и в ядре), а также множество самих решений в игре снижают нормативную ценность решения, и встает вопрос о выборе по каждой игре некоторого единственного дележа, который можно было бы достаточно обоснованно считать «справедливым». Для классической кооперативной теории таким дележом оказался вектор значений Шепли (см. II.6.3). Ему же в работе [7] удалось распространить соответствующее определение на случай игр без побочных платежей.

Ряд дальнейших результатов, касающихся игр без побочных платежей, а также обстоятельная библиография приводятся в обзорной статье Аумана [2].

[Старт] [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] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [ 224 ] [225] [226] [227] [228] [229] [230] [231] [232]