Равновесие по Бержу тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Р Г Б ОД 1 а АПР 1995

Санкт-Петербургский Государственный Университет ФАКУЛЬТЕТ

ПРИКЛАДНОЙ МАТЕМАТИКИ - ПРОЦЕССОВ УПРАВЛЕНИЯ

На правах рукописи Вайсман Константин Семенович

УДК 519.833.2

РАВНОВЕСИЕ ПО ВЕРХУ (01.01.09 - математическая кибернетика)

(^

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

к

Санкт-Петербург - ¡995

- г -

Работа выполнена в Орехово институте.

Зуевс-ком педагогическо

Научный руководитель -

доктор физико-математи ческих наук, профессор В.И. Жуковский.

Официальные оппоненты

профе ссор, доктор физико-математических наук, академик РАЕН С.Н. Васильев,

Ведущая организация -

кандидат физико-математи ческих наук

Д.В. Кузютин.

Институт кибернетики им. В.М.Глушкова АН Украины

Защита состоится ЛлуЛе^^ 1995 р. на заседанш

специализированного совета К-063.57.16 по присувдешю учено; степени кандидата физико-математических наук в Санкт-Петербургском Государственном Университете.

*

С диссертацией можно ознакомиться в библиотеке Санкт-Петербургского университета.

Автореферат разослан " " 1995г.

Ученый секретарь специализированого совета,

доктор физико-математи- В.Ф.Горьковой

ческих наук

Общая характеристика работы

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

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

о \

зшения используется ситуация равновесия по Нашу" как цинственно возможное решение бескоалиционной игры. Этого же зшения придерживаются и в теории дифференциальных бескоалици-шых игр, развитие которой связано с именами Т.Ватера, .М.Вайсборда, В.В.Захарова, В.И.Жуковского, А.Ф.Кононенко, .Ф.Клейменова, Дж.Лайтманна, 0.А..Малафеева, Л.А.Петросяна, .Н.Пшеничного, А.А.Чикрия, С.В.Чистякова и др. Однако Данному ринципу оптимальности присущ ряд негативных сторон3}, в эстности, в диссертации выделены классы игр, в которых 1туация равновесия по Нэшу просто не существует. Одна из ззможностей "борьбы" с негативными свойствами - формализация звых видов решений, которые, обладая достоинствами ситуации звновесия п„ Нэшу, одновременно "снимали" бы некоторые его здостатки. Такому решению (равновесной по Бержу ситуации) и эсвящена диссертация.

Во-вторых, в исследованиях бескоалиционных игр не штывались помехи, возмущения и другого вида неопределенности, которых известны лишь границы изменений. Реальные же энфликты "протекают" в условиях неопределенности. Не имея ^формации о реализации конкретной неопределенности, игроки при ¿боре своих стратегий ориентируются на возможность появления обой из них. "Игровой смысл" неопределенностей - их можно

) Воробьев Н.Н. Основы теории игр. Бескоа/1*циощше игры.- М.: эука, 1984.- 945с.

) Nash D. Non-cooperative games // Ann. Math. - 1951. - V.54, 2.- P. 286-295.

) Жуковский В.И., Тынянский Н.Т. Равновесные управления много-жтериальных динамических систем.- М.: МГУ, 1984.- 224с.

- А -

трактовать как действия дополнительного игрока, который, в имея своей функции выигрыша, выбором неопределенности стремите максимально "навредить" выигрышам действующих игроков. Дву возможным подходам учета неопределенностей при формализаци решений бескоалиционной игры на основе концепции равновеси по Бержу посвящены главы II и III диссертации.

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

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

4 ) ' _

также подхода векторного максимина , и метод динамическог программирования, объединенный с методом функций Ляпунова.

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

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

Апробация работы. Основные результаты диссертации доложен в 1994г. на Всероссийской математической школе "Понтрягински чтения - V" (г. Воронеж), V школе "Математические проблемы эко логии" (г.Чита), III Международной конференции "Многокритери альные задачи при неопределенности" (г.Орехово-Зуево) и научны семинарах института Кибернетики им В.М.Глушкова и Санкт-Петер бургского университета.

4) Zhukovskii V.I., Salukvadze M.E. The Vector-Valued Maximin. New York: Academic Press, Inc., 1994.- 404p.

Публикации. Основные результаты изложены в препринте [б], статьях С1, 7 3 и тезисах [2, 3» 4, 51, некоторые из них выполнены в соавторстве. Утверждения, вошедшие в диссертацию, получены автором самостоятельно.

Структура и объем работы. Диссертация состоит из введения и трех глав, разбитых на 12 параграфов. Объем работы 110 стра-яиц машинописного текста. Библиография содержит 53 названия.

Содержание работы.

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

В первой главе рассматривается бескоалиционная игра N лиц:

г = < <Л <*»<«* >•

п .

'де in={ 1.....N> - множество номеров игроков; х^с ш 1 - множест-

ю стратегий xl игрока ie£N; упорядоченные наборы (xf ,...,xN)= x >сть сшуации игры Г; fAx)- функция выигрыш i-ro игрока.

n

1редяолагается, что ft{x) непрерывны на X = ПХ£. "Партия игры

¿=1

"' интерпретируется как одновременный и независимый выбор ;аждым из игроков Ы in некоторой "своей" стратегии х^ Xt, при itom игрок I заинтересован в получении возможно большего вы-грыша fi (х), {е ш.

Используются следующие обозначения

^ч*3^.....Xi-t *Xi+l.....XN^e *

^[NNi ,Xi )~(xt ......xi-l 'Xi 'xi +i • • * • •

Определение 1. Ситуацию x назовем равновесной по Берху ля игры (1). если

шах min ft {xt ) ^/^(зР), ¿«in.

Свойство 1. Для антагонистической игры (т.е. при т = {1,2} и /1 (х) = ~/г(х) = /(х)) равновесная по Бержу ситуация совпадает с седловой точкой функции ,хг).

Свойство 2. Ситуация равновесия по Бержу устойчива по отношению к отклонению от нее любых N-1 игроков.

Свойство 3. Выигрыши игроков в равновесной по Бержу ситуации х6 не меньше их гарантированных (максиминных) выигрышей.

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

Во второй главе рассматривается бескоалиционная игра прс неопределенности

< т. «,¥). Г(х,у) >, (2;

Здесь и и X те же, что и в игре (1). Неопределенности т/е у<= к"1, функция выигрыш {-го игрока задана непрерывной на Х*У скалярной функцией /¡(х,у), й и; N - вектор - столбец /(х,у) = = (/^х.у)...../ц(х.у))-

При принятии решений в игре (2) игрокам следует учитывать два обстоятельства:

• "бескоалиционный характер" игры,

• необходимость учета действия неопределенности.

Далее используем два подхода к формализации решения игр (2). Первый представляет собой аналог свдловой точки антагонис тической игры, второй - модифицирует понятие векторного лакеи мша*).

Определение 2. Пару (хв,у3)е ХхУ назовем равновесие Берха-Слейшера игры (2), если

a) при всех Х^^ имеет место

b) выполняются условия индивидуальной рациональности max min /¿Ц^.з^.у3) =£ /£ (д^.у3),

c) при любых у<= Y несовместна система неравенств

/¿(Ау) < f^^.y3),

Аналогично формализутся еще два решения'игры (2): равновесие Бержа-Парето, Берха-Джоффриона и установлена связь между данными тремя равновесиями. Все три введенных решения игры (2) являются гарантирующими (в "векторном смысле").

В §5 рассматривается линейно-квадратичная игра двух Лиц при неопределенности

Г2 = < {1.2}. {R2n.Rn>, (■ft(xi,X2.y))i=uz >. В этой игре Xt ,Хг<е CRn, уе lRm;

filXj.x^y) = xpitXt + 2х;в1гх'^ + xpi3x2 + у'Ъыу +

+ 2dJtxt + 2&[^хг + 2d'3y . (1=1,2)

где Df .- постоянные матрицы соответствующих размерностей, , D£3 и Bi4 симметричны, вектора-столбцы соответствующих размерностей и постоянны, штрих сверху обозначает операцию транспонирования .

Утверждение 1. Если

a) T>i3< О, Ъг{< 0, Bi4+DS4>0;

b) матрицы

игг. ъ1г. ъ-р21 - D;19D;2, d~]ъгг - <D\гг\3

невырозвдены,

то равнрвесие Бержа-Джоффриона (з?,уСл) (и, следовательно, равновесия Бержа-Парето и Бержа-Слейтера) игры Г2 существуют и имеют вид

- в -

уа = - (ъы+ъ^ги<11Э+<1гз). о)

Определение 3. Тройка {х* ,х*,у3)<в ш2п+т называется рав-навесиел Нзш-СлеСтера игры Г2, если

(х, ,ж|.у3) {х%х%,у3) к11, г

и при всех у« к® несовместна система неравенств

,у ) < /^^.а^.у®) (1=1.2).

Утверждение 2. Если в игре Г2 матрицы 1>и >0 и (или) В23>0, то в ней не существует равновесия Нэша-Слвйтера.

Следствие 1. Пусть для игры Г2 выполнены коэффициентные ограничения а), Ъ) из утверждения 1 и условия утверждения 2. Тогда в игре Г2 не существует равновесия Нэша-Слейтера, а равновесие Бержа- Слейтера (-Парето и -Джоффриона) существует и имеет вид (3).

Формализацию решения игры (2) (аналога векторного максими-на) проведем в три этапа

Этап 1°. Каждой ситуации х^ X игры (2) поставим в соответствие множество У3(г) минимальных по Слейтеру неопределенностей у3(х) в многокритериальной задаче

№) = < У, /(х,у)>,

которую получаем из (2), фиксируя ситуацию х.

Этап 2°. Для каждой у3(х)<^ построим бескоалиционную игру

Г (У3 (а:)) = < м, (ХЛ^, {/¿(х,у3(2))>

которую получаем из (2), положив у=у3(х)е у3, где зЯ есть множество всех у3(х) удовлетворяющих условию

/ОЕ.у) < /(Х,у3(х)), Ууе у,

(что означает отрицание /£(х,у) < /£(х,у3(х)), й и).

Пусть В(у3(г)) - множество ситуаций равновесия по Бержу агры Г(у3(х)).

Этап 3°. Обозначим через

В = и (х®,у3(х®))е х*У, у3(Х®)еЗЯ

т.е. В есть множество всех тех пар (хв,у3(хв)), где х® есть равновесная по Бержу ситуация игры Г(у3(х)), а у3(х®)- значение функции у3(х) при х=х®.

Определение 4. Пару (х*,у3(х*))е В назовем неулучшелыл равновесжл Берха-Слейтера (НРБС) игры (2), если

/(х\у3(х*)) i /(хВ,у3(хв)), У(хВ,у3(хв))е 0.

Свойство 4. Множество ¿Г* НРБС внутренне устойчиво, т.е. для любых двух НРБС (х(г),у(г))е 2"* (г = 1,2) будет

Лхт.у(1)) * Лх(г>,у<2)).

Третья глава посвящена линейно-квадратичной дифференциальной игре трех лиц при неопределенности:

«1.2.3}. 2. Ш.).=/>г>3 . 2. Ц(11,гД,Д,)),=11г1з>. (4)

В такой дифференциальной игре изменение управляемой системы 2 описывается линейным уравнением

з

х = А(Пх + Ё В Ц)и£ + В(1)2, х(^)=х ;

¿=1 *

„ Юу

вектора ХеК , , матрицы А(- )еСпхпС0,13], В. (■

е С [О.«], В(-)еС [0,-63; ■0=сопзЪ>О; начальная позиция

п*п£ п*ш

[0,тЭ)«кп; и£- управлящее воздействие 1-го игрока

(£=1.2,3). ъ- неопределенный фактор. Множество стратегий 1-го игрока

- ю -

U. = {Ut+ u.(t,s)|u.(t,x) = Q£(t)x, Q£ (• )eCn xn[0,«]>,

(i=1,2.3)

тогда множество ситуаций U=(Uf,U2,U3) будет U=Ul *U2*U3i множество неопределенностей (помех, возмущений и т.п.):

, Z = <Z+ z{t ,х)Iz(t,х) = P(t)x, Р(-)еС „ [О,«]}.

Кажднй игрок выбирает и использует "свою" стратегию U£ + u£(t,х) = Q£(t)x, U£el/£ (i=1,2,3). Независимо от действий игроков в игре (4) реализуется некоторая неопределенность Z + + z(t,x) = Р(£)х. В результате "развитие игры во времени" происходит в соответствии с векторным линейным однородным дифференциальным уравнением с непрерывными (по t) коэффициентами

х = £A(t) + | влг)йлг) + B(t)P(t)]x. x(tj=x.

£= 1

Решение этого уравнения x(t), t $ t ^ i>, "порождает'' реализации выбранных игроками стратегий и£Ш = u£(t,x(t)) = Q£(t)x(t) (i=1,2,3) и появившейся в процессе игры неопределенности zlt] = = z(t,x(t))= P(t)x(t).

На полученных в итоге пятерках (x(t), uf Сt], игШ, u3lt], zti]), t $ t ^ fl, определена функция выигрыша игрока i, заданная квадратичным функционалом

■б з

J. (U,Z,t ,х ) = х'Св)С.х('в) + Г( Е u'[t]D. .u.lt] +

ь ♦ * i L J J

t J=1

+ z'ltlb.zlt])« (i=1,2,3),

где квадратные матрицы соответствующих размерностей С£, D£j, Х£ постоянны и симметричны.

Определение 5. Пару (UB,Zs)e U*Z назовем равновесиел Бераса-СлеШера игры (4), с начальной позицией )е[0,-в)"Кп,

если

1°. ситуация UB=(U®,U|,U|) является равновесной по Бержу в дифференциальной игре

<{1,2,3}, S, 2 {Jt(U.Z3.tt.Xjy^lt2 3>.

2°. неопределешость Zs минимальна по Слейтеру в трех-[ритериальной динамической задаче

<Z,tJ£(UB.Z,tt,^)>£=if2>3>. Введем функции

971 rdfivr 3 1

1 1 dî L дх -i l j=i 3 3 j

+ | u'JDt и + z'L z (i=1,2,3),

j=i J J

ôV. r 37> л.r з ,

4 4 ôi L J L J=1 J J J

з

j=1 J ^ J

де n»n- матрицы

= 1 oU) . W=1.2.3).

J r=1 J

Ud) = 2 cfrDr , G lot) = | rfrCr.

r=1 r=1

вкже будем использовать вектор 7=(7f,72,73,74)е к4.

Утверждение 5«/ - Пусть для дифференциальной игры (4) яюлневы следуЕщив условия:

a) при каждой î=1,2,3 найдется хотя бы один индекс Je [1,2.3), {jîJ, для которого D£y<0;

b) существуют <**<= л = {cMdj ,агшЧ3)|cft= const>0, (i=1,2,3)} единственные (u(t,x,7), z(t,x,7)) = (ut(t,x,V), u^t.x^),

7), z(t,x,7)), реализующие следущие экстремумы

max W£ (t.z,u£(t. 1,7) ,1^^,2(1,1.7) ,7£) =

= 1»с(Г,х,и(£.х,7),2(£.г.7),7£), te N={1.2.3}.

min W4{t,x,u(t,x,V),z,Vj,<t*) = z

= 4i4U,x.u(t,x,V).z(t,x,V).V4.d*) ДЛЯ любых te [О.тЭ), Rn, Ve R4;

c) система уравнений в частных производных

=0 (>1,2,3,4)

с граничными условиями

V£ (ti,x)=;r'C£x (i=1,2,3), V4 (•ö.x^'Cirf* )х, имеет непрерывно дифференцируемое решение V°(t,x) = (V°(t,x)

d) функции ut(t,x,V°(t,x)) = u®(t,x), (i=1,2,3) и z(t,;r,V0(£,£)) = zG(t,x), имеют вид

u®(t.x) = Q®(i)x, zG(t,x) = PG(t)x,

где Qf(-).Pa(')^Cnxni0,-6).

Тогда при любых начальных позициях (tt,xt)e [0,'0)><{Rn4}n

пара (UB,ZG) такая, что

U® * Q®(t)x, (i=1,2,3), ZG + PG(t)x

является равновесием Бержа-Джоффриона (и, следовательно, Бержа Парето и Бержа-СЛейтера) для игры (4), а соответствующие вы игрыши игроков будут

,1£(ив,га,^,х%) =V°(tt-.xt) (£=1.2.3).

Выделим класс дифференциальных игр вида (4), для которого установим существование равновесия Бержа-Джоффриона.

При этом будем предполагать, что в игре (4) п^ = ш = п Bi(i)=B(i)=Ert, D£t=D0, D.^-D,, С£=С, Ъ.=Ъ U,J=1,2,3).

Утверждение 4. Предположим, что

a) Dj>0, 1>0,

b) система матричных уравнений типа Риккати

е + е[А(г)-£ 1е4] + [А'(п-е42Г ']в + виБ^+Б;^;1^ +

+ в.1_1в. = о

в4 + в4[А(1)+ЗБ71е] + [А* Ц)+38Б~1]94 - (о()в4 +

. + ес71 (V213/= °„хп- е(о>=04(о>=с.

имеет продолжимое на интервал [0,•в] решение (В* (г) ,в*а)).

Тогда равновесие Бержа-Джоффриона (ив.?,а)=(и®.и|,и|,га) игры (4) существует и имеет вид

и? + = Б710*(Г)х («=1.2.3),

ъй + = -х-1 в*а)х,

выигрыши игроков при таком решении и любой начальной позиции Ю,'в)*{кпчОп} будут

<т.(ив,2°,^,г ) с с=1,2.3).

В заключении главы получены необходимые условия существования равновесия Бержа-Слейтера игры (4). которые одновременно позволяют установить структуру такого решения.

При этом необходимые условия формализуются для более широкого класса стратегий и неопределенностей. Именно, множество стратегий С-го игрока -

и'к)= си<+ и.(1,2)|и£(4,г) = ъ.а)х, с^ю.-т

(«=1.2.3)

и множество неопределенностей -

г(к)= и* г{ь,х)\2{г,х) = ?ц)х, Р(-)^с^[0,«]>.

Здесь С^^Ю.'д] - множество п*п - матриц с кусочно-непрерывными

(на [0,3]) элементами, имеющими конечное число точек разрыва ■ первого рода.

Теорема, Пусть

1) при каждом «=1,2,3 найдется, по крайней мере, один индекс ^е<1,2,3), 3*1, для которого Б£^<0,

2)лара (№)= (и^,и|,и|,23)е П^к>х •2'(к) <где и® +

¿=1

+ и®(Г,х)= 0®(£)х, г34-23(Г,1) = Р3(Пх, 0?(-),Р3(-)^ С(к>[0.«]

ее I П*И

(¿=1,2,3)), является равновесием Бержа-Слейтера игры (4).

Тогда существуют три дифференцируемые при почти всех Ге функции Ляпунова-Беллмана (1=1,2,3) такие, что

а) для всех хе о?п

У.(3,х)=х'С£х (£=1,2,3);

при почти всех ге [^.а] и любых хе кп Ъ выполняются равенства

(Г,х)) = О ({=1,2,3); с) для любых стратегий и£ •«■ х)= 0£и)х, и.е

(1,х),и®(£,х),и3(£,х),23(£',г),У2(Г,х)) ^ О, (Г.хЭ^Ц.х), и|(1,х),;г3и,х),У3и.х)) $ 0;

с1) при всех неопределенностях 2* га,х) = Р(1)х, Ъе. 2"Ск) несовместна система неравенств

№£(£,х,ив(1,х),2(£,х),7.(£,Х)) <0 ((=1,2,3).

ЗАКЛЮЧЕНИЕ.

1. Введено понятие равновесной по Бержу ситуации - нового решения бескоалиционной игры и установлены его основные свойства.

2. Выделены классы игр» в которых существует равновесие пс Бержу, а равновесие по Нашу отсутствует.

3. Приведены достаточные условия существования гаратирухлцегс равновесия по Бержу для линейно-квадратичной дифференциально! игры при неопределенности.

4. Для указанной игры установлены необходимые условия существования гарантирующего равновесия по Бержу, которые одновременно выявляют структуру такого решения.

Публикации по теме диссертации.

I. Вайсман К.С. Равновесие по Бержу в одной дифференциальной агре // Сложные динамические системы: Сб.научн.тр.- Псков: псковский пединститут, 1994.- с.58-63.

Vaisman K.S. The Berge Equilibrium Рог Linear-Quadratic Differential Game // Abstracts ol the Third International Workshop "Multiple criteria problems under uncertainty" - September >-9, 1994,- Orekhovo-Zuevo, Russia.- P.96.

j. Вайсман К.С., Жуковский В.И. Свойства равновесия по Бержу// 'езисы докладов V Школы "Математические проблемы экологии".-1ита: 1994.- С.27-28.

к Вайсман К.С., Жуковский В.И. Структура равновесных по Бержу ¡ешений // Тезисы докладов ВМШ "Понтрягинские чтения -V".-юронеж: 1994.-С.29.

Vaisman,К.S. and Zlmkovskly.V.I. The Berge Equilibrium un-ler uncertanty // Abstracts of the Third International Work-hop "Multiple criteria problems under uncertainty" - September -9, 1994.- Orekhovo-Zuevo, Russia. - P.9T.

. Zhukovskly.V.I., Sulukvadze.M.E. and Vaisman,K.S. The Berge qullibrlum:Preprint.- Tbilisi: Institute of Control Systems.-1994.- 31p.

. Житомирский Г.И., Вайсман К.С. О равновесии по Бержу // ложные динамические системы: Сб. научн. тр. - Псков: Псков-кий пединститут, 1994.-С.52-57.

Заказ № 367 Тираж 100 Отпечатано в Орехово-Зуевской типографии