close

Вход

Забыли?

вход по аккаунту

?

Гарантированные по выигрышам и рискам дележи в кооперативной игре.

код для вставкиСкачать
Известия Института математики и информатики. Иевск. 2005. Є2(32)
УДК 519.833.7
А.В. Аввакумов
dewsha81mail.ru
ГАРАНТИРОВАННЫЕ ?О ВЫИГРЫШАМ
И РИСКАМ ДЕЛЕЖИ В КОО?ЕРАТИВНОЙ ИГРЕ
Ключевые слова:
1
кооперативная игра без побочных платеей, риск,
гарантированный делё, неопределённость
Abstrat. The formalization of guaranteed division by result and risk
in the ooperative game when some unertainty was realised and without the inidental payments, moreover there are supposed only sope of
hanges are known about the unertainty, but any stati harateristis
are undened.
1.
?остановка задачи
Рассматрим кооперативную игру двух лиц без побочных платеей и при неопределённости
h{1, 2}, {Xi }i=1,2 , Y, {fi (x, y )}i=1,2 i .
(1.1)
В игре (1.1) участвуют два игрока: первый и второй; кадый
из них выбирает свою стратегию xi ? Xi ? Rn (i = 1, 2) , в
результате образуется ситуация
i
x = (x1 , x2 ) ? X
= X1 ╫ X2 ? Rn (n = n1 + n2 );
независимо от их выбора в игре реализуется неопределённость
y ? Y ? Rm ; на образовавшихся таким образом парах
(x, y) ? X ╫ Y определена функция выигрыша i -го игрока
1
Работа поддерана грантом РФФИ
51
fi (x, y ) (i
= 1, 2) , значение которой на конкретной паре (x, y)
называется выигрышем i -го игрока в ситуации x ? X и при
неопределённости y ? Y .
Введём (согласно требованиям экономистов) функции риска. Учитывая єкооперативный характер игры (1.1), рассмотрим двухкритериальную задачу (для кадой неопределённости
y ? Y ):
hX, {fi (x, y )}i=1,2 i ,
(1.2)
которую получим из (1.1), фиксируя y ? Y .
Ситуация x?(y) ? X ?y ? Y называется максимальной по
Слейтеру (слабо эффективной) в задаче (1.2), если при любых
x ? X и для кадого y ? Y несовместна система неравенств
fi (x, y ) > fi (x? (y ), y ) (i = 1, 2).
(1.3)
У т в е р д е н и е 1.1. Если в игре (1.1)
1) мноества Xi (i = 1, 2) | выпуклые компакты, а Y есть
компакт;
2)
fi (x, y ) (i = 1, 2) строго вогнуты по
x ? X при кадом y ? Y и непрерывны на X ╫ Y ,
то многозначное отобраение X S [y ? : Y ? X , определяемое несовместностью системы неравенств (1.3), имеет непрерывный
селектор x? (y ) ? X S [y ? ?y ? Y.
функции выигрыша
З а м е ч а н и е 1.1. Моно указать и другие достаточные условия существования непрерывного селектора x?(y) . Далее, не оговаривая особо, считаем, что используемая векторфункция x?(y) имеет непрерывные компоненты на Y .
Функцию риска i(x, y) для критерия fi(x, y) введём (следуя
идее принципа минимаксного соаления Сэвида [1?) в виде
(1.4)
i(x, y) = fi(x? (y), y) ? fi (x, y) (i = 1, 2).
Функция i(x, y) численно оценивает риск (соаление) i -го
игрока о том, что при неопределённости y ? Y он (согласованно с
52
партнёром) выбрал свою стратегию из ситуации x , а не из x?(y) ,
хотя последняя и доставляет векторный максимум в задаче (1.2).
У т в е р д е н и е 1.2. Если в (1.1) функции выигрыша fi (x, y ) непрерывны на X ╫ Y и x? (y ) непрерывны на Y ,
то функции риска i (x, y ) , определённые в (1.4), непрерывны.
В ряде статей по экономике требуется, чтобы игроки ориентировались на возмоно большие выигрыши и одновременно на
возмоно меньшие риски. Учитывая это, игре (1.1) поставим в
соответствие вспомогательную кооперативную игру при неопределённости
h{1, 2}, {Xi }i=1,2 , Y, {fi (x, y ), ?i (x, y )}i=1,2 i .
(1.5)
В (1.5) мноества Xi , Y и функции fi(x, y) те е, что в
(1.1). Отличие лишь в том, что функция выигрыша i -го игрока в игре (1.5) стала векторной (fi (x, y), ?i (x, y)) , причем вторая компонента ?i(x, y) специально взята со знаком єминус.
В игре (1.5) кадый игрок i за счёт выбора своей стратегии
xi ? Xi стремится к возмоно большим значениям одновременно
обеих компонент fi(x, y) и ?i(x, y) своей функции выигрыша
(fi(x, y), ?i (x, y)) (i = 1, 2) . ?ри этом,
во-первых, игроки вынудены учитывать возмоность реализации любой неопределённости y ? Y (им известно лишь само
мноество Y );
во-вторых, игрокам разрешены любые переговоры о выборе совместной ситуации x ? X ;
в-третьих, запрещено єправилами игры уступать часть своего
выигрыша партнёру (в этом и есть смысл єигры без побочных
платеей).
53
2.
Формализация гарантированных делеей
Для кадой функции выигрыша fi(x, y) (i = 1, 2) и при кадой
неопределённости y ? Y введём максимины
f10 [y ? = max min f1 (x1 , x2 , y ),
x1 ?X1 x2 ?X2
(2.1)
f20 [y ? = max min f2 (x1 , x2 , y ).
x ?X x ?X
2
2
1
1
У т в е р д е н и е 2.1. ([2, с. 110?). Если в игре
(1.1) мноества Xi (i = 1, 2), Y суть компакты, а fi(x, y)
(i = 1, 2) непрерывны на X ╫ Y , то функции fi0 [y? (i = 1, 2) из
(2.1) непрерывны на Y.
Далее фиксируем некоторую неопределённость y = yd ? Y
и введём мноество ситуаций x ? X , удовлетворяющих условию индивидуальной рациональности для функций выигрыша
fi (x, y ) (i = 1, 2) :
n
o
X (y d ) = x ? X|fi (x, y d ) > fi0 [y d ? (i = 1, 2) .
(2.2)
Л е м м а 2.1. Имеет место
?01 [y d ? = max min ?1 (x1 , x2 , y d ) = f10 [y d ? ? C1 [y d ?,
x1 ?X1 x2 ?X2 (2.3)
?02 [y d ? = max min ?2 (x1 , x2 , y d ) = f20 [y d ? ? C2 [y d ?,
x ?X x ?X
2
где
2
1
1
Ci [y d ? = fi (x? (y d ), y d )(i = 1, 2).
В самом деле, из (1.4) получаем
max min
x ?X x ?X
1
1
min
= xmax
?X x ?X
1
1
2
2
h
2
2
h
?1 (x1 , x2 , y d )
i
=
?f1 (x? (y d ), y d ) + f1 (x1 , x2 , y d )
i
min f1 (x1 , x2 , yd ).
= ?C1 [yd? + xmax
?X x ?X
1
1
2
54
2
=
У т в е р д е н и е 2.2. Если ситуация x ? X (yd )
(мноество X (y d ) определено в (2.2)), то
?1 (x, y d ) > max min ?1 (x1 , x2 , y d ) ,
x1 ?X1 x2 ?X2 (2.4)
?2 (x, y d ) > max min ?2 (x1 , x2 , y d ) ,
x ?X x ?X
2
2
1
1
и обратно.
Д о к а з а т е л ь с т в о. Утвердение следует из (1.4),
(2.3) и цепочки эквиваленций
i
h
i
x ? X (y d ) ? x ? X|fi (x, y d ) > fi0 [y d ? (i = 1, 2) ?
h
i
? x ? X|fi (x, y d ) ? Ci [y d ? > fi0 [y d ? ? Ci [y d ? (i = 1, 2) ?
h
i
? x ? X| ? i (x, y d ) > ?i0 [y d ? (i = 1, 2) .
h
З а м е ч а н и е 2.1. Неравенства (2.4) євырезают из
мноества X те ситуации x , которые удовлетворяют условию
индивидуальной рациональности для єминус функций риска.
Фактически утвердение 2.2 показало, что мноество ситуаций,
которые удовлетворяют условию индивидуальной рациональности как для функций выигрыша в игре (1.1), так и для єминус
функций риска, совпадают меду собой (вследствие специального вида функций риска (1.4)). Этот факт будет использован в
следующем определении.
О п р е д е л е н и е 2.1. В кооперативной игре (1.1)
(без побочных платеей и при неопределённости) ситуация
xS ? X реализует гарантированный по выигрышам и рискам
делё (f1S , f2S , S1 , S2 ) , если существует неопределённость
yS ? Y , для которой fiS = fi (xS , yS ), Si = i (xS , yS ) (i = 1, 2) и
1) неопределённость yS ? Y является минимальной по Слейтеру
в четырёхкритериальной задаче
(2.5)
Y, {fi (xS , y ), ?i (xS , y )}i=1,2 ,
55
которую получаем из (1.5) при фиксированной ситуации
x = xS , (т.е. при любых y ? Y несовместна система неравенств
fi (xS , y ) < fiS ,
2) ситуация
даче
xS ? X
i(xS , y) > Si (i = 1, 2));
(2.6)
является максимальной по Слейтеру в за-
hX (yS ), {fi (x, yS ), ?i (x, yS )}i=1,2 i ,
(2.7)
которую получаем из (1.5) при фиксированной неопределённости y = yS и заменой X на X (yS ) , где X (yS ) удовлетворяет условию индивидуальной рациональности (2.2) для функций
выигрыша fi(x, y) (i = 1, 2) в игре (1.1) при yd = yS (т.е. при
любых x ? X (yS ) несовместна система неравенств
fi (x, yS ) > fiS ,
i(x, yS ) < Si (i = 1, 2)).
(2.8)
?ри этом f S = (f1S , f2S ) назовём гарантированным векторным
выигрышем, S = (S1 , S2 ) | гарантированным векторным риском, F S = (f1S , f2S , S1 , S2 ) | гарантированным по выигрышам
и рискам делеом игры (1.1), а тройку (xS , f S , S ) ? X ╫ R4 |
гарантированным по исходам и рискам решением кооперативной
игры (1.1).
З а м е ч а н и е 2.2. a) предлоенное здесь определение является аналогом седловой точки (xS , yS ) ? X ╫ Y скалярной функции F (x, y) , которая определяется цепочкой равенств
F (xS , y ) = F (xS , yS ) = max F (x, yS ).
min
y?Y
x?X
(2.9)
В самом деле, левое равенство в требовании 1) из определения
2.1 заменено на векторный минимум (по Слейтеру), а правое в 2)
заменено на векторный максимум (таке по Слейтеру). В определении моно было бы использовать и другие векторные оптимумы (по ?арето, по Борвейну, по Доффриону и А-оптимумы);
56
b) из требования 1) определения 2.1 получаем єгарантирующий смысл предлагаемого понятия. Он состоит в том, что из
несовместности системы (2.6) следует: при реализации в игре
любой неопределённости y ? Y и применении игроками стратегий из ситуации xS соответствующие выигрыши fi(xS , y) не
могут стать меньше fiS и одновременно соответствующие риски
i(xS , y) | больше Si , то есть гарантированный векторный выигрыш f S ограничивает снизу векторный выигрыш f (xS , y) для
всех y ? Y , а гарантированный векторный риск S ограничивает сверху векторный риск (xS , y) при тех е неопределённостях
y?Y ;
) для построения гарантированного по выигрышам и рискам
делеа достаточно построить пару (xS , yS ) ? X ╫ Y , удовлетворяющую требованиям определения 2.1, а затем с помощью
(xS , yS ) уе найти fiS = fi(xS , yS ), Si = i(xS , yS ) (i = 1, 2) .
Эту пару (xS , yS ) будем дальше называть седловой точкой по
Слейтеру для игры (1.5).
3.
Достаточные условия
Введём функции
H1 (x, y, ?)
=
2
P
i=1
H2 (x, y, ? ) = ?
[fi (x, y) ? (1 ? ?i)fi (x? (y), y)?,
2
P
i=1
[fi (x, y) ? (1 ? ?i )fi (x? (y), y)?,
(3.1)
где x? (y) | непрерывная на Y вектор-функция, являющаяся
максимальным по Слейтеру решением задачи (1.2) при любом
y ? Y ; постоянные ?i , ?i ? [0, 1? (i = 1, 2) .
У т в е р д е н и е 3.1. (Достаточные условия существования седловой точки (xS , yS ). ) ?усть существуют кон-
57
станты
?i , ?i ? [0, 1? (i = 1, 2) и пара (xS , yS ) такие, что
max H1 (x, yS , ?) = H1 (xS , yS , ?),
max
H2 (xS , y, ? ) = H2 (xS , yS , ? ).
y?Y
x?X (yS )
Тогда пара
игры
(1.5);
(x S , y S )
(3.2)
является седловой точкой по Слейтеру для
здесь мноество ситуаций
X (yS ) (удовлетворя-
ющих условию индивидуальной рациональности) определено в
(2.2), (2.1).
Д о к а з а т е л ь с т в о. Согласно работе [3, .71? ситуация xS ? X (yS ) будет максимальной по Слейтеру в четырёхкритериальной задаче (2.5), если существуют постоянные
?i ? [0, 1? (i = 1, 2) такие, что
max [?1 f1 (x, yS ) + ?2 f2 (x, yS ) ? (1 ? ?1 )1 (x, yS )?
x?X (yS )
?(1 ? ?2 )2 (x, yS )? = Idem[x ? xS ?.
?одставляя сюда явный вид функций риска i(x, y) (i = 1, 2) из
(1.4), получим, с учётом обозначений (3.1), первое равенство из
(3.2). Справедливость второго равенства из (3.2) устанавливается
аналогично.
З а м е ч а н и е 3.1. Введём вспомогательную бескоалиционную игру двух лиц
h{I, II}, {X, Y }, {H1 (x, y, ?), H2 (x, y, ? )}i .
(3.3)
В игре (3.3) игрок I за счёт выбора своей стратегии x ? X (ситуации для игры (1.1)) стремится к возмоно большему выигрышу
(значению своей функции выигрыша H1 (x, y, ?) ) при дополнительном ограничении x ? X (yS ) (где X (yS ) мноество ситуаций x ? X игры (1.1), удовлетворяющих условию индивидуальной рациональности (2.2) для функций выигрыша в игре (1.1)
при yd = yS ). Игрок II за счёт выбора своей стратегии y ? Y
58
(неопределённости в игре (1.1)) стремится к возмоно большему
значению своей функции выигрыша H2 (x, y, ? ) . Тогда равенства
(3.2) определяют ситуацию равновесия по Нэшу (xS , yS ) в бескоалиционной игре двух лиц (3.3) при дополнительном ограничении x ? X (yS ) . Заметим, что в (3.3) постоянные ?i , ?i ? [0, 1?
и функции выигрыша Hi(╖) (i = 1, 2) определены в (3.1).
Описанный факт сведения задачи построения пары (xS , yS ) к
находению ситуации равновесия по Нэшу в игре (3.3) при ограничении x ? X (yS ) моет быть использован,
во-первых, при выявлении достаточных условий ( в виде ограничений на элементы игры (1.1)), при которых существует гарантированный по выигрышам и рискам делё;
во-вторых, при построении явного вида гарантированного решения для частных видов игры (1.1).
Дальше будет рассмотрен частый вид игры (1.1), для которой
будет предлоен конструктивный способ построения гарантированного делеа.
4.
Игра с єразделёнными функциями выигрыша
Рассмотрим игру (1.1), где функции выигрыша игроков имеют
вид
fi (x, y ) = i (x) + ?i (y ) (i = 1, 2),
(4.1)
то есть рассматриваем кооперативную игру двух лиц при неопределённости и без побочных платеей
h{1, 2}, {Xi }i=1,2 , Y, {i (x) + ?i (y )}i=1,2 i .
(4.2)
В игре (4.2) мноество Xi стратегий xi у i -го игрока и мноество Y неопределённостей y те е, что в (1.1), отличие лишь в
том, что функции выигрыша fi(x, y) єразделены по ситуациям
и неопределённостям, именно, имеют вид (4.1). Для игры (4.2)
будем предполагать, не оговаривая специально, что выполнено
59
У с л о в и е 4.1. Мноества Xi (i = 1, 2) и Y суть непустые компакты, а скалярные функции i(x) (?i (y)) (i = 1, 2)
непрерывны на X = X1 ╫ X2 (соответственно на Y ).
Будем таке использовать двухкомпонентные векторы
= (1 , 2 ), ? = (?1 , ?2 ).
Л е м м а 4.1.
?ри любых неопределённостях
функция риска для функции выигрыша
i(x) + ?i (y)
y?Y
имеет вид
i(x, y) = i(x? ) ? i(x) (i = 1, 2),
(4.3)
x? ? X S | мноество максимальных по Слейтеру альтернатив x? в двухкритериальной задаче
где
hX, (x)i .
(4.4)
Д о к а з а т е л ь с т в о. Задача (1.2), с учётом (4.1),
примет вид
hX, {fi (x, y ) = i (x) + ?i (y )}i=1,2 i ,
(4.5)
а максимальная по Слейтеру ситуация x? (y) для (4.5) определяется несовместностью (при кадом y ? Y ) системы из двух
неравенств
i(x) + ?i (y) > i(x?(y)) + ?i(y) ?x ? X (i = 1, 2),
что эквивалентно несовместности
i(x) > i(x?(y)) ?x ? X (i = 1, 2).
?оследнее означает, что, во-первых, x?(y) не зависит явно от y ,
во-вторых, x? является максимальной по Слейтеру ситуацией в
двухкритериальной задаче (4.4) (мноество их в лемме 4.1 обозначено символом X S ). Исходя из (1.4), функция риска примет
вид (4.3).
60
З а м е ч а н и е 4.1. Так как по условию 4.1 мноество
X является компактом в Rn , а i (x) (i = 1, 2) непрерывны,
то из работы [3, . 142? следует, что мноество X S есть непустой компакт. В качестве x? моно взять любую точку их X S ,
но она долна быть одной и той е для обеих функций риска
i(x, y) (i = 1, 2) .
?ерейдём к построению мноества (2.2). Введём обозначения
для максиминов 0i (i = 1, 2) и максиминных стратегий x0i
(i = 1, 2) :
01 = xmax
min 1 (x1 , x2 ) = xmin
1 (x01 , x2 ),
1 ?X1 x2 ?X2
2 ?X2
02 = xmax
min 2 (x1 , x2 ) = xmin
2 (x1 , x02 ).
?X x ?X
?X
2
2
1
1
1
(4.6)
1
Заметим, что из (4.6) получаем
01 6 1 (x01 , x2 ) ?x2 ? X2 ,
02 6 2 (x1 , x02 ) ?x1 ? X1 .
(4.7)
Кроме того, согласно работе [2, . 109? при выполнении условий
4.1 указанные в (4.4) максимины i0 и максиминные стратегии
x0i (i = 1, 2) существуют.
Л е м м а 4.2. Для любых неопределённостей y ? Y
мноество (2.2) в игре (4.2) имеет вид
= x ? X|i(x) > 0i (i = 1, 2) ,
X (y ) = X
(4.8)
при этом мноество
является непустым компактом.
X
Д о к а з а т е л ь с т в о. Мноество (2.2) для игры
(4.2) преобразуется следующим образом:
n
o
X (y d ) = x ? X|i (x) + ?i (y d ) > i0 + ?i (y d ) (i = 1, 2) =
=
x ? X|i (x) > 0i (i = 1, 2)
61
= X ? X.
Мноество X не пусто, так как ситуация из максиминных стратегий x0 = (x01 , x02 ) в (4.6) удовлетворяет неравенствам (в силу
(4.7))
i(x0 ) > i0 (i = 1, 2),
и, следовательно, x0 ? X . Наконец, мноество X замкнуто,
согласно нестрогим неравенствам в (4.8). Так как X ? X , а X
ограничено (что следует из компактности X = X1 ╫ X2 ), то и
ограничено. Из ограниченности, замкнутости и непустоты X
X
получаем, что мноество X из (4.8) есть непустой компакт.
У т в е р д е н и е 4.1. Если выполнены условия 4.1,
,
то в игре (4.2) для всех y ? Y существует ситуация xS ? X
реализующая гарантированный по выигрышам и рискам делё
(xS ) + ?(y), (x? ) ? (xS ) ;
xS | максимальная
по Слейтеру ситуация в двухкрите определено в (4.6),
риальной задаче X, (x) , мноество X
?
(4.8), x | максимальная по Слейтеру ситуация в
задаче hX, (x)i .
здесь
Д о к а з а т е л ь с т в о. Для игры (4.2) мноество
(лемма 4.2). Тогда, согласно требованию 1) определения 2.1, виду fi(x, y) из (4.1) и i(x, y) из (4.3), при всех y ? Y
несовместна система из четырёх неравенств
i(xS ) + ?i(y) < i(xS ) + ?i(yS ),
(4.9)
i(x?) ? i(xS ) > i(x? ) ? i(xS ) (i = 1, 2).
Но вторая подсистема обращается в равенства, и поэтому система (4.9) несовместна при любых y ? Y (в качестве yS моно
использовать любую неопределённость y ? Y ).
Требование 2) определения 2.1 для игры (4.2) сводится к несовместности (при любых x ? X ) системы из четырёх неравенств
i(x) + ?i(yS ) > i(xS ) + ?i(yS ),
i(x? ) ? i(x) < i(x? ) ? i(xS ) (i = 1, 2),
X (yS ) = X
62
что эквивалентно несовместности при любых x ? X системы из
двух неравенств
i(x) > i(xS ) (i = 1, 2).
(4.10)
В свою очередь, несовместность системы (4.10) при всех x ? X
означает, что xS есть максимальная
по Слейтеру ситуация в
двухкритериальной задаче X, (x) . Вследствие компактности
(лемма 4.2), непрерывности компонент i(x) вектора
X
(x) = (1 (x), 2 (x)) и из работы [3, . 142? следует, что такая
ситуация xS ? X существует.
З а м е ч а н и е 4.2. Из утвердения 4.1 получаем следующий способ построения гарантированного по выигрышам и
рискам решения игры (4.2):
a) найти максимальную по Слейтеру ситуацию x? в двухкритериальной задаче hX, {i (x)}i=1,2 i ;
b) найти максимины
min 1 (x1 , x2 ),
01 = xmax
1 ?X1 x2 ?X2
min 2 (x1 , x2 );
02 = xmax
?X x ?X
2
2
1
1
) построить мноество
= x ? X|i (x) > 0i (i = 1, 2) ,
X
это мноество определяется пересечением
\
(X ) = (X ) R>2 + 0 ,
S
где (M ) =
(x), R>2 = { = (1 , 2 )|i > 0 (i = 1, 2)} , тоx?M
гда R>2 +0 есть сдвиг первой четверти координатной плоскости
R2 в точку 0 = (01 , 02 ) ;
d) найти максимальную
по Слейтеру
ситуацию xS в двухкри
{i (x)}i=1,2 ; для этого достаточно при
териальной задаче X,
каком-либо числе ? ? [0, 1? решить оптимизационную задачу
max [?1 (x) + (1 ? ?)2 (x)? = ?1 (xS ) + (1 ? ?)2 (xS ),
x?X
63
заметим, что такой е приём (моет быть, с другим числом
? ? [0, 1? ) моно применить при построении x? в a);
e) выписать явный вид гарантированного по выигрышам и
рискам решения игры (4.2) по формуле
xS , (xS ) + ? (y ), (x? ) ? (xS ) ?y ? Y.
Заметим, что вообще говоря, во-первых, x? 6= xS , во-вторых,
как x? , так и xS определяются неоднозначно вследствие мноественности максимальных по Слейтеру альтернатив в многокритериальных задачах (в предлоенном здесь алгоритме моно
использовать любые).
Автор благодарит В.И. Жуковского за постановку задачи и
обсудение работы.
Список литературы
1. Sawadge L.Y. The theory of statistial deision
//J. Amerian Statistial Assoiation. 1951. Є 46. P. 55-67.
2. Жуковский В.И. Кооперативные игры при неопределённости и их прилоения. М.: Эдиториал УРСС, 1999.
3. ?одиновский В.В.,
Ногин В.Д. ?арето-оптимальные ре-
шения многокритериальных задач. М.: Наука, 1982.
64
Документ
Категория
Без категории
Просмотров
6
Размер файла
218 Кб
Теги
рисками, выигрыша, дележа, игре, гарантированное, кооперативний
1/--страниц
Пожаловаться на содержимое документа