Введение
Актуальность проблемы. Основным предметом изучения в диссертационной работе являются динамические кооперативные игры, впервые рассмотренные Л.А.Петросяном [10, 13, 14]. Различным аспектам теории динамических кооперативных игр посвящены работы [6, 9, 15, 16, 18, 21, 22, 41, 33, 42, 53].
Теория динамических кооперативных игр отличается множественностью принципов оптимальности, привнесенных из классической теории игр с трансферабельной полезностью [5, 19, 24, 26, 30, 46, 47, 49]. Так же, как и в теории неантагонистических дифференциальных игр, использование принципов оптимальности из статической теории приводит к противоречиям, возникающим из-за потери динамической устойчивости выбранного решения. Впервые это было замечено в [10, 11]. Динамическая устойчивость решения означает, что любой отрезок оптимальной траектории определяет оптимальное движение относительно соответствующих начальных состояний. Отсутствие динамической устойчивости приводит к возможности отказа от ранее принятого плана действий в некоторый текущий момент. В связи со сказанным при исследовании динамических кооперативных игр важное значение имеет построение динамически устойчивых решений. В работе [50] был представлен принцип оптималь-
2
ности, предлагающий динамически устойчивое решение из (7-ядра для дифференциальных кооперативных игр и построена процедура распределения дележа (ИРЛ) [41], обеспечивающая неотрицательные выплаты агентам вдоль оптимальной траектории. Однако, при использовании аналогичных процедур в многошаговых ТП-играх мы можем столкнуться с отрицательными платежами на некотором шаге. Это, фактически, означает, что игроки вынз^ждены возвращать часть заработанных сумм для сохранения динамической устойчивости решения. Последнее при водит к необходимости построения ПРД, учитывающих дискретный характер выплат выигрышей игрокам, специально для многошаговых игр.
Основой изучения свойств решений динамических кооперативных игр являются аналогичные свойства этих решений в статической теории. В разное время этой теме были посвящены работы (4, 17, 25, 26, 34, 38, 40, 43] и многие другие.
Одним из важных свойств решений кооперативных игр является свойство редуцированной игры (20, 23, 26, 28, 29, 31, 35, 36, 39, 45, 48, 51, 52, 54], или согласованность. Согласованность решения означает, что при выходе из исходной игры некоторой коалиции игроков оставшиеся мог}гт придерживаться в редуцированной игре того же решения, что и в начальной, при этом значения индивидуальных выигрышей останется прежним. В данной работе вводится подобное понятие для динамических кооперативных игр, устанавливаются условия динамической согласованности для дележей из 5С-ядра, предлагается процедура регуляризации динамически неустойчивого решения с помощью редукции исходной игры.
Цель работы заключается в исследовании реализуемости во вре-
3
мени решений многошаговых кооперативных игр, изучении свойств селекторов С-ядра классических и динамических кооперативных игр, построении процедур перераспределения выигрышей в многошаговых кооперативных играх.
Научная новизна. В диссертационной работе впервые были установлены необходимые и достаточные условия динамической устойчивости решений из б'С’-ядра для многошаговых кооперативных игр, предложены процедуры перераспределения доходов для многошаговых кооперативных игр, введено понятие динамической согласованности принципа оптимальности, исследованы процедуры регул я ри-зации динамически неустойчивого решения из С-ядра с использованием редукции исходной игры, построена кооперативная модель реализации механизмов Киотского протокола, направленного на снижение выбросов парниковых газов. Основные результаты работы опубликованы в [7, 8, 27, 56, 55].
Практическая ценность. Предложенные в диссертации способы перераспределения суммарного дохода игроков в многошаговых кооперативных играх могут быть использованы в многошаговых моделях экономики, экологии.
Апробация работы. Результаты диссертационной работы докладывались на семинарах кафедры Математического моделирования энергетических систем факультета Прикладной математики — процессов управления Санкт-Петербургского государственного университета (далее — ПМ-ПУ СПбГУ), семинарах Центра теории игр при факультете ПМ-ПУ СПбГУ, научных конференциях факультета ПМ-ПУ СПбГУ «Процессы управления и устойчивость» (2001, 2002 гг.), Международном симпозиуме по динамическим играм и
4
приложениям «1800-2002» (Санкт-Петербург, 2002 г.), Международной конференции «Теория игр и приложения» «ІСМ-ОТА 2002» (Китай, 2002 г.).
5
Глава 1
Селекторы С-ядра в классических кооперативных играх
Исследование свойств решений кооперативных игр с трансферабель-ной полезностью является одной из задач современной теории игр. С тех нор, как фон Нейман и Моргенштерн [37] ввели понятие игры в форме характеристической функции (кооперативной игры), было предложено множество принципов оптимальности [2, 3]. Наиболее известными и популярными решениями являются вектор Шепли [46] и ЛГ-ядро [47]. Вектор Шепли в общем случае не принадлежит множеству недоминируемых дележей (С-ядру) [30], что делает его уязвимым но сравнению с ЛГ-ядром. Однако, и ЛГ-ядро не является достаточно удобным в связи с трудностями вычисления. В этой главе будет рассмотрено многоточечное решение 5С-ядро [53], дающее возможность относительно просто строить селекторы С-ядра.
Выбор решения для конкретной экономической, политической, экологической или другой модели можно облегчить, установив, каким именно принципам «равенства», или «справедливости», должны отвечать те дележи, которые будут предлагаться этим решением.
6
Б этой главе будут изучены такие свойства дележей из 5(7-ядра, как индивидуальная рациональность, Парего-оптимальность (эффективность), анонимность (симметричность в смысле перестановки игроков), стратегическая эквивалентность, свойства нулевого игрока и равнозначных подходов («равным агентам — поровну»), линейность, согласованность.
1.1 Основные понятия и определения
Приведем определения основных терминов, которыми будем пользоваться в этой части работы.
Определение 1.1.1. Кооперативная игра с трансферабельной полезностью (ТП-игра) — это пара (К',и), где N — это конечное множество игроков, а и : 2 —> К“1* — характеристическая
функция, удовлетворяющая д(0) = 0. Непустое подмножество 5 множества N называется коалицией (обозначается 5 С М).
Определение 1.1.2. Решением ф ТП-игры (П,и) будем называть множество векторов выплат с неотрицательными координатами <£(ЛГ, и) С К.+ таких, что т* < и(Н) для любого
х Е ф(П,и).
Определение 1.1.3. Говорят, что решение ф удовлетворяет свойству индивидуальной рациональности (ИР), если для любой игры (N>0) выполняется неравенство т* > ^({г}) для каждого игрока г Е N и произвольного вектора х Е ф(ГТ,и).
Определение 1.1.4. Решение ф называется оптимальным по Парето (эффективным.) (ПО), если для любой игры (АТ, г;) и любого
7
вектора х £ ф(М,и) верно 2*€лгж* = ^(ЛГ).
Определение 1.1.5. Говорят., что решенье ф отвечает•. аксиоме ”болвана” (АБ), если в произвольной игре (А, г») при любом выбранном векторе х £ ф(А, г>) ”болван” получает свой гарантированный выигрыш. "Болваном” называется игрок г £ N, который в любую коалицию вносит лишь значение ^ ({?’}), т.е.
и(5) +^({'0) = г/(Й и {г}). У5 С АГ \ {«}-
Определение 1.1.6. Говорят, что решенье ф отвечает аксиоме нулевого игрока (АН), если в ТГГигре (А, и) при любом выбранном векторе х £ ф(М,ь) нулевой игрок получает нулевой выигрыш. Нулевым игроком называется игрок I £ N, для которого верно следующее: и {г}) = и(Б), У5 С N \ {г}.
Определение 1.1.7. Решение ф называется удовлетворяющим аксиоме анонимности (симметрии) (СИМ), если для любой игры (б/, и) верно следующее: при г 6 А, х £ ф(М,и) ив — перестановке на множестве N справедливо Ох £ ф(!\гуви). Здесь игра (А,вг:) и вектор Ох определяются соответственно (0и)(05) := г'(5) для всех 5 С А и (0х)(9г) := х(г) для всех г £ N.
Определение 1.1.8. Решение ф называется стратегически эквивалентным (СЭК), если для любой игры (А, и), для которой верно ф(N, и) ф 0, произвольного вещественного числа а > 0 и вектора (5 £ 1Е1А выполняется <£(А, аг> 4/3)(5) = ая(5) + ^2jeSPj для всех 5 С А. Здесь игра (А, см -1- /3) задается следующим образом: (аи 4- Р)(Б) = аг?(5) 4 @1 ^ля 6сех $ С N.
8
Определение 1.1.9. Решение ф удовлетворяет свойству равнозначных подходов (РЛ), если для игроков 6 N таких, что и(Л\Л) = ?;(5Ц7) С ДО\{Ь7*Ь веРН0 равенство ф{(М, и) = ф$(Ы,у).
Определение 1.1.10. Решение ф удовлетворяет, свойству линейности (ЛИН), если для любых ТП-игр (И, у) и (/V, и) и постоянной с € 1Я. выполняются условия
(1) ф^,и + и)=ф(М,и) + ф(М,и),
(2) ф(М, су) = сф(.Ъ\и),
если (и + и)(5) = г'(5) + гг(5) и си(в) = с • ^(5), У5 С N.
1.2 Свойства основания 5С-ядра и большого 5С-ядра
Рассмотрим следующую задачу линейного программирования для классической кооперативной игры (Л^,г>):
гаш£> (1-1)
при условии & > Ц5), V# С N, 5 Ф N. (1-2)
Обозначим через Х(,(ЛГ,у) множество решений задачи (1.1), (1.2). В
случае, когда это не приводит к неоднозначности, вместо
Х°(Лг,г;) будем писать Л'0.
9
Определение 1.2.1. Множество SC(v,t°) = Ь = (6,... ,in) I ti > = v(N)
= j^(6,..,wi(4°+« (»(*)-£«?] >
где а- = (аь... ,an): > О, У^сц = 1; < v(N) >
iex i€N )
называется SC-ядром кооперативной игры (iV, г') относительно точки £ X°(N,v), а X{)(N,v) — основанием SC-ядра.
Определение 1.2.2. Большим SC-ядром ТП-игры (ЛГ,д) называется объединение всех SC-ядер этой игры
GSC(N,v) = U SC{ v,£°).
е°€Х°(ЛГ,«)
SC-ядро и большое SC-ядро были впервые введены в [53]. Там же была показана эквивалентность условий сбалансированности кооперативной игры и непустоты ее большого SC-ядра.
Обратимся теперь к свойствам основания SC-ядра. Сначала покажем анонимность элементов из множества Xй.
Теорема 1.2.3. Основание SC-ядра сбалансированной игры удовлетворяет, аксиоме симметрии.
Доказательство. Необходимо показать, что для любого решения ЗЛП (1.1), (1.2) £и € XU(JV, v) и любой перестановки в игроков из множества N верно
X°(9N,9v).
10
У5сЯ\{г,Л, 5#АГ\{г,Л-
Докажем это утверждение для перестановки 0(г,у), которая меняет местами игроков г и у. Запишем систему ограничений (1.2) в виде
Е*65б+^>«(5и{0)
Е^6 + ^>г-(5и{Д)
Е*65 6 + & + С., > Ч5 и {*> Л)
и применим к ней 0{г,_?);
Е^Ч- > Ч*Л
Е*е5& + & > <Ч5 и {Л) = »('З' и я Е *<=$& + 6ч ^ и {Л) = Ч5 и О Е*е$6 + & + & ^ 0гг(5' и {*> Л) = Ч5 и {*• Л).
У5С^\{*,Л, 5#^\{*,Л.
Отсюда очевидно, что для всех £° € А'°(ЛГ,г;) и 0£° € Х°(0Л',бд) выполняются равенства
Л = &, у*е^\{»,л,
Л = Л„ л = Л-
Любой перестановки можно добиться попарными перестановками игроков, следовательно, теорема доказана.
Следующие утверждения непосредственно вытекают из Теоремы 1.2.3.
Следствие 1.2.4. Основание БС-ядра удовлетворяет свойству равнозначных подходов.
Доказательство. Пусть игроки г,; 6 N удовлетворяют условию г>(5иг) = у(Биз') С \ {г, 7}. Покажем, что равенство =
11
- Київ+380960830922