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

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

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

ШЕВКОПЛЯС Екатерина Викторовна

КООПЕРАТИВНЫЕ ДИФФЕРЕНЦИАЛЬНЫЕ

ИГРЫ

СО СЛУЧАЙНОЙ ПРОДОЛЖИТЕЛЬНОСТЬЮ

Специальность 01.01.09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

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

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

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

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

профессор Петросян Леон Аганесович

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

профессор Гарнаев Андрей Юрьевич

кандидат физико-математических наук Молоствов Виталий Серафимович

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

Защита состоится

Саратовский государственный университет имени Н.Г. Чернышевского (г. Саратов)

I, Л^

2004 г. в

_час. на заседании

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

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

н м

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

2004 г.

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

OjV

л ' -"1 •' > В. Ф. Горьковой

L>J р

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

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

Основа теории кооперативных динамических игр была построена Л.А. Петро-сяном, в развитие теории кооперативных дифференциальных и теории кооперативных многошаговых игр в различное время свой вклад внесли Н.Н. Данилов, Дж. Заккур, В.В. Захаров, Н.А. Зенкевич, В. И. Жуковский, С. Йоргенсен, А.Ф. Клейменов, А.Ф. Кононенко, А.В. Кряжимский, Д.В. Кузютин, В.Н. Лагунов, ОА. Малафеев, В.В. Розен, Дж. А. Филлар, С.В. Чистяков, Д.В.К. Янг, Е.Б. Яновская и др. Естественным подходом к изучению кооперативных динамических игр, как игр дележей, является попытка переноса результатов классической кооперативной теории "однократных" игр Неймана-Моргенштерна. Однако при использовании результатов классической теории необходимо дополнительно исследовать вопрос о динамической и сильно динамической устойчивости полученного решения. Попытки применения динамически неустойчивых принципов оптимальности при решении прикладных задач приводят к нереализуемости таких принципов, поскольку в некоторый момент времени возникают условия, когда соглашения о кооперации могут быть пересмотрены. Это обстоятельство впервые было замечено Л.А. Петросяном в 1977 году. Позднее введенные им термины динамической и сильно динамической устойчивости в англоязычной литературе трансформировались в "состоятельность во времени" и "сильную состоятельность во времени" соответственно. Исследованиям проблемы динамической устойчивости посвящены работы Р. Виллигера, Дж. Заккура, В.В. Захарова, Л.А. Петросяна, Д.В.К. Янга.

Стоит также отметить, что в последнее время большой интерес вызывают модели игр, предусматривающие наличие фактора той или иной неопределенности, которая не может контролироваться игроками, но может ими учитываться при разработке оптимального поведения. Стохастические игры были введены Л.С. Шепли, кооперативные дифференциальные игры при наличии неопределенности изучались В.И. Жуковским, B.C. Молоствовым, А.Ф. Кононенко. Л.А. Петросян и Д.В.К. Янг построили теорию кооперативных дифференциальных игр с неопределенными выигрышами.

j РСС. НАЦИОНАЛЬНАЯ 3 БИБЛИОТЕКА

! ¿гащ

В данной работе под "неопределенностью" понимается случайная продолжительность кооперативной дифференциальной игры. Случайной величиной является момент окончания игры с известной функцией распределения. Отметим, что дифференциальные игры преследования двух лиц со случайной продолжительностью впервые были исследованы в работе Л.А. Петросяна и Н.В. Мурзова "Теоретико-игровые задачи механики" в 1966 г. В рассматриваемой авторами задаче продолжительность игры Т являлась случайной величиной с абсолютно непрерывной функцией распределения Д!) и множеством возможных значений в отрезке [0, Т0]. В этой же работе впервые было выведено уравнение типа Айзекса- Беллмана для заданной таким образом игры преследования.

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

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

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

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

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

Основные положения, выносимые на защиту:

1. Исследованы проблемы динамической и сильной динамической устойчивости в новых классах игр - в кооперативных дифференциальных играх со случайной продолжительностью и в кооперативных многошаговых играх со случайным числом шагов.

2. Получены аналитические выражения для процедуры распределения дележа при динамической устойчивости принципа оптимальности для данных классов игр.

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

4. Получено уравнение Гамильтона-Якоби-Беллмана для нахождения решения кооперативной дифференциальной игры со случайной продолжительности.

Апробация работы. Основные результаты были представлены на семинарах кафедры математической теории игр и статистических решений, на семинарах Центра теории игр, на XXX и XXXI научных конференциях "Процессы управления и устойчивость"(Санкт-Петербург), на 3 международной конференции "Logic, Game Theory and Social Choices"(Италия, University of Sciena), на семинаре Механико-математического факультета Саратовского государственного университета имени Н.Г. Чернышевского (г.Саратов).

По материалам диссертации опубликованы работы [1-7].

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

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

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

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

В § 1.1 определяется кооперативная дифференциальная игра п лиц со случайной продолжительностью Т — to в форме характеристической функции.

Рассмотрим дифференциальную игру п лиц Г(хо) из начального состояния х0 СО случайной продолжительностью Т — ta. Динамика игры задается системой обыкновенных дифференциальных уравнений:

х = /(х,1ц,...,ип), х е Дт, щ е и С сотр/г1, ж(40)=х0.

(1)

Игра начинается в момент to из состояния х. ДЛЯ случайной величины Т (момента окончания игры Г(х„)) задана функция распределения которая определена при Ь € [4о, оо) и удовлетворяет условию нормировки: f = 1.

Функцию "мгновенного" выигрыша игрока г в момент времени г, г 6 [£0,00)1 обозначим как Предполагаем, что являются непрерыв-

ными функциями на Я". Тогда ожидаемый интегральный выигрыш игрока I, 1 = 1,..., п, имеет вид:

гоо Н

Щх0,ии...,ип)= / Н{{х{т))<1ты>0, г = 1 ,...,п. Jto J^a

(2)

Кооперативная форма игры Г(х0) означает, что игроки перед началом игры договариваются об использовании ими таких допустимых программных управлений

что соответствующая им кооперативная траектория х*А) будет максимизировать математическое ожидание общего выигрыша

(предполагаем, что максимум достигается):

tí fel J*°

Траекторию x'{t) и программные у п р а в л е НИЯб У Д е м называть оптимальными. Для простоты дальнейшего изложения будем предполагать, что оптимальная траектория единственна (все сказанное ниже справедливо для каждой оптимальной траектории).

Для каждой коалиции S С N, где N - множество всех игроков, рассмотрим антагонистическую дифференциальную игру Г^^го) между игроками (коалициями) S и N\S из состояния x(to) = х0 СО случайной продолжительностью Т — to и динамикой х = /(х,щ,... ,us,uw\s), где из € П ¡gs-D¿>iíjv\s € Hj^^sDj. Здесь Dt является множеством допустимых стратегий г'-го игрока, в частности, могут быть использованы кусочно-программные стратегии. Выигрыш KS игрока S (максимизирующего игрока) полагается равным сумме выигрышей игроков, входящих в S, выигрыш игрока N\S полагается равным —¡В-о п р о с о существовании значения игры не является тривиальным и зависит от класса рассматриваемых стратегий. Предположим, что значение этой игры существует и обозначим его Val r^ysfxo)- В том случае, когда значения и ís¡5yr\á>(:E($ е существует, мы можем использовать значение maxmin Kt(xo,Us,litros) (либо

если "максимин"не достигается), исходя из свойств су-

^ u«\sies

пераддитивности "максимина". Введем характеристическую функцию V(S,Xo), SCN по следующей формуле:

Игру Гу(а:о) =< N,V{•,X(|) >, где N - множество игроков, У(-,Хо) - характеристическая функция (4), будем называть кооперативной дифференциальной игрой со случайной продолжительностью. Построенная на основе вспомогательной антагонистической игры характеристическая функция удовлетворяет свойству су-

«S "N\S igs

О, 5 = 0;

V(S,z0) = Val Гзл\5(хо), S С N-,

maxEZ=lK¡(xa,u), S = N.

(4)

пераддитивности. Из формулы (3) получаем Т/Г(ЛГ, Жо) — значение игры Гу(яо):

Обозначим как Ь(ха) множество всех дележей в игре Гу(хо): ¿(^о) = {£ = {&} • = ^{¿},Хо), ¿ = Для семейства подыгр Г(а:*(19)),

I? 6 {¿о,оо) вдоль оптимальной траектории х*{£), в которые игроки попадают с вероятностью (1 — ^(т?)), аналогичным образом введем характеристическую функцию V(5,!*($)), Я С ЛГ и множество дележей Ь(х*(19)). Кооперативный вариант подыгры будем обозначать как Гу(ж*(й)).

В игре Гу(®о) выполняется принцип оптимальности (уравнение) Беллмана:

Определение 1 Решением игры или принципом оптимальности (ПО) для семейства подыгр Гу(у) называется точечно-множественное отображение С(у)С.Ь(у), определенное для всех — множество дости-

жимости системы, т.е. множество точек из Я", которые могут быть достигнуты в момент 1? из начального состояния хо в соответствии с системой уравнений (1) при использовании всевозможных допустимых программных управлений

В §1.2 формализуется принцип динамической устойчивости решения кооперативной дифференциальной игры п лиц со случайной продолжительностью Т — Хо

Предположим, что перед началом игры игроки договариваются об использовании ими некоторого принципа оптимальности (ПО) С(хо) и рассчитывают получить некоторый соответствующий ему дележ 6 С(хо). Вектор-функцию 7(0 = {7»(0 при помощи которой дележ {&} может быть представлен виде

6 = Г [* ъ(т)ЛгЛР(0,

•/¡О Jtо

(6)

будем называть процедурой распределения дележа (ПРД).

Определение 2 Пусть С(:с*($)) 5^0, VI? € [¿о,оо). Принцип оптимальностиС(го) называется динамически устойчивым принципом оптимальности (ДУПО), если

для любого дележа существует ПРД {7;М>0}> -г € [к, со), такая, что

вектор (ожидаемый дележ в игре вычисленный по формуле

принадлежит тому же принципу оптимальности, т.е. € С(х*{в)).

Согласно данному определению, при динамической устойчивости С(хц), любой

дележ имеет следующий вид:

5 = сн{0) + (1 - Г(0)) Ц* ъ(т)Лт +, (8)

где а,(19).- математическое ожидание выигрыша г-го игрока на промежутке оч(#) = ^ Последнее слагаемое в (8) представляет собой мате-

матическое ожидание выигрыша игрока в подыгре Гу(х*(0)) при условии, что игра не закончилась до момента д. Здесь мы под выигрышем в подыгре подразумеваем ожидаемый дележ $ и уже накопленную к моменту ■д сумму Предлагаемый способ реализации дележа обладает важным свойством: в каждый момент времени игроки могут рассчитывать на реализацию одного и того же принципа оптимальности в текущей подыгре и, следовательно, не имеют оснований для нарушения ранее принятого соглашения. Механизмом, осуществляющим выполнение такого принципа, является выбор ПРД {7,(0}, которая регулирует распределение доходов игроков во времени.

Предполагая существование Р'{д) и ($)', г = 1,.. -, п, и дифференцируя (8) по верхнему пределу получаем формулу для вычисления ПРД:

= -<£)'■ (9)

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

В § 1.3 рассматривается модель игры, в которой случайная величина Т имеет непрерывную функцию распределения на интервале [¿а,Т/), а в момент времени Т/ имеет разрыв (скачок) р. Считаем, что после момента Т/ игра продолжения

не имеет. Условия нормировки могут быть сформулированы следующим образом: Т1

Определения выигрышей игроков, процедуры распределения дележа, характеристической функции множества дележей и

принципа оптимальности С(хо) С Ь{хо) аналогичны сформулированным в § 1.1. Показывается, что при динамической устойчивости С(хо) каждый дележ {&} € С(жо) представим в следующем виде:

(10)

Получено интегоальное упавнение ттля ПРЯ {т.МТ:

рП*) + РП*)

Г'

■ у 7Ат)йт ■■

9(1

В § 1.4 предлагается конструктивный способ улучшения или регуляризации классических принципов оптимальности, не являющихся динамически устойчивыми в общем случае. Введем функцию У^.Хо) по формуле:

т*<,)=тх-м)^сж

(12)

Заметим, что У(Мо) = 0, У(ЛТ,х0) = У(Л>0), У^и^хо^У^ь^оНУ^,^).

Первые два свойства проверяются непосредственно, для доказательства третьего используется супераддитивность функции У(5,1о)- Таким образом, функция У(5, Яс) удовлетворяет классическим свойствам характеристической функции. Аналогичным образом вводится характеристическая функция У(5, для текущей подыгры, начинающейся в момент 1?. Фактически, далее мы будем рассматривать регуляризованную кооперативную игру ГУ(:Го). Предположим, что С(х*(1?)) во всех подыграх. Определим для некоторого селектора е С{х*{$)), "д € [¿о, оо] вектор-функцию по формуле:

(13)

При помощи новой, неотрицательной ПРД (13) сформируем следующий вектор

/■оо /Ч

1=1 / а

■/«О -/«О

У(М,х'(т))

¿т ¿р(г).

(14)

Доказывается, что вектор с компонентами (14) является дележом в игре с новой характеристической функцией У{Б,хо) (12). Кроме того, выплаты, сделанные игрокам до момента £ оо), согласно ПРД (13) являются осуществимыми, т.е. сумма выплат равна заработанному к этому моменту общему выигрышу игроков. Рассмотрим следующее подмножество множества дележей Ь(хц) (построенного для новой характеристической функции

Введенное таким образом множество С{хо) С Ь(хо) назовем регуляризованным принципом оптимальности или регуляризованным решением игры Гу(хо) (как было указано выше, фактически здесь уже рассматривается игра Гр(хо)).

Теорема 1 Множество С(хо) является динамически устойчивым принципом оптимальности.

В §1.5 получено уравнение Гамильтона-Якоби-Беллмана, с помощью которого можно находить значение кооперативной дифференциальной игры со случайной продолжительностью. Обозначим сумму мгновенных выигрышей игроков в момент < к Н(х({)) = /г,(х(()). >бщем случае будем рассматривать Предположим, что случайная величина Т является абсолютно непрерывной, т.е. имеет плотность Будем искать решение не для одной

оптимизационной задачи (4) при ограничениях (1), а для целого семейства задач следующего вида:

I Н(х(т),и(т))(1пИ, (16)

где вычисляется согласно уравнению движения (1), Пусть

— функция Беллмана для данной оптимизационной задачи:

Ш(х, д) = шах(4) £ Н{х(т)Мт)¥^. (17)

Тогда максимуму функционала (3) в игре будет соответствовать значение

функции Беллмана при Получено

следующее функциональное уравнение (уравнение Гамильтона-Якоби-Беллмана):

уоо

тах / /^(4) 4 J■в

Для игры с показательным распределением случайного момента

ее окончания Т имеем следующий вид уравнения (18):

Данное уравнение совпало с полученным ранее уравнением Гамильтона-Якоби-Беллмана для "одномерной" оптимизационной задачи с дисконтированием е-'1'1"'0?

Предложенные в параграфах § 1.4, § 1.5 методы нахождения оптимальной траектории и построения динамически устойчивого принципа оптимальности при помощи новой ПРД, приводятся в форме алгоритма в параграфе §1.6. В §1.7 изучается вопрос регуляризации вектора Шепли и С-ядра.

Теорема 2 Пусть С(хо) — С-ядро. Необходимыми условиями динамической устойчивости С-ядра С(ато) являются С(г*($)) 5^0, € [¿2,гс>); ) существование такой ПРД 7(г), г € [¿о,оо) для любого дележа £ 6 С(хо) , что в любой момент времени для любого подмножества выполняются следующие

ограничения:

У{Ы,х0) - \ Б,хй) - (1 - > Г Р ъ{т)Лг*Р®+

,65 Ч-По •'(о

+(1 - />(0)) I* 7> + (1 - \ 5, !*(«?)) - У(ЛГ,Х*0?))

Теорема 3 Пусть изначально выбранный игроками принцип оптимальности С(хо) является С-ядром, которое не является динамически устойчивым. Рассмотрим У(5,1о) и С(хц,Б)— новую характеристическую функцию и соответствующее ей С-ядро. Согласно формуле (15) определим регуляризованный принцип оптимальности С(хо) на основе С-ядра С(хо). Справедливо следующее включение:

С{¡го) С С(х0).

Теорема 4 Вектор Шепли, вычисленный для характеристической функции является динамически устойчивым.

В § 1.8 изучается свойство сильной динамической устойчивости принципов оптимальности, которое является усилением свойства динамической устойчивости.

Определение 3 Принцип оптимальности С{хо) (или решение игры Гу(:го)) называется сильно динамически устойчивым принципом оптимальности (СДУПО),

>

если для любого дележа £ € б(хо) существует ПРД {71(т)^0}> т € ^о>о°)> такая, что вектор определенный по следующей формуле

£ = ££ + (1 - *•(*)) Т.М^г + , (20)

принадлежит ¿7(х0) для любого селектора

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

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

В § 1.11 формализуются кооперативные дифференциальные игры со случайной продолжительностью для случая дисконтирования выигрышей игроков. Игра происходит аналогично описанной в § 1.1 игре с поправкой на ди-

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

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

В § 2.1 кооперативная многошаговая игра со случайным числом шагов определяется в форме характеристической функции. Рассмотрим древовидный граф й =

который может быть конечным (обозначим как ) или бесконечным Пусть ¿Т - множество всех вершин, а М — отображение, заданное на множестве Z^.

Для бесконечного графа

дополнительно

потребуем, чтобы множество Мг было конечно для любой вершины I- Пусть в каждой вершине гб2 графа О задана одновременная игра п лиц в нормальной форме — множество игроков,

одинаковое для всех

— множество стратегий (конечное множество) I-г о игрока (г е ЛГ) в вершине— функция выигрыша игрока

г (г б N, и* € Щ). Набор стратегий и1 = (ы^, и' е Щ, { е К, назовем

ситуацией в игре Г(г). Функции выигрышей игроков в одновременной игре Г(я) предполагаются неотрицательными: Щ(и{, ^ 0. Переход из одной вершины

графа гк в другую г^-ц € Мгк зависит от реализовавшейся ситуации на предыдущем шаге, то есть динамика игры задана рекуррентно:

2*+1= /(*, и*"), (21)

где и'к — ситуация, реализовавшаяся на шаге к, к = 0,1,...,/ — 1 для конечного графа (Мг, = 0) и к — 0,1,... для игры на бесконечном графе С?2- Число шагов в игре является целочисленной случайной величиной т, для которой считаем заданным распределение вероятностей 0 < Р} < 1, = Здесь р^ — вероятность того, что игра закончится на 7-ом шаге. Для бесконечного графа бг суммирование производится до бесконечности, то есть Х^оР^' = Далее везде при суммировании до I мы будем подразумевать как конечную сумму в случае игры на конечном графе, так и бесконечную (для бесконечного варианта), т.е. ряд, который будем предполагать сходящимся.

Многошаговая игра С?(го) со случайным числом шагов задается следующим образом: в вершине го (т.е. на нулевом шаге) графа С осуществляется одновременная игра Г(го), в которой реализуется сит У^цир, я . е е игра либо прекращается с вероятностью ро, либо переходит в другую вершину графа г £ М1а соответственно с заданной динамикой (21): = /(го,и20) € М(го). На к-ом шаге игры Ст(-го), в вершине 2* графа (7, происходит одновременная игра

и реализуется ситуация далее игра либо прекращается с вероятностью р*, либо переходит в другую вершину графа й: = /(2^,иг*). На последнем шаге I игры на конечном графе 0\, игра заканчивается с вероятностью рь при этом в вершине (Мч = 0) разыгрывается одновременная игра Г(2|) (иначе игра заканчивается в одной из предшествующей вершин При игре на бесконечном графе процесс переходов из

вершины в вершину соответственно с (21) является бесконечным. По аналогии с терминологией главы I будем называть реализовавшийся путь г = гд,...,21 траекторией игры (для игры на бесконечном графе

Кооперативная форма игры 6(20) предполагает, что игроки перед началом игры договариваются об использовании ими таких стратегий в каждой

игре Г(г), что соответствующая им т р а е и м и -

зировала бы математическое ожидание суммарного выигрыша всех игроков:

Для случая I = оо здесь и далее предполагаем, что на параметры задачи (вероятности p и выигрыши h) наложены ограничения, обеспечивающие сходимость соответствующих рядов. Траекторию z будем далее называть оптимальной. Предположим, что максимум в (22) достигается. Также для простоты будем полагать, что оптимальная траектория единственна. Дальнейшие рассуждения будут справедливы для любой оптимальной траектории.

Как и в главе I, введем характеристическую функцию V(5,.zo),5 С N следующим образом: - значение антагонистической игры Gs,ff\s(zo) (если оно существует). В том случае, когда значения антагонистической игры не существует, в качестве будем использовать "максимин": V(S,z0) — maxmin £L=o (Х^о^гЧ"2*))?™. где Us —

определяется аналогично. Для значения игры G„(za) выполняется принцип оптимальности (уравнение) Беллмана:

В § 2.2 исследуется проблема динамической устойчивости в игре С„(го).

Определение 4 Пусть f = {£¡} 6 C(zq). Если компоненты дележа представимы в виде

то вектор-функция {АО^ь)}*^'"^ называется процедурой распределения дележа (ПРД) в игре GV(z0).

Далее для уменьшения громоздкости будем использовать обозначение - выплата г'-му игроку на к-ом шаге.

Предположим, что во всех подыграх

Определение 5 Принцип оптимальности С(Иц) называется динамически устойчивым (ДУПО), если для любого дележа С(2ц) существует процедура распределения дележа {/?,'} ^ 0, в € {0,1,...,/}, такая, что вектор = {£*}, вычисленный для подыгры С?у{.гл) по формуле

(23)

принадлежит тому же принципу оптимальности

в подыгре

Данному определению эквивалентно следующее представление любого дележа в случае динамической устойчивости

С» = а.00 + (1 - &)£>*+£). где оч(я) = ЕЕ^Р- (24)

Получено аналитическое выражение для ПРД:

(25)

В § 2 3 определяется новая характеристическая функция, которая в дальнейшем будет использоваться в качестве характеристической функции регуляризованной игры:

I то

N.

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

В § 2 4 проводится регуляризация классических принципов оптимальности при помощи новой ПРД, которая обеспечивает динамическую устойчивость решений для данного класса игр Предположим, что С(г*) ф% во всех подыграх Определим для {£*} € С(г/с),г = 1,...,п, к = 0,...,1, в е к т о^рп о формуле:

I т

, > „л:-1гп

(26)

6 "¿¿г Рт-

Доказывается, что вектор {&}, построенный по формуле (26), является дележом в игре - некоторое расширение игры

Определим

Фактически, мы вводим новую ПРД ¡} = {/З^}^!,'1',,/, /^>0, обеспечивающую динамическую устойчивость

К = (Г

(27)

На последнем шаге I, в случае игры на конечном графе О,, выплаты игрокам назначаются прежние: Щ = Уг = 1 ,...,п.

Теорема 5 Множество С{го) представляет собой динамически устойчивый принцип оптимальности (ДУПО) в регуляризованной игре Су(гц).

Заметим, что введенная по формуле (27) ПРД обладает свойством осуществимости таких выплат - суммарные выплаты игрокам на каждом шаге к в точности равны заработанной ими сумме.

В § 2 5 изучается вопрос регуляризации вектора Шепли и С-ядра для данного класса игр. Утверждения и доказательства теорем данного параграфа являются дискретным вариантом теорем раздела § 1.7. В §2.6 приводится алгоритм регуляризации вектора Шепли на основе результатов параграфов § 2.4, § 2.5.

В §2.7 формулируется понятие сильной динамической устойчивости, аналогичное определению сильной динамической устойчивости, данному в § 1.8. В § 2.8 предлагается способ построения новых принципов оптимальности, обладающих свойством сильно динамической устойчивости. При этом используется регуляризация с помощью ПРД (27) на основе "составных" селекторов, т.е. до некоторого

1 используется селектор

а начиная с шага

,5 некоторый другой селектор = $,...,1. Если дележ в ПО единственный,

то свойства динамической и сильно динамической устойчивости являются эквивалентными.

В § 2.9 приводится пример динамически устойчивого решения в многошаговой игре двух лиц. Регуляризация вектора Шепли представлена в примере §2.10.

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

шага ,

ПО ТЕМЕ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ СЛЕДУЮЩИЕ

РАБОТЫ:

1. Петросян Л.А., Баранова Е.М., Шевкопляс Е.В. Многошаговые кооперативные игры со случайной продолжительностью. Труды Института Математики и Механики уральского отделения РАН, т.10, вып. 2, 2004, стр. 116-130.

2. Petrosjan L.A., Shevkoplyas E.V. Cooperative Solutions for Games with Random Duration. Game Theory and Applications, Volume IX. Nova Science Publishers, 2003, pp.125-139.

3. Petrosjan L.A., Shevkoplyas E.V. Time-consistency Problem in Differential Cooperative Games with Random Duration. Extended abstracts. Third International Conference "Logic, Game Theory and Social Choices". Italy, University of Sciena, 2003, pp.164-171.

4. Petrosjan L.A., Shevkoplyas E.V. Cooperation Under Condition on Random Duration. Proc. 4 ISDG Workshop. Germany, Hannover University, 2003, pp.1-10.

5. Петросян Л.А., Шевкопляс Е.В. Кооперативные дифференциальные игры со случайной продолжительностью. "Вестник СПбГУ1', издание СПбГУ, 2001, серия 4, выпуск 1, стр. 21-28.

6. Шевкопляс Е.В. "Кооперативные многошаговые игры со случайным числом шагов. Труды XXXI научной конференции "Процессы управления и устойчивость". СПбГУ, 2000, стр. 501-504.

7. Шевкопляс Е.В. Кооперативные дифференциальные игры со случайной продолжительностью. Труды XXX научной конференции "Процессы управления и устойчивость". СПбГУ, 1999, стр. 547-551.

Подписано к печати 11.10.2004 г. Формат бумаги 60X84 1/16. Бумага офсетная. Печать ризографическая. Объем 1 усл. п. л. Тираж 100 экз. Заказ 3364. Отпечатано в отделе оперативной полиграфии НИИХ СПбГУ с оригинал-макета заказчика. 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 26.

* 1 9 s 3 3

Введение

1 Кооперативные дифференциальные игры со случайной продолжительностью.

§1.1 Определение кооперативной дифференциальной игры Гу(жо) в форме характеристической функции.

§ 1.2 Принцип динамической устойчивости в игре Гу(жо) • • • •

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

§ 1.4 Регуляризованные динамически устойчивые принципы оптимальности

§1.5 Уравнение Гамильтона-Якоби-Беллмана.

§ 1.6 Алгоритм регуляризации принципов оптимальности в игре

Г уЫ.

§ 1.7 Регуляризация С-ядра и вектора Шепли в игре Гу(ж0) • •

§ 1.8 Сильно динамически устойчивые принципы оптимальности.

§ 1.9 Сильная динамическая устойчивость регуляризованных принципов оптимальности

§ 1.10 Пример регуляризации вектора Шепли.

§1.11 Кооперативные игры с дисконтированными выигрышами

2 Многошаговые кооперативные игры со случайным числом шагов.

§2.1 Определение многошаговой кооперативной игры Gy{z$) в форме характеристической функции.

§ 2.2 Принцип динамической устойчивости в игре Gy (zo)

§ 2.3 Введение новой характеристической функции

§ 2.4 Регуляризованные динамически устойчивые принципы оптимальности

§ 2.5 Регуляризация вектора Шепли и С-ядра в игре Gy(zo)

§ 2.6 Алгоритм регуляризации вектора Шепли в игре Gy(zo)

§2.7 Сильно динамически устойчивые принципы оптимальности

§2.8 Регуляризованные сильно динамически устойчивые принципы оптимальности.

§2.9 Пример динамически устойчивого решения в кооперативной многошаговой игре двух лиц.

§2.10 Пример регуляризации вектора Шепли в кооперативной многошаговой игре двух лиц.

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

Это обстоятельство впервые было замечено JI.A. Петросяном в 1977 году [25]. Позднее введенные им термины динамической и сильно динамической устойчивости в англоязычной литературе трансформировались в "состоятельность во времени "и "сильную состоятельность во времени "соответственно. Исследованиям проблемы динамической устойчивости посвящены работы [9], [23], [24], [29] и др.

В настоящее время одним из наиболее бурно развивающихся разделов теории игр являются кооперативные дифференциальные игры [4], [13], [15], [39]. Также следует отметить перспективное направление, связанное с развитием теории стохастических игр, введенных Шепли в 1953 году [56], а также дифференциальных игр при наличии неопределенности [11], [12] , [14], [33], [49], поскольку использование при моделировании фактора той или иной неопределенности позволяет наиболее адекватно описывать самые разнообразные процессы, происходящие в экономике, экологии, менеджменте, торговле, при принятии решений в области международных отношений, систем безопасности и пр!

В данной работе вводится новый класс дифференциальных игр — кооперативные дифференциальные игры п лиц со случайной продолжительностью Т — to. Случайность времени существования любого организма, системы, процесса заложена в окружающую человека реальность, поэтому спектр приложений кооперативных дифференциальных игр со случайной продолжительностью может быть велик. Отметим, что в работе J1.A. Петросяна и Н.В. Мурзова "Теоретико-игровые задачи механики" в 1966 г. [30] впервые были исследованы дифференциальные игры преследования двух лиц со случайной продолжительностью. В рассматриваемой авторами задаче продолжительность игры Т являлась случайной величиной с абсолютно непрерывной функцией распределения F(t) и множеством возможных значений в отрезке [0,То]. В этой же работе впервые было выведено уравнение типа Айзекса-Беллмана для заданной таким образом игры преследования.

В кооперативных дифференциальных играх супераддитивность характеристической функции не обеспечивает сохранение кооперации между игроками во время всей игры.Предположим, что перед началом игры игроки договариваются об использовании ими некоторого принципа оптимальности С{хо) и по окончанию игры рассчитывают получить некоторый соответствующий ему дележ £ Е С{хо). Развитию игры во времени соответствует движение вдоль оптимальной траектории #*(£), на которой по определению игроки получают наибольший ожидаемый дележ. Однако движение вдоль оптимальной траектории еще не обеспечивает, сохранение кооперации. Действительно, при движении вдоль x*(t) игроки попадают в подыгры с текущими начальными состояниями, в которых один и тот же игрок имеет различные возможности. Следовательно, в некоторый момент -д может возникнуть ситуация, когда решение текущей игры будет неоптимальным в смысле первоначально выбранного принципа оптимальности С{х$). В таком случае перед игроками встанет вопрос о целесообразности придерживаться далее намеченного перед началом игры соглашения действовать "совместно оптимально". Последнее будет означать динамическую неустойчивость принципа оптимальности С{хо) и, соответственно, самого движения по траектории x*(t). Следовательно, проблема динамической устойчивости является очень важной для кооперативных дифференциальных игр со случайной продолжительностью. Разрешить данную проблему предлагается путем введения специальных выплат (процедуры распределения дележа), которые будут регулировать распределение общего выигрыша во времени так, чтобы ни в какой момент времени t G [£0, сю) ни у кого из игроков не возникло желание уклониться от первоначального соглашения.

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

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

Научная новизна работы заключается в том, что в ней:

1. введены новые классы кооперативных динамических игр — кооперативные дифференциальные игры со случайной продолжительностью и кооперативные многошаговые игры со случайным числом шагов,

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

3. получено и обосновано уравнение Гамильтона-Якоби-Беллмана для кооперативных дифференциальных игр со случайной продолжительностью.

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

Основные положения, выносимые на защиту:

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

2. Получено аналитическое выражение для процедуры распределения дележа при динамической устойчивости принципа оптимальности.

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

4. Получено уравнение Беллмана-Гамильтона-Якоби для нахождения значения кооперативной дифференциальной игры со случайной продолжительности .

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

Апробация работы. Основные результаты были представлены на семинарах кафедры математической теории игр и статистических решений, на семинарах Центра теории игр, на XXX и XXXI научных конференциях "Процессы управления и устойчивость" (Санкт-Петербург, 1999, 2000 гг.), на 3 международной конференции "Logic, Game Theory and Social Choices" (Италия, University of Sciena, 2003), на семинаре Механико-математического факультета Саратовского государственного университета имени Н.Г. Чернышевского (Саратов, 2004). 1

По материалам диссертации опубликованы работы [28], [36], [37], [32], [53], [54], [55].

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

Заключение

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

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

3. Получено уравнение Беллмана-Гамильтона-Якоби для функционала, являющегося математическим ожиданием совместного выигрыша игроков.

4. Рассмотрены кооперативные многошаговые игры со случайным числом шагов. Введены понятия процедуры распределения дележа, динамической и сильно динамической устойчивости принципа оптиv мальности. Приведен алгоритм регуляризации принципов оптимальности для данного класса игр.

1. Айзеке Р. Дифференциальные игры. М., 1967.

2. Беллман Р. Динамическое программирование. М., 1960.

3. Болтянский В. Г. Математические методы оптимального управления. Москва, "Наука", 1969.

4. Вайсборд Э. М.,Жуковский В. И. Введение в дифференциальные игры нескольких лиц и их приложения. М.: "Советское радио", 1980.

5. Вентцелъ Е. С.,Овчаров Л. А. Теория вероятностей М.: "Наука", 1969.

6. Воробьев Н. Н. Основы теории игр. Бескоалиционные игры. М: Наука, 1984.

7. Воробьев Н. Н. Теория игр для экономистов-кибернетиков. М.: На• ука, 1985.

8. Горелик В. А., Кононенко А. Ф. Теоретико-игровые модели принятия решений в эколого-экономических системах. М., 1982.

9. Данилов Н.Н. Кооперативные многошаговые игры с побочными платежами // Изв. Вузов. Мат. 1991. №2. С.33-42.

10. Данилов В.И. Лекции по теории игр. М: РЭШ, 2002.

11. Жуковский В. И. Кооперативные игры при неопределенности и их приложения. М.: Эдиториал УРСС. 1999, 334 с.

12. Жуковский В. И., Молоствов В. С. Многокритериальная оптимизация систем в условиях неполной информации. М.: Международный научно-исследовательский институт проблем управления, 1990, 112 с.

13. Клейменов А.Ф. Неантагонистические дифференциальные игры. Екатеринбург: Наука, 1993, 184 с.

14. Кононенко А. Ф., Халезов А. Д., Чумаков В. В. Принятие решений в условиях неопределенности. М.: ВЦ АН СССР, 1991. 197 с.

15. Красовский Н. Н., Субботин А. И. Позиционные дифференциальные игры. М., 1974.

16. Куммер Вернд. Игры на графах. М: Мир, 1982.

17. Лагунов В. Н., Сушкин В. В. Многошаговые позиционные игры N лиц. Тверь, 1993.

18. Мулен Э. Теория игр с примерами из математической экономики. М: Мир, 1985.

19. Нейман В. фон, Моргенштерн О. Теория игр и экономическое поведение. М: Наука, 1970.

20. Петросян Л. А., Данилов Н. Н. Устойчивость решений в неантагонистических дифференциальных играх с трансферабельными выигрышами // Вестник Ленинградского университета. 1979. №1

21. Петросян Л. А., Захаров В. В. Математические модели в экологии. СПб: Изд. СПбГУ, 1996.

22. Петросян Л. А., Зенкевич П. А., Семина Е. А. Теория игр. М: Высш. шк., 1998.

23. Петросян Л. А., Кузютин Д. В. Игры в развернутой форме: оптимальность и устойчивость. СПб: Изд. СПбГУ, 2000.

24. Петросян Л. А., Томский Г. В. Динамические игры и их приложения. Л: Изд. ЛГУ, 1982.

25. Петросян Л. А. Устойчивость решений в дифференциальных играх со многими участниками. Вестник Ленинградского университета, 1977, N 19, Вып. 4.

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

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

28. Петросян Л. А., Баранова Е. М., Шевкопляс Е. В. Многошаговые кооперативные игры со случайной продолжительностью. Труды Института Математики и Механики уральского отделения РАН, т.10, в.2, 2004, стр. 116 130.

29. Петросян Л. А., Данилов Н. Н. Кооперативные дифференциальные игры и их приложения. Томск, 1985.

30. Петросяп JI. А., Мурзов Н. В. Теоретико-игровые задачи механики. Литовский математический сборник, вып.VI, 1966.

31. Петросян Л. А., Савищенко Н. И. Теоретико-игровая модель загрязнения воздушного бассейна. СПбГУ, 1997.

32. Петросян Л .А., Шевкопляс Е. В. Кооперативные дифференциальные игры со случайной продолжительностью. "Вестник СПбГУ", издание СПбГУ, 2001, серия 4, выпуск 1, стр. 21-28.

33. Петросян Л. А., Янг В. К. Кооперативные дифференциальные игры с неопределенными выигрышами. "Ветник СпбГУ", выпуск 3, 2000.

34. Феллер В. Введение в теорию вероятностей и ее приложения, т.1, 2. М.: "Мир", 1967.

35. Розен В. В. Математические модели принятия решений в экономике. М.: Книжный дом "Университет", 2002.

36. Шевкопляс Е .В. Кооперативные дифференциальные игры со случайной продолжительностью.//Труды XXX научной конференции "Процессы управления и устойчивость". СПбГУ, 1999, стр. 547-551.

37. Шевкопляс Е .В. Кооперативные многошаговые игры со случайным числом шагов". //Труды XXXI научной конференции "Процессы управления и устойчивость". СПбГУ, 2000, стр. 501-504.

38. Янг Л. Лекции по вариационному исчислению и теории оптимального управления. Москва, "Мир", 1974.

39. E.J. Dockner, S. Jorgensen, N. van Long, G. Sorger. Differential Games in Economics and Management Science. Cambridge University Press, 2000.

40. Dolchetta I. C. Hamilton-Jacobi-Bellman Equation and Optimal Control. International Series of Numerical Mathematics. Vol. 124. 1998, Birkhauser Verlag, Bazel. pp. 121-128.

41. Fudenberg D., Tirole J. Game theory. Cambridge: MIT press, 1991.

42. Germain, M., Toint, P., Tulkens, H., de Zeeuw, A.J. Transfers to Sustain Core-theoretic Cooperation in International Stock Pollutant Control. CLIMNEG, Working Paper No. 6, 1998.

43. Haurie, A., Zaccour, G. Differential Game Models of Global Environment Management. Annals of the International Society of Dynamic Games 2, 3-24, 1995.

44. Kaitala, V., Pohjola, M. Sustainable International Agreements on Green House Warming: a Game Theory Study. Annals of the International Society of Dynamic Games 2, 67-88, 1995.

45. Filar, G. A. and L. A. Petrosjan. Dynamic Cooperative Games. International Game Theory Review. 2000, Vol. 2, No. 1, pp. 47-66.

46. Owen G. Game Theory. W. B. Saunders Company. Philadelphia-London-Toronto. 1986.

47. Straffin P. D. Game Theory and Strategy. Washington. Washington: The Math. Associat. America, 1993.

48. Villiger R., Petrosjan L.A. Construction of Time-Consistent Imputations in Differential Games // Proc. 2nd International Conference "Logic, Game Theory and Social Choice". 2001.

49. Zhukovsky V.I., Molostvov V.S., and K.S.Vaisman. Non-Cooperative Games under Uncertainity. Game Theory and Applications. Eds. by L.A.Petrosjan and V.V.Mazalov, Vol. III.

50. Kleimenov A. F., Kryazhimskii A. V. Normal Behavior, Altruism and Aggression in Cooperative Game Dynamics, IIASA, IR-98-076, Laxenburg, 1998, 48 p.

51. Petrosjan L. A., Zaccour G. Time-consistent Shapley Value Allocation of Pollution Cost Reduction, Journal of Economic Dynamics and Control, Vol. 27, 381-398, 2003.

52. Petrosjan L. A. The Shapley Value for Differential Games, New Trends in Dynamic Games and Applications, Geert Olsder eds., Birkhauser, 409-417, 1995.

53. Petrosjan L. A., Shevkoplyas E. V. Cooperation under condition on random duration. Proc. 4 ISDG Workshop.Germany, Hannover University, 2003. pp.1-10.

54. Petrosjan L. A., Shevkoplyas E. V. Cooperative Solutions for Games with Random Duration. Game Theory and Applications, Volume IX. Nova Science Publishers, 2003. pp. 125-139. 1.

55. Shapley L.S. Stochastic games // Proc. Nat. Acad. Sci. U.S.A. 1953. V. 39, pp. 1095-1100.

56. Shapley L.S. A Value for n-person Games. // Contributions to the Theory of Games II. Princeton: Princeton University Press, 1953, pp.307-317.