1smol_yakov_e_r_metody_resheniya_konfliktnykh_zadach-1

В самом деле, возьмем произвольную точку y P (Y0) и допустим, что y / P (Y ). В силу неравенств (4.6) и следующего из них включения Y0 YA оказывается, что y YA. Допущение, что точка y не является S-экстремальной точкой множества Y , означает, что найдется такая точка y¯ Y , y¯ 6= y , ÷òî y y¯ + S, причем точка y¯ удовлетворяет включению y¯ K, поскольку в противном случае не обеспечивается включение y y¯ + S ïðè y K. Однако включение y¯ Y ∩ K = Y0 противоречит определению S-экстремальности точки y Y0, согласно которому не должно найтись точки y¯ Y0, такой, что y y¯ + S. Это противоречие и показывает, что

оптимальные по Парето A0-равновесия.

5.Многозначные конфликтные задачи

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

Построим усиленную базовую систему равновесий для многозначных игровых задач.

Допущение 5.1. Пусть Qi, i = 1, N метрические пространства, а G

4

компактное множество в их произведении Q = Q1 × . . . × QN , и пусть на множестве G определены замкнутые ограниченные многозначные функционалы Ji[q], i = 1, N, замкнутые в том смысле, что при каждом i = 1, N множество значений функционала Ji[q], q G, замкнуто в пространстве E1 × G, ãäå E1 множество вещественных чисел (заключение аргумен-

та функционала в квадратные скобки указывает на факт многозначности функционала).

Предполагается, что i-й игрок, выбирая стратегию (состояние) qi, i = 1, N, из доступного ему сечения G(qi) множества G или из проекции P rQiG множе- ñòâà G на пространство Qi, стремится обеспечить максимум многозначного

функционала Ji[q], q = q1 . . . qN .

Определение 5.1. Ситуацию q G назовем усиленной Asi - экстремальной (соответственно, усиленной достижимой Asdi -

экстремальной) в игре с многозначными функционалами Ji[q], i = 1, N, если при заданной стратегии qi допустимой оказывается только одна

131

стратегия qi = G(qi ) или если любой стратегии qi G(qi ) \ qi i-го игрока можно поставить в соответствие по крайней мере одну допустимую

i 4 i

стратегию qˆ = qˆ < qi > G(qi) остальных игроков так, чтобы имело место отношение

из множества достижимых для i-го игрока значений) функционала Ji â каждой из точек (ˆqi, qi) G(qi) не больше любого значения Ji[q ] â òî÷- êå q . Ситуацию q назовем ситуацией усиленного As-равновесия (соот-

ветственно, ситуацией усиленного достижимого Asd-равновесия), åñëè неравенства (5.1) удовлетворяются в точке q äëÿ âñåõ i = 1, N.

Приведем для сравнения более слабый аналог определения 5.1, изложенный в главе 1, который является основой для построения (слабой) базовой системы равновесий для многозначных игровых задач.

Определение 5.2. Ситуацию q G назовем ситуацией многозначного

A-равновесия, если при каждом i = 1, N в неравенстве (5.1) некоторое из множества значений Ji[ˆqi < qi >, qi] не больше некоторого значения Ji[q ].

Замечание 5.1. Что касается понятия достижимости ситуации, то необходимость в этом понятии видна хотя бы из того, что в некооперативной игре попасть из некоторой точки в некоторую другую точку игроки могут не произвольным образом, а лишь по вполне определенным линиям (траекториям)

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

Ji многозначен, то этот функционал принимает в точке q¯, в общем случае, строго определенное значение (которое мы называем достижимым) из множества всех его значений в этой точке (что легко видеть из рассматриваемого ниже примера). В этом и состоит особенность так называемых достижимых равновесий. Когда мы говорим о многозначных и усиленных многозначных A-равновесиях, то имеем в виду ситуации, в которых платежный функцио-

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

132

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

лируемых в определении 5.1, рассмотрим модификацию на случай многознач-

ных конфликтных задач ¯0-равновесия.

C

Определение 5.3. Ситуацию q G назовем ситуацией усиленного

(соответственно достижимого) ¯0-равновесия в игре с многозначными

C

функционалами Ji, åñëè

где любое из множества значений (соответственно любое из множества достижимых для i-го игрока значений) Ji[qi , qi] функционала Ji

из точек (qi , qi) не больше любого значения Ji[q ] в точке q .

Âкачестве еще одного независимого усиления равновесий из определения

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

Определение 5.4. Ситуацию q G назовем ситуацией многозначно-

го (соответственно достижимого) равновесия в игре с многозначными функционалами Ji, åñëè

где любое из множества значений (соответственно любое из множества достижимых для i-го игрока значений) Ji[qi , qi] функционала Ji

из точек (qi , qi) не больше любого значения Ji[q ] в точке q .

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

пускает дальнейшее усиление этих равновесий, посредством, например, D,

0, ¯ s- è ¯ s-равновесия и D D-равновесий. Ради наглядности приведем только B D

только для N = 2.

Определение 5.5. Ситуацию q G назовем усиленной Bis- экстремальной (соответственно усиленной Bisd-достижимой), åñëè îáðà-

133

где любое из множества значений (соответственно любое из множества достижимых для k-го игрока значений) Jk[qi , qk] в каждой из точек (qi , qk) G(qi ) не больше любого значения Jk[q ] в точке q . Назовем ситуацию q G усиленным Bs-равновесием (соответственно усиленным достижи-

где любое из множества значений (соответственно любое из множества достижимых для i-го игрока значений) Ji[q ] не больше любого значения

¯ s-равновесием (соответ- Ji[q ]. Назовем ситуацию q G усиленным D

отсутствия в игре равновесий типа (5.3) и неединственности равновесий типа (5.2). Демонстрацией того, что эти равновесия определяют совершенно естественные игровые равновесия, может служить рассмотренный ниже пример и установленная в Главе 4 для антагонистических игр тесная связь с седловыми

точками аналогичного им D-равновесия.

Заметим, что чем слабее равновесие, тем слабее условия его существования, в связи с чем искать всегда существующее равновесие следует среди слабейших. Из приведенных выше понятий равновесия наиболее слабым является равновесие, даваемое определением 5.2. В следующей теореме доказывается существование этого равновесия.

Теорема 5.1. В игре с ограниченными замкнутыми функционалами Ji[q], i = 1, N, существует A-равновесие с любой заданной точностью ε.

Доказательство. Как следует из пояснений, даваемых после каждого из неравенств (5.1) (5.5), рассматриваемые нами операции max, min, sup, inf

134

многозначны, а следовательно, величина

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

С учетом многозначности числа J10 и определения многозначной операции

т.е. при каждом q1 G(q1ε1 ) найдется хотя бы одно значение в правой части этого неравенства, которое не меньше хотя бы одного значения в левой части.

В то же время из самого определения (5.6) числа J10 следует, что если

Q1ε1 множество всех стратегий q1ε1 , удовлетворяющих неравенству (5.7),

причем это неравенство означает, что для каждой указанной пары стратегий (ˆq1, q1) найдется хотя бы одно значение в левой части этого неравенства, которое не больше хотя бы одного значения в правой части.

Из неравенств (5.8) и (5.9) следует

J1[ˆq1; q1] ≤ J10 − ε1 ≤ J1[q1; q1ε1 ].

Àиз последних неравенств, если сравнить их с неравенством (5.1) при i = 1, следует, что любая ситуация (q1; q1ε1 ) G, ãäå q1 G(q1ε1 ), является

многозначной A1-экстремальной с точностью ε1.

в которой операции sup è inf понимаются в рассмотренном выше многознач- ном смысле, и дальнейшее доказательство этой теоремы (с учетом фактора

135

многозначности) почти полностью повторяет соответствующее доказательство теоремы 1.1.2 из главы 1.

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

Пример 5.1. В многозначной игре с двумя участниками 1-й игрок, выбирающий свою чистую стратегию u1 из множества U1 = [-1,1], и второй игрок, выбирающий свою чистую стратегию u2 из множества U2 = [-1,1], стремятся обеспечить каждый максимум своей платежной функции

f1(u1, u2) = u1(u1 − u2)/(u21 + u22), f2(u1, u2) = u2(u1 − u2)/(u21 + u22).

è f2 постоянны (см. рис. 2.6).

Целесообразно начинать поиск равновесий в сложных играх с наиболее слабых равновесий, постепенно переходя ко все более и более сильным. На этом примере демонстрируется, что в отношении многозначных игровых задач не следует ограничиваться какой-либо одной базовой системой равновесий и, оставаясь в ее рамках, пытаться искать наиболее сильное равновесие, а следует, начав с наиболее слабой базовой системы, рассматривать затем и более сильные базовые системы. Сначала в рамках наиболее слабой базовой системы равновесий (используя определение 5.2 и легко формулируемые его аналогичные усиления равновесий типа (5.2), (5.3)) получаем

136

A1 = OSV EF O OT HKIO, A2 = G, A = A1 ∩ A2,

B1 = LM ST, B2 = HN V P NP KE,

B = B1 ∩ B2 = O (сильнозависимое равновесие ).

Поскольку B-равновесие состоит из одной точки O, то никакое дальнейшее

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

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

Ad1 = A1, Ad2 = OEF OKI ST, Ad = Ad2, B1d = B1, B2d = EF IK KE S T, Bd = B1d ∩ B2d = {O, L, M, S, T };

здесьBd − многозначное достижимое сильнозависимое равновесие .

Естественным дальнейшим усилением Bd-равновесия является достижи-

Рассмотрим теперь более сильную базовую систему равновесий, задаваемую определениями 5.1, 5.3 5.5. В рамках первой трактовки игры получаем

As1 = A1 \ O = OSV EF O OT HKIO \ O, As2 = (G \ ST ) O, As = As1 ∩ As2 = As1 \ ST,

B1s = LM ST \ O, B2s = HN NP P V KE \ O;

здесьBs = − усиленное сильнозависимое равновесие (5.2) .

Таким образом, если в слабой базовой системе (A −B)-равновесий точка O оказалась равновесной (хотя и малоинтересной для игроков), то в усиленной базовой системе (As − Bs)-равновесий эта точка уже не является рав-

новесием (иначе говоря, она является недостаточно сильным равновесием, чтобы существовать в усиленной системе равновесий).

137

Что же касается достижимых равновесий в рамках усиленной базовой системы (Asd −Bsd)-равновесий, то они должны оказаться подмножеством мно-

жества Ad − Bd-равновесий. Имеем

Asd1 = Ad1 \ O, Asd2 = Ad2, Asd = Asd2 \ O,

B1sd = B1d \ O, B2sd = B2d \ O, Bsd = Bd \ O = {L, M, S, T }.

Во всех равновесных ситуациях из множества Bsd платежные функции

игроков однозначны. Однако не все они предпочтительны для каждого из игроков, в связи с чем множество равновесий Bsd может быть усилено. По-

добное усиление дает определение 5.6:

Действительно, ситуации L è M предпочтительнее для обоих участников, чем ситуации S è T , òàê êàê Ji[L] = Ji[M] > Ji[S] = Ji[T ], i = 1, 2.

хотя и получает в этих точках всего лишь f1 = 1/2, что значительно меньше

√

его максимально возможного значения f1max = ( 2 + 1)/2, реально не может

рассчитывать на большее, поскольку, во-первых, при любом его отклонении

от точки L или M у 2-го игрока имеются угрозы uˆ2 < u1 >, возвращающие

√

состояние игры на линию u2 = ( 2 − 1)u1, на которой игроки получают столько же, сколько в точках L и M, а во-вторых, применение 2-ым игроком даже смешанной стратегии, формально гарантирующей ему при бесконечном числе партий усредненный выигрыш в одной партии J1 = 1 (что больше, чем

значение J1 =1/2, которое он получает в точках L è M), не позволяет ему, однако, гарантировать в одной партии никакого положительного выигрыша.

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

тегий q1(u1) è q2(u2), дающих решение игры в смысле равновесия по Нэшу (5.3),

каждой (из бесконечного числа) партий игры.

138

1-му игроку целесообразно согласиться с выигрышем, который он получа- ет в точках L è M, если учесть, что его возможности в этой игре значительно

более ограниченные, чем у 2-го игрока. В самом деле, множество ситуаций, в отношении которых у 2-го игрока не имеется эффективных угроз против первого игрока, существенно уже (совпадает со множеством OIS OF T ),

чем множество ситуаций OF HKO OIV EO, в отношении которых у 1-го игрока не имеется эффективных угроз против 2-го игрока.

139

Глава 3. КООПЕРАТИВНЫЕ ИГРОВЫЕ ЗАДАЧИ

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

q может быть таковой, что в ней один из

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

âкоторой он не получил бы уже почти ничего. Если принять во внимание, что в любой задаче всегда имеется ситуация, в которой реализуется максимальный суммарный выигрыш всех участников, то, следовательно, проблема справедливого дележа кооперативного дохода всегда вста¼т перед участниками в любой конфликтной задаче. Но, к сожалению, эта проблема так и осталась нереш¼нной в 20-м веке. И, как показала история теории игр, эта задача оказалась посложнее, чем поиск устойчивых состояний (равновесий)

âконфликтной задаче, хотя и с поиском последних классическая теория игр не очень-то преуспела.

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

140