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


[Старт] [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]


225

§ 4. БЕСКОАЛИЦИОННЫЕ И КОАЛИЦИОННЫЕ ИГРЫ

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

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

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

Более формально принцип осуществимости цели выглядит следующим образом.

Если s - ситуация в игре Г, a st - произвольная стратегия игрока i, то через s \\ st обозначается ситуация, получаемая из ситуации s в результате замены в ней имеющейся стратегии игрока i на его стратегию st.

Ситуация 5* в игре Г называется приемлемой для игрока i, если для любой его стратегии st имеет место неравенство Ht (s* st) Нг (5*). Ситуация называется равновесной, если она является приемлемой для каждого игрока.

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

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

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

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

Пусть

Выигрыши игрока 1

Выигрыши игрока 2



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

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

В этом примере мы снова сталкиваемся с нашим неумением сводить кооперативный аспект проблемы к стратегическому. Канонический выбор среди многих ситуаций равновесия произвольной игры является сложной проблемой. Интересные подходы к этому кругу вопросов содержатся в работах Харшаньи [1], а также Крелле и Кёнена [1].

3. Довольно общие принципы разумности договоров между игроками предложил Нэш в своей работе [2].

Каждый договор между двумя игроками приводит к получению ими некоторых выигрышей г* и г2. Это значит, что каждый договор характеризуется парой чисел (г4, г2) и может быть поэтому представлен точкой на плоскости. Предположим, что R есть множество точек, соответствующих всевозможным договорам. Среди всех возможных исходов договоров выделяется один, к которому игроки приходят, когда попытка договориться не увенчивается успехом. В этом случае выигрышами игроков будут те количества, которые получаются игроками в одиночестве. Соответствующая такому исходу точка г° = (rj, г°2) иногда называется «статус-кво».

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

Согласно Нэшу, естественно потребовать, чтобы справедливая договорная схема удовлетворяла следующим аксиомам:

(1) Эффективность

F(R, r°)r°

(иными словами: договор справедлив, если каждый из договаривающихся от него не проигрывает).

(2) Симметрия: если множество R расположено симметрично относительно биссектрисы координатного угла г4 = г2, а компоненты вектора г° равны, то и компоненты вектора F (R, г°) должны быть равны (при одинаковом положении в схеме игроки должны получать одинаковые выигрыши).

(3) Оптимальность по Парето: в договоре F (R, г°) оба игрока не могут одновременно увеличить свои выигрыши (это свойство договора скорее следует связать не с его справедливостью, а с его общей разумностью: разумный договор нельзя улучшить так, чтобы каждый из его участников увеличил свой выигрыш).

(4) Монотонность относительно области: если Rt a Rz и F (R2, r°) £

то F (i?1? r°) = F (Д2, г°) (если в «широкой» договорной схеме справедливость требует выбора договора из более «узкой» схемы, то при переходе к узкой схеме сохранится старый справедливый договор).

(5) Инвариантность относительно начала отсчета и единиц измерения: при любых положительных к± и к2

Ч(о I) я+г- (о 0 г°+г Но г°)+к



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

Сформулированная система аксиом является полной. Именно имеет место следующая теорема: если функция F = (F±, F2) удовлетворяет аксиомам (1) - (5), то

(Ft (R, г") - г[) (F2 (R, г°) - 4) = max (г, - rj) (rz - r°2),

r=(ri, r2)E#

т. е. справедливым договором признается тот, при котором максимизируется произведение приращений выигрышей игроков по сравнению со статус-кво.

Подробный критический анализ этого круга вопросов содержится в книге Льюса и Райфы [1].

4. Существование ситуаций равновесия в любой конечной бескоалиционной игре (разумеется, вообще говоря, в смешанных стратегиях) было доказано Нэшем [1]. Это доказательство, как и первое доказательство фон Неймана [1] теоремы о минимаксе (естественным обобщением которой оно является), опирается на теорему Брауера о неподвижной точке. Однако, в отличие от теоремы о минимаксе, здесь едва ли можно надеяться на нахождение доказательства, опирающегося на достаточно элементарные и «достаточно эффективные» процедуры (вроде теоремы об отделимости выпуклых множеств). Дело в том, что, как показывают примеры, с увеличением числа игроков для нахождения компонент ситуаций равновесия приходится выполнять иррациональные операции все более высоких степеней.

Теорема Нэша поддается обобщению на случай бесконечных игр. Несколько весьма интересных примеров теорем такого рода содержится в книге Бургера [1].

5. Обычно в бескоалиционных играх принимается, что игроки могут в качестве смешанных стратегий применять любое вероятностное распределение на множестве чистых стратегий. У Вень-цзюн [2] рассматривает игры, в которых множество чистых стратегий каждого игрока задано вместе с некоторым своим покрытием, причем допускаются только такие смешанные стратегии, в которые входят только такие чистые стратегии, которые принадлежат одному и тому же элементу покрытия. Такие игры он называет играми с ограничениями. В играх с ограничениями равновесными ситуациями считаются те ситуации а, в которых Нг (о \\ st) :g Ht (а) для всех i и всех тех чистых стратегий st, которые принадлежат элементу покрытия, агвероятность которого равна единице. Используя весьма тонкие топологические рассуждения, У Вень-цзюн установил, что достаточным условием существования ситуаций равновесия в играх с ограничениями является, во-первых, связность нервов покрытий множеств стратегий всех игроков и, во-вторых, неравенство нулю их характеристики Эйлера - Пуанкаре.

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

Алгорифм для численного решения биматричных игр был указан Н. Н. Воробьевым [1] и затем усовершенствован Куном [2]. Более практичный, но не столь полный алгорифм принадлежит Лемке и Хаусону [1].

Бесконечные бескоалиционные игры удается решать лишь в отдельных, весьма немногочисленных случаях. К их числу принадлежит весьма интересный пример игры «олигополистов», приводимый в книге Бургера [1].

[Старт] [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]