Многошаговые игры с полной информацией и переменным коалиционным разбиением тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Санкт-Петербургский государственный университет

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

МАМКИНА Светлана Игоревна

Многошаговые игры с полной информацией и переменным коалиционным разбиением.

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

кибернетика "

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

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

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

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

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

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

профессор Захаров Виктор Васильевич

кандидат физико-математических наук, доцент Денис Вячеславович Кузютин

Ведущая организация : Институт прикладных математических

исследований Карельского научного центра Российской академии наук

Защита диссертации состоится « 26 » октября 2005 г. в_часов на

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

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

Автореферат разослан « »_2005 года.

Ученый секретарь

Диссертационного Совета, ^

доктор физ.-мат. наук, профессор /) ^^ ВФ' Горьковой

JOO^L, 236 ¿¿2<Г

Общая характеристика работы

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

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

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

Исследованием статических коалиционных игр также занимались Р.Ауман, М. Машлер, С. Харт и М. Курц и др. При этом в качестве принципа оптимальности дано определение (^-устойчивой конфигурации.. H.H. Воробьев ввел более общее понятие (р -уст э®ЧИВости7 " köTjpiJt^ ^ грн

•''FKA

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

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

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

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

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

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

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

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

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

Практическая ценность. Работа носит теоретическую направленность. Полученные результаты представляют теоретический и практический

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

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

1. Построение многошаговой игры с переменным коалиционным разбиением, и построение принципов оптимальности для многошаговой игры с переменным коалиционным разбиением.

2. Построение класса всех абсолютных равновесий по Нэшу в многошаговых играх с полной информацией. Выделение единственного абсолютного равновесия, определенного в работе как индифферентное равновесие.

3. Выделение единственно решения для многошаговой игры с переменным коалиционным разбиением.

4. Исследование позиционной состоятельности, и индивидуальной секвенциальной рациональности предложенных принципов оптимальности и проведение регуляризации с использованием процедуры распределения дележа.

5. Формулировка и доказательство теорем о реализуемости предложенных принципов оптимальности в некотором квазипоследовательном коррелированном равновесии в игре с переменным коалиционным разбиением.

Апробация работы. Результаты работы докладывались на 11 -ом международном симпозиуме по динамическим играм и приложениям ISDG2004 (Аризона, США), на 1-ом семинаре Китайского отделения международного общества динамических игр (WCC2004) (Qingdao, Qingdao University, Китай), 40-й Московской международной конференции по "Исследованию операций" (ORM2004), на XXXV научной конференции

"Процессы управления и устойчивость" (Санкт-Петербург), на семинаре центра теории игр при факультете ГТМ-ГТУ СПбГУ.

Публикация работы. Материалы исследований опубликованы [1-6].

Структура и объем работы. Диссертационная работа состоит из введения, 4 глав (13 параграфов), списка используемой литературы. Общий объем диссертации - 104 страницы. Список используемой литературы включает 47 наименований. Работа содержит 3 рисунка.

Основное содержание работы

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

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

В §1.1 дается определение динамической игры Г с переменным коалиционным разбиением на конечном древовидном графе и дано детальное описание рассматриваемой игры.

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

Пусть # = {1,...,п} - множество игроков. Под разбиением множества игроков N будем понимать множество множеств Ак = {SJ , таких что п = 0; у ^ ('; = N. Множество всех допустимых разбиений множества N обозначим через Д .

Определение 1. Позиционной игрой п лиц с переменным коалиционным разбиением Г( х0) называется дерево игры К, на котором заданы:

1. Разбиение множества вершин (позиций) на п + 2 множества Р1,Р2,...,РГ1,Р„¥], Р„г, называемое разбиением на множества очередностей. Позиции х е Р! называются личньми позициями г -го игрока, для / = /,..., и; позиции х е Рпл1 позициями случайного хода; позиции * е Рп+2 - окончательными позициями (для х е Рп+2 и только для них имеет место г(х) = 0 ). Предполагается, что х0 е .

2. Для каждой из вершин х разбиение х) сг А множества игроков N такое, что

Г А(х) = Цу), Чу 6 г{х), если х е Рп+] \Зуе2(х):А(х)$А(у), если хеРп+!

3. Для каждого уе2(х) = {у1,...,у„/,хеРп+, вероятностное распределение

Рх(У1)-—Рх(Уг)> Рх(Ук)-^, к=1,...,г, I

уе2(х)

4. На множестве позиций хеР, и и , / = /,.,« набор вещественных чисел к(х) = (к/х),. ,(К(Х))- Числа \(х), ¡=1,..,п, называются мгновенными выигрышами игроков I е N.

Игра начинается в позиции х0 е Рл+;, в которой задано некоторое коалиционное разбиение А(х0)с:А. В позиции х0 ходит случай и, в соответствие с вероятностями, определенными условием 3 определения 1 в позиции х0, выбирает альтернативу х; е 2(х0), которой соответствует некоторое коалиционное разбиение А(Х1) с: Д. Предположим, что х1 еР . ..

Тогда в позиции х, ходит игрок ¡(х,) и выбирает альтернативу Х2 е Z(/лгу), действуя в интересах коалиции его содержащей, в соответствии с реализовавшимся коалиционным разбиением в позиции х0 е Рп1 .Если же

XI е Р„+/, т.е. в позиции X; ходит случай, то в позиции х; альтернатива х: выбирается в соответствии с вероятностями, определенными условием 3 определения 1 для позиции Х2. Выбранной таким образом позиции Х2<=.2(Х1) соответствует коалиционное разбиение Д^дг^сД, которое может совпадать с коалиционной структурой в х;, а может и нет и т.д.

Если на шаге к, хк гР^иР^, то в позиции хк ходит игрок Цхк) и выбирает альтернативу хы е2(хк), действуя в интересах коалиции его содержащей. Если на к -ом шаге игра попадает в позицию случайного хода, т.е. € Р^,, то в позиции хк альтернатива хы выбирается в соответствии с вероятностями, определенными 3 определения 1 для позиции хк. Выбранной таким образом позиции хы & 7,(хк) соответствует коалиционное разбиение А(хк^)сА, которое может совпадать с коалиционной структурой в хк, а может и нет.

Игра продолжается до достижения некоторой позиции со е . Это происходит за конечное число шагов, т.к. дерево К конечно.

В §1.2 предложен алгоритм построения принципа оптимальности РМБ -вектора, основанного на равновесии по Нэшу для игроков коалиций и на аналоге вектора Шепли (кооперативный принцип оптимальности) для игроков внутри коалиций.

Предположим, что длина игры Т(х0) равна Т + 1. Рассмотрим разбиение множества всех позиций дерева игры К(х0) на Т + 1 множество XГ1,Х,,...,Х,:Хт ={х0}, где множество X, состоит из позиций, достигаемых из начальной позиции в точности за T — t ходов. Обозначим позиции, принадлежащих множеству Х1, через у,, Г = 0.....Г.

На каждом из множеств X,, Г-0,...,Т строятся функции г': X, -» й*,

имеющие смысл ожидаемого (прогнозируемого) выигрыша игрока г, г = 1,...,п в позиции у, е X,, при условии, что игроки действуют в соответствии с предложенным алгоритмом. Сперва рассмотрим случай Тогда

^уйг'Гу:!\кХу,)'если (о

I МуЛ если у, е

где ^¡''(у,-!) функции построенные на множестве Xа позиции у1_1 е Z(y,), выбираемые в вершине у, определяются из условий:

тах I Г'(у)= I гГ'(~у,-,)> (2)

к(у,)

если у, <£ и . Формула (2), вообще говоря, определяет вершину неоднозначно, что в свою очередь порождает не единственность решения.

Пусть теперь у1 е Так как А (у,) может и не совпадать с Л(у,_г), уeZ(y!),то нам необходимо выделить выигрыши игроков из коалиционных выигрышей, т.е. определить некоторый дележ суммарного

и

выигрыша для каждой коалиции {У,.] ■ Выберем произвольно

коалицию ^ (у,_1 )еА(у,_,). Рассмотрим кооперативную игру 18к (ун1) | лиц С(у,_1,5к(у1_,)). Выигрыш наибольшей (8к( у,^)) коалиции в кооперативной игре у1_1, ( у)) полагаем равным:

*Уы.й*(Уы))= Е Г1 (У,-,)- (3)

У,-!)

Способ построения характеристических функций приведен в §1.3. В качестве оптимального дележа коалиционного выигрыша у,_,)).

мы рассматриваем вектор Шепли с компонентами (Як (у,_,)), у,_,), где £ (\ (.У,.,)) = \>(У,-,, ^ (У[—})), При этом, для определения

компонент вектора Шепли 81г1(Зк(у1_!)), /'сЗк(у\_1) пользуемся х.ф. К с Зк(у,_,), Б^у^ьЦу,^).

Аналогично, находим дележ и для других коалиций из {Ыyt_,)\Sk(у,_,)}. Вводим PMS вектор по формуле:

PMS{y,)= I pjy^mts.iy^h,Су,), (4)

где SPMS, (у,_, ) = Sh/Sk ( у,)), i&Sk(y,_,), а ру (}>,_, ) вероятность реализации альтернативы у,_1 е Z(y,). Полагаем:

г,'{у,) = Ш,{у,), (5)

Заметим, что из-за возможного наличия случайного хода предлагаемая схема выбора не определяет путь (дугу) однозначно, и мы получаем некоторое поддерево. Назовем это поддерево пучком путей. В случае, если в у,не имел место случайный ход (у, £Р„+,), то "пучок" будет состоять из единственной дуги (или одной вершины, если у, е Р„+2).

Спускаясь по дереву игры Г(х0) от позиций у() е X(J х0 к начальной позиции ут =х1) и последовательно определяя выборы игроков на о множествах Xt, t—o,...,T, мы построим "пучок" путей, который реализуется в игре Т(х0) и найдем PMS(xg) для всей игры Г(х0). Будем называть этот "пучок" путей оптимальным пучком в Г(х0), реализованным в результате предложенного алгоритма.

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

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

В §1.4 приведен пример построения PMS -вектора.

Во второй главе с целью выделения единственного оптимального пучка и соответственно единственного PMS -вектора для игры с переменным

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

В §2.1 построен класс абсолютных равновесий по Нэшу в стратегиях поведения для многошаговых игр с полной информацией. Рассмотрим позиционную игру п лиц с полной информацией (?(хв). Пусть Л^ = {/,..., I,.. .73} множество игроков.

Определение 2. Ситуация равновесия по Нэшу в стратегиях поведения

((Ь,( ).....Ьп (■)) = Ь(-) называется абсолютным равновесием в игре 0(хГ)), если

ее сужение в любой подыгре С(х) является ситуацией равновесия в этой подыгре.

Рассмотрим множество позиций X,, состоящее из позиций, достигаемых из начальной позиции х0 в точности за Т - ? ходов. Обозначим множество

позиций, принадлежащих X,, через х,, ¡ = 0.....Т.

В каждой из позиций х, еХп 1=0, ,,Т зададим функции.

Г й,(*,), если X, е Рп„

н:(х,)= £ рХ:(у)НГ'(у), если х,*Рп+1 - (6)

\У<&Цх,)М

2,и,)(х,)=а^тахН;'{у), (7)

у&М

где Я,"' (у ) функции построенные на множестве Х,_,. Стратегии Ьг (•) строим в позиции х1 е Р) , /' е N по правилу:

X,.,, е тах если \2,(х^{хА = 1

*>■(■)= I ^ ) ' (8)

Р,, = К (у). У£ ) (х,)). если ¡г,(х1 )(х,)|>/ в (6) и (7) X Р„(у)*°-

Обозначим через Ьх' (•) = (/>/' (■)) ситуацию в подьпре 0(х,),

построенную на первых I шагах алгоритма.

Продолжая спускаться по дереву игры О(х0) к начальной позиции х0 и последовательно определяя выборы игроков в оставшихся множествах Хт, г = ? + /,..„Г, мы построим ситуацию Ъч(■) = (;),-.-,Ь*°(■))= Ь (■), и соответствующие выигрыши, реализуемые в игре С(х0).

Теорема 1. Ситуация Ь(-) = {Ь, (■).....Ьп (•)) образует ситуацию абсолютного

равновесия по Нэшу в О(х0).

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

Теорема 2. Любая ситуация абсолютного равновесия по Нэшу в О(х0) может быть получена в результате реализации построенного алгоритма при соответствующим образом выбранных вероятностных распределениях

хер, 2»)=/. (9)

В §2.3 среди всего класса абсолютных равновесий по Нэшу выделено единственное равновесие, определенное в диссертационной работе как "индифферентное" равновесие, отражающее "безразличие" игрока г'(х) при выборе альтернативы у е 2^х )(;е ). В позициях х е К(х0), в которых принимающему решение игроку фс) безразлично, какую из альтернатив у е 2'ух ) выбрать, т.е. |2,(д. | > 7, предпишем игроку г'(х) выбрать вершины у е ) с равными вероятностями, т.е. вероятность выбора

каждой из альтернатив ук е 2^ )(д: ), к = 1, в позиции хеК(х0)

1

равна19~П'

\2лЛх\

В §2.3 приведен пример построения индифферентного равновесия.

В третьей главе рассмотрена модифицированная игра с переменным коалиционным разбиением и на основе индифферентного равновесия

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

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

В §3.2 для модифицированной игры с переменным коалиционным разбиением предложен принцип оптимальности, приводящий к единственному решению- PMS вектору. Выведены основные функциональные уравнения для построения этого единственного решения.

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

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

т.е. PMS и PMS вектора доопределяются в каждой из вершин оптимального пучка.

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

Определение 3. Будем говорить, что PMS вектор является позиционно состоятельным, если

PMS ,(!,) =

PMS,(z,_i) + h,(z,), если z, <2 Pnrl uPn.

X Pi, i1,-! )PMS- ) + К (z,), если z, e h\zt), если

для всех t = T,...,l, zt_, eZ(z,).

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

A,(z,) с целью обеспечения позиционной состоятельности PMS вектора. В каждой позиции оптимального пучка Z вводим специальное правило пошаговых выплат ßt{z,), z, е Z t = О,...,Т.

ш-

PMS, (z,) - PMS, (z,_,), если z, £ P„+I u Pn

PMS, (z,) - если z,ei>„

/14.2

n+l

PMS, (z,), еш i = ö

__w _

Обозначим через B,(zm) математическое ожидание сумм

к=0

i = l,...,n, вычисленных вдоль некоторого фиксированного отрезка траектории оптимального пучка fm = {zm,...,z0}, z0ePnl2 и z,=x0, где /длина оптимального пучка. Аналогичным образом вводится позиционная состоятельность PMS вектора и пошаговые выплаты ßt (z,), z, е Z t = 0,. ,,T. Справедлива теорема:

Теорема 3. B,{z) = PMS,(z) и B,(z) = PMSt(z), zeZ, 1 = 1.....п

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

Определение 4. Пусть z принадлежит оптимальному пучку (z е Z). Под

усеченной подыгрой Г(г) будем понимать игру, деревом которой является поддерево подыгры Г(г), состоящее из вершин X(z), обладающих свойством: если zeZ{y), уеРп>!, z£Pn+l и * е ^ f\X(z)^\JPn, 2, хфу,

и (z ~7 )* (.г) = z, то не существует к'< к, такого что (z 'f(x) = y'ePn+ir\X(z), (z~' f(x) - множество тех позиций, из которых

за к ходов возможен переход в позицию х. Выигрыши игроков в окончательных позициях полагаем равными rt (z).

Определение 5. Будем говорить, что PMS вектор секвенциально индивидуально рационален, если имеет место:

M,(x)>v,(i), / = /,...,и

х е X(z) при некотором zeZ.

Теорема 4. PMS и PMS вектора секвенциально индивидуально рациональны.

В §4.4 показано, что PMS и PMS вектора реализуемы в некоторым образом определенной ситуации равновесия в регуляризованной игре с полной информацией и переменным коалиционным разбиением. Определение 6. Ситуация м(-) = (м,(•)<•••. «„(•)) называется квазипоследовательным равновесием в игре с полной информацией и переменным коалиционным разбиением, если ее сужение в каждой усеченной

подыгре r(z), zeZ(y), у е Рпл, является ситуацией равновесия по Нэшу в этой усеченной подыгре.

Теорема 5. PMS вектор реализуем в некоторой ситуации квазипоследовательного равновесия в регуляризованной игре с полной информацией и переменным коалиционным разбиением. Определение 7. Ситуацию в коррелированных смешанных стратегиях мы будем называть коррелированной ситуацией квазипоследовательного равновесия ¡1 в игре с переменным коалиционным разбиением Г, если все ситуации и"(') = (и*(-),...,м*(')), реализуемые с положительной вероятностью в

ситуации [1, являются ситуациями квазипоследовательного равновесия в игре Г.

Теорема 6. PMS вектор может быть реализован в некоторой ситуации коррелированного квазипоследовательного равновесия в стратегиях поведения.

По теме диссертации опубликованы следующие работы:

1. Мамкина С.И., Петросян Л.А. Структура множества ситуаций абсолютного равновесия по Нэшу в играх с полной информацией. Труды XXXV научной конференции "Процессы управления и устойчивость", 2004, С. 639-647.

2. Петросян JI.A., Мамкина С.И. Игры с переменным коалиционным разбиением. Вестник СПбГУ, 2004, Сер 1, Вып. 3, С.60-69.

3. L.A. Petrosjan, S.I. Mamkina. Dynamic Games with Coalitional Structure. J. of Quigdao University, 2004, Vol.17, p. 38-47.

4. L.A. Petrosjan, S.I. Mamkina. New Value for Dynamic Coalitional Games. Proceedings of the 4th Moscow International Conference on Operations Research (ORM2004), 2004, p. 173-175

5. L.A. Petrosjan, S.I. Mamkina. New Value for Dynamic Games with Perfect Information and Changing Coalitional Structure Poceedings of the 11th International Symposium on Dynamic Games and Applications, Tucson Arizona, 2004, Vol. 2, p.1-15.

6. L.A. Petrosjan, S.I. Mamkina. Value for the Games with Changing Coalitional Structure. Game Theory and Applications, 2005, Vol. 10, p.141-152.

Отпечатано копировально-множительным участком отдела обслуживания учебного процесса физического факультета СПбГУ. Приказ № 571/1 от 14.05.03. Подписано в печать 14.09.05 с оригинал-макета заказчика. Ф-т 30x42/4, Усл. печ. л. 1. Тираж экз., Заказ № 251/с 198504, СПб, Ст. Петер! оф, ул. Ульяновская, д. 3, тел. 428-43-00.

РНБ Русский фо]

2007-4 3572

Получено 2 Ч ДЕК 2005

Введение.

Глава 1. Динамическая игра с переменным коалиционным разбиением.и

§ 1.1. Определение динамической игры с переменным коалиционным разбиением.и

§ 1.2. Алгоритм построения решения.

§ 1.3. Построение характеристических функций вспомогательных кооперативных игр.

§ 1.4. Пример.

Глава 2. Структура множества всех ситуаций абсолютного равновесия по Нэшу в играх с полной информацией.

§ 2.1. Абсолютные равновесия в стратегиях поведения.

§ 2.2. Описание всего класса абсолютных равновесий.

§ 2.3. Индифферентное равновесие в позиционных играх с полной информацией.

Глава 3. Построение единственного решения в игре с переменным коалиционным разбиением на основе индифферентного равновесия.

§3.1. Модифицированная игра с переменным коалиционным разбиением.

§ 3.2. Основные функциональные уравнения для построения единственного решения с использованием индифферентного равновесия.бо

Глава 4. Стратегическая устойчивость решений в играх с переменным коалиционным разбиением.

§ 4.1. Распространение решения на все позиции оптимального

ПуЧКа.

§ 4.2. Позиционная состоятельность решений и регуляризация.

§ 4.3. Индивидуальная секвенциальная рациональность решений.

§ 4.4. Квазипоследовательное равновесие и коррелированное квазипоследовательное равновесие в играх с переменным

I коалиционным разбиением.

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

В кооперативных моделях изначально предполагается, что игроки объединяются в большую коалицию, включающую всех игроков, с целью максимизации общего выигрыша. При этом различаются два типа задач: задачи с трансферабельной и нетрансферабельной полезностью. В первом случае речь идет о векторной оптимизации выигрыша, во втором максимизируется сумма выигрышей игроков. Основными принципами оптимальности в кооперативных моделях являются: С-ядро, вектор Шелл и, ЫМ-решение, вектор Банзафа, ядрышко и др. Указанные принципы оптимальности относятся к так называемым «нормативным» принципам. Однако в практических задачах трудно предположить возможность объединения участников конфликта (игроков) в одну большую коалицию с одной стороны, и также является не достаточно реальным предположение о том, что никакая кооперация между игроками невозможна. Поэтому наиболее актуальной является задача, в которой допускается объединение игроков в коалиции, образующих некоторое разбиение всего множества игроков.

Впервые исследованием таких задач занимался Оуэн в 1977 году ([33-34]). Он обобщил понятие вектора Шепли для игр с коалиционными разбиениями, введя так называемый вектор Оуэна-Шепли. При вычислении этого вектора предполагалось, что элементы коалиционного разбиения - коалиции, действуя как игроки, могут объединяться в большую коалицию. И для нахождения выигрышей коалиций использовался вектор Шепли. Далее, внутри каждой коалиции допускалась возможность объединения игроков в подкоалиции, и для нахождения коалиционного дележа использовался вектор Шепли. Таким образом, сперва вектор Шепли применялся на уровне коалиций, принадлежащих коалиционной структуре, для определения выигрышей этих коалиций, а затем вектор Шепли применялся для дележа коалиционного выигрыша. Таким образом, можно утверждать, что коалиционный вектор Оуэна, получался путем двух кратной композиции векторов Шепли.

В 1988 году Ван дер Бринк и Ван дер Лан [42] определили нормализованный вектор Банзафа, который распределяет максимальный суммарный выигрыш игроков пропорционально вектору Банзафа. Этот же подход использовался Ван дер Бринком и Ван дер Ланом в 2005 году году для нахождения решения игры с коалиционным разбиением.

Исследование статических коалиционных игр может быть найдено также в работах [ 1, 2, 20, 27, 30]. Здесь в качестве принципов оптимальности дано определение у/ устойчивой конфигурации. В 1960 г. H.H. Воробьев (см. [6 ]) ввел более общее понятие (р устойчивости, которое в 1967 г. он распространил на смешанные расширения коалиционных игр (см. [7 ]) Имеются и другие принципы оптимальности, для классических коалиционных игр: «класс разумных исходов», «замкнутый исход» и др.

В работе [ 21 ] сделана попытка распространения принципов кооперативной теории на игры с заданной коалиционной структурой.

Подробное обсуждение указанных вопросов можно найти в книгах Э. Вилкаса [3,4 ].

Однако указанные подходы (в частности, предложенный Ван дер Бринком и Ван дер Ланом, также как и подход Оуэна) предполагают возможность объединения элементов коалиционного разбиения в большую коалицию. Но это предположение не может быть во всех случаях приемлемо, поскольку сам факт возникновения коалиционного разбиения и происходит от того, что полная кооперация игроков невозможна. Поэтому более естественным является подход, при котором игра первого уровня между элементами коалиционного разбиения происходит как стратегическая игра, то есть полная кооперация коалиций как игроков не предполагается. В этом случае для этой игры в качестве принципа оптимальности может быть использовано равновесие по Нэшу [31]. А уже на втором этапе выигрыши, полученные в равновесии по Нэшу игроками коалициями, могут распределяться согласно принципам оптимальности кооперативной игры.

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

Справедливости ради следует отметить, что в работе Харшаньи и Зельтена [18 ] предложен метод трассирования для нахождения единственного равновесия по Нэшу в одновременной игре, который, хотя бы в теоретическом плане, позволяет снять проблему единственности в одновременной (статической) игре. Но указанный метод достаточно громоздок и едва ли может быть применен для игр с большим количеством участников.

По-другому обстоит дело в динамических играх с полной информацией. В игре с полной информацией всегда существует абсолютное равновесие по Нэшу в чистых стратегиях ([14,15]). И в данной диссертации нам удалось выделить единственное «индифферентное» равновесие по Нэшу в таких играх. Именно основываясь на этом, мы предложили другой принцип оптимальности для игр с переменным коалиционным разбиением и полной информацией, а именно: для игроков коалиций в качестве принципа оптимальности мы рассматриваем «индифферентное» равновесие по Нэшу, а внутри коалиции осуществляем дележ в соответствии с вектором Шепли. Получившийся в результате такой двухэтапной процедуры вектор выигрышей мы называем pms вектором.

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

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

Таким образом, данная тема является актуальной и ее исследование вносит определенный вклад в развитие теории игр.

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

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

Практическая ценность. Работа носит теоретическую направленность. Полученные результаты представляют теоретический и практический интерес. Основная практическая ценность определяется многочисленными применениями коалиционных игр для моделирования работы парламентов и других 8 общественных организаций, в которых возможно объединение участников в различные партии (коалиции) ([19, 23, 24, 25, 26, 28, 32, 43, 47]). Принципы оптимальности, предложенные в работе, использовались при исследовании более сложных многошаговых игр с изменяющейся коалиционной структурой.

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

1. Построение многошаговой игры с переменным коалиционным разбиением, и построение принципов оптимальности для многошаговой игры с переменным коалиционным разбиением.

2. Построение класса всех абсолютных равновесий по Нэшу в многошаговых играх с полной информацией. Выделение единственного абсолютного равновесия, определенного в работе как индифферентное равновесие.

3. Выделение единственно решения для многошаговой игры с переменным коалиционным разбиением.

4. Исследование позиционной состоятельности, и индивидуальной секвенциальной рациональности предложенных принципов оптимальности и проведение регуляризации с использованием процедуры распределения дележа.

5. Формулировка и доказательство теорем о реализуемости предложенных принципов оптимальности в некотором квазипоследовательном коррилированном равновесии в игре с переменным коалиционным разбиением.

Апробация работы. Результаты работы докладывались на 11-ом международном симпозиуме по динамическим играм и приложениям ISDG2004 (Аризона, США), на 1-ом семинаре Китайского отделения международного общества динамических игр (WCC2004) (Qingdao, Qingdao University, Китай), 4-й Московской международной конференции по "Исследованию операций" (ORM2004), на XXXV научной конференции "Процессы управления и устойчивость" (Санкт-Петербург), на семинаре центра теории игр при факультете ПМ-ПУ СПбГУ. Основные результаты опубликованы в работах [8], [10], [28-31].

Структура и объем работы. Диссертационная работа состоит из введения, 4 глав (13 параграфов), списка используемой литературы. Общий объем диссертации - 104 страницы. Список используемой литературы включает 47 наименований. Работа содержит 3 рисунка.

1. Ауман Р., Дряз A. Coopérative Games with Coalition Structure. 1.t J. Gametheory, 1974, V.4, P.217-237.

2. Ауман P., Машлер M. The Bargaining set for coopérative games . Advanced in game theory. Ann. Math. Studies. V.52. Princeton: Princeton Univ. Press, 1964, P. 443-476.

3. Вилкас Э.Й. Оптимальность в играх и решениях. М.: Наука, 1990.

4. Вилкас Э.Й. Понятие оптимальности в теории игр. Современные направления теории игр. Вильнюс: Минтис, 1976.

5. Воробьев Н.Н. Коалиционные игры . Теория вероятности и ее применение, 1967, Т12, вып.2, С.289-306.

6. Воробьев Н.Н. Устойчивые ситуации в коалиционных играх . Докл. АН СССР, 1960, Т131 №2, С.493-495.

7. Клейменов А.Ф. К кооперативной теории бескоалиционных позиционных дифференциальных игр . Докл. АН СССР, 1990, Т32 №1, С.32-35.

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

9. Кун Г. У. Позиционные игры и проблемы информации. В сборнике Позиционные игры под ред. Н.Н. Воробьева, И.Н. Врублевская. М.: "Наука", 1967 г., С.13-40.

10. Льюс, Райфа. Игры и решения. М: ИЛ, 1961.

11. Мамкина С.И., Петросян Л.А. Структура множества ситуаций абсолютного равновесия по Нэшу в играх с полной информацией. Труды XXXV научной конференции "Процессы управления и устойчивость", 2004, С. 639-647.

12. Понтрягин Л.С., Болтянский В.Г., Гаикрелидзе Р.В., Мищенко Е.Ф. Математическая теория оптимальных процессов. М., 1961.

13. Петросян Л.А., Аешин Д.А. Значение динамических игр с частичной кооперацией. Труды института математики и механики. Том 6, №1,2, Екатеринбург, 2000, С. 160-172.

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

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

16. Петросян Л.А., Мамкина С.И. Игры с переменным коалиционным разбиением. Вестник СПбГУ, 2004, Сер 1, Вып. 3, С.60-69.

17. Печерский С. Л., Соболев А. И., Проблема оптимального распределения в социально-экономических задачах и кооперативные игры. Л.: Наука, 1983.

18. Харшаньи Д., Зельтен Р. Общая теория выбора равновесия в играх. СПб: Эконом, шк., 2001.

19. Bettina Klaus. Coalitional Strategy-Proofness in Economies with Single-Dipped Preferences and the Assignment of an Indivisible Object. J. Games and Economics behavior. 2001, Vol. 34, 64-82.101

20. Davis M., Maschler M. Existence of Stable Payoff Configuration for Cooperative Games. Essays in Mathematical Economics in Honor of O. Morgenstern, M. Shubik ed, 1967, Princeton, P. 39-52,

21. Dragan I., Poters J., Tijs S. Superadditivity for Solutions on Coalitional Games. Libertas Mathematica 9, 1989, 101-110.

22. Fudenberg D., Tirole J. Game Theory. Mass: MIT Press, 1991.

23. Fukuda. E., Muto., Dynamic Coalition Formation in the Apex Game. Preprint version, 2004

24. Jinpeg Ma. Job Matching and Coalition Formation with Utility or Disutility of Co-Workers. J. Games and Economics behavior. 2001, Vol. 34, 83-104.

25. M. Josune Albizuri, Jose M. Zarzuelo. On Coalitional Semivalues. J. Games and Economic Behaviour, 2004, Vol. 49 №2, p. 237-245.

26. Juan Vidal-Puga and Gustavo Bergantinos. An Implementation of the Owen Value. J. Games and Economics behavior. Aug 2003, Vol. 44, №2.

27. Hart S., M. Kurz. Stable Coalitional Structures. Coalitions and Collective Action, Ed. by M.J. Holler. Wurzburg, 1984, p. 236-258.

28. Katsunori Ano, Susumu Seko, Takashi Suzuki. Nonsymmetric Indices of Power and their Applications to the House of Councilors in Japan.

29. Kuhn H.W. Extensive Games and Problem Information. Ann. Math Studies. 1953. Vol. 28, p.193-216.

30. Luce R.D. A Definition of stability for n-person games. Ann. Math, 1954, V.59, P. 357-366.

31. Nash J. Equilibrium Points in n-person Games. Nat. Acad. Sei. U.S. 36, p. 48-49.

32. Ono R., Muto. S. Party Power in the House of Councilors in Japan: An Application of the Nonsymmetric Shapley-Owen Index. J. Operations research Society of Japan, 40, p. 21-33.

33. Owen G. Game Theory. Third edition, Academic Press, 1995.

34. Owen G., Political Games. Naval Research Logistics Quarterly, 18 (1989), p. 345-355.

35. Ray D., Vohra R., A Theory of Endogenous Coalition Structure. J. Games and Economics behavior. 1999, Vol. 26, p. 286-336.

36. L.A. Petrosjan, S.I. Mamkina. Dynamic Games with Coalitional Structure. J. of Quigdao University, 2004, Vol.17, p. 38-47.

37. L.A. Petrosjan, S.I. Mamkina. New Value for Dynamic Coalitional Games. Proceeding of the 4th Moscow International Conference on Operations Research (ORM2004), 2004, p. 173-175

38. L.A. Petrosjan, S.I. Mamkina. New Value for Dynamic Games with Perfect Information and Changing Coalitional Structure. Poceedings of the 11th International Symposium on Dynamic Games and Applications, Tucson Arizona, 2004, Vol. 2, p. 1-15.

39. L.A. Petrosjan, S.I. Mamkina. Value for the Games with Changing Coalitional Structure. Games Theory and Applications, 2005, Vol. 10, p.141-152.

40. Shapley L.S. A Value for n-person games. In Contributions to the Theory of Games II (Eds. H. Kuhn and A.W. Tucker). Ann. Math. Stud. 28, Princeton University Press. Princeton, NJ.

41. Van Damme E.E.C. A Relation between Perfect Equilibria in Extensive form Games and Proper Equilibria in Normal Forms Games. Intern. J. Game Theory. 1984. Vol. 13, p.1-13.

42. R. Van den Brink, G. van der Laan. Axiomatization of the Normalized Banzhaf Value and the Shapley Value. Social Choice and Welfare, 15. Springer-Verlag, 1998.

43. Vazquez-Brage M., Van den Nouweland A., Garcia-Jurado I. Owen's Coalitional Values Aircraft Landing Fees . Math. Soc. Sci.34, 1997, p. 273-286.

44. Vohra R., A Theory of Endogenous Coalition Structure. J. Games and Economics behavior. 1999, Vol. 26, p. 286-336.

45. Winter E. A Value for Cooperative Games with Levels Structure of Cooperation. Int. J. Game Theory, 1992, 18, p. 27-240.

46. Winter E. The Consideration and Potential for Values of Games with Coalition Structure. J. Games and Economics Behavior. 1992, Vol. 4, p. 132-144.

47. Wojciech Olszewski. Coalition Strategy-Proof Mechanism for Provision of Excusable Public Goods. J. Games and Economics Behavior. Jan 2004, Vol. 46, №1.