Кооперативное принятие решений: элементы статики и динамики тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

| 5 ДЕК 1238

Гао Хунвэй

КООПЕРАТИВНОЕ ПРИНЯТИЕ РЕШЕНИЙ: ЭЛЕМЕНТЫ СТАТИКИ И ДИНАМИКИ

01.01.09. - математическая кибернетика

АВТОРЕФЕРАТ

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

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

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

Научный руководитель: доктор фиэ.-мат.наук, профессор Л.А.Петросян

Официальные оппоненты: доктор физ.-мат. наук, .1.

Ведущая организация: Санкт-петербургский государственный технический университет.

диссертационного совета К-063.57.16 по защите диссертации на соискание ученой степени кандидата физико-математических наук в Санкт-Петербургском государственном университете по адресу: 199004,Санкт-Петербург, 10-я пиния В.О. 33, аудитория 41.

С диссертацией можно ознакомиться в библиотеке имени Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская набережная 7/9.

Автореферат разослан У? / ноября 1996

Ученый секретарь

диссертационного совета

доктор фиэ.-мат.наук,

профессор В.Ф.Горьковой.

профессор В.В. Колбин кандидат физ.-мат. наук, доцент В.А.Уланов

Защита состоится «03- декабря

часов на заседании

*>

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Так, в частности, сопоставление экономики "Робинзона Крузо" и экономики общественного обмена привело в первой половины ХХ-го столетия математика Дж.фон Неймана и экономиста О.Моргенштерна к созданию теории игр, которая предоставляет математический инструмент анализа поведения экономических агентов, находящихся в определенном хозяйственном взаимодействии друг с другом, но преследующих свои интересы.

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

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

Цель исследования. Основная цель исследования состоит в распространении и развитии положений динамической теории кооперативных игр на класс игр с распределением затрат. Кроме того, преследуется цель исследовать и некоторые проблемы статической теории кооперативных игр (как, налример, проблема множественности ИМ-решений), что в опредеелнной мере стимулируется достижениями динамический теории.

'Научная новизна. Выносимые на защиту результаты диссертации - они формулируются в конце автореферата - являются новыми.

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

Апробация работы. Основные результаты работы были доложены на Международном конгрессе по компьютерным системам и прикладной математики (СБАМ'ЭЗ) в Санкт-Петербурге, на Международной конференции по интервальным вычислениям и методам компьютерной алгебры в науке и инженерии (1гпег/аГ94) в Санкт-Петербурге, на семинарах кафедры математической статистики, теории надежности и теории массового обслуживания факультета прикладной математики • процессов управления Санкт-Петербургского университета.

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

Струк1ураи объем работы. Работа состоит из введения, трех глав, включающих 8 параграфов, и библиографии. Объем основной части работы сосотавпяет 100 страниц. Библиография включает 25 ссыпок.

СОДЕРЖАНИЕ РАБОТЫ

Во введении кратко охарактеризованы исследуемые а диссертации вопросы и описано ее содержание по главам.

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

Во втором параграфе первой главы на основе понятия слабого доминирования вводится и исследуется понятие слабого NM-решения.

Определение 1. Пусть v - классическая кооперативная игра с

множеством игроков I = {1,2,___,n), a E(v) - множество дележей в этой

игре. Будем говорить, что дележ х = (хь ... х„) е E(v) слабо доминирует дележ у = (уь ..., у„) e E(v) по коалиции Sel, если

Определение 2. Будем говорить, что дележ х в игре v слабо доминирует дележ у в той же игре, если он его слабо доминирует по некоторой коалиции Sel.

Определение 3. Множество депежей LcE(v) назовем слабым NM - решением в игре v, если:

никакие два дележа из этого множества L слабо не доминируют друг друга и

2) всякий дележ из множества E(v)\L слабо доминируется некоторым дележом из множества L.

доминирующий дележ yeE(v), необходимо и достаточно, чтобы для некоторой коалиции Sel выполнялось неравенство

и

того, чтобы существовал дележ xeE(v),слабо

y(S)<v(S)

(здесь, как обычно y(S) =

Следствие. Множество всех слабо недоминируемых дележей в игре v совпадает с ее С - ядром, т.е. совпадает с множеством решений следующей системы:

X(I)=V(I)

X(S)J>V(S), Sel, S*0,I

Теорема 2. Если С - ядро является слабым NM • решением в :; данной игре у, то оно является единственным ее слабым NM -решением.

В отличие от теории Неймана-Моргенштерна в параграфе 2 первой главы получено следующее простое достаточное условие того, чтобы С-ядро сбалансированной игры было (единственным) слабым ее NM-решением.

Теорема 3. Для того, чтобы С- ядро сбалансированной игры v было слабым ее NM - решением достаточно, чтобы каждая из гиперплоскостей

x(S) = v(S), Sel, 1 < |S|<| 11 была опорной к нему гиперплоскостью.

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

В 3-ем параграфе 1-ой главы излагается подход к сужению множества NM-решений в играх, имеющих много таких решений. Суть этого подхода состоит в том, чтобы сравнивать по предпочтительности в данной игре v различные NM-решения (и,вообще, различные подмножества множества дележей) и, на этой основе, выбирать в каком-то смысле лучшие из них, можно, сравнивая их базы, т.е. определенные векторные характеристики

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

Необходимые определения и результаты этого параграфа приводятся ниже.

Пусть V(I) - множество всех игр (функций) v^-^R, удовлетворяющих условиям: v(0)=0 и v(I)

Определение 4. Пусть v б V(I). Всякое непустое подмножество М множества дележей E(v) в игре v будем называть компромиссом в этой игре.

Определение 5. Всякий компромисс в игре v е V(I), который состоит только из одного дележа, будем называть совершенным.

Определение б. Базой компромисса М в игре v 6 V(I) будем называть функцию w: 2J-> R такую, что

при этом естественно считается, что w(0) = 0.

Множество всех функций w: 2'-> R, каждая из которых является базой того или иного компромисса в игре v обозначим W„. Зафиксируем у е V(I) и рассмотрим вектор-функцию

©:W„-» Ä2"-1

®(w) = (®i (w),... ®2"i (w))

такую, что

©*(w) = шах min [v(S)-w(S)] Ve 2" SeV

|V| = K

"> Понятие базы компромисса, определяемое ниже, впервые было введено в работе: Чистяков C.B. Динамический аспект решения классических кооперативных игр //ДАН России, 1993, том 330, №6.

Определение 9. Будем говорить, что функция и е V/, не менее предпочтительна, чем функция е ^АГ,, если вектор ©(и) лексикографически не больше вектора т.е.если либо ®(и)= либо первая ненулевая координата вектора ©(и) - ©(V/) отрицательная.

Если функция и е не менее предпочтительна, чем функция V е (в указанном в определении 9 смысле), то будем иметь иг:, V/.

Определение 10. Будем говорить, что компромисс М' с Е(у) не менее предпочтителен, чем компромисс М" с Е(у), если база компромисса М' не менее предпочтительна, чем база компромисса М". В случае, если последнее условие выполнено, будем писать М".

Определение 11. Пусть Рс WY, Р*0. Тогда п - ядром множества функции Р в игре V назовем множество всех максимальных элементов этого множества для отношения ^ .

п - ядро множества функций Р в игре V обозначим п„(Р).

Определение 12. Пусть <2 с 2ЕМ*<0), <3*0. Тогда N - ядром множества компромиссов в игре v назовем множество всех максимальных элементов множества <3 для отношения

N - ядро множества компромиссов в игре V обозначим

К«).

Теорема 4. Пусть V е "У(1). Если множество Р с V/,,, Р*0, замкнуто, то п„(Р)*0.

Следствие. Пусть V е У(1), (¡) с ,0), Q и множество

Р(С>) = {V/ е 13 Мер: w - база М) замкнутое. Тогда 1чГ„(С>>*0.

Особый интерес представляет тот случай, когда С?-множество всех ЫМ-решений в данной игре. Этот случай рассматривается на конкретном примере игры с бесконечным

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

Теорема 5. В любой игре veV(I) п - ядро множества функций W, состоит из единственного элемента n(v), при этом функция (игра) n(v) - аддитивная, а совершенный компромисс в игре v, который имеет своей базой эту функцию, состоит из того единственного своего дележа, который является п - ядром множества дележей в этой игре v*>.

Во второй главе диссертации определенная динамическая версия кооперативной теории, предложенная ранее С.В.Чистяковым для игр с распределением прибыли, распространяется на игры с распределением затрат.

Под игрой с распределением затрат понимается всякая функция V: 21 -» R+, которая удовлетворяет следующим условиям:

v(0) = 0 и v(I) £ £ v¡.

iel

Множество всех таких функций (игр») обозначим V(I). Под множеством дележей в игре veV(I) (с распределением затрат) в этой главе понимается множество всех векторов х е Rn, n=|I|, таких, что

IXi =V(I) HOíXiáV; Viel

iel

Соответственно ядром (С-ядром) игры veV(I) здесь называется множество всех х е E(v) таких, что 2x¡ ¿v(S) , V Sel,

ieS

l<|S|<n.

Здесь имеется ввиду классическое понятие n-ядра, введенное .Шнайдлером.

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

Определение 17. Базой компромисса М в игре уеУ(1) назовем функцию V/ : 21 —> такую, что

• Множество всех функций ууеУ(1), каждая из .которых является базой некоторого компромисса в игре уеУ(1) обозначим а объединение всех множеств '№,(1), уеУ(1) обозначим W(I). Далее в 1-ом параграфе 2-ой главы устанавливаются, в частности, следующие утверждения.

Теорема 6. Каждая игра \уе'№(1) является субаддитивнойГ>

Теорема 7. Для того, чобы компромисс М в игре v еУ(1) был совершенным, необходимо и достаточно, чтобы его база была аддитивной игрой.

Определение 18. Компромиссы в игре 7бУ(1), которые имеют одну и ту же базу, будем называть эквивалентными.

Определение 19. Компромисс МДу) в игре veV(I), который имеет своей базой функцию и который содержит любой

другой компромисс из своего класса эквивалентности, будем называть полным компромиссом.

Теорема 8. В любой игре уеУ(1) всякий полный компромисс М^), совпадает с ядром игры V? и, следовательно, всякая игра угеШ(1) является сбалансированной.

*> Т.е. \у(ЗиТ) ^ УЗ,Тс1, Зг>Т=0. Если же каждое из

последних нестрогих неравенств выполняется как равенство, то игра V/ называется аддитивной.

Теорема 9. В любой сбалансированной игре veV(I) ее ядро C(v) является полным компромиссом, причем если w - база этого компромисса, то w(S) i v(S), VS с I.

Теорема 10. Какова бы ни была игра veV(I) множество W„(I) является выпуклым многогранником.

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

Определение 20. Пусть VcV(l), V*0. Если из того, что veV следует, что Wv(I)cV, то множество V будем называть подпространством пространства V(I) (игр с распределением затрат).

подпространстве V пространства игр V(I) будем понимать всякий оператор В : V -> Vтакой, что Bov е WV(I) V veV.

Определение 22. Принцип оптимальности В на подпространстве Vпространства игр V([) будем называть а) совершенным, еспи Bov е V,(I)*> V v еV; беспрерывным, если оператор В непрерывен на подпространстве V n W(I);

в) монотонным, если Bov <.v V veVnW(I), т.е. (Bov)(S) ^ v(S), V S с I V veVnW(l).

Определение 23. Пусть В • произвольный принцип оптимальности на подпространстве V и v(°)eV. Если последовательность игр

{ VW JVi, vM =Bovfr-D, к 6 N (1) сходится к игре v* е V и Bov*= v* то эту игру v* будем называть финальным решением игры \<Р\ отвечающим принципу оптимальности В.

Под принципом оптимальности на

> Здесь Va (I) - множество всех аддитивных игр V G V (I )

Последовательности игр (1) естественным образом сопоставляется последовательность компромиссов:

{ МОО }шк=ь MOO =Mv»(v(w?), к е N (2) в которой MW - полный компромисс в игре v^-1), имеющий своей базой игру V®. Очевидно, каждое из множеств этой последовательности является также и полным компромиссом в игре vP>.

Теорема 11. Пусть В - непрерывный и монотонный принцип оптимальности на подпространстве V пространства игр V(I). Тогда каждая игра v<°>eV имеет финальное решение v'eV, отвечающее этому принципу оптимальности, причем для данной игры v(°>eV соответствующая ей и принципу оптимальности В последовательность полных компромиссов не возрастает по включению и сходится в метрике Хаусдорфа к полному компромиссу М*в игре v<P>, имеющему своей базой игру v*.

В том же параграфе 2 второй главы описан один конкретный класс монотонных и непрерывных принципов оптимальности.

Последняя теорема, по крайней мере, неявно указывает на то, что особый интерес представляют такие принципы оптимальности на том или ином подпространстве V, для которых финальное решение у" любой игры v^eV представляют собой аддитивную игру. Такие принципы оптимальности называются финально совершенными и изучаются в 3-м параграфе 2-ой главы.

Рассматриваются, в частности, следующие принципы оптимальности: пусть V - произвольное подпространство пространства игр V(I) такое, что C(v)*0 VveV. Пусть далее Os:V int R+, Sel, S=*0, I, - произвольные непрерывные функции и Ва: V-»V такой принцип оптимальности, что VveV Baov - база компромисса

М (v) = argmmmax——-—L

хеОМ *** CCS{V)

Показано, что каждый из так определенных принципов оптимальности является финально совершенным.

В третьей главе рассматривается оптимальный процесс платежей в динамических играх с распределением затрат при помощи концепции динамической устойчивости, введенной впервые Л.А.Петросяном (согласования во время процесса распределения), описанный в терминах кооперативных дифференциальных игр.

Пусть С(хо, Т-адН) полные затраты в игре из начального состояния Хо и продолжительностью Т-1о. И пусть векгор-функция

Определение 26 Принцип оптимальности Цхо,Т-1о,М) называется динамически устойчивым (согласованным во времени), если для каждого ^°еС(хо,Т-1:о,1Ч), существует ФРЗ и (г), так что

для всех 1е[1о,Т], 0.

Определение 27. Будем называть 6-обобщенной функцией

11© € Я», и(Г) - (и,(0, и2(0.....ип(г)), 0

п

'0 _•_, "(о

распределения затрат (ОФРЗ) векгор-функцию (и®), где

и/(г)=и^),к=0,1.....ш-1де[дх,р1+1),1 еМ

<2ге[Г0,Т], к=0,1.....ш-1; 10= (?о< <21<...< С^Т,

<2»ч- <3*= т=| Т-10|/6, а

Рассмотрим вектор Шелли о^х^), 14)

Определение 28. Назовем 5-обощенным вектором Шеппи вектор { сг/(.х0, Т - Г0 ) },Ем. где

■"о

дж£[1о,Т], (2,= 6, к=0,1,...ш-1, т=| Т-10|/6.

5-обобщенный вектор Шеппи является динамически устойчивым.

Введено понятие обобщенного вектора Шеппи. Доказано, что если существует предел

то обобщенный вектор Шеппи динамически устойчив.

Введено достаточное условие динамической устойчивости Опорного плана ралределения затрат. Также исследована динамическая устойчивость Банзафа индекса

В заключении диссертации формулируются основные положения диссертации, которые выносятся на защиту. Эти положения состоят в следующем:

1.Предложена модификация понятия КГМ-решения классической кооперативной игры, а именно, так называемое, слабое ЫМ-решение, юэторое, в свою очередь, базируется на усовершенствованном понятии доминирования дележей.

2.Получено неимеющее аналога в теории Неймана-Моргенштерна достаточное условие того, чтобы ядро данной игры было слабым МЫ-решением, а тогда, как показано также, оно является единственным слабым ее МЫ-решением.

3.В несбалансированных играх проиллюстрировано принципиальное отличие слабых ИМ-решений от обычных, "сильных", а именно показано, что ни одно из ЫМ-решений может не быть слабым ЫМ-решением, а последние, в отличие от "сильных" в

существенных несбалансированных играх могут состоять из одного дележа.

4.Предложен способ решения проблемы сужения множества NM-решений в играх, имеющих много таких решений. На конкретном примере проиллюстрировано, что он может приводить к выбору единственного, в некотором смысле наилучшего NM-решения.

5.На класс кооперативных игр с распределением затрат распространена одна из версий динамической теории кооперативных игр, ранее предложенной для класса игр с распределением прибыли.

6. Введено понятие динамической устойчивости (согласованности во времени) процесса распределения затрат. Показано, что распределение затрат в смысле обобщенного вектора Шепли является динамически устойчивым. Также исследована динамическая устойчивость Опорного плана распределения затрат.

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

По теме диссертации опубликованы следующие работы:

1. Оао Hong we i -The Dynamic Cost Allocation Games, International Congress on Computer System and Applied Mathematiks CS AM'93, Abstracts, 1993, St.Peterburg, p.28.

2. Gao Hongwei -The Shapley Value in Dynamic Cost Allocation Games, International Conference on Interval and Computer-Algebraie Methods in Science and Engineering INTERVAL'94, 1994, St.Peterburg, p. 115.