Квазисовершенные принципы оптимальности в классических кооперативных играх тема автореферата и диссертации по математике, 01.01.09 ВАК РФ
|
Васецов, Матвей Евгеньевич
АВТОР
|
||||
|
кандидата физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Санкт-Петербург
МЕСТО ЗАЩИТЫ
|
||||
|
1998
ГОД ЗАЩИТЫ
|
|
01.01.09
КОД ВАК РФ
|
||
|
|
||||
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
г в оа
. „ дьи498
На правах рукописи
ВАСЕЦОВ Матвей Евгеньевич
КВАЗИСОВЕРШЕННЫЕ ПРИНЦИПЫ ОПТИМАЛЬНОСТИ В КЛАССИЧЕСКИХ КООПЕРАТИВНЫХ ИГРАХ
Специальность 01.01.09 — математическая кибернетика
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата физико-математических наук
Санкт-Петербург — 1998
Работа выполнена на кафедре математической статистики, теории надежности н массового обслуживания факультета приклад-нон математики - процессов управления Санкт-Петербургского государственного университета.
Научный руководитель: - доктор физико-математических наук,
профессор C.B. Чистяков.
Официальные оппоненты: - доктор физико-математических наук
А.Ю. Гарнаев; - кандидат физико-математических наук
C.JI. Псмерскии.
Ведущая организация: Институт математики и механики Уральского отделения РАН.
Защита диссертации состоится " ^ 1998г.
в Afe часов на заседании диссертационного совета К-063.57.16 по защите диссертаций на соискание ученой степени кандидата физико-математических наук в Санкт-Петербургском государственном университете по адресу: 199004, г. Санкт-Петербург, 10-линия.В.О., д.ЗЗ, ауд.
С диссертацией можно ознакомиться в библиотеке СПбГУ им. A.M. Горького по адресу: 199034, г. Санкт-Петербург, Университетская наб., 7/9.
Автореферат разослан " û-? " 1998г.
Ученый секретарь диссертационного совета, доктор физико-математических наук,
В.Ф, Горьковой
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. Со времени своего возникновения и до недавнего времени теория класс ических кооперативных игр развивалась как статическая теория, т. е. как тикая теория, в которой принятие решения о дележе или о распределении общего блага рассматривалось как одноактное действие. Последнее, однако, не всегда соответствует реальности, в которой окончательный компромисс о распределении благ достигается не; мгновенно, а является исходом сложного многошагового процесса согласования интересов и взаимных уступок заинтересованных сторон. Возможно, имея это в виду, основоположники классической кооперативной теории игр Дж. фон Нейман и О. Моргенштсрн в своей монографии "Теория игр и экономическое поведение1' писали: "Несомненно, динамическая теория была бы более полной и поэтому более предпочтительной" [3, с. 70].
На необходимость моделирования и анализа динамического процесса достижения согласия, по вопросу распределения некоторого блага, указывалось и в работе Дж. Быокенена "Границы свободы" [1], в которой с точки зрения теории общественного выбора была изложена концептуальная схема такого процесса.
По-видимому, впервые определенный подход к построению динамической теории классических кооперативных игр был предложен в работе C.B. Чистякова [5], где окончательный, совершенный компромисс рассматривался как предел итеративной последовательности, моделирующей в соответствии с набранным принципом оптимальности, или, иначе, принципом достижения окончательного компромисса, многошаговый процесс принятия решения о распределении общего блага. При этом итерационный оператор отолсдествлялся с соответствующим принципом оптимальности, а в случае сходимости указанной последовательности к однозначному решению, т. е. к распределению или дележу, этот оператор назывался финально совершенным.
При рассмотрении в качестве модели процесса согласования интересов определенной итеративной последовательности естественно возникает вопрос об изучении характера её сходимости, исследование которого и определяет выбор темы диссертационной работы. В связи с этим наиболее актуальным является вопрос о том, не бу-
дет ли некоторая степень данного финально совершенного оператора значения совершенным оператором значения, т.е. таким оператором, который каждой игре ставит в соответствие однозначное ее решение. Постановка последнего вопроса ■— вопроса о квазисовер-шенностп принципа оптимальности — предполагает исследование природы определения изучаемого оператора.
Цель работы заключается в развитии упомянутой выше динамической теории классических кооперативных игр. Предлагаемое развитие, в частности, состоит в распространении этой теории с задачи дележа на более общую задачу распределения, а в основном — в изучении вопроса о квазисовершенности параметрического семейства принципов оптимальности типа принципа минимакса [5].
Научная новизна. Свойство квазисовершенности принципов оптимальности, как и вопрос распространения упомянутой выше динамической теории с задачи дележа на задачу распределения, изучается впервые. Основные результаты, полученные в диссертации, являются новыми.
Теоретическая и практическая ценность полученных результатов, с одной стороны, состоит в том, что они расширяют сферу возможных приложений динамической теории классических кооперативных игр, а с другой стороны, — в том, что установленное свойство квазисовершенности рассматриваемых принципов оптимальности, позволяет предложить эффективные алгоритмы поиска соответствующих совершенных компромиссов на основе решения конечного числа задач линейного программирования. В свою очередь, это составляет естественную основу для исследования разнообразных распределительных задач экономики.
Апробация работы. Результаты исследований, представленных в работе, докладывались на международной научной конференции "Game Theory and Economics" (Санкт-Петербург, 1996г.), на XXIV научной конференции факультета прикладной математики-процессов управления СПбГУ "Процессы управления и устойчивость" (Санкт-Петербург, 1998г.), на семинаре в Институте математики и механики Уральского отделения РАН (Екатеринбург, 1998г.), на городском семинаре по теории игр под руководством проф. JI.A. Петросяна (Санкт-Петербург), на семинаре лаборатории теории игр и принятия решений Санкт-Петербургского экономико-
математического института РАН (Санкт-Петербург, 1998г.), а также на семинарах кафедры математической статистики, теории надежности и массового обслуживания факультета прикладной математики - процессов управления Санкт-Петербургского государственного университета.
Диссертация выполнена при поддержке Российского фонда фундаментальных исследований и проводилась по проекту №98-0101056.
Публикации. Результаты диссертации нашли отражение в работах [7] - [10], приводимых в библиографическом списке цитируемой литературы в конце реферата.
Структура работы. Диссертация состоит из введения, трех глав, заключения, библиографического списка использованной литературы из 70 наименований и имеет общий объем 123 страницы. Параграфы каждой из глав имеют свою нумерацию, при этом первая цифра означает номер главы, а вторая — номер параграфа. Нумерация пунктов параграфа состоит из трех чисел, из которых первые две совпадают с соответствующими номерами главы и параграфа.
В автореферате представлены только основные утверждения и определения из диссертации, нумерация которых совпадает с оригинальной н имеет следующий вид: первая цифра означает номер главы, а вторая -— порядковый номер. Нумерация формул является независимой.
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснована актуальность темы диссертации, сформулированы цели ц задачи исследования, отражены научная новизна, теоретическая и практическая значимость работы.
В первой главе дано распространение динамической версии теории кооперативных игр, предложенной ранее C.B. Чистяковым [5], с классической задачи дележа на более общую задачу распределения [4]. Обсуждению последней задачи посвящен §1.1.
Пусть I = {1,2,..., ?i}, (n = ¡/¡), — множество игроков в кооперативной игре п лиц, a tC(I) = 21 \ {0, /}. Всякую числовую функцию v : 21 —■» R,v(0) = 0, будем называть классической кооперативной игрой [3]. Совокупность всех таких функций — V(i), будем
называть пространством классических кооперативных игр в задаче распределения или дележа.
Пусть a; (S) = ]Cies Xi• Для ИГРЫ v £ ^(-0 обычно рассматривают следующие множества: L(v) = {х = (а^,..., хп) £ 7?я|х(/) = v(I)} — множество распределений [4]; E{v) = {х £ ^ и* Vf £ /} —
множество дележей [3]; C{v) = {я £ E(u)|i(5) ^v(S) VS £ К(Г)} — С-ядро [2].
В основе динамической теории классических кооперативных игр лежат понятия компромисса и его базы, которые вводятся §1.2 в виде следующих определений.
Определение 1.6. Всякое непустое ограниченное множестве «М С L(v) будем называть компромиссом о классической кооперативной игре и £ V(I).
Как предполагается в [5, 9], в задаче дележа ограниченности множества М С Е(и) не требуется.
Всякий компромисс М. в игре v £ V(I), состоящий из единственного распределения, будем называть совершенным.
Определение 1.8. Базой компромиссам в uzpev £ V(/) назовем такую функцию w : 21 —> R, что
w(S) = inf x(S), u/(0)=O.
х€.М
Очевидно, что база любого компромисса является классическое кооперативной игрой, т.е. w £ V(J).
Пусть v £ V(i), a W„ — множество всех игр (функций) w £ V(I) каждая из которых является базой того или иного компромисса ] игре v.
Компромиссы в классической кооперативной игре v, имеющие од ну и ту же базу, будем называть эквивалентными.
Компромисс M.w{y) в игре v £ V(/), который имеет своей базо! данную функцию w £ VVv и содержит любой другой компромисс и своего класса эквивалентности, назовем полным.
Лемма 1.1. В любой игре v £ V(I) всякий полный компромис М ш(г>) совпадает сС-ядром игрыги, тп.е, Mw{v) = C(w).
Кооперативная игра у € У(/) является супераддитивной (аддитивной), если г;(5 и Т) > и(5) -Ь и(Г) \/5, Г С /, 5 П Т = 0 (соответственно, «(£ и Т) = ь{8) + и(Г) 75, Т С /, Я П Г = 0) [2].
Лемма 1.2. База любого компромисса в игре V £ У(1) является сунераддитионой играй,
Теорема 1.1. Компромисс в игрег! £ У(/) является совершенным тогда и только тогда, когда его база является аддитивной игрой.
Теорема 1.2. ЕслиС-ядро игрыи € непусто, то оно является полным компромиссом в эгпой игре, при этом если ю — база этого компромисса, то ^у(З) для всех в С I (для Б — 0,1 последние нестрогие неравенства выполняются как равенства).
В теории кооперативных игр часто изучают различные множества кооперативных игр с темп или иными свойствами. В связи с этим в §1.3 введено следующие
Определение 1.12. Подпространством пространства У(1) классических кооперативных игр для задачи распределения (деле' жа) назовем такое его подмножество V, которое удовлетворяет следующим условиям: 1)У ф 0, 2) 'WV С V Уи Е V.
К числу подпространств пространства кооперативных игр У(1), очевидно, относятся следующие широко известные его подмножества: множество слабо сбалансированных игр — Уи1ь{1), т.е. игр для которых справедливо у(1) ^ и({*})"> множество всех супераддитивных игр — У5£1(/); множество всех аддитивных игр —1;д(/); множество всех сбалансированных игр — И(/) [2]. Кроме того, к подпространствам пространства игр можно отнести множество
¿е/
всех баз — = а также множество всех точных игр
— Уе(/) (игра и € /) называется точной [б], если для С I существует х 6 С(и) такой что х^ = v(S)). Оказывается, что справедлива следующая
Теорема 1.3. Щ1) = Уе(/). '
В теории кооперативных игр рассматривают также следующие подмножества множества V(/): множество всех выпуклых игр — Ус(/), (для которых справедливы неравенства: ь(3)-\-ь(Т) ^ и(5иГ') + и(5ПТ) Т С I), множество игр с большим ядром — ТЛе(/), (игра V £ У(/) имеет большое ядро; если Уу 6 Л" такого, что 1/(5) ^ и(5)
С существует а: € С(и) такой, что у ^ а,-) [б].
Заметим, что, согласно [2, С], справедливы строгие включения: Уа(1) С Щ1) С Уи{1) С Уе(/) С Уь(/) С Уеа(П с С V{I).
Принимая во внимание аргументацию новых определений, представленных выше, в настоящей работе рассматривается распространение понятпя принципа оптимальности в классических кооперативных играх, первоначально определенное на подпространстве Уи>ь С У(/) для задачи дележа (§2.1) [5], на пространство У(7) для задачи распределения. Этому понятию в §1.3 дана следующая форма.
Определение 1.13. Под принципом оптимальности на подпространстве V пространства классических кооперативных игр У(1) будем понимать асякий оператор Л : V —> V, такой, что А о у & И*,, Уи €Е V, при этом принцип оптимальности Л будем называть
а) совершенным, если А о у € Уа(/) Уу Е V;
б) непрерывным, если оператор А непрерывен на V П УУ(1);
в) монотонным, если А о у^у \/и € V П т.е. (Л о
Уг» б V П УУ(/), У5 С I-
Для произвольного принципа оптимальности, соответствующая игра Лог; однозначно определяет всего лишь некоторый полный компромисс. Поэтому можно сделать следующий шаг в решении задачи распределения, построив компромисс и найдя его базу уже для игры А о у. Таким образом, можно построить и некоторую итеративную последовательность кооперативных игр. Для этого введем следующее
Определение 1.14. Пусть А — произвольный принцип оптимальности определенный на подпространстве V пространства У(/) и пусть исходная игра —€ V. Если последовательность
Р^Г-!' (!)
сходится к uzpev* G V, являющейся неподвижной точкой оператора Л, то соответствующую uzpyv* будем называть финальным решением исходной игрыу^а\ отвечающим принципу оптимальности Л.
Отметим, что определения, аналогичные последним, ранее были предложены в работе C.B. Чистякова [5] для задачи дележа.
Для последовательности (1), исходя из определений компромисса и его базы, сопоставим последовательность множеств
°=[, Mlk) =MvW(v(k-1]) С L(vM), (2)
гдеЛ^„(к) — полный компромисс в имеющей своей
базой игру
Содержательно можно считать, что последовательность (1), а следовательно, и последовательность (2), моделирует итеративный процесс принятия решения ("механизм переговоров") в исходной игре при этом установлена следующая
Теорема 1.4. Пусть А — монотонный и непрерывный принцип оптимальности на подпространстве V пространства V(I). Тогда каждая исходная игра € V имеет финальное решение v* € У, отвечающее этому принципу оптимальности, при этом для данной игрыи6 V соответствующая ей и принципу оптимальности А последовательность полных компромиссов (2) не возрастает по включению и сходится в метрике Хаусдорфа к полному компромиссу Ai* в исходной игреь^, имеющему своей базой игруь*.
В §1.4 рассмотрены принципы оптимальности А на подпространстве V С V(/) для которых каждая исходная игра £ V имеет финальное и при том аддитивное решением*, т.е. t>, G Va(7), которое отвечает выбранному принципу оптимальности А Такие принципы оптимальности называются финально совершенными (на V)[5].
Во второй главе развитие динамической теории классических кооперативных игр [5] продолжается для задачи дележа и в качестве пространства классических кооперативных игр рассматривается множество всех слабо сбалансированных игр Vwb{I), поскольку для таких игр множество E(v) непусто.
Определение 2.2. Принцип оптимальности Л : V i—> V будем называть квазисовершенным на подпространстве V С Vwi,(1), если 3 к Е N такое, чток-л степень А^ оператора Л является совершенным принципом оптимальности на том же подпространстве.
Таким образом, для принципа оптимальности А, обладающего свойством квазисовершенности, независимо от выбора исходной игрыт/0) итеративная последовательность (1) сходится не более нем за к шагов к аддитивному финальному решению т.е. = v*, и
6 Vü(/)-
В соответствии с [5], в §2.1 рассмотрен один класс принципов оптимальности определенный на подпространстве Уб(Д
Пусть R+ — положительная вещественная полуось и С+(/С(/) х Vb(/)) — множество всех функции р : 1C(J) х 1Д(/) i—> таких, что каждая из функций ps — ß{S, •) : Vb{I) •—> S € £(/) является непрерывной на Уь(/).
Определение 2.3. Для каждого ц £ C+(K.(I) х Уб(-О) определим функцию piß : (v,x) 1—>
piß(v,x) = max [x(S)~fS)], и S Vb(I), x G C(v), (3) seM/)
u многозначное отображение: v i—t Miß{v) С C(u),
■M1(1(u) = ai'gmm piß{v,x). (4)
x£C(u)
Теперь для каждого p G C+(fC(I) X Vb{I)), определим принцип оптимальности A\ß : Vb(/) i—> Vb(/), считая, что A^j. о v — база компромисса J\4 iß(v). Так определенный принцип оптимальности Aifj. назовем принципом минимакса, соответствующим функции
р е с+(ОД х vb(i)).
С учетом определений базы хсомпромисса и оператора Aiß, показано, что
(Alßov)(S) = min a(S) VS £ ОД. (5)
Пусть
qiAv) = mm plM(u,a;), v£Vb{I). (6)
хёС(и)
В параграфе §2.2 доказаны следующие утверждения.
Лемма 2.1. Пусть¡л £ С^.(К.(1) хУ<,(Г)). На подпространствеУь{1) равенство = 0, имеет место тогда и только тогда, когда
V £ Уа(1)> Щ следовательно, <71Д(и) >0 Ун € ^¿,(-0 \ ^Л-О-
Теорема 2.1. Каждый из принципов о7гтимальности ц £ С+(1С(1) х Уь(/)), Авллется монотонным, непрерывным и финально совершенным.
Последняя теорема ранее была установлена в [5]. В диссертации дано несколько иное её доказательство (см. [9]).
Параграф 2.3 посвящен доказательству основного утверждения второй главы (см. ниже теорему 2.2), которое опирается на следующие леммы.
Лемма 2.2. Пусть ц £ С+(!С(1) X Уь(/)). Для любой игры и £ И(/)\ Уа(/) существует такал коалиция Э £ 1С(1), что (Аг^ о г;)(5) =
Лемма 2.3. Пусть /л £ С+{Ц1) X Уь(/)) м(0> 6 Щ1)\Уа{1). Тогда существует такая коалиция 5 € £■{!)> что
(Д1м о «(°))(5) + (Л1м 0 «(0))С \ 3) = (7)
Лемма 2.4. Пусть ц £ С+(/С(7) х У6(/)) ии^ £ УЬ(/)\У„(/). Тог(?а, ес/ш 5 £ — та коалиция, для которой справедливо равенство (7), то для нее также при любомк 6 N справедливо равенство:
(4; о „<■»)($) + (Ак11Х о У(0>)(/ \ 5) = «<»)(/). (8)
Заметим, что утверждения лемм 2.3, 2.4, очевидно, справедливы и в том случае, когда £ Уа(/).
Обозначим через Т множество всех неупорядоченных пар (5,1 \ 5),5 € ОД. Очевидно, |Т| = |ВД|/2. Пусть и<°> € Уь{1). Для
каждого к £ N через 7л-(и^) обозначим множество всех тех пар (5, / \ 5) £ Т, для которых при данном к справедливо равенство (8). Для краткости далее вместо будем писать Тк-
Лемма 2.5. Для любого к Е N справедливо включение Ти С 71+ь при этом, если для некоторого т Е N Тт = Тт+\, то множество Т,п, и следовательно, и любое множество Тк, к ^ т, совпадает с множеством Т.
Следствие. Пусть I = |АС(7) | = 2" - 2, {п = |/|) и = Тогда о + (Л^ о <,(0>)(/ \ 5) = и<°>(7), € /С(1).
Основным результатом второй главы является следующая теорема.
Теорема 2.2. Каждый из принципов оптимальности Л^, ц 6 С+(К,{1) х У(Д/)), является квазисовершенным.
Отметим, что из доказательства теоремы 2.2 следует, что для принципа оптимальности Л = Л^, € С+(АГ(/) х вне зави-
симости от выбора из итеративный процесс (1) сходится
не более чем за к* = 2П_1 — 1, (п = |/|), итераций.
С учетом (6), определению компромиссаМх^(ь) можно придать следующую форму:
Отметим, что нахождение предела итеративной последовательности (1), для принципа оптимальности Л = Е С+(1С(1) х Уь(/)), сводится к решению пары экстремальных задач (6) (при условии (3)) п (5) (при условии (9)) на каждой итерации указанной последовательности. Важным обстоятельством при этом является то, что каждая из упомянутых выше экстремальных задач эквивалентна определенной задаче линейного программирования. Обоснование этого положения посвящен §2.4, в котором, в частности, доказаны следующие утверждения.
М.1Ц (и) = {х Е С(и) | х) =
(9)
Следовательно, учитывая определение С-ядра, имеем
(10)
Лемма 2.6. Яусть р, £ С+(/С(/) х Vb{I)) uv Е Vb{I)- Экстремаль-нал задача (6) (при условии (3)) эквивалентна следующей задаче линейного программироаангт:
min Zn+i,
где B¡M(v) - множество решений следующей системы:
-x(S) + fis(v)zn+! ^ -v(S) V5 е JC{I), x(S) Z v(S) VSGK(Í), x[I) = v(I),
Лемма 2.7. Пусть ß 6 C+(/C(/) x (/)) uve Vb(/). Множество Miii(v) (см. (4) и (9)) совпадает с множеством решений системы (10), и следовательно, для любого S € £(-0 экстремальная задача (5) представляет собой задачу линейного програмлшрования на минимум линейной функции: x{S) =
В §2.5 рассматривается одно естественное распространение принципа шшпмакса с пространства сбалансированных игр V¿(/) на все пространство игр V(I) для задачи распределения. Пусть С+(АГ(7) х У(/)) — множество, всех функций /j. : /С(1) х У(/) i—> таких, что каждая из функций fis = : V(í) i—> R+, S 6 K,{I)
является непрерывной наУ(/).
Для каждого /1 6 C+(ÄT(/) х V(/)) определим функцию plfl : (v,x) i—>ptp{v¡x),
и многозначное отобрал<ение M.^ : v i—> Aíi^(u) С £(«),
M i(i(v) = argmhi piß{v,x), (11)
где
•ñ/.л _ i CH> ecJIU u e W).
~ \ L(v), если y G У(/) \ Va(/). Для задачи распределения в §2.5 доказана следующая
Лемма 2.8. Для игры v £ V(-0> множество С L(v), iipu
р. £ С+(/С(/) X V(/)), определенное в (11), является непустым и компактным множеством.
Из последней леммы следует, что множество(v) С L(v), при /i Е С+{К.(1) х V(í)), является компромиссом в игре v € V(Z).
Определение 2.4. Длл каждого ц £ C+(¡C(I) х V(/)), определим принцип оптимальности А\И : V(í) i—► V(-0> считая, что Ai^ о v — база компромиссаM-ipiv), определенного в (11). Принцип оптимальности Ai fl назовем принципом минимакса для задачи распределения, соответствующим функции /t £ C+{IC[I) х V(I)).
В гл. 1 показано, что Ai^ о и £ Уь(Л Vu £ V(/), а финальное решение любой сбалансированной игры г^0', соответствующее принципу минимакса А^ц для задачи распределения, равно финальному ее решению, соответствующему принципу минимакса Ai^. Поэтому отыскание финального решения несбалансированной игрьиА0\ соответствующего принципу оптимальности Д^, сводится к отысканию финального решения игры т/1' = А\ц соответствующего принципу оптимальности Ai
Третья глава посвящена численным исследованиям принципов
оптимальности, среди которых рассматривается принцип минимакса и принцип минимума диспропорции [5], определение которого дано в §3.3.
Определение 3.2. Для Vá € C+(JC(I) х Vo(I)) на Vb(I) определим
функциюp2s : (v,x) i—i P2¿(v,x),
P2s(v,x)= max K l , , ~ mm 1 v ' . ,v , x £ C(v), (12
v ' SíK(i) 8s{v) sec(/) Ss(v) w \ /
и многозначное отображение M.26 '■ v 1—* M2s(v) С C(v),
M.2¿{v) = argmin P25{v,x). rtC(u)
Теперь для 5 £ C±(IC(I) x V¡,(/)) определим принцип оптимальности A^s на подпространств с V¿,(/), считая, что Ai& о v — база компромисса j\Á2s{v) в игре и G V(,(/). Так определенный принцип оптимальности А25 назовем принципом минимума диспропорции, соответствующий функции S G C+(/C(I) х V¡,(I)).
Легко показать, что множество M.2&{v) непусто и компактно. Учитывая это и определения базы компромисса и оператора А25 имеем
(•42iou)(S)= min i(S) VSe/C(i). (13)
Пусть для v £ V;,(/)
(J2ö{v) - min p2s{v, x). (14)
x£C(v)
тогда
M2S(v) = {x € C(u) I P2s(v, x) = g2S(v)}. (15)
Следовательно, нахождение предела итеративной последовательности (1) для принципа оптимальности Л26; при^ £ C+(/C(i") х Vö(/)), сводится к решению пары экстремальных задач (14) (при условии (12)) и (13) (при условии (15)). Более того, в п. 3.3.2. доказаны следующие
Лемма 3.1. Пусть & 6 С+(!С(Г) х Vb(/)) и v £ Vi,(1). Экстремальная задача (14) (при условии (12)) эквивалентна следующей задаче линейного программирования:
min - хп+2,
где B2s{v) — множество решений следующей системы
\ -x(S) + Ss(v)xn+1 > -v(S) VS£JC(l), x(S) - Ss(v)x„+2 > v(S) VS £ Ц1),
z(I) = v(J),
Xn+2 ^ 0.
Лемма 3.2. Пусть S £ C+{JC{I) x Vb(i)) uv £ Уь(7). Для любогоS £ !C(I) экстремальная задача (13) (при условии (15)) эквивалентна следующей задаче линейного программирования:
min x(S),
(x,in+1 v)
rddeJ\Í2s(v) — множество решений следующей системы
-x(S) + 5s{v)x,l+1 > -v(S) VSelC(I),
x(S) - 6s(v)xn+2 > «(5) V5 6/C(í),
.T„+i-in+2 = (m{v),
x(I) = v{I),
a;n+2 ^ 0.
Численные исследования рассмотренных принципов оптимальности обусловлены двумя важными проблемами.
Во-первых, на примере игры 6 Vb(/), I — {1,2,3,4}:
гА°'({1,2,3,4}) = 100, ü<0>({¿})=0 Vi € {1,2,3,4}, v<°>({l,2}) = 5G, »<°>({1,3}) = 30, «<°>({1,4}) = 44, W<°> ({2,3}) = 48, W<°> ({2, 4}) - 3G, v™ {{3, 4}) = 42, (16) vW ({1,2,3» = 80, «<»>({1,2,4}) = 70, v<o>({lf3,4}) = 50, ^({2,3,4}) = 60,
показано, что принцип мпнимакса Ai = Aif¿, при — 1
V5 6 (см. и. 3.2.1.), и, соответственно, принцип оптимальности Аг — A2S1 при = 1V5 G /С(1) (см. п. З.4.1.), вообще говоря,
не являются совершенными vi поэтому результаты теоретических исследований принципа минимакса, проведенное в диссертации, в некотором смысле являются исчерпывающими.
Для игры (16) показано, что играг»^1^ = Aov^°\ при А = А\ на одноэлементных коалиции имеет значения: г)^({1}) = 28, и'^({2}) = 28, г>^({3}) = 24,г/^({4}) = 10, а, соответственно, при А = Ai на одноэлементных коалициях имеет следующие значения: и^({1}) = 57/2, и(1)({2}) = 57/2, г;(1>({3}) = 24,и<1)({4}> = 33/2. Полученные данные означают, что для этих принципов оптимальности игра ^ Va(/), и следовательно, ни один из них не является совершенным.
Во-вторых, на примере нгрыг/0) € Vc(/), I = {1,2,3}: гА°>({|}) = 0 Vi €{1,2,3},
^({1,2,3}) = 1, . (17)
»(°>({1,2}) = 1/3, «/<°>({1,3}) = 1/6, v<°>({2,3}) = 1/12.
показано, что финальное ¡решение, отвечающее каждому из упомянутых выше принципов оптимальности, не совпадает ни с вектором
Шепли, ни с »¡-ядром [2, 4]. В частности, вектор Шеплп Ф(и) Е Я3 для игры (17) имеет вид: Ф(и(0)) = (7/18, 25/72, 19/72), а её п-ядром является вектор: 'у(и^) = (1/3, 1/3, 1/3) [2]. В тоже время, как показано в а. 3.2.2., для принципа мнннмакса Ailt, при = 1 VS Е финальным решением игры (17) будет ад-
дитивная игра, которая на одноэлементных коалициях имеет следующие значения: и(1)({1}) = 4/9, и(1)({2}) = 13/3G, и(1)({3» = 7/36, а соответственно для принципа минимума диспропорции _A2s, при (>s(v^) = 1 VS1 Е ¡С{1), финальным решением будет также аддитивная игра, у которой значения на одноэлементных коалициях имеют вид: и(1)({1}) = 7/18, у(1)({2}) = 11/36, i>(1)({3}) = 11/36. Факт аддитивности финального решения для принципа минимума диспропорции установлен в п. 3.4.2.
В заключении сформулированы основные научные результаты диссертационной работы, выносимые на защиту, которые состоят в следующем:
— предложен и обоснован новый динамический подход к решению общей задачи распределения в теории классических кооперативных игр;
— для параметрического семейства принципов оптимальности типа принципа мишшакса доказано, что они обладают свойством квазисовсршенности и установлена оценка сверху для числа шагов, за которое сходится соответствующие им итерационные процессы вне зависимости от выбранной исходной игры;
— показано, что принцип мишшакса не является совершенным, т.е. соответствующая итерационная последовательность в общем случае сходится более чем за одну итерацию. Аналогичный результат установлен и для принципа минимума диспропорции;
— описаны задачи линейного программирования, к решению которых сводится реализация исследуемых принципов оптимальности (принцип минимакса и принцип минимума диспропорции);
— на модельных примерах проведен сравнительный анализ принципа мишшакса, принципа минимума диспропорции, вектора Шепли и п-ядра.
Библиографический список цитируемой литературы
1. Бьюкенен Дж. Сочинения. — М.: Таурус Альфа, 1997. — 5С0 с. — (Нобелевские лауреаты по экономике, Т.1).
2. Мулен Э. Кооперативное принятие решений: Аксиомы и модели. — М.: Мир, 1991. — 4G4 с.
3. Нейман Дж. фон, Моргенштерн О. Теория игр и экономическое поведение. — М.: Наука, 1970. — 709 с.
4. Печерский C.JI., Соболев А.И. Проблема оптимального распределения в социально-экономических задачах и кооперативные игры. -— JL: Наука, 1983. — 176 с.
5. Чистяков C.B. Динамический аспект решения классических кооперативных игр. // Докл. АН. — 1993. — Т. 330, №6. — С. 707-709.
6. Ichiishi Т. Comparative Cooperative Game Theory // International Journal of Game Theory. — 1990. — Vol. 19, Issue 2. — P. 139152.
Библиографический список публикаций автора по теме
диссертации
7. Васецов М.Е. К вопросу о совершенности двух принципов оптимальности в кооперативных играх // Процессы управления и устойчивость: Труды XXIX научной конференции. — СПб.: НИИ Химии СПбГУ, 1998, — С. 300-308.
8. Васецов М.Е., Чистяков C.B. Об одном классе квазисовершенных принципов оптимальности в классических кооперативных играх. Деп. в ВИНИТИ, №3352-В97, от 17.11.97.
9. Васецов М.Е., Чистяков C.B. О некоторых квазисовершенных принципах оптимальности в кооперативных играх // Вестн. С.-Петербург, ун.-та. Сер. 1. 1998. Вып. 4. (№22).
10. Chistykov S.V., Vasetsov M.Y. Quasiperfect Optimality Principles for Classical Cooperative Games. // Game Theory and Economics. N.N. Vorob'ev memorial conference. June 27-30, 1996. Abstracts. — P. 11.
Введение
Глава 1. Элементы динамической теории классических кооперативных игр для задачи распределения
§1.1. Задача распределения и задача дележа в теории классических кооперативных игр.
§1.2. Определение понятий компромисса и его базы для задачи распределения.
§1.3. Принципы оптимальности в классических кооперативных играх для задачи распределения.
§1.4. Финально совершенные и существенно монотонные принципы оптимальности в динамической теории классических кооперативных игр.
Глава 2. Принцип минимакса для задачи дележа
§2.1. Основные понятия динамической теории классических кооперативных игр для задачи дележа и определение принципа минимакса.
§2.2. Теорема о финальной совершенности принципа минимакса для задачи дележа.
§2.3. Теорема о квазисовершенности принципа минимакса для задачи дележа.
§2.4. Эквивалентность одной итерации принципа минимакса задачам линейного программирования.
§2.5. Принцип минимакса для задачи распределения.
Глава 3. Численные исследования принципа минимакса и принципа минимума диспропорции
§3.1. Исходные данные для численных исследований принципа минимакса и принципа минимума диспропорции.
§3.2. Численные исследования принципа минимакса.
3.2.1. Результаты вычислений для игры четырех лиц
3.2.2. Результаты вычислений для игры трех лиц.
§3.3. Принцип минимума диспропорции для задачи дележа
3.3.1. Определение принципа минимума диспропорции
3.3.2. Эквивалентность одной итерации принципа минимума диспропорции задачам линейного программирования
§3.4. Численные исследования принципа минимума диспропорции
3.4.1. Результаты вычислений для игры четырех лиц
3.4.2. Результаты вычислений для игры трех лиц
§3.5. Замечания к сравнительному анализу исследуемых принципов оптимальности.
Диссертация посвящена развитию динамического аспекта фундаментальной проблемы распределения, изучаемой обычно в рамках теории классических кооперативных игр.
Актуальность темы. Проблема распределения некоторого общего блага, произведенного в результате разумной человеческой деятельности или же предоставленного природой, является неотъемлемой частью экономической жизни человека в современном обществе.
По своему характеру процесс принятия решения человеком о том или ином распределении такого блага не всегда является "одноактным" действием. Это связано со многими причинами, основа которых заложена и в человеческой природе.
Человек, принимая те или иные решения о "справедливом" распределении или о выборе способов такого распределения, просто вынужден учитывать, и учитывает, предпочтения тех или иных людей, причастных к распределяемому благу. Таким образом, многогранность и динамичность подхода к решению поставленной задачи распределения обусловлена наличием различных интересов у людей, принимающих решения. Нельзя все же, не отметить, что участники распределения, в общем, стремятся к достижению определенного согласия (компромисса) в выборе принципов разумного поведения. В противном случае они могут остаться ни с чем. Все это, в известной мере, предопределяет не однократный подход в разработке методов анализа и расчета разумного человеческого выбора.
Определенную методологическую основу для расчета согласия и при5 нятия коллективных решений предоставляет, как известно, теория игр и, в частности, одно из её направлений — теория классических кооперативных игр.
Предметом этой теории обычно является так называемая, задача распределения (дележа), которая в содержательных терминах может быть описана следующим образом.
Предположим, что члены некоторого сообщества /, называемые далее игроками, в рамках того или иного совместного предприятия получили или могут получить определенный доход. Требуется разделить этот доход между всеми игроками так, чтобы не только удовлетворить известным претензиям каждого игрока в отношении "причитающейся" ему части общего дохода, но и, по возможности, полнее удовлетворить аналогичным претензиям любой из коалиций игроков, то есть любой обособленной их группы 5 из I.
Подчеркнем, что в этих задачах заранее не исключается, что претензиям одновременно всех коалиций удовлетворить невозможно. В последнем случае можно сказать, что претензии коалиций несбалансированны. В то же время, в отличие от задачи распределения, в задаче дележа предполагается, что индивидуальные претензии игроков сбалансированы, то есть все они могут, а по условию и должны быть, удовлетворены одновременно.
Как негласно предполагается, также особая роль коалиций и коалиционных претензий в рассматриваемой задаче состоит в том, что свои интересы, а именно желание получить возможно большую часть общего дохода, игроки могут отстаивать, объединяясь в коалиции и определенным, мотивированным образом выдвигая такие коллективные требования, которые, возможно, превышают сумму индивидуальных претензий всех членов соответствующей коалиции. Имея в виду сказанное здесь, задачу распределения иногда представляют как задачу наиболее справедливого распределения общего дохода без обязательного для выполнения учета индивидуальных претензий игроков, но все же с учетом претензий 6 объединений игроков.
Отметим, что более подробно содержание и проблематика задач распределения и дележа обсуждаются в первой главе диссертационной работы.
Далее, касаясь приложений теории классических кооперативных игр, отметим, что результаты этой теории используются в различных распределительных задачах экономики, среди которых можно назвать модель страхования автомобилей [55], модель распространения инноваций [58], модель голосования [23, 30], модель процессов ценообразования в сфере государственных заказов [44]. По поводу последней модели отметим, что в ней при помощи кооперативной теории решается вопрос об определении "справедливых" цен по договорам субподряда, с целью ограничений монополий и поддержки малого бизнеса.
Со времени своего возникновения и до недавнего времени теория классических кооперативных игр развивалась как статическая теория, т. е. как такая теория, в которой принятие решения о дележе или о распределении общего блага рассматривалось как одноактное действие. Одноактное распределение, однако, не всегда соответствует реальности, в которой окончательный компромисс о распределении благ достигается не мгновенно, а является исходом сложного многошагового процесса согласования интересов и взаимных уступок заинтересованных сторон. Возможно, имея это в виду, основоположники классической кооперативной теории игр Дж. фон Нейман и О. Моргенштерн в своей монографии "Теория игр и экономическое поведение" писали: "Несомненно, динамическая теория была бы более полной и поэтому более предпочтительной" [31, с. 70].
На необходимость моделирования и анализа динамического процесса достижения согласия, по вопросу распределения некоторого блага, указывалось и в работе Дж. Бьюкенена "Границы свободы" [7], в которой с точки зрения теории общественного выбора была изложена одна из возможных концептуальных схем такого процесса. 7
Заметим, кстати, что работы Дж. Бьюкенена [7], как и многие другие (например [2, 29, 61]), свидетельствуют о том, что теория кооперативных игр стала языком экономического анализа и служит основой для моделирования различных прикладных задач распределения в экономике.
Стоит отметить также, что теория кооперативных игр, в качестве своего экономического приложения содержит и теорию совершенных рынков или иначе — теорию общего экономического равновесия. В ней обычно рассматриваются две группы участников процесса распределения ресурсов — сторона спроса и сторона предложения, и, кроме того, решается проблема существования в некотором смысле равновесного распределения [1, 42]. Однако и в этой теории не предполагается какого-либо многошагового подхода к отысканию решения в задаче распределения ресурсов.
По-видимому, впервые определенный подход к построению динамической теории классических кооперативных игр был предложен в работе C.B. Чистякова [49], в которой, хотя бы и ограниченная определенными рамками, сделана попытка построения целостной такой теории. В данной теории окончательный, совершенный компромисс в интересах сторон, участвующих в задаче дележа, рассматривался как предел итеративной последовательности, моделирующей в соответствии с первоначально избранным принципом оптимальности, или, иначе, принципом достижения окончательного компромисса, многошаговый процесс принятия решения о распределении общего блага. При этом итерационный оператор отождествлялся с соответствующим принципом оптимальности, а в случае сходимости указанной последовательности к однозначному решению, т. е. к дележу, этот оператор назывался финально совершенным.
Изложению основ динамической теории классических кооперативных игр, а также её распространению с задачи дележа на задачу распределения, посвящена первая глава диссертационной работы. 8
До недавнего времени одним из наиболее содержательных определений понятия принципа оптимальности было такое определение [13, 45], в рамках которого принцип оптимальности отождествлялся с отображением, ставящим в соответствие любой игре из заданного их множества, определенный компромисс (непустое подмножество множества дележей или распределений) в этой игре. Предложенное в работе C.B. Чистякова [49], новое определение принципа оптимальности трактует его как отображение заданного множества игр (точнее заданного подпространства игр (см. §1.3, §2.1 диссертационной работы)), в себя. Примечательно, что новое определение вполне согласуется со старым — они почти равносильны, точнее соотносятся друг с другом примерно так, как соотносятся понятия выпуклого множества и его опорной функции. Однако главное, пожалуй, то, что в рамках нового определения принципа оптимальности имеется возможность моделировать динамику процесса достижения окончательного, в некотором смысле, компромисса. Более того, отметим, что это новое определение позволяет конструировать новые принципы оптимальности на основе старых, используя то, что каждая итерация динамического процесса связана содержательно с промежуточным пересмотром текущих амбиций индивидуальных игроков и их коалиций.
Рассматривая в качестве модели процесса согласования интересов определенную итеративную последовательность, естественно возникает вопрос об изучении характера её сходимости, исследование которого и определяет выбор темы диссертационной работы. В связи с этим, наиболее актуальным является вопрос о том, не будет ли некоторая степень данного финально совершенного оператора значения совершенным оператором значения, т.е. таким оператором, который каждой игре ставит в соответствие однозначное ее решение. Постановка последнего вопроса — вопроса о квазисовершенности принципа оптимальности — предполагает исследование природы определения изучаемого оператора.
Цель работы заключается в развитии упомянутой выше динамической теории классических кооперативных игр. Предлагаемое развитие, 9 в частности, состоит в распространении этой теории с задачи дележа на более общую задачу распределения, а в основном — в изучении вопроса о квазисовершенности параметрического семейства принципов оптимальности типа принципа минимакса [49].
Доказательству квазисовершенности упомянутого выше семейства принципов оптимальности посвящена вторая глава диссертации.
Научная новизна. Свойство квазисовершенности принципов оптимальности, как и вопрос распространения упомянутой выше динамической теории с задачи дележа на задачу распределения, изучается впервые. Основные результаты, полученные в диссертации, являются новыми.
Теоретическая и практическая ценность полученных результатов, с одной стороны, состоит в том, что они расширяют сферу возможных приложений динамической теории классических кооперативных игр, а с другой стороны, — в том, что установленное свойство квазисовершенности рассматриваемых принципов оптимальности позволяет предложить эффективные алгоритмы поиска соответствующих совершенных компромиссов на основе решения конечного числа задач линейного программирования. В свою очередь, это составляет естественную основу для исследования разнообразных распределительных задач экономики.
Основные научные результаты диссертационной работы, выносимые на защиту, состоят в следующем: предложен и обоснован новый динамический подход к решению общей задачи распределения в теории классических кооперативных игр; для параметрического семейства принципов оптимальности типа принципа минимакса доказано, что они обладают свойством квазисовершенности и установлена оценка сверху для числа шагов за которое сходится соответствующие им итерационные процессы вне зависимости от выбранной исходной игры; показано, что принцип минимакса не является совершенным, т.е.
10 соответствующая итерационная последовательность в общем случае сходится более чем за одну итерацию. Аналогичный результат установлен и для принципа минимума диспропорции; описаны задачи линейного программирования, к решению которых сводится реализация исследуемых принципов оптимальности (принцип минимакса и принцип минимума диспропорции); на модельных примерах проведен сравнительный анализ принципа минимакса, принципа минимума диспропорции, вектора Шепли и п-ядра.
Численные исследования рассматриваемых принципов оптимальности и упомянутый выше сравнительный анализ этих принципов рассмотрены в третьей главе диссертационной работе.
Отметим также, что основные положения диссертации, выносимые на защиту, более подробно изложены и прокомментированы в заключении.
Апробация работы. Результаты исследований, представленных в работе, докладывались на международной научной конференции "Game Theory and Economics" (Санкт-Петербург, 1996г.), на XXIV научной конференции факультета прикладной математики-процессов управления СПбГУ "Процессы управления и устойчивость" (Санкт-Петербург, 1998г.), на семинаре в Институте математики и механики Уральского отделения РАН (Екатеринбург, 1998г.), на семинаре лаборатории теории игр и принятия решений Санкт-Петербургского экономико-математического института РАН (Санкт-Петербург, 1998г.), на городском семинаре по теории игр под руководством проф. JI.A. Петросяна (Санкт-Петербург), а также на семинарах кафедры математической статистики, теории надежности и массового обслуживания факультета прикладной математики - процессов управления Санкт-Петербургского государственного университета.
Диссертация выполнена при поддержке Российского фонда фундаментальных исследований и проводилась по проекту №98-01-01056.
Публикации. Результаты диссертации нашли отражение в работах [9, 10, 11] и [56], приводимых в библиографическом списке использои ванной литературы в конце диссертационной работы.
Структура работы. Диссертация состоит из введения, трех глав, заключения, библиографического списка использованной литературы из 70 наименований и имеет общий объем 123 страницы.
Заключение
В диссертационной работе получены следующие результаты:
1. Предложен и обоснован новый динамический подход к решению общей задачи распределения в теории классических кооперативных игр. В рамках этого подхода принятие решения трактуется не как одноактное действие, что имеет место в других известных подходах, а как многошаговый процесс, определяемый выбором принципа оптимальности, который отождествляется с отображением пространства классических кооперативных игр в себя.
2. Исследовано параметрическое семейство принципов оптимальности типа принципа минимакса. Для этого семейства упомянутый выше многошаговый процесс сходится к аддитивной игре, которая однозначно определяет распределение в исходной игре. Доказано, что каждый принцип оптимальности из этого семейства обладает свойством квазисовершенности и установлена оценка сверху для числа шагов, за которое сходится соответствующий выбранному принципу оптимальности итерационный процесс, вне зависимости от выбранной исходной игры. Отдельные из этого семейства принципов оптимальности имеют ясный экономический смысл, что служит основой возможного их приложения к решению прикладных задач.
3. Даны описания задач линейного программирования, к решению которых сводится реализация исследуемых принципов оптимальности (принцип минимакса и принцип минимума диспропорции). Таким образом показано, что вычисление элементов итеративной последовательности, соответствующих исследуемым принципам оптимальности, может
116 быть проведено с помощью известных методов теории линейного программирования.
4. С помощью методов этой теории установлено, что принцип мини-макса, при единичных значениях его параметров, вообще говоря, не является совершенным. В свою очередь, это означает, что соответствующая итерационная последовательность в общем случае сходится более чем за одну итерацию. Аналогичный результат установлен и для принципа минимума диспропорции, также при выборе единичных значений соответствующих параметров.
5. При помощи соответствующих задач линейного программирования на модельных примерах проведен сравнительный анализ принципа ми-нимакса, принципа минимума диспропорции, вектора Шепли и п-ядра.
Далее, прокомментируем, кратко, отдельные из сформулированных выше основных положений диссертационной работы, а также коснемся, возможных направлений развития полученных результатов.
За рамками этой теории остаются многие актуальные проблемы соответствующей теории, которые в работе до сих пор не упоминались. Так, например, остается открытым вопрос о квазисовершенности принципа минимума диспропорции, хотя, положительное решение этого вопроса кажется вполне правдоподобным.
Стоит заметить также, что известный аксиоматический подход [41] к решению задач распределения или дележа следует, быть может, пересмотреть на основе положений динамической теории классических кооперативных игр, поскольку некоторые из известных аксиом, возможно, будут не соответствовать динамической природе рассматриваемой многошаговой модели, а некоторые — не полностью характеризовать динамический процесс достижения совершенного компромисса.
В качестве перспективных направлений исследований следует указать построение аналогов динамической теории классических кооперативных игр для арбитражных схем [18, 24, 27, 41], игр поиска [37] и многокритериальных задач оптимизации [21, 34, 35]. Одним из интересных
117 направлений распространения многошагового подхода может представлять собой и динамический подход к теории нечетких кооперативных игр [17, 53].
Актуальными, в связи с возможными приложениями к экономике, будут являться пересмотренные в рамках динамической теории классических кооперативных игр задачи исследования модели рынков, модели обмена [1, 42, 53, 61], модели поведения фирм на рынке [47], модели внутрифирменной организации [2] и другие различные модели экономического взаимодействия [25].
Касаясь дальнейшего распространения динамического подхода, отметим, что на основе этого подхода интенсивно развивающаяся в настоящее время теория кооперативных дифференциальных игр [8, 22, 38, 40, 50] также могла бы найти одно из направлений своего развития.
1. Алипрантис К., Браун Д., Бёркеншо О. Существование и оптимальность конкурентного равновесия. — М.: Мир, 1995. — 384 с.
2. Аоки М. Фирма в японской экономике. — СПб.: Лениздат, 1995. — 431 с.
3. Ашманов С.А. Линейное программирование. — М.: Наука, 1981. — 340 с.
4. Ашманов С.А., Тимохов A.B. Теория оптимизации в задачах и упражнениях. — М.: Наука, 1991. — 446 с.
5. Берж К. Общая теория игр нескольких лиц. — М.: Гос. Изд.-во Физ.-Мат. Лит., 1961. — 128 с.
6. Бондарева O.A. Некоторые применения методов линейного программирования к теории кооперативных игр. — Проблемы кибернетики, 1963, №10. — С. 119-140.
7. Бьюкенен Дж. Сочинения. — М.: Таурус Альфа, 1997. — 560 с. — (Нобелевские лауреаты по экономике, Т.1).
8. Вайсборд Э.М., Жуковский В.И. Введение в дифференциальные игры нескольких лиц и их приложения. — М.: Советское радио, 1980. — 304 с.
9. Васецов М.Е. К вопросу о совершенности двух принципов оптимальности в кооперативных играх // Процессы управления и устойчивость: Труды XXIX научной конференции. — СПб.: НИИ Химии СПбГУ, 1998. — С. 300 308.119
10. Васецов М.Е., Чистяков C.B. Об одном классе квазисовершенных принципов оптимальности в классических кооперативных играх. Деп. в ВИНИТИ, №3352-В97, от 17.11.97.
11. Васецов М.Е., Чистяков C.B. О некоторых квазисовершенных принципах оптимальности в кооперативных играх // Вестн. С.Петербург. ун.-та. Сер. 1. 1998. Вып. 4. (№22).
12. Васильев Ф.П. Численные методы решения экстремальных задач.1. М.: Наука, 1980. — 552 с.и
13. Вилкас Э.И. Оптимальность в играх и решениях. — М.: Наука, 1990. — 256 с.
14. Воробьев H.H. Теория игр для экономистов-кибернетиков. — М.: Наука, 1985. —■ 272 с.
15. Гавурин М.К., Малоземов В.Н. Экстремальные задачи с линейными ограничениями. — JL: Изд-во ЛГУ, 1984. — 176 с.
16. Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. — М.: Наука, 1972. — 368 с.
17. Демьянов В.Ф., Рубинов A.M. Основы негладкого анализа и квазидифференциальное исчисление. — М.: Наука, 1990. — 432 с.
18. Дюбин Г.А., Суздаль В.Г. Введение в прикладную теорию игр.1. М.: Наука, 1981. — 336 с.
19. Ильин В.А., Позняк Э.Г. Основы математического анализа. 4.1.1. М.: Наука, 1982. — 616 с.
20. Карлин С. Математические методы в теории игр, программировании и экономике. — М.: Мир, 1964. — 840 с.
21. Кини P.JL, Райфа X. Принятие решений при многих критериях: предпочтения и замещения. — М.: Радио и связь, 1981. — 560 с.
22. Клейменов А.Ф. Неантагонистические позиционные дифференциальные игры. — Екатеринбург.: Наука, 1993. — 185 с.120
23. Кулаковская Т.Е., Наумова Н. И. Некоторые методы нестатистического анализа социологических и экспертных данных // Сб. Математические методы в социально-экономических исследованиях.
24. СПб.: ТОО ТК "Петрополис", 1996. — С. 79-99.
25. Кукушкин Н.С., Морозов В.В. Теория неантагонистических игр.
26. М.: Изд-во МГУ, 1984. — 104 с.
27. Левин М.И., Макаров В.Л., Рубинов A.M. Математические модели экономического взаимодействия. — М.: Физматлит, 1993. — 376 с. — (Теория и модели системного анализа).
28. Линейные неравенства и смежные вопросы. Сб. Статей под редакцией Г.У. Куна и А.У. Таккера. — М.: ИЛ, 1959. — 472 с.
29. Льюс Р.Д., Райфа X. Игры и решения. — М.: ИЛ, 1961. — 642 с.
30. Мак-Кинси Дж. Введение в теорию игр. — М.: Физматгиз, 1960.420 с.
31. Мулен Э. Теория игр с примерами из математической экономики.1. М.: Мир, 1985. — 200 с.
32. Мулен Э. Кооперативное принятие решений: Аксиомы и модели. — М.: Мир, 1991. — 464 с.
33. Нейман Дж. фон, Моргенштерн О. Теория игр и экономическое поведение. — М.: Наука, 1970. — 709 с.
34. Обен Ж.-П., Экланд И. Прикладной нелинейный анализ. — М., Мир, 1988. — 510 с.
35. Оуэн Г. Теория игр. — М.: Мир, 1971. — 232 с.
36. Подиновский В.В., Гаврилов В.М. Оптимизация по последовательно применяемым критериям. — М.: Советское радио, 1975. — 192 с.
37. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. — М.: Наука, 1982. — 256 с.121
38. Партхасаратхи Т., Рагхаван Т. Некоторые вопросы теории игр двух лиц. — М.: Мир, 1974. — 296 с.
39. Петросян JI.A., Гарнаев А.Ю. Игры поиска. — СПб.: Изд.-во СПбГУ, 1992. — 216 с.
40. Петросян JI.A., Данилов H.H. Кооперативные дифференциальные игры и их приложения. — Томск.: Изд.-во Томск, ун-та, 1985. — 276 с.
41. Петросян JI.A., Зенкевич H.A., Семина Е.А. Теория игр. — М.: Высш. шк., Кн. дом "Университет", 1998. — 340 с.
42. Петросян JI.A., Томский Г.В. Динамические игры и их приложения. — JL: Изд.-во Ленингр. ун-та, 1982. — 252 с.
43. Печерский C.JL, Соболев А.И. Проблема оптимального распределения в социально-экономических задачах и кооперативные игры.1. JL: Наука, 1983. — 176 с.
44. Розенмюллер И. Кооперативные игры и рынки. — М.: Мир, 1974.160 с.
45. Рокафеллар Р. Выпуклый анализ. — М.: Мир, 1973. — 472 с.
46. Смирнов Р.О.,Чистяков C.B. О механизме размещения государственного заказа на конкурсной основе // Вестник ЛГУ. Сер. 5, 1989. Вып.4. (№26).
47. Современное состояние теории исследования операций // Под ред. H.H. Моисеева. — М.: Наука, 1979. — 464 с.
48. Схрейвер А. Теория линейного и целочисленного программирования. Т. 1. — М.: Мир, 1991. — 360 с.
49. Тироль Ж. Рынки и рыночная власть: Теория организации промышленности. — СПб.: Экономическая школа, 1996. — XLII + 745 с.
50. Федоров В.В. Численные методы максимина. — М.: Наука, 1979.280 с.122
51. Чистяков С.В. Динамический аспект решения классических кооперативных игр // Докл. АН. — 1993. — Т. 330, №6. — С. 707-709.
52. Чистяков С.В. О построении сильно динамически устойчивых решений кооперативных дифференциальных игр // Вестник ЛГУ. Сер.1, 1992. Вып. 1. (№1).
53. Чистяков С.В. Процессы управления в условиях конфликта и неопределенности // Дис. . докт. физ.-мат. наук. СПб. 1993.
54. Banzhaf J. F. Weighted voting doesn't work: a mathematical analysis // Rutgers Law Rev. — 1965. — V. 19 — R 317-343.
55. Billot A. Economic Theory of Fuzzy Equilibria. — Springer-Verlag, 1992. — 167 p.
56. Bird Ch. A Class of Convex Nuclei Solution Concepts From Difference In Coalition Excesses // SIAM Journal of Applied Mathematics. — Vol. 29, No. 3, November 1975. — R 503-510.
57. Borch K. Application of Game Theory to some Problems in Automobile Insurance // The ASTIN Bulletin. — 1962. — Vol. 2, No 2. — R 208-221.
58. Chistykov S.V., Vasetsov M.Y. Quasiperfect Optimality Principles for Classical Cooperative Games // Game Theory and Economics. N.N. Vorob'ev memorial conference. June 27-30, 1996. Abstracts. — P. 11.
59. Davis M., Maschler M. The kernel of a cooperative game // Naval Res. Log. Quart., 1965, Vol.12. — P. 223-259.
60. Driessen Т., Muto S., Nakayama M. A Cooperative Game of Information Trading: The Core, the Nucleolus and the Kernel // ZOR Methods and models of Operations Research. — 1992. — No 36. — P. 55-72.
61. Gillies D.B. Solution to general non-zero games // Contributions to the theory of games. — V. IV, Ann. Math. Studies., 1959. V. 40. — P. 48-85.123
62. Ichiishi T. Comparative Cooperative Game Theory // International Journal of Game Theory. — 1990. — Vol. 19, Issue 2. — P. 139-152.
63. Ichiishi T. Game Theory for Economic Analysis. Academic Press. NY, 1983.
64. Kohlberg E. On the nucleolus of a characteristic function game // SIAM Journal of Applied Mathematics. — Vol. 20, No. 1, January 1971. — P. 62-66.
65. Rabie M. E. A note an exact games // International Journal of Game Theory.-1981. V10, No 3/4. — P. 131-132.
66. Schmeidler D. Cores of Exact Games, I. // Journal of Mathematical Analysis and Applications. — No 40. 1972. — P. 214-225.
67. Schmeidler D. The nucleolus of a characteristic function game // SIAM J. Appl. Math. — 1969. V.17. — P. 1163-1170.
68. Shapley L.S. A value for n-person games // Contributions to the theory of games. — V. 11; Ann. Math. Studies. V 28. — Princenton: Princenton Univ. Press, — 1953. — P. 307-318.
69. Shapley L.S. Cores of convex games // International Journal of Game Theory. — 1971. No 1. — P. 11-26.
70. Shapley L.S. On balanced sets and cores // Naval Res. Log. Quart. — 1967. — V. 14. — P. 453-460.
71. Sharkey W.W. Cooperative Games with Large Cores // International Journal of Game Theory. — 1982. — 11. No 1, 2. — P. 175-182.
72. Walkup, Wets. Lifting projections of convex polyhedra // Pacific J. Math., — 1969. — No. 28. — P. 465-475.
