Вектор Шепли в кооперативных динамических играх тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

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

ЕГИАЗАРОВА Элина Валерьевна

ВЕКТОР ШЕПЛИ В КООПЕРАТИВНЫХ ДИНАМИЧЕСКИХ ИГРАХ

Специальность: 01.01.09. "Математическая кибернетика"

А В Т О Р Е Ф Е Р А Т диссертации на соискание ученой степени кандидата физико-математических паук

С анкт-11 етер бу рг 1997

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

Научный руководитель: доктор физико-математических наук,

профессор Петросян Л. А.

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

профессор Захаров В. В.

кандидат физико-математических наук Дюбин Г. II.

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

технический университет.

Защита состоится 1997 г. в ^?часов на заседа-

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

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

Автореферат разослан " ^ " <уСС99"

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

д.ф.м.н., профессор ( г^Лу^^ Горьковой В.Ф.

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

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

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

Ланные вопросы рассматриваются в кооперативной теории динамических игр. По-видимому, первой работой по динамическим играм со многими участниками следует считать работу Л. Л. Пе-тросяна, II. В. Мурзова "Игра на перетягивание со многими участниками" (Вестник ЛГУ, 1967 г. N 13, вып 3, с. 125-129).

Динамические игры со многими участниками подробно исследовались в работах П. Л. Григорепко, П. 11. Данилова, Г. Н. Дюбина,

B. II. Жуковского, В. В. Захарова, А. Н. Красовского, II. II. Кра-совского, А. Ф. Конопенко, В. В. Мазалова, О. А. Малафеева, М. С. Никольского, В. Д. Ногина, Л. А. Петросяна, А. Ф. Клейменова, С. В. Чистякова.

Большое внимание этому направлению в настоящее время уделяется и зарубежными специалистами. Здесь следует отметить работы следующих авторов: С.Иоргенсона, Т. Заккура, С. Игпигуро,

C. Кобайаши, И. Каллусски, А. Орге, Дж. Филлара, В. Кайтала, М. Пойола и др.

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

Основная цель диссертационной работы — построение и исследование вектора Шепли и его обобщений (/?-вектора, КС-вектора) в динамической игре оптимальног о размещения конечного множества объектов, динамической игре на минимизацию затрат в транспортной сети специального вида и динамической игре приобретения информации о новых технологиях. Одновременно ставится цель исследовать построенные принципы оптимальности на динамическую устойчивость. В случае, когда динамическая устойчивость не имеет места, построены новые регуляризованные принципы оптимальности, обладающие свойством динамической устойчивости.

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

Благодаря использованию этого подхода впервые удалось показать динамическую устойчивость вектора Шепли, /?-вектора и КС-всктора в игре на минимизацию затрат в транспортной сети и ее циклическом обобщении. Доказана динамическая неустойчивость вектора Шепли в комбинаторной игре оптимального размещения конечного множества объектов, в игре приобретения информации о новых технологиях и ее разновидности (монополистическая торговля). Проблема динамической неустойчивости решена посредством проведения регуляризации характеристической функции и построения новых регуляризованных принципов оптимальности.

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

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

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

Апробация работы. Основные результаты работы докладывались на Международной конференции по интервальным вычислениям и методам компьютерной алгебры в науке и инженерии (Interval' 94) в Санкт-Петербурге, Ш-ей Международной конференции "Многокритериальные задачи при кг:определенности" в 1994 г. в Орехово-Зуево, на Международном научном конгрессе "Народы содружества независимых государств накануне третьего тысячелетия: реалии и перспективы", на Международной конференции памяти Н. Н. Воробьева "Теория игр и экономика", проходивших в 1996 г. в Санкт-Петербурге, на семинарах кафедры математической статистики, теории надежности и массового обслуживания факультета прикладной математики -- процессов управления Санкт-Петербургского университета, а также на Санкт-Петербургском городском семинаре по теории игр (руководитель Л. Л. Петросян).

Публикации. Основное содержание работы опубликовано в работах [J] - [5]:

Структура и объем работы. Диссертация состоит из введения, четырех глав (22 параграфа) и списка использованной литературы. Объем работы составляет 104 страницы. Библиография содержит 39 наименований.

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

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

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

В § 1.1 представлена, постановка задачи размещения конечного множества объектов. Задача была сформулирована в работе U. Faigle, W. Kern, "On Some Approximately Balanced Combinatorial

Cooperative Games", однако рассматриваемые нами вопросы исследуются впервые.

Рассмотрим комбинаторную игру размещения тг предметов по т корзинам. Размер г-го предмета— a,-, i = 1,2,... ,п; размер j-ой корзины — bj, i = 1,2,...,m. Предполагается, что а, ^ bj для любых i и j, что означает, что всякий предмет может поместиться в любую корзину. Игроками считаются владельцы предметов и владельцы корзин.

Обозначим через N множество всех игроков, |ЛГ| = п + т. Рассмотрим игру в кооперативной форме.

Тогда v(N) определяет общий доход игроков при оптимальном заполнении корзин.

т

v{N) = max^2^2ai, (1)

3 = 1 i€A,

где Aj --множество предметов, заполнивших корзину j.

Будем полагать, что характеристическая функция в рассматриваемой игре — вещественно-значная функция v : 2N —> R, удовлетворяющая формуле (1) и следующим условиям:

1) «(0) - О,

2) v(SUT) ^ v(S) + v(T), если 5 С N, Т С N, Sr\T= 0. Коалиция S С N включает в себя подмножество А множества

предметов и подмножество В множества корзин, т. е. S = AUB, А С {1,2,...,п},£С{1,2,...,ш}.

Определим характеристическую функцию v(S), S = ylUB, 5 С Лг, как максимум общего размера предметов из А, которые могут быть упакованы в корзины из В:

v(S) — maxУ^ а,-, (2)

j i£Aj

где максимум берется по всевозможным разбиениям множества А на подмножестваА\, А2, ■ ■■ , А\щ, таким, что

сч ^ bJ> Vе в-

iGAj

Если коалиция 5 состоит только из владельцев предметов, или только из владельцев корзин, то = 0.

Пусть Л2, ... , Ат — разбиение множества А, доставляющее максимум в формуле (1). Таким образом, через А1, Л2, ... , Ат обозначен оптимальный способ заполнения корзин.

В § 1.2 введена многошаговая игра Г(ш) размещения предметов по т корзинам. Рассматривается динамическое развитие игры и исследуется распределение во времени дохода, получаемого каждым игроком согласно вектору Шепли.

Обозначим через В— ;'-ую корзину, 3 = 1, 2,

,т,В= и В5. 1=1

Пусть

Ак = и Аг

(3)

2=1

в-к = и^-

(4)

В результате шага к образуется подыгра Г(?тг — к), в которой вектор Шепли определяется компонентами:

8Ъ,{Вк,А\Ак)

£

(.ч-Щ1 + т-к-8)[ (I + т — к)\ :

/=и\л*|, з = |5|, 1= 1,2,... ,п +

(5)

8Ь ¿(-вй, —доход г-го игрока в подыгре Г(т—к), когда корзины

В\,В2,... ,Вк уже заполнены, А \ А¡. — множество неразмещенных в результате к тагов предметов, А = {1, 2, ... , га}.

В § 1.3 вводится определение динамической устойчивости вектора Шепли для игры размещения конечного числа объектов. Доказана динамическая неустойчивость вектора Шепли в рассматриваемой игре.

В § 1.4 предложена регуляризация вектора Шепли. Для этого вводится функция v(S') : 2Л —>• /2+ следующим образом:

m—1 г ^

где v(S',j), v(N;j) — значения коалиций S и N соответственно в подыгре Г(ш — j); a,{Aj+\) — общий размер предметов, заполнивших корзину В; +1 оптимальным образом.

Утверждение. Определенная по формуле (б) функция v(S) является хара ктер истине с кой.

Приводится и доказывается теорема о динамической устойчивости вектора Шепли, соответствующего новой характеристической функции (6), в игре размещения объектов Г(ш).

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

/iiW=Sh,( Ät;I\Ät).g(It+1) (?)

Е а(^)

j=k + i

Очевидно, ßi(k) >0, Vi = 1, 2,. .. , п + m, V/fc = 0,1,... , m - 1.

В § 1.5 представлен пример, призванный проиллюстрировать динамическую устойчивость регуляризованного вектора Шепли.

Глава 2 посвящена исследованию иг ры на минимизацию затрат в сети специального вида. Впервые задача была введена в работе Bird G.G. "On cost allocation for a spanning tree: Л game theoretic approach", рассматривалась в H.Aarts. T.Driessen "The Irreducible Core of a Minimum Cost Spanning Tree (Jame". Наше обращение, к этой игре связано с исследованием вектора Шепли и его обобщений (/?-вектора, КС-вектора) на динамическую устойчивость. Обобщения вектора Шепли введены в работе Kurz М. "Coalitiorial value"(The Shapley value: essays in honor of Lloyd S. Shapley, p. 155-177).

§ 2.1 посвящен представлению постановки задачи на минимизацию затрат. Игра состоит в следующем: множество производителей М обеспечивает множество потребителей К определенными товарами либо услугами. Задача состоит в определении такого пути,

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

1.(5) = £ а, (8)

1€5ПК = К'

где _

-ем

(V, = ^ I

к(г, г) > 0, к(г,г) > О, г € А', с € М для любых 5' - М и К', К'С К, |А'|$>1.

Для всех других коалиций ,$'' ф 8, г(З') = 0.

В § 2.2 приведено аксиоматическое определение /^-вектора для коалиционной структуры вида

0,(К') = (В1,В1) (9)

/=1,2,..., ш, В, - М и А', В, = К \ А', \К'\ = I.

Показано, что в любой другой коалиционной структуре игроки имеют нулевые доходы. Сконструирован ,0-вектор для рассматриваемой игры с коалиционной структурой (9).

§ 2.3 посвящен нахождению значения КС-вектора для коалиционной структуры (9).

Теорема. КС-вектор определяется по следующим формулам:

1 -су,-, г СЕЛ, ПА,

¥(1>,/ЫК'У)= ^ »' +1 ' (10)

-о,, г € В\

Ф-'КА(А')) = £ „,. + ± £ «,., ; 6 м. (11)

т + 1 2ш

В § 2.4 рассматривается ди||)феропциальная игра на минимизацию затрат

Г(т/°, г°,Т-10) (12)

с предписанной продолжительностью Т— ¿о из начального состояния

(у0, Л

Введем следующие обозначения. Через У1, Уг,... ... , Ут обозначим производителей, т. е. игроков из множества М; через ^2,... — потребителей из Й.'. Пусть 6 й1 — пе-

ременная состояния, соответствующая игроку V), и6 V} С Т1к — управляющая перемещая игрока У,-; 2г Р Г{1 — переменная состояния игрока '¿I, VI Е Уг С Ик — его управляющая переменная. Тогда дифференциальные уравнения имеют вид:

Уз = Ъ (Уз >из',П,---, Щ), У] (<о) = У°,

¿г = V,-; , Чт), = г?,

3 — 1,... ,пг; г = 1,... ,к.

Пропускные способности определяются для любых х',х" Е МиК и зависят от соответствующих переменных состояния. Предположим, что

V®' € М, х" € К,

где у' некоторое значение переменной состояния, соответствующее х' € М, а г" — значение переменной, соответствующее х" £ К. Для всех других х' и х" к(т/, г") — 0.

Пусть коалиции 5 имеют следующий вид:

,9 = М и К', К' С К, К" ф 0.

Для 5 = М и К'

■"ЕЕ 1\щ{1)М1))(13)

Для всех иных коалиций, отличных от вышеуказанных,

Рассмотрим теперь семейства подыгр Г[у{1),г{{)\Т— I) и характеристических функций — I) вдоль оптимальной траек-

В подыгре T(y(t), z(t); Т — t) характеристическая функция определяется следующим образом:

где под {yj(t),Ji(t)} понимается оптимальная траектория. Доказаны следующие теоремы.

Теорема. р-вектпор динамически устойчив в дифференциальной игре (12).

Теорема. КС-вектор в дифференциальной игре Г(у°, г°; Т — ¿о) динамически устойчив.

Циклическое обобщение игры на минимизацию затрат в сети рассматривается в главе 3.

В § 3.L вводится определение циклической игры на минимизацию затрат в транспортной сети специального вида. Имеется п групп игр на минимизацию затрат, в каждой из которых через Л',- обозначается множество потребителей, через M¡ — множество производителей, i = 1,2,... , п. Множество всех игроков в игре обозначим как

п п

N = К U М, К - у I<¡, М = (J M¡. Каждая г'-ая группа (Л,-, М,-)

i-1 t=I

связана с (J\;;_i, M¿_i) и (Л\+1, Mí+i) следующим образом: любой потребитель из X; может посещать производителей из M¿_i; любой производитель из M¿ доступен для потребителей из A",+i.

В § 3.2 получены формулы для потенциала и вектора Шепли в рассматриваемой игре.

§ 3.3 определяет значение /?-вектора для коалиционной структуры

тории {y(t),z(t)}, t€[t0,T],

л,-ем ihsK'

р = (ВиВ2>... ,Вп), Bi = Ki\JMi, ¿=1,2,...,ii, (16)

а § 3.4 посвящен определению КС-вектора в игре с той же коалиционной структурой (16).

В § 3.5 введена дифференциальная игра

„1° „2й „2° „,нО „пО.тп

Т(у , г ,у ,г ,... ,у , г и - к) (Ь)

с предписанной продолжительностью Т — ¿о, определены процедуры распределения дележей для всех исследуемых принципов оптимальности, которые, вследствие неотрицательности доказывают динамическую устойчивость вектора Шепли, /^-вектора и КС-вектора в циклической игре на минимизацию затрат.

КС-вектор в дифференциальной игре на минимизацию затрат имеет следующий вид:

Ф1 К /?) = —; у0, Т - /о) + Д(Я;; у0, т - *о), те ¡и, иц -Ь 1 I

тщ 4- 1 ¿1Щ

3 € М{, г = 17^.

Динамическая устойчивость КС "-вектора, следует из неотрицательности процедуры распределения дележа, которая определяется по формулам:

1 у; ел/,

ем,-!

1 ел", уу-'ел/,-! ' чеА", уел/,

Глава 4 посвящена исследованию игры торговли информацией о новых технологиях конечному множеству производителей. Задача

была сформулирована в работе T. Driessen, S. Muto, M. Nakayama "Л Coopérative Game of Information Trading: The Core, the Nucleoulus and the Kernel".

ß § 4.1 представлена кооперативная форма этой игры. Пусть t из 71 производителей приобрели информацию о новой технологии. Тогда через {E(t), E*(t)\t 6 {0,1,... , п}} обозначим набор функций, удовлетворяющих следующим предположениям:

1 )E{t) > E*(t),Vt G {1/2, ... - 1},

2)E{t) }> E(t + 1 ),Vf G {1.2,... , н - 1),

3)£-(0 Îî £*(<+!), Vi£ {0,1,...,п-1},

4)7J(1) > E*{0) > 0.

Множество всех игроков обозначается через Лг0, № = N U {0}, N = {1,2,... ,и}.

Кооперативная игра (№,v) информационной торговли определяется следующим образом:

v(S°) = тих{1Е{1) + (я-1)Е'{^ t е {0, 1,... ,«}), (18)

V,S'° С Лг°, 5" = ,Ь'и {0}, S С N,

v(S) = sE'(n - .s), V.S'CiV. (19)

В § 4.2 сконструирован вектор Шешш для у той игры, а в § 4.3 доказана теорема о его динамической неустойчивости.

3 4.4 предлагает пример, иллюстрирующий динамически неустойчивый вектор Шепли в игре информационной торговли при п — 4.

13 § 4.5 введена новая характеристическая функция для подыгры Г(и — к), определяемая следующим образом:

j — k

где

tn-k ~ \Тп~к\

, _ , E(tn.k), j е г«-* vU)- ï E'(tn-t), итп~к

j = А + 1, ... , и, к = 0, 1,. .. , п — 1;

— оптимальное количество покупателей в подыгре Г(гг. — к), — множество покупателей, |T"-t| = tn-k-

Утверждение. Функция v(S°]k), определяемая по формуле (20), является характеристической функцией для рассматриваемой игры.

Вектор Шенли, соответствующий характеристической функции v(S°]k), назовем регуллризованным:

£ {'»)• (21)

,6S° *

Теорема. Регуляризованный вектор Шепли, определяемый по формуле (21), динамически устойчив.

Приведен рассмотренный в § 4.4 пример, для которого определены значения регуляризованного вектора Шенли.

В § 4.6 представлена так называемая игра информационной торговли с монополией, в которой предполагается, помимо п?едполо-жений из § 4.1, выполнение следующих условий:

E(l)>lE(l), Vi £ {1,2,... ,п},

E'(l) = Q, Vi € {1, 2,... , и}.

Характеристическая функция в игре с монополией имеет вид:

v(.S°) = max(E(l),sß*(0)), V5° С № (22)

v(S) = 0, Vi' С N, S ф N, (23)

v{N) = nE'(Q). (24)

В § 4.7 сконструирован вектор Шепли и доказаны следующие теоремы:

f "Теорема. Имеется игра с монополией, определяемая по формулам

{j8S)-(24).

Пусть выполнено следующее условие

Е{ 1) > пЕ*(0).

Тогда вектор Шепли динамически неустойчив в (№;v) при любом значении п (п 2).

Теорема. Если в рассматриваемой игре выполнено

Е{ 1) ^ 2£*(0),

то вектор Шепли динамически неустойчив в (Л^11, у) для п ^ 3. В § 4.8 выбрана коалиционная структура

Сконструирован /?-вектор для коалиционной структуры (25) и доказаны утверждения о его динамической неустойчивости.

Общие выводы но работе.

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

Для игры на минимизацию затрат в транспортной сети доказана динамическая устойчивость вектора Шепли и принципов оптимальности (¿¿-вектор, КС-вектор) для коалиционных структур специального вида.

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

Представлена игра размещения конечного числа объектов, принадлежащая классу комбинаторных игр, в которой доказана динамическая неустойчивость вектора Шепли. Для этой игры сконструирована новая характеристическая функция и доказана теорема о динамической устойчивости соответствующего ей вектора Щепли.

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

(25)

где

В£ = К"11{0}, КСМ, КфИ, Вп„к = N \ К.

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

Основные результаты диссертации опубликованы в следующих

работах:

1. Eguiazarova Е. V. The Dynamic Stability of the Shapley value in diamond-shaped game//Intern. Conf. on Interval and Computer -Algebraic Methods in Science and Engineering. Interval'94. Abstracts. St.-Petersburg, 1994.

2. Eguiazarova E., Kazakova-Freze N. The Shapley value for traveling salesman game // Multiple criteria problems under uncertainty: Abstracts. The 3-d Intern. Workshop, Orekhovo-Zuevo, Russia, 1994.

3. Егиазарова Э. В., Казакова-Фрезе H. О неустойчивости долгосрочных проектов// "Народы содружества независимых государств накануне третьего тысячелетия: реалии и перспективы": Тезисы. Межд. научный конгресс. Санкт-Петербург, 1996.

4. Eguiazarova Е. V. The Shapley value for a Bin Packing Game// Game Theory and Economics. N. N. Vorob'ev memorial conference. Abstracts. St.-Petersburg, 1996.

5. Егиазарова Э. В. Вектор Шепли в одной комбинаторной игре// Межвузовский сборник научных трудов. Сложные управляемые системы. Москва, 1996.