книги / Математические методы в системах поддержки принятия решений
..pdfs |
{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