книги / Математические методы в системах поддержки принятия решений

s	{0>	<l>	{2}	...	w	{0,1>	{0, 2}
<HS)	0	0	0		0	(Pi - p ) x 1	(Pl - P)xt
							Продолжение таблицы
(»-	1. »}		{0, 1, 2}		{n -	2, n - 1, n}	{0, 1, 2, .... /»}
0			2			0	n
			]£(/>/ -P)x,				£ ( P i ~ P )X>
			/=0				/=0

Возникает вопрос; как справедливым образом распределить доход между производителем и потербителями сырья — участниками коали­ ции. Для получения ответа вычислим соответствующие компоненты

вектора Шепли Ф0(й) — доход производителя (/ = 0) и Ф((б) — доход »- го потребителя. Имеем:

(|‘У|-1)!(/»+Н5|)!

<*>.<*)= X	<d (5)-6(5V = 0))x,. =
ie S
S c N

(|5|-1)!(я+Н5|)!m - 4 S ) Xl.

€5	(«+!)!
S c N
Перед очередной записью правой части полученного выражения за­
метим, что всего может быть		различных коалиций; но только к

Cjfj'2 может «подключаться» производитель. Такое утверждение следует

из анализа таблицы и непосредственно подтверждается равенством

= с1*Н + c m-2

где второе слагаемое в правой части есть количество коалиций, в каж­ дой из которых может участвовать производитель, а первое — количест­ во коалиций, участие производителя в которых исключено. Коалиции из числа cjfj*' дохода не доставляют; они исключаются из дальнейшего

вычисления Ф0($). В связи с этим получаем, что

№2
Y (|5|-1)!(я+Н.У|)!	(W-1)!	f	_
(л+1)!	(1,^1- 2)!(я+Н‘У|)! h * '

141

S O T - » „

f М - Р

S' n

/=1

Y , ( p , - p ) x i- n(n+1) /*i

Итак, Ф0(й) = ^ ^ ( л - p )x (. 2 /=1

Выполним аналогичные вычисления для компонент Ф,{б), / * 0 , * =1 , 2 , п, и получим Ф /б) = 0,5(р, - р)х, — результат, определяющий

доход /-го потребителя.

Сходным с вектором Шепли является понятие индекса Банзафа. Определение. Индексам Банзафа для i-го игрока в игре с характеристи­

ческой функцией 6 называется величина р, =	где т^б) — число коа-
	Д б )

лиций, в которых игрок / является решающим, коалиции становятся выиг­ рывающими, Е(Ь) ^ ( б ) , И — [1, п].

/еЛГ Заменим аксиому Шепли о носителе игры двумя аксиомами:

Ф,(б) = 0 — для нулевого игрока i, т.е. для которого б (5\{/}) = 0, S c zN , и ^ Ф , (б) = d(N). Тогда для класса простых игр, т.е. таких игр (N,

i e N

6), что 6(6) = 1 или 6(5) = 0 V S и 6(5) > 6(7), S-=> Т, очевидно, что ком­ поненты вектора Шепли будут вычисляться по выражению вида

0 ,(0 )- у «	«	.
Игрок / называется вето-игроком,	когда б(Л/\{/}) = 0 для простой

игры (Т, б) в (0—1) редуцированной форме, т.е. когда 6(5) = 1 или 6(5) = 0 V5 с N.

Таким образом, индекс Банзафа есть показатель важности игрока при выборе окончательного подходящего для него решения; иначе гово­ ря, этот индекс показывает долю коалиций, в которых игрок i — ре­

шающий, а вектор Шепли при этом преобразуется в индекс весов с зна­ чениями из [0,1] и показывает долю упорядочиваний игроков, при которых игрок i приносит решающий голос при принятии решения по­

средством голосования.

При организации кооперативной игры, как уже отмечено, естест­ венным образом возникает вопрос, как сторонам образовать коалиции,

142

если все они стремятся к справедливому распределению выигрыша и характеристическая функция суперадцитивна, т.е.

!}(£,) + ■Q(S2) <

u S2), S , n S 2 = 0 , S, U S2c N.

Для ответа на него наряду с использованием подхода, основанного на проверке компонент вектора Шепли, введем величину, называемую [48; 78] эксцессом коалиции:

e(Sjc) = -d(S) — x(S), x(S) =	V S ^ N , x(S) — дележ,
	i e S

т.е. e(Sjc) — мера неудовлетворенности сторон, входящих в коалицию S. Это линейная непрерывная функция по х и дискретная по коалициям.

Общее количество возможных коалиций, без учета пустой, равно 2W— 1. Совокупность эксцессов из 2W — 1 элементов значений опреде­ ляет близость дележей к характеристической функции.

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

min т а xe(S,x),

{х| S c N

где {*} — множество дележей.

Это дискретная минимаксная задача по терминологии, данной в [7], ее решение может быть получено согласно необходимому условию

min	max f— e (S ,x ')y x - x '	[ = 0 ,
(x)	5«Г(х*)^Эх	)

где K(x*) — совокупность коалиций, на которых достигается минимум верхней огибающей эксцессов по S, т.е. огибающей вида max е(5,х ).

С учетом отмеченного свойства эксцесса как функции от х и

свойств дележей как векторов необходимое условие можно переписать в виде

min max		- x ] ),..., £ ( * , - x 't ) = 0,
w	{us,	j

где Sb ..., Sme У(х*), и затем применить [6] принцип уравнивания част­

ных критериев — сумм этого необходимого условия. Полученное выра­ жение означает, что стороны образуют коалиции с одинаковым эксцессом.

143

5.4. Необходимые и достаточные условия оптимальности выбора решений в динамических

кооперативных конфликтах

Введенные принципы оптимальности остаются в силе и при оты­ скании оптимальных решений сторон, принимающих участие в дина­ мических кооперативных (коалиционных) конфликтах. В этом случае любая коалиция S c N располагает векторным уравнением состояния

динамической системы

г(0= Л 0, z(t), и,(0,

«,(0> «ж (0, ,

h < t< T ,

множеством стратегий

U .= Y [ U lt us(f) е Us, u,{f) е U„

i<=s

функцией выигрыша

Js (us (t),U j« )J e N \S ) =

т

= 5 > , ( 7 \ Z(T)) + J F , (t, Zff), И (Г),.... и, (0, им (/),.... ик (t))dt] ies

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

д (0 ) = 0, б(Л0 = шах (и,, и2,..., и„),

/ = 1

) = шах min Js (us ,U j ,j e N\S.

Для вычисления fl(S) — гарантированного выигрыша воспользуемся необходимым и достаточным условием п. 2.3 и запишем его для гаран­ тирующей стратегии коалиции S. Чтобы стратегия и® коалиции S была

гарантирующей, необходимо существование функций %(/, z) и < р г ) , непрерывных всюду на [f0, 7] х Е? и непрерывно дифференцируемых на

[/0, 7] х £*, за исключением конечного числа гиперплоскостей tk, к = 1,

2, ..., и таких, чтобы выполнялись условия:

1) ips (T,z(T)) = J	g0 i (T,z(T)), 9 NXS(T ,Z(T))= ^ 0 j ( T ,z ( T ) ) V z e Р ;
/eJ

2)во всех точках непрерывной дифференцируемости функций <р„

ФN \S

144

“A	^ FJ{t,us'u ^ N'z)
	jeN\S

= Ж [^L+^ L^/,Ms ’UW ’d + ] b Fi (/)M * 'u S# = 0;

3)для любых допустимых us e Us

4 f~+H r ^ t,us,Uf*s,z)+^ F‘(r,M5,Unxs,z)*°*

ie S

+~ l£ Lf('t,us,UNXS,z)+ ^ FJ (t,us,UNSS,z)~°'

je N \S

Вычисление ti(7V) суть задача оптимального управления для условий определенности (она может быть решена методами, изложенными в п. 6.8 при введении <р*(/,г(0)-

Задача. Пусть движение системы описывается уравнением &t) = z(t) + u x(t) + u2{t),

z(t0) = 2, на отрезке времени [f0 = 0, Г = 2], где управления ux(t) е [-1, 0], u2{t) е [-1, 0] и их выбор должен осуществляться согласно критериальным функционалам /|(д(0) и J2{u{t) соответственно. Требуется найти значения характеристической функции в кооперативной динамической игре двух сторон при условии, что их цели достигаются посредством мак­ симизации введенных критериев, которые определены функционалами

		т				т
	Ji(uu u2) = jzf.t)dt+ z2(T) и				У2(и,,1/2) = - | z k t)d t- z 2(T).
		о				о
Р е ш е н и е . Для вычисления значений характеристической функции
			* 0 » .	Щ2}), Щ\> 2}),
		й({1}) = max			fl({2})= шах т т 12(щ ,и2),
		u \	u2		и |	w2
		#({U}) = max(/,(w1,w2)+ ( / 2(Wj,i/2))
			i/,«2
воспользуемся выражениями достаточных условий
max m inf^		1^ * — (г<0+ u{(t))+		«2(/)+ z(/)l = 5$lL5lM 2,			<р(г(7),7) = г 2(7),
•i	»i [	«			J	Э/
max m i n | M		M ( J < 0 +	«,(/))+ и2« )~		* 4 = - М Ж М ,		<р(г(7),7) = - гЦт),
ч	ч [	«			J	Э/

«,(*)+ Иг(/))+ г(,)- z ( o J = - ^ |f ^ '

4>fe(7),7) = г2(7) - г2(7),

Ю - 5396

145

из которых получаем оптимальные управления
a) и°(0 = 0, u%(t) = - 1, если ^ -		> О, или u \ t ) = - 1, «“(/) = о, если ^ - < 0;
1	dZ	1		дZ
b) « ° (/)= - 1 ,	«2 ( 0 = 0, если ^ - > 0 , или i/°(0 = 0, х £ (/)« -1 ,			если ^£L <0;
	dz	1		dz
c) «°(0 = «2(0 = 0, если ^ > 0, или «°(0 = «2(/) = -1 ,			если	< 0.
1	dz	1	Эz

При таких управлениях следует вычислить траектории движения системы на отрезке времени [0, 2] и значения характеристической функции. Приведем результаты вычисле­ ния для случаев:

а) при	> 0 траектория г°(0 = 1 + е', коалиция представляется только первой сто-
	oz
роной, значение характеристической функции

		2
	й({1}) = max m in /i(«i,«2) = J o + e')dt+ (1+ ет)2 = 1+ e 2 + (1+ e2)2;
	и \ «2	о
b) при	> 0 траектория z°(0 = 1 + e', коалиция представляется только второй сто-
	Эz
роной, значение характеристической функции

2

tf({2}) = m axm in/2(«1,«2) = --f(l + e ') d t- ( \ + ет)2 = -(1+ е2)- (1 + е2)2;

«1 «2	J
	о

rkft

c) при — > 0 траектория zP(t) = 2е', в этом случае обе стороны составляют одну коа- dz

лицию, значение характеристической функции

	а
д({1Д}) = тах(У ,(и,,и2)+ / 2(и,,и2)) =	U e 'd t-	[ l e 'd t + i l e 'f ~ (2 е')г =0.
uxu2	J	J

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

Штакельберга и Гермейера

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

146

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

Сторона-лидер свою функцию выигрыша F(x, у) и функцию выиг­ рыша другой стороны G(x, у) использует как информацию для предска­

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

наилучших действий ведомой стороны, т.е.

У(х) = Arg max G(x,y).

yeY

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

путем max min F(x,y).

х еХ yeY

Таким образом, устанавливается ситуация равновесия по Штакельбергу. Проиллюстрируем вычисление конкретно.

Задача. Пусть две конкурирующие фирмы поставляют на рынок товар одного и того же назначения в количестве х { (xj = х) и х2 (х2 = у) соответственно, цена товара р = 1 - *| - *2»Р > 0. Прибыль фирм от реализации товара:

F(x, у) = П!(X1, *2, р) =рх{ - 0,5*2,				с (*> У) = П2(*|, *2. Р) = Рх 2 - 0.5*2,
*|еДГ,»ДГ,	*2 s		* 2	= К,	Xi = * 2	= [0, 0,5].
Найти оптимальные стратегии поведения фирм по Штакельбергу и сравнить их со
стратегиями, оптимальными по Курно, Нэшу, Парето.						согласно выражениям
Р е ш е н и е . Определяем с т р а т е г и и				по	К у р н о
ЭП.(х.,х2,р)			л			л
— 1V 1		= 0 при условии — - = 0,
dX|
ЭП2(-У1,Х2,р) _			Q п р и у СЛОВИИ			= 0:
дх2						дх2
(1 -* , - * 2)- * ,	- 1 = 0;			(1 -* , - *2) - *2- j = 0.

Отсюда находим оптимальные по Курно стратегии х,* = х2 = 1/6.

Н э ш о в с к и е с т р а т е г и и определяются из системы уравнений

шах П|(Х|,Х2,/’),	max n 2(xj*,x2,p)
Xj€X|	*2€^2

и граничных значений х { е [0,#0,5], х2 е [0, 0,5]. Из решения системы уравнений с учетом граничных условий получаем ситуации равновесия — оптимальные стратегии:

(х, = 0, х2 = 0,5), (х, = 0,5, х2 = 0), (х, - 1/6, х2 = 1/6).

ю*

147

С т р а т е г и и по П а р е т о	найдем	согласно аналитическому методу построения
множества Парето в пространстве альтернатив				х Х2, т.е. по выражению
grad U fa , хъ р) = - \			grad П2(х,, хъ р).
Или получаем систему
ЭП} _	^ ЭП2	ЭП1		^ ЭП21
Эх,	ЭЬс,	Ъх2		дх2 ’
из ее решения имеем
*1 + х2 = 0,5		и	х, + х2 = 1/4.

Искомое множество Парето описывается уравнением Xj + х2 = 1/4.

Этот результат непосредственно устанавливается проверкой выполнения равенства

grad Щ х ь х2, р) = - \ grad П2(х,, х2, р)

для стратегий, взятых из множества х х + х2 = 1/4 и из множества х, + х2 = 0,5, е

*2 6 *2, * - * 2 - 1 0 , 0,5].

Так, возьмем из множества х, + х2 = 0,5 стратегию х1=1/8, х2 = 1/8. Далее, выполним

все действия согласно выражениям
	ЭП|	и	а п ,	э п 2
			— -	ах2 х, =х2=1/8
Xj*X2mt/S	^*2 X, «2=1/8		ах, *,=*2=1/8

получим подтверждение проверяемого равенства. Аналогичные же действия для произ­ вольно выбранной стратегии х, = 1/4, JC2 = 1/4 из множества х, + х2 = 0,5 не приводят к подтверждению проверяемого равенства.

Найдем оптимальные с т р а т е г и и по Ш т а к е л ь б е р г у , когда первая фирма (П^х,, х2)) — лидер, т.е. когда она имеет право первого хода и сообщает второй фирме (П2(х,, х 2)) свою стратегию х ь а вторая находит при этом свою наилучшую стратегию по­ ставки товара на рынок как x2(xj) из условия максимизации своего критерия — прибыли, т.е. из условия

= 0,

откуда xj(x, ) = 1/4 - 0,5х, — оптимальная стратегия второй фирмы.

Теперь первая фирма, зная стратегию х2(х ,), Находит свою оптимальную стратегию

из условия	= 0, в результате х х = 1/4 — оптимальная стратегия первой фирмы.
Эх,	•

Итак, оптимальные по Штакельбергу стратегии фирм есть

Х\ = 1/4, х2(х ,) = 1/8.

Из решения данной задачи следует очевидный вывод: наибольшую прибыль фирмы могут обеспечить, если они будут следовать оптимальным стратегиям по Штакельбергу.

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

148

сообщаемой ей стратегии сторона-лидер может взять любую функцию fly) 6 {/}, у € Y. Получив fly), ведомая сторона максимизирует свой вы­

игрыш; естественно, что при этом определяется и

Y (f) = Arg max G (f{y),y)

уе Г

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

согласно ее критерию эффективности

sup inf F (f(y),yY (Л п /)

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

Теорема Гермейера. Наилучший гарантированный результат стороны-

лидера равен
	max[A, М],
где М = min max F(x,y),	Е = Arg max [min <7(x,y)],
y e Y x e X	y e Y	x e X
sup F (x,y), D * 0
K = (x , y ) e D
D & 0
D = \(x>y) e X x Y\G(x9y) > max min G(x9y )L
I	y e Y x e X	I

и каждая стратегия JC°, соответствующая max[A", M\, составляет опти­ мальную гарантирующую стратегию первой стороны, иначе говоря, в про­ цессе отыскания max [А- М] устанавливается и искомая оптимальная гарантирующая стратегия первой стороны. В общем случае искомая стра­ тегия является е — оптимальной,

х®, если у - у г,	К> М ,
х oеpt • х е(у), если у е Е ,	К й М ,

хИ (у) — стратегия наказания в остальных случаях,

инаилучший гарантированный результат равен тах[А, М\ —е.

Изложенные в теореме необходимые условия составляют основу

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

Рассмотрим двухуровневый иерархический конфликт. Первый уро­ вень представляет одну сторону, второй п — независимых равноправ­

149

ных других сторон. Динамика конфликта описывается системой диффе­ ренциальных уравнений

# t) = f(x(t),u(t)), x(t0) = х0,

=	Zi(t0) = zM, i = 1 ,n,
t e [f„, 7], u(t) e	U, 6,(0 6 Vh	(*)

где u{t) — управление первой стороны;

6,(0 — управление /-й стороны второго уровня.

Динамика изменения состояния каждой /-й стороны второго уровня зависит как от своего управления 6,(0, так и от управления u(t) — пер­

вой стороны (верхнего уровня). Каждая сторона располагает своим функционалом выигрыша:

г	__
F { u ( t\m ) = J/o (x(t),z(t),u(t),m )dt, i=	1 ,П -
*0

функционал первой стороны,

г

F, (и(0,б, (0) = J /, (x(t),Zi (t),u, (0 ,6 , (t))dt

'о

— функционал /-й стороны второго уровня.

Каждая сторона стремится максимизировать свой выигрыш посред­ ством выбора оптимального управления при выполнении ограничений по динамике операции (*). Отмеченные сведения известны всем сторо­ нам. При этом первая сторона является ведущей, ей принадлежит право первого хода, и она сообщает свое управление u{t) всем сторонам второ­

го уровня. Последние максимизируют свои функционалы при условии полученного u(t), т.е.

6 “(/,«(0) = arg max / > ( / ) , б, (/)), / = 1,л. д/ (/)бК/

В результате, когда первая сторона сообщает оптимальное и°(0, име­ ет место ситуация равновесия (и0(/),б “(0,б “(О,...,б® (/)) в рассматривае­

мом иерархическом конфликте, которая является ситуацией равновесия по Нэшу. Но так как выбор оптимальных управлений сторонами второ­ го уровня осуществляется при получении от первой стороны соответст­ вующего u(t) е U, то первой стороне становятся известны реакции сто­

рон второго уровня — имеет место взаимная информированность. Поэтому первая сторона выберет для себя такое и°(0, чтобы выполня­ лось условие (максимальный гарантированный результат)

150