Построение максимально стимулирующего решения для некоторого класса кооперативных игр тема автореферата и диссертации по математике, 01.01.11 ВАК РФ

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

СМИРНОВ Евгений Николаевич

ПОСТРОЕНИЕ МАКСИМАЛЬНО СТИМУЛИРУЮЩЕГО РЕШЕНИЯ ДЛЯ НЕКОТОРОГО КЛАССА КООПЕРАТИВНЫХ ИГР

Автореферат

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

по специальности 01.01.11 — Системный анализ и автоматическое управление

Нижний Новгород, 1995

Работа выполнена в Нижегородской государственной архитектурно-строительной академии (НГАСА).

Научный руководитель — доктор физико-математических наук, профессор В. А. Брусин.

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

, г

— доктор технических наук, профессор Ю. М. Максимов (НГТУ),

— кандидат физико-математических наук, доцент А. В. Баркалов (ННГУ).

Ведущая организация — Научно-технический центр Российской инженерной академии при Волжской государственной академии водного транспорта.

Защита состоится «. .1995 года в 1час.

на заседании диссертационного совета К 063.77,01 в Нижегородском государственном университете по адресу: ГСП-20, 603600, г. Н. Новгород, пр. Гагарина, 23, корп. 2, конференц-зал.

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

Автореферат разослан «.

Ученый секретарь диссертационного совета кандидат физико-математических наук, Ч

доцент с/ В. И. ЛУКЬЯНОВ

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

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

В работах X. Райфы, Д. Исбелла, Е. Калаи, Р. Майерсона и А. Рота рассматривались так называемые пропорциональные арбитражные схемы (АС).

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

В.И.Ротарем и А.О.Калашниковым пзказано существование МС-решения для случая произвольного числа участников.

Однако упомянутые доказательства не дают ответа на вопрос о конкретной структуре МС-решения.

Предлагаемая диссертация посвящена построению МС-решения для некоторого класса кооперативных игр с функцией суммарного дохода достаточно общего вида.

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

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

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

' Научная новизна. В работе получены следующие основные результаты: •

1. Теорема существования п единственности МС-ретсншс для задачи распределения доходов с произвольным числом участнаьов. • 2. Построено МС-решенне в явном ппде для оадачк распределения доходов с двумя участками.

3. Построено MC-pciceimc для оадачи распределения доходов с тремя и более участниками в случае, когда функция суммарного дохода R есть функция от суммы вкладов. • *

4. Строится последовательность функций, аппроксимирующих первую составляющую МС-решення. .

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

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

Апробация работы. Результаты работы докладывались на семинаре _ Института социально-экономических проблем Академии наук СССР (1985 г.), на 11 научной конференции молодых ученых механико-математического факультета ГЬрьковского государственного университета и НИИ механики при Горьковском государственном университете (1986 г.), на семинаре лаборатории Вероятностных проблем управления экономическими объектами ЦЭМИ АН СССР (1988-90 гг.), на семинаг pax кафедр Нижегородского государственного университета: теории функции (1990-94 гг.), информатики и автоматизации научных исследовании (1995 г.), математического обеспечения ЭВМ (1995 г.), на семинаре кафедры высшей математики Нижегородской государственной архитектурно-строительной академии (1994-1995 гг.).

Публикации. По результатам выполненных исследований опубликовано 9 работ, перечень которых приведен в конце автореферата. В работах [l]i[2],[9]' В.И.Ротарю принадлежат постановка оадачи, основные определения, доказательство теорем существования и единственности. Остальные результат^! получены автором самостоятельно.

Структура и объем работы. Диссертационная работа состоит из введения, пяти глав, заключения и одного приложения. Объем работы составляет 81 стр. машинописного текста и 14 рисунков. Библиография содержит 36 наименований.

КРАТКОЕ СОДЕРЖАНКЕ ДИССЕРТАЦИИ.

Во введении излагаются основные результаты работы. «

Приведем постановку задачи. Два или несколько участников осуществляют вложения в некоторый процесс. Будем предполагать, что вклады участников допускают количественную оценку.

В дальнейшем нам удобно будет представить вклады участников в виде вектора Ь = (Ь|,...,Ьп).

Предполагается также заданной функция Я = Я(Ь\,..., Ь„) - суммарный эффект производственного процесса при векторе вкладов Ь.

Функцию Я будем считать неубывающей по всем аргументам.

В контексте той или пной задачи величина Я получает соответствующую интерпретацию. Мы обычно букем называть величину Я суммарным доходом или просто доходом.

Задача состоит в том, чтобы некоторым "разумным" образом распределить этот доход между участниками. Пусть = д,(Ь) — доход участника ¿. Считая, что распределению подвергается весь коллективный доход, получаем, что функции д^Ь) должны удовлетворять уравнению:

.....Ьп) + ... + дп(Ьи...,Ьп) = Я(Ьи...,Ъп) (1)

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

Естественно считать также, что при увеличении вклада участником г доходы остальных, по крайней мере, не убывали, т.е. функция не убывает по аргументам Ь^, г,] = 1,п,г =г у.

Это требование будем называть принципом неподавления.

Конечно, оба эти требования в совокупности означают просто мо-нотонйость функций & по всем аргументам.

Тккпм образом, вводится

•г

Аксиома 1. Функция & <онотопяа но аргументам Ь,-, г,] = 1,п. Следующее требование связано с так называемой паритетностью участников. Ограничимся случаем, когда функция Я симметрична. Тогда естественно потребовать,что бы выполнялась Аксиома 2. Ио того, что Ь; > 6,-, следует, что > д,, г,з = 1,п. Класс функций, удовлетворяющих уравнению (1) и аксиомам 1 и 2, будем называть классом стимулирующих решений

Класс © не пуст - ему принадлежит, например, так называемое "уравнительное" решение.

т = ШЬ).--:Ш) = (Л(Ь)/п,...,Л(6)/п)

Определение. Пусть р = (р1,...,рп) - перестановка множества (1,... ,п). Обозначим через 1р множество точек таких, что Ьл > ... > > 0; Максимально стимулирующим решением (МС-решением) задачи распределения доходов будем называть вектор-функцию д{Ь) == • из класса @ такую, что для любой перестановки р при

всех Ъ&1Г ...

»60

(2)

9рп-1= ' йиР Яр.-Д6)

«ео. »«(Ч^,^•■•'^.-1 .■

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

В главе"2 вводится определение максимально стимулирующего решения (МС-решения) и доказывается теорема существования и единственности МС-решения. '

Кроме того, показывается, что непрерывность (абсолютная непрерывность) функции суммарного дохода Л по одной из координат влечет непрерывность (соответственно абсолютную Ведрерывность) МС-решения по этой координате).

В главе 3 строится максимально стимулирующее решение в случае двух участников.

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

э+(61Л) = Л(Ь1,62)-Л(62,Ь2)/2 дЦЪиЪ2) = ЩЬ2,Ьг)/2 9ЧЬ) = (дПЬ),9№) 9Т(Ь1,Ь2) = Я(Ь1Л)/2 д2(Ь1М) = Щ1,Ь2)-Я(ЬиЬ1)/2 3~(Ь) = (91{Ь),91(Ъ)) дЧ{Ъ) = пии{^(Ь),9Г(Ь)}

Решение д+(Ь) возникает следующим образом.

Пусть Ь = (61,62) - произвольная точкаобластп В — {Ь: Ь1>Ъ2> 0},

Ъ=(Ь2,Ь2),Ъ=(Ь1,Ь1)-

Ситуации, отвечающие векторам вкладов Ь, Ь, Б, будем называть ситуациями 1, 2, 3 соответственно. В качестве одного из возможных вариантов распределения Л предлагается следующее: Пусть участники первоначально находятся в ситуации 1. В этом случае доходы участников равны:

91(Ь) = 92(Ь) = ЩЬ2,Ь7)/2

Предположим, что первый участник увеличил свой вклад и мы перешли к ситуации 2. Оставим второму участнику тот же доход, что он имел в ситуации 1, а ъа пряращенкз суммарного . /«ода отдадим первому.

В ситуации 2 доход второго участника:

92(b) = дг{Ъ) = R[hM)/2 = gl(b),

а доход первого участника

I

^(6) = ЛСбж.бз) - Д(6х,Ьх)/2 =

Решение <?4(Ь) не всегда приемлемо, так как функция д{ (Ь) может быть не монотонна по аргументу Ь*.

В качестве альтернативного варианта распределения R предлагается, решение д~, означающее следующее:

Пусть сначала участники находились в ситуации 2.

Предположим, что второй участник увеличил свой вклад и мы перешли к ситуации 3 с вектором вкладов 5 = (b\, Ьг).

Доходы участников в ситуации 3

Э1(5)=92(Б) = Л(Ь1;Ь,)/2

Дадим первому участнику в ситуации 2, сколько он имел бы в ситуации 3:

91(b) = ei(t; = R(h,h)/2 = 97(b)

Доход второго участника в ситугщии 2:

д2(Ь) = ЩЬиЬ2) - Я^ьМ/г = 92(b)

Конечно, д~(Ь) также не всегда приемлемое решение, так как функция 5J (6) может быть не монотонна по аргументу £>j.

Тем не менее, в ряде ситуаций MG-решенпем оказывается вектор-функция д"(Ь), причем структура решения определяется знаком второй смешанной производной функции Л: Лк^'ь^г) = cPR/dbidbj. Будемго-ворить, что функция R удовлетворяет условию (Ai), если соотношение -^12(61,62) = 0 при каждом Ь] > 0 однозначно разрешимо относительно Ьг и определяет непрерывную убывающую функцию = £(ЬХ),

б

причем при 62 > £(Ь|) Яп(ЬиЬз)<0, а при 0 <62 <£(6,) ^12(61,62) >0. '

Если же при к > £{Ь|) Ли^,^) > О, а при 0<Ьг<ф1) Лп^гМ) < 0.

будем говорить, что функция Л удовлетворяет условию (А2). Кривую, определяемую условием Л^ЬьЬг) = 0» обозначим через I, точку ее пересечения с биссектрисой первого координатного угла через А, координаты этой точки через (Ьл, Ьл). Будем говорить, что функция Я удовлетворяет условию (Б), если при каждом Ьх > ЬА уравнение

Я(ЬъЬ1)/2 + ЩЬ7,Ь3)/2 = ЦЬиЪ2)

пли, что эквивалентно, уравнение дЦ~(Ь 1,62) = однозначно

разрешимо относительно Ь^ и определяет гладкую убывающую функцию Ъх = <р{Ь\). '

Теорема 3.1. Если выполнены условия (А1) и (Б), то в области В — {Ь: Ь| > Ь] > 0} МС-решенпе задается формулой:

9(Ь) = 9°(Ь)

Отдельно рассматривается случай, когда Л(Ь1,б2) = Я(Ь% + Ьз)-ТЬорема 3.2. Если выполнено условие (А2), МС-решение в области В ~ {Ь : Ь] > 62 > 0} задается соотношепплмп:

при 0 < &2 < Ь < Ьл .Ш = 9Т{Ь) = ЩЬ1М)/2,

щ>п(ЬъЬ2)£1 91(ЬЬЬ7) = Я(Ьа,Ьл)/2+ / Д,(*,«)«*».

(ЬлМ

.где: Н\ = ЭЯ/'дЬх, криволинейный интеграл 2-го рода берется вдоль кривой I от точки А до точки (61,62)

при 0<&2< £(61) < ЬА < 62 при £(&!) < Ь2 < Ьл <

>(Ь,Л) = ШьШ + ЩЬгМ) -

где ¿1 = ч(Ьг) ~ функция, обратная к функции

при Ьл<Ьз<Ь1

л(Ьь'Ьа) = ЗГМ) = Л(ЬьЬ,) - Л(Ь2,Ьг)/2

Отдельно рассматривается случай, когда Л(61,62) = Л(&х + 62). Отмечено существование так называемых "зон безразличия", т.е. областей, в которых увеличение вклада одним из участников не приводит к увеличению его дохода.

Пила 4 посвящена поиску МС-решения в случае трех и более участников.

Для случая трех и более участников поиск решения вызывает затруднение. Автору пока удалось найти МС-решение в явном виде только для -функции вида Л(6|,... ,£>„) = Д(ЕЬ») причем функция И(и) предполагав ется возрастающей, дважды непрерывно дифференцируемой, Л(0) = 0 и Л" сохраняет знак. Доказывается

' Теорема 4.1. Пусть в задаче распределения доходов с тремя участниками функция Л может быть представлена в виде Л = Л(6Х+62+63), где Л(и) - монотонно возрастающая, дважды непрерывно дифференцируемая функция, Л(0) = 0, Л* сохраняет знак в области В = {6: 6| > Ьг>63>0}.

Тогда при Л" > 0 МС-решение описывается формулами

91(^1,^2,6}) в Л(б1 + 6г + 63) — Л(26г + Ьз)/2 — Л(365)/6 й(6,Л,63) = Л(2Ьг + 63) - Л(365)/6 ¿3(61,62,63) = Л(36з)/3,

а при Л* < 0

д'АЬхмм) = Л(зЫ/з

НЬи 62,63) = Л(6Х + 2Ьг)12 - Л(36,)/6

НЬММ) = Л(б! + Ьг + 63) - Я(Ь, + 2Ьа)/2 - Л(ЗЬ,)/б

Отдельно исследуется случай, аогда Л*' -2 б г? области В, '.

Показывается, что в зчюм саучее МС-^ттевпш является распределение доходов пропорционально вкладам.

Приводится обобщение теоремы 4.1 для произвольного числа участников.

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

Задача поиска МС-решения в области В п-мерного пространства заменяется задачей построения некоторой функции дд,п> определенной на дискретной решетке Вд|П, нелинейным разностным соотношением.

Показывается, что на множестве Вд|П функция дд,„ растет не быстрее, чем функция Л, т.е. что справедливы соотношения:

О < 5д,п(Ьь---А + А>---|ЬП) - гд,п(Ьх,• • •,-• -»М <

гдеточхи (г>1,...,Ь,-.....Ь„) и (&!,..., Ь<+Д,...,ЬП) принадлежат множеству Вд,„.

Функция кусочно линейно продолжается на область В. Однозначность продолжения обеспечивается тем "фактом, что в (п + 1)-мерном пространстве через (п+1) точку можно провести единственную п-меряую гиперплоскость.

Варьируя Д, мы получаем однопараметрическое семейство функций {<?д,п}» определенных в области В. г. ' '

Показывается, что это семейство удовлетворяет условиям теоремы Арцела и является компактным в пространстве С(В) функций, непрерывных в области В.

Вводится класс <&о функций, являющихся пределами всевозможных последовательностей ддь,п(6), равномерно сходящихся в области В при Д* —0. • ;

Показывается, что класс @о - вырожденный и состоит но одной функции 51 (Ь}~ первой составляющей МС-решения. Отсюда выводится

Теорема 5.1. Пусть функция Л(Ь1,...,Ь„) не убывает по всем аргументам, имеет непрерывные частные производные первого порядка,

множество В&>п определено соотношением

Дй,п = {Ь : bi = PiA, Л > О, Л - целые, Pi > Р2 >...>*>„ > 0}, функция определена на множестве соотношением Эл.п(6ь - • •, Ь» • • •, Ьп) = nun{g^,n(bi - А,..., bit..., Ь„)+ ЩЪ,..., Ь;,..., Ьп) - R(by - Д,..., Ь<,..., Ь„),..., Эд,п(Ьь,. •, Ьп) + R{bu..., ь„.•, Ю--R(bl)...,bi-A,...,bn),...,g&,n(bu...tbi,..,,ba + A)}

и. кусочно-линейно продолжена на множество В\Вд>п. Тогда для любой последовательности положительных чисел {At}, сходящихся к нулю, соответствующая последовательность {?д»,п(Ь)} равномерно сходится в .области В к функции gi(b) - первой составляющей , МСфешения. • .

В приложении выводится, уравнение в частных производных, которому удовлетворяет функция gi(b) - первая составляющая МС-решения:

• и

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

Приводится метод решения уравнения (3) в случае двух участников. Среди множества решений выделяется максимальное.

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

1. Ротарь В.И., Смирнов E.H. Принцип максимальйои стимуляции в оадаче дележа, j В сб. "Исследования по математической экономике и теории управления". - М.: ЦЭМИ, 1982; С. 115-136.

2, Ротарь В.И., Смирнов' E.H. Об одном решении задачи дележа: / В сб. "Модели и методы стохастической оптимизации" - М.: ЦЭМИ, 1983. С. 153-180. '

3. Смирнов Е.Н. Об одной задаче распределения доходов. / В сб. "Вероятностные проблемы управления я математическая экономика." -М.:ЦЭМИ, 1984(85). С. 159-166.

4. Смирнов Е.Н. Аппроксимация МС-решения решениями нелинейного разностного уравнения, f Материалы 11 научной конференции молодых ученых механико-математического факультета и НИИ механики при Горьговском государственном университете. Апрель 1986, Горький, ГГУ.

5. Смирнов Е.Н. Решение оадачи распределения доходов при дополнительных ограничениях на функцию эффекта. / В сб. "Исследования по стохастической оптимизации и математической экономике". - М.: ЦЭМИ, 1986. С. 167-174.

6. Смирнов Е.Н. Нахождение максимально стимулирующего решения в арбитражной схеме с тремя участниками. / В сб. "Автоматизация управления производством в автомобильной промышленности". - М., 19§8.С. 107-117.

7. Смирнов Е.Н., Виноградова Е.Н. Построение последовательности функций, сходящихся к МС-решению оадачи распределения доходой с тремя участниками. / В сб. "Автоматизация управления производством и автомобильной промышлейностп". - М., 1988. С. 118-127.

8. Смирнов Е.Н. Понсх МС-решения как решения нелинейного уравнения в частных производных. / В сб. "Автоматизация управления производством в автомобильной промышленности"'. М.', 1989. С. 115— 136.

9. Rotar V.I., Smiraov E.N. The Maximum invective Solutions in Bargaining Problem.// Mathematical Social Scienses. V. 24 (1992). Pp. 118", North-Holland.

Подл, к печати_Формат 6ШЕО 1/16 £ушга газетная

Печать офсетная. Объем 0,7 печ.л. Ткраж 100 экз. Заказа Бесплатно; . ' •

Нижегородский государственной университет',603600,Н.Новгород, пр-кт Гагарина.23 ____•' •

Полиграфический центр Нижегородской государственной архитектурно-строительной академии 603600,Н.Коэгород.Илышская,65-