Методы поиска точек равновесия в билинейной игре с ненулевой суммой тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение

Оглавление

Глава1. Итерационный метод поиска точки равновесия

1.1. Постановка игровой задачи

1.2. Постановка равновесной задачи

1.3. Существование решения

1.4. Градиентный подход с прогнозированием

Глава2. Методы регуляризации с расширением множества

2.1. Возмущенная задача. Примеры неустойчивых задач

2.2. Метод стабилизации

2.3. Метод невязки

2.4. Метод квазирешений

ГлаваЗ. Методы регуляризации в сочетании со штрафными функциями

3.1. Метод стабилизации со штрафами

3.2. Метод невязки со штрафами

3.3. Метод квазирешений со штрафами

Исследование математических моделей многих сложных явлений экономики, естествознания, связанных с поиском компромисса и согласования частично (или полностью) противоположных интересов сторон конфликта составляет содержание области математики, которую называют равновесным программированием и которая охватывает ряд важных задач теории игр и экономического равновесия [1], [2], многокритериального принятия решений в условиях неопределенности [3], обратных задач оптимизации [4], вариационных неравенств [5]. Основную задачу равновесного программирования можно сформулировать следующим образом. Пусть имеется некоторая функция Ф(г>,го), (v,w) Е W х W ,где W—заданное множество из п-мерного пространства Еп. Требуется найти точку v* Е W, для которой

УадбЖ (0.1)

Такую точку v* называют точкой равновесия. Многие важные проблемы исследования операций, вычислительной математики и математической экономики сводятся к задаче (0.1). Если функция Ф(-и, w) не зависит от г;, то задача (0.1) превращается в обычную задачу минимизации.

К настоящему времени достаточно хорошо изучена проблема существования точек равновесия, равносильная проблеме существования неподвижных точек v Е W(v) экстремального отображения w = w(v) функции Ф(г>, w) на W, определяемого из условия min^^ Ф(г>, w) = Ф(и, w(v)), v Е W, w(v) Е W. Экстремальные отображение, как правило, является многозначным и при доказательстве существования неподвижной точки обычно пользуются теоремами Какутани [6], Fan Ку [7], Oettli [8], обобщающие классические теоремы о неподвижных точках для многозначных отображений.

Что касается конструктивных методов поиска точек равновесия, пригодных для использования на компьютерах, то здесь значительные результаты получены лишь для отдельных классов задач (0.1), таких, как задачи оптимизации, седловых задач, вариационные неравенства. Однако эти методы в основном разрабатывались и исследовались при значительных ограничениях на функцию Ф(у,ги) (требования типа выпуклости по переменной w и вогнутости по v, нулевой суммы игры, сильной монотонности оператора в вариационних неравенствах и m.n). Между тем многие практически важные задачи математической экономики, теории игр не удовлетворяют этим ограничениям и ранее разработанные методы к таким задачам не вполне применимы. Поэтому можно считать, что разработка методов решения достаточно общих задач (0.1) практически только начинается, о чем свидетельствуют имеющиеся немногочисленные работы (Карпе-левич Г.М.[9], Антипин А.С [10], [20], [25],[27], [28], Шпирко С.В.[11], Васин А.А.[12], Богданов А.В. [13]).

При разработке методов решения задачи (0.1) следует ещё учитывать, что эта задача, вообще говоря, неустойчива к возмущениям функции Ф(г>,и>) и множества W, и для их решения нужно использовать специальные методы, называемые методами регуляризации. Имеется относительно небольшое число работ в которых предложены и исследованы методы регуляризации неустойчивых равновесных задач. (Васильев Ф.П, Антипин А.С[14], [15], [16]-[18], Шпирко С.В.

И])

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

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

Пусть выигрыш (или расходы) первого игрока выражается функцией fi(xhx2) = (хи Схх2 + Ci) + 1/2{В1хих1), (0.2) его стратегии х\ G Х\ = {х\ е Е711 : xi > 0, А\Х\ < Ьг} = {ж! G Eni : xi > 0, gu{xi) = {aU: хг) - Ьц < 0, i = l,mi}, (0.3) выигрыш (или расходы) второго игрока—функцией

2О1, х2) = {С2х 1 + с2, х2) + 1/2(В2х2, х2), (0.4) его стратегии ж2 G Х2 = {х2 е Еп> : х2 > 0, А2х2 < ь2} = х2 G £П2 : х2 > 0, g2i(x2) = (a2i,x2) -b2i<0,i = 1 ,ш2}, (0.5) где матрицы Ci, С2, В\, В2, А\, А2 имеют размерности п\ х n2,n2 х ni,ni х ni,n2 X n2,mi х п\,т2 X п2 соответственно, векторы ci G , с2 G ЕП2, bi G Emi, b2 G i?™2, а** — г-ая строка матрицы A*, bki - i-ая координата вектора bk,k = 1,2. Каждый из игроков выбирает свои стратегии Ж1 G G Х2, желая минимизировать свою функцию выигрыша /1 , Ж2), /2(^1, ж2) соответственно. Пусть W = Х\хХ2 -ф 0. Пара стратегий {х\,х\) G Ж называется точкой равновесия Нэша

19], если h(x\,x\) < и(хъх\) VxiGXb (0.6) f2(x\,x2) < /2(ж;, ж2) Уж2 G х2.

Множество точек равновесия Нэша такой игры будем обозначать через W*. Содержательный смысл точки равновесия Нэша состоит в том, что ни один из игроков не заинтересован нарушать состояние равновесия, поскольку никто из них не может в одностороннем порядке уменьшить значение своей целевой функции.

Заметим, что в сформулированной игре (0.2)-(0.6) целевые функции состоят из билинейных слагаемых (xi,Oicc2), {С2х 1,ж2), которые связывают двух игроков, и линейных и квадратичных слагаемых (Ci,Xi) + l/2(BiXi,Xi), i = 1,2, которые отражают предпочтение каждого из игроков, а множество стратегий Х\1 Х2 игроков представляют собой многогранные множества. Игру (0.2)-(0.6) в дальнейшем кратко будем называть билинейной игрой двух лиц. Методы решения таких игр до сих пор в основном разрабатывались в предположении, что сумма выигрышей (расходов) игроков равна нулю

20]: $i(xi,x2) + Ф2{х1,х2) — 0 V^i G Х\, х2 G Х2; методы решения игр с ненулевой суммой исследованы недостаточно.

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

Диссертация состоит из трех глав и приложения. В параграфе 1 главы 1 обсуждается постановка задачи (0.2)-(0.6), показывается, что эта задача равносильна при Вi > О, В2 > 0 задаче (0.1), где

P{v,w) = {(С+ B)v,w) + (c,w), (0.7)

W = {w e En : w > 0, Aw < b} = {w > 0 : gi(w) = (аг, w) - b < 0, г=Т~т}, (0.8) где а— i-я строка матрицы А, Ъг —i-я координата вектора 6, т = mi + 777,2, 77 = ?7i + 772- Кратко обсуждаются вопросы существования решения задачи (0.1), (0.7), (0.8).

В параграфе 2 главы 1 для решения задачи (0.1), (0.7), (0.8) предлагается итерационый метод градиентного типа: рп = тт+(рп + ап(Ауп-Ь))7 vn = ir+{vn - ап((С + B)vn + с + Атрп)), рп+1 = тт+(рп + ап(АГ - b)), v n+1 = 7T+{vn - ап((С + B)vn + с + Атрп))) (0.9) где ап выбирается, например, из условия

0 < е < ап < 1/у/2\С + В|2 + |Л|2, е > 0 Доказана следующая

Теорема 2: Пусть множество W* решений задачи (0.1), (0.7), (0.8) не пусто, пусть С + В > 0. Тогда при любом выборе начального при-бижения (г>°,р°) последовательность (г>п,рп), определяемая процессом

0.9), сходится монотонно по норме к одной из седловых точек (v*,p*) функции Лагранжа задачи (0.1), (0.7), (0.8), причем v*—решение задачи (0.1), (0.7), (0.8).

Заметим, что итерационный метод (0.9) был предложен А.С. Антипиным [27] для нелинейных задач поиска точки равновесия, но его сходимость в [27] была установлена при дополнительном предположении: \рп\ < const, п = 1,2,.

В главах 2, 3 предлагаются и исследуются основные методы регуляризации (методы стабилизации, невязки, квазирешений) для задачи (0.1), (0.7), (0.8) при условии, что вместо точных матриц А = {ау}, В = {bij},C — {C{j}, векторов b = {Ьг}, с = {с3} известны их приближения А(8) = {%•(£)}, В (8) = {bij(8)}, С(8) = {<:„(£)}, Ь(8) = (Ьг(<5)}, с(£) = {с?(£)}, такие, что Cij(8) - сг] | < 8 , | bij(8) -bij\<8, \aij(8) - atJ | < 8, (0.10) bi(8) -bi\<8 , |Cj(8) - Cj\ <8, 8> 0.

На первый взгляд может показаться, что в качестве приближенного решения задачи (0.1), (0.7), (0.8) можно взять точку vs G являющуюся решением возмущенной равновесной задачи: $s(v5,vs) < W; G ОД, (0.11) составленной по аналогии с исходной задачей, где

S>s(v,w) = ((С (6) + B(8))v,w) + <с(*),™> п(8) = {w е Еп : w > 0, A(8)w < b(8)}} (0.12)

ClW. Н - (Т w!

-(т^0 )■"«-( кз) •«•'-( as)'

В параграфе 1 главы 2 показывается, что задача (0.1), (0.7), (0.8) может оказаться неустойчивой, и решение vg возмущенной задачи 0.11), (0.12) (если оно существует), может сильно отличаться от решения исходной задачи при любых сколь угодно малых > 0; приводятся примеры неустойчивых задач.

В параграфе 2 главы 2 предлагается и исследуется метод стабилизации с расширением множества. Вводится множество

W(5) = {w Е Еп : w > 0, giS(w) < 0(1 + Hi), i = T/m}, в > 5,

0.13) показывается, что оно является расширением множества W. Вводится функция Тихонова ts(v,w) = $$(v,w) + a\w\l, v, w E W(S), ce > 0. (0-14)

Метод стабилизации заключается в определении точки v = v$ Е W(S) из условия ts(vs,vs) < inf ts(vs,w) + б, б > 0. (0.15) wew(S)

Теорема 3: Пусть выполнены условия ((0.10) на приближения входных данных задачи (0.1), (0.7), (0.8), VF* ф 0 матрицы В > 0, С + В > 0, параметры в = 0(5), а = а(5), е — метода (0.13)-(0.15) таковы, что в{5) > S > 0, а(6) > 0, е{5) > 0, Km(в (6) + <*(£) + е(5)) = 0, (0.16)

S—>-0 sup < sup < QOj шлв(5) + а(5)) < е(5) (0.17) где Mi—достаточно большая константа. Тогда

Нтр(^,Ж«)=0, Нт/?(Ф(^,^),Ф,) = 0, (0.18) о—>0 о—>0 где Ф* = {Ф : Ф = Ф(у,у), v Е W*}, p(vs,z) = inf — z\— расстояние z<EZ от точки vs до множества Z.

Метод (0.13)-(0.15) ранее был предложен в [16] для нелинейных равновесных задач, но его обоснование было дано при более жёстких ограничениях.

В параграфе 3 главы 2 предлагается и исследуется метод невязки с расширением множества. Вводится множество {v Е W(S) : < inf [Ф6(у, w) + 6M2\w\l] + а} а > 0, w€W(S)

0.19) где М2—достаточно большая константа. Метод невязки заключается в определении точки v = vs G из условия vs\l< inf \w\l + fM, fi>0. (0.20) шё V (0)

Теорема 4: Пусть выполнены условия (0.10) на приближения входных данных задачи (0.1), (0.7), (0.8), W* ф 0, матрицы В > 0, С + В > 0, параметры в = 0(£), <т = <т(£) метода (0.19), (0.20) таковы, что а{5) > 0, fi{5) > 0, lim(0(£) + <т(Я)) = 0, (0.21)

S—>-0

Тогда

6(6) >5> 0, 5М?0 < <т(<5), sup fi(S) < 00.

5>0 lim/^,^) =0, Птр(Ф(^,^),Ф,) = 0, (0.22) о—>U d—>0 где Ф* = {Ф : Ф = Ф(г>, v), v G W*} и p(vs, Z) = inf 2;h—расстояние от точки vs до множества Z. Если еще lim /1(8) = 0, то

J—>о lim^vj, W**) = 0 Нт/>(Ф(^,^),Ф„) = 0, (0.23) где W** = {v G W* : \v\\ < Ц}, Ф** = {Ф : Ф = $(v,v),v G W*„}.

Метод (0.19), (0.20) ранее был предложен в [16] для нелинейных равновесных задач, но его обоснование было дано при более жёстких ограничениях.

В параграфе 4 главы 2 предлагается и исследуется метод квазирешений с расширением множества. В этом методе предполагается, что известно число г, такое, что

Mi < Г (0.24)

Вводится множество

W(S,r) = {г> G W{6) : Mi < г}. (0.25)

Метод квазирешений заключается в определении точки v$ из условий v6eW(5,r), $6{vs,vs)< inf' + 20M3\w\1} + £, £ > 0, wEW(d)

0.26) где М3—достаточно большая константа.

Теорема 5: Пусть выполнены условия (0.10) на приближения входных данных задачи (0.1), (0.7), (0.8), матрицы В > 0, С + В > 0, параметры 9 = 0(6), £ = £(5) метода (0.25), (0.26) таковы, что = HmW)+ £(£)) = 0, (0.27) о—>-0 в{6) > S > 0, 3в(5)Мъ < i(5).

Тогда im p(vs,W*r) = 0 , lim Ф*г) = 0, (0.28) о—>0 о—>0 где W*r = {v Е W* : \v\\ < г}, Ф,г = {Ф : Ф = v G W*r}.

Метод (0.25), (0.26) ранее был предложен в [16] для нелинейных равновесных задач, но его обоснование было дано при более жёстких ограничениях.

В главе 3 предлагаются и исследуются основные методы регуляризации в сочетании со штрафными функциями. Для учета ограничений Ах < b из (0.8) используется простейшая штрафная функция т i= 1 в качестве её приближения берется функция то г= 1

В параграфе 1 главы 3 рассматривается метод стабилизации в сочетании со штрафными функциями. Вводится функция Тихонова ts(v,w) = Ф6(у,и)) + КРб(ш) + а\'ш\1, а>0, К > 0, v,w > 0, (0.29) ищется точка удовлетворяющая условиям vs > 0, ts(vs, vs) < ts{vs,w) + e(S) Vw > 0, e > 0. (0.30)

Теорема 6: Пусть выполнены условия ((0.10) на приближения входных данных задачи ((0.1), (0.7), (0.8), W* ф 0, матрицы В >

О, С + В > 0 параметры а = > О, К = if (Я) > О, е = е(5) > О, 8 > О, удовлетворяют условиям

Ма(К-\5) + 5 + К(5)5 + а(£)) < е(5), 6(5) > 5 > О, sup < оо, sup -< 1, (0.31)

0<J<Jo 0<£<£о OL limК(5) = +оо, lim 5К(5) = 0, lim(a(5)+e(£)) = 0 , inf а(5)(К(5)) > О,

0.32) где М4—достаточно большая константа.Тогда

Yimp(vs,W,) =0, итр(Ф(^,^),Ф,)=0. (0.33) о—>0 о—>0

Метод (0.29), (0.30) ранее был предложен в [15] для нелинейных равновесных задач, но его обоснование было дано при более жёстких ограничениях.

В параграфе 2 главы 3 предлагается и исследуется метод невязки в сочетании со штрафными функциями. Вводится множество

V(5) = {v Е En,v > 0 : Ф^г/, v) + KPs(v) < inf {<&s(v, 0

KPs{w) + (5 + 5K)M5\w\1} + (t, сг > 0, (0.34) где М5—достаточно большая константа. Определяется точка v = vg G V(5) из условия

М?< inf \w\l + ii, [i >0. (0.35) ги£К(о)

Теорема 7: Пусть выполнены условия (0.10) на приближения входных данных задачи (0.1), (0.7), (0.8), W* ф 0, матрицы В > 0, С + В > 0, параметры К = К(5), а = с(^), Д = М^) метода 0.34), (0.35) таковы, что выполнены условия

5 + 5К(5) + К~\5))Мь < а(5), sup /1(8) < 00, lim((j(<$) + <Щ£)) = 0, lim =+oo. (0.36) (J—>0 J—>0

Тогда lirn^,W*) = 0, 1ип/>(Ф(^,г;*),Ф*) = 0. (0.37) о—>-0 о—>0

Если еще lim а(5) = 0, то <*->о 4 ' imp(vs,W**) = 0, Пт/9(ФЦ,^),Ф„) = 0, (0.38) о—>0 d—>■[) где = {v е W* : < = {Ф : Ф = £ W**}.

Метод (0.34), (0.35) ранее был предложен в [17] для нелинейных равновесных задач, но его обоснование было дано при более жёстких ограничениях.

В параграфе 3 главы 3 предлагается и исследуется метод квазирешений в сочетании со штрафными функциями. В этом методе предполагается, что известно число г такое, что

W* П Q(r) ф 0, Q[r) = {w > 0 : Hi < г}, (0.39)

Ищется точка vg, удовлетворяющая условиям vs е Q(r), Фs(vs,vs) + KPs(vs) < mfjfis(vs,w) + KPs(w)+

8 + 6К(5))М6\у>\1]+£, £>0, (0.40) где —достаточно большая константа.

Теорема 8: Пусть выполнены условия (0.10) на приближения входных данных задачи (0.1), (0.7), (0.8), матрицы В > 0, С + В > 0, параметры К = К(5), £ = £(£) метода (0.39), (0.40) таковы, что

3(1 + г)2 (6 + 6К(6) + K{S)~l)M1 < lim К(6) = +оо lim(6К(5) + £(£)) = 0. (0.41)

Тогда

Kmp(vs,WtnQ(r)) = 0 , Нт/>(Ф(^,^),Ф,) = 0 (0.42) о—>0 д—>0 где М7—достаточно большая константа и Ф* = {Ф(г*, г;) : v G W* П

ОМ}

Метод (0.39), (0.40) ранее был предложен в [18] для нелинейных равновесных задач, но его обоснование было дано при более жёстких ограничениях.

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

Основные результаты диссертации:

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

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

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

Основные результаты диссертации опубликованы в [32]-[36]. Автор выражает глубокую благодарность своим научным руководителям Анатолию Сергеевичу Антипину, Федору Павловичу Васильеву за постановку задачи, за внимательное научное руководство.

1 ИТЕРАЦИОННЫЙ МЕТОД ПОИСКА ТОЧКИ РАВНОВЕСИЯ

1. Карлин С. Математические методы в теории игр, программировании и экономике. М.: Мир. 1964.

2. Полтерович В.М. Экономическое равновесие и хозяйственный механизм. М.: Наука. 1990.

3. Жуковский В.И., Молоствов B.C. Многокритериальная оптимизация систем в условиях неполной информации. М.: МНИИПУ. 1990.

4. Антипин А.С. Обратная задача оптимизации: постановка задачи и подходы к ее решению// Обратные задачи математического программирования. М.: ВЦ РАН. 1992. С.4-58.

5. Harker Р.Т., Pang J.-Sh. Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications// Mathematical Programming. 1990. 48. P.161-220.

6. Aubin J.-P. Optima and Equilibria. An Introduction to Nonlinear Analysis. Springer. 1998.

7. Aubin J.-P., Frankowska H. Set Valued Analysis. Boston etc.: Birkhauser. 1990.

8. Blum E., Oettli W. From optimization and variational inequalities to equilibrium problems. The mathematics Student. 1993, 1-4: C. 1-23.

9. Корпелевич Г.М. Экстра-градиентный метод для отыскания седловых точек и других задач.// Экономика и математические методы 1976. Т.12, No.4, 747-756.

10. Антипин А.С. О сходимости и оценках скорости сходимости проксимальных методов к неподвижным точкам экстремальных отображений// Журнал вычисл. мат. и мат. физ. 1995. Т. 35. N 5. С.688-704.

11. Шпирко С.В. Метод кососимметричной регуляризации для решения равновесных задач: Кандид, диссертац. М.: ВЦ РАН. 2000.

12. Васин А.А. Модели динамики коллективного поведения. М: МГУ.1989

13. Богданов А.В. Условия сходимости итеративных процессов в повторяющихся играх. Кандид, диссертация. ВМиК МГУ. Москва. 2000

14. Антипин А.С., Васильев Ф.П. Методы регуляризации поиска неподвижной точки экстремальных отображений // Вестн. МГУ. Сер.15. Вычисл.матем. и кибернетика. 1998. No.l С.11-14.

15. Васильев Ф.П., Антипин А.С. Методы стабилизации для решения задач равновесного программирования с неточно заданным множеством. Журнал вычисл. матем. и матем. физики. 1999. Т. 39, No.И. С.1779-1786.

16. Антипин А.С., Васильев Ф.П. Метод невязки для решения равновесных задач с неточно заданными множеством. Журнал вычисл. матем. и матем. физики, 2001, т.41, N 1, с.3-8.

17. Антипин А.С., Васильев Ф.П. Метод квазирешений для решения равновесных задач с неточно заданным множеством. Вестник Российского университета Дружбы Народов, серия математическая, 2001, т.8, N8. С. 10-16.

18. Nash J.F. Jr. Equilibrium points in n-person games, Proc. Nat.Acad.Sci.// USA, 1950, 36, 48-49.

19. Васин В.В., Агеев A.JT. Некорректные задачи с априорной информацией. Екатеринбург. 1993.

20. Антипин А.С., Делавархалафи А. Билинейные игры двух лиц с ненулевой суммой //Вестн. МГУ. Сер 15. Вычисл. матем. и киберн. 2002. No.l, 28-35.

21. АН Delavarkhalafi, Anatoly Antipin. Calculating a saddle point of a bilinear problem.// Proceeding of the 2 International conference of applied Mathematics. Iran University of Science and Technology. Tehran, Iran, 2000, pp. 87-96.

22. Ali Delavarkhalafi, A stabilization method for two-person nonzero sum games. //Тезисы докладов 7-й международной научной конференции "Обратные и некорректно поставленные задачи", МГУ, ВМиК, М, 2001, с.26.

23. Антипин А.С. Васильев Ф.П Делавархалафи А .Метод стабилизации с расширением множества для поиска точек равновесия Нэша в билинейной игре двух лиц с ненулевой суммой.//Вестн. МГУ. Сер 15. Вычисл. матем. и киберн. 2002. No.3.

24. Делавархалафи А. Методы регуляризации для поиска точек равновесия Нэша в билинейной игре двух лиц с ненулевой суммой.// МГУ, М., 2001, 18 с. Рукопись депонирована в ВИНИТИ от 05.12.2001, N 2526-в 2001.