Содержание к диссертации
Введение
Глава 1. Динамическая игра с переменным коалиционным разбиением
1.1. Определение динамической игры с переменным коалиционным разбиением и
1.2. Алгоритм построения решения 19
1.3. Построение характеристических функций вспомогательных кооперативных игр 28
1.4. Пример
Глава 2. Структура множества всех ситуаций абсолютного равновесия по Нэшу в играх с полной информацией 37
2.1. Абсолютные равновесия в стратегиях поведения 37
2.2. Описание всего класса абсолютных равновесий 47
2.3. Индифферентное равновесие в позиционных играх с полной информацией
Глава 3. Построение единственного решения в игре с переменным коалиционным разбиением на основе индифферентного равновесия 57
3.1. Модифицированная игра с переменным коалиционным разбиением 57
3.2. Основные функциональные уравнения для построения единственного решения с использованием индифферентного равновесия 60
Глава 4. Стратегическая устойчивость решений в играх с переменным коалиционным разбиением 74
4.1. Распространение решения на все позиции оптимального пучка 74
4.2. Позиционная состоятельность решений и регуляризация. 76
4.3. Индивидуальная секвенциальная рациональность решений 88
4.4. Квазипоследовательное равновесие и коррелированное квазипоследовательное равновесие в играх с переменным коалиционным разбиением 91
Литература
- Построение характеристических функций вспомогательных кооперативных игр
- Индифферентное равновесие в позиционных играх с полной информацией
- Основные функциональные уравнения для построения единственного решения с использованием индифферентного равновесия
- Индивидуальная секвенциальная рациональность решений
Введение к работе
Актуальность темы. Подавляющее число моделей, исследуемых в современной теории игр, делятся на два основных класса: стратегические и кооперативные. Под стратегическими моделями понимаются игры стратегий, то есть игры, в которых участники конфликта выбором стратегий стремятся максимизировать свою функцию выигрыша, и допускается минимальная возможность кооперации, заключающаяся в выборе тех или иных «оптимальных» ситуаций. Основными принципами оптимальности в таких задачах являются ситуация равновесия по Нэшу, а также различные арбитражные схемы (арбитражная схема Нэша, арбитражная схема Калаи-Смородинского и др).
В кооперативных моделях изначально предполагается, что игроки объединяются в большую коалицию, включающую всех игроков, с целью максимизации общего выигрыша. При этом различаются два типа задач: задачи с трансферабельной и нетрансферабельной полезностью. В первом случае речь идет о векторной оптимизации выигрыша, во втором максимизируется сумма выигрышей игроков. Основными принципами оптимальности в кооперативных моделях являются: С-ядро, вектор Шелл и, NM-решение, вектор Банзафа, ядрышко и др. Указанные принципы оптимальности относятся к так называемым «нормативным» принципам. Однако в практических задачах трудно предположить возможность объединения участников конфликта (игроков) в одну большую коалицию с одной стороны, и также является не достаточно реальным предположение о том, что никакая кооперация между игроками невозможна. Поэтому наиболее актуальной является задача, в которой допускается объединение игроков в коалиции, образующих некоторое разбиение всего множества игроков.
Впервые исследованием таких задач занимался Оуэн в 1977 году ([33-34]). Он обобщил понятие вектора Шепли для игр с коалиционными разбиениями, введя так называемый вектор Оуэна-Шепли. При вычислении этого вектора предполагалось, что элементы коалиционного разбиения - коалиции, действуя как игроки, могут объединяться в большую коалицию. И для нахождения выигрышей коалиций использовался вектор Шепли. Далее, внутри каждой коалиции допускалась возможность объединения игроков в подкоалиции, и для нахождения коалиционного дележа использовался вектор Шепли. Таким образом, сперва вектор Шепли применялся на уровне коалиций, принадлежащих коалиционной структуре, для определения выигрышей этих коалиций, а затем вектор Шепли применялся для дележа коалиционного выигрыша. Таким образом, можно утверждать, что коалиционный вектор Оуэна, получался путем двух кратной композиции векторов Шепли.
В 1988 году Ван дер Бринк и Ван дер Лан [42] определили нормализованный вектор Банзафа, который распределяет максимальный суммарный выигрыш игроков пропорционально вектору Банзафа. Этот же подход использовался Ван дер Бринком и Ван дер Ланом в 2005 году году для нахождения решения игры с коалиционным разбиением.
Исследование статических коалиционных игр может быть найдено также в работах [ 1, 2, 20, 27, 30]. Здесь в качестве принципов оптимальности дано определение у/ устойчивой конфигурации. В 1960 г. Н.Н. Воробьев (см. [6 ]) ввел более общее понятие <р устойчивости, которое в 1967 г. он распространил на смешанные расширения коалиционных игр (см. [7 ]) Имеются и другие принципы оптимальности, для классических коалиционных игр: «класс разумных исходов», «замкнутый исход» и др.
В работе [ 21 ] сделана попытка распространения принципов кооперативной теории на игры с заданной коалиционной структурой.
Подробное обсуждение указанных вопросов можно найти в книгах Э. Вилкаса [3,4 ].
Однако указанные подходы (в частности, предложенный Ван дер Бринком и Ван дер Паном, также как и подход Оуэна) предполагают возможность объединения элементов коалиционного разбиения в большую коалицию. Но это предположение не может быть во всех случаях приемлемо, поскольку сам факт возникновения коалиционного разбиения и происходит от того, что полная кооперация игроков невозможна. Поэтому более естественным является подход, при котором игра первого уровня между элементами коалиционного разбиения происходит как стратегическая игра, то есть полная кооперация коалиций как игроков не предполагается. В этом случае для этой игры в качестве принципа оптимальности может быть использовано равновесие по Нэшу [31]. А уже на втором этапе выигрыши, полученные в равновесии по Нэшу игроками коалициями, могут распределяться согласно принципам оптимальности кооперативной игры.
В то же время такой подход, по-видимому, не был рассмотрен ранее поскольку в так называемых одновременных (статических) играх п лиц ситуация равновесия по Нэшу существует лишь в смешанных стратегиях и не является единственной, а выигрыши в ситуации равновесия являются математическими ожиданиями. Поэтому не совсем понятно, какой смысл может иметь распределение математического ожидания выигрыша коалиции между ее участниками.
Справедливости ради следует отметить, что в работе Харшаньи и Зельтена [18 ] предложен метод трассирования для нахождения единственного равновесия по Нэшу в одновременной игре, который, хотя бы в теоретическом плане, позволяет снять проблему единственности в одновременной (статической) игре. Но указанный метод достаточно громоздок и едва ли может быть применен для игр с большим количеством участников.
По-другому обстоит дело в динамических играх с полной информацией. В игре с полной информацией всегда существует абсолютное равновесие по Нэшу в чистых стратегиях ([14,15]). И в данной диссертации нам удалось выделить единственное «индифферентное» равновесие по Нэшу в таких играх. Именно основываясь на этом, мы предложили другой принцип оптимальности для игр с переменным коалиционным разбиением и полной информацией, а именно: для игроков коалиций в качестве принципа оптимальности мы рассматриваем «индифферентное» равновесие по Нэшу, а внутри коалиции осуществляем дележ в соответствии с вектором Шепли. Получившийся в результате такой двухэтапной процедуры вектор выигрышей мы называем PMS вектором.
В работе показано, что PMS вектор стратегически обеспечен в том смысле, что он является результатом коррелированного квазипоследовательного равновесия в игре с полной информацией.
Указанный подход оказался особенно плодотворным для игр с полной информацией, моделирующих более реальные процессы, в которых коалиционное разбиение не является постоянным, а может изменяться в поцессе игры.
Таким образом, данная тема является актуальной и ее исследование вносит определенный вклад в развитие теории игр.
Основной целью работы является исследование многошаговых коалиционных игр с полной информацией и переменным коалиционным разбиением и построение в таких играх принципов оптимальности, обладающих свойством индивидуальной рациональности, позиционной состоятельности, единственности, а также являющихся устойчивыми относительно отклонений индивидуальных игроков и свободными от предположения о возможности полной кооперации игроков коалиций.
Научная новизна. В диссертационной работе впервые исследованы многошаговые игры с полной информацией и переменным коалиционным разбиением. Впервые были предложены принципы оптимальности, основанные на некооперативном поведении коалиций как индивидуальных игроков и полной кооперации внутри каждой коалиции, являющейся элементом коалиционного разбиения. Для построения единственного решения было впервые использовано определенное в диссертации индифферентное равновесие по Нэшу, которое для игр с полной информацией обладает свойством единственности. Исследована позиционная состоятельность предложенного принципа оптимальности и проведена регуляризация с использованием процедуры распределения дележа. Показано, что решение игры, построенное с использованием предложенного принципа оптимальности может быть получено как результат некоторого равновесия по Нэшу в определенным образом сформированной игре.
Практическая ценность. Работа носит теоретическую направленность. Полученные результаты представляют теоретический и практический интерес. Основная практическая ценность определяется многочисленными применениями коалиционных игр для моделирования работы парламентов и других общественных организаций, в которых возможно объединение участников в различные партии (коалиции) ([19, 23, 24, 25, 26, 28, 32, 43, 47]). Принципы оптимальности, предложенные в работе, использовались при исследовании более сложных многошаговых игр с изменяющейся коалиционной структурой.
Основные положения, выносимые на защиту.
Построение многошаговой игры с переменным коалиционным разбиением, и построение принципов оптимальности для многошаговой игры с переменным коалиционным разбиением.
Построение класса всех абсолютных равновесий по Нэшу в многошаговых играх с полной информацией. Выделение единственного абсолютного равновесия, определенного в работе как индифферентное равновесие.
Выделение единственно решения для многошаговой игры с переменным коалиционным разбиением.
Исследование позиционной состоятельности, и индивидуальной секвенциальной рациональности предложенных принципов оптимальности и проведение регуляризации с использованием процедуры распределения дележа.
Формулировка и доказательство теорем о реализуемости предложенных принципов оптимальности в некотором квазипоследовательном коррилированном равновесии в игре с переменным коалиционным разбиением.
Апробация работы. Результаты работы докладывались на 11-ом международном симпозиуме по динамическим играм и приложениям ISDG2004 (Аризона, США), на 1-ом семинаре Китайского отделения международного общества динамических игр (WCC2004) (Qingdao, Qingdao University, Китай), 4-й Московской международной конференции по "Исследованию операций" (ORM2004), на XXXV научной конференции "Процессы управления и устойчивость" (Санкт-Петербург), на семинаре центра теории игр при факультете ПМ-ПУ СПбГУ. Основные результаты опубликованы в работах [8], [Ю], [28-31].
Структура и объем работы. Диссертационная работа состоит из введения, 4 глав (13 параграфов), списка используемой литературы. Общий объем диссертации - 104 страницы. Список используемой литературы включает 47 наименований. Работа содержит 3 рисунка.
В первой главе рассмотрена многошаговая игра с полной информацией на конечном древовидном графе. Мы предполагаем, что коалиционные разбиения могут изменяться в различных позициях игры. Изменения происходят случайным образом. Нами предложен некоторый принцип оптимальности, который основывается с одной стороны на равновесии по Нэшу для игроков коалиций, а с другой стороны - на кооперативных принципах оптимальности для игроков внутри коалиций.
В 1.1 дается определение динамической игры Г с переменным коалиционным разбиением на конечном древовидном графе и дано детальное описание рассматриваемой игры.
В 1.2 предложен алгоритм построения принципа оптимальности PMS-вектора, основанного на равновесии по Нэшу для игроков коалиций, а с другой стороны - на кооперативных принципах оптимальности для игроков внутри коалиций. Однако, поскольку равновесие по Нэшу не является единственным, то, как показано в первой главе, такой подход не приводит к единственному решению.
В 1.3 предложен способ построения характеристической функции для вспомогательных кооперативных игр, участвующих при построении оптимального решения в игре с переменным коалиционным разбиением Г.
В 1.4 приведен пример построения PMS-вектора
Во второй главе с целью выделения единственного решения из пучка оптимальных решений для игры с переменным коалиционным разбиением Г описан весь класс абсолютных равновесий по Нэшу для многошаговых игр с полной информацией в стратегиях поведения. Введено понятие индифферентного равновесия.
В 2.1 построен класс абсолютных равновесий по Нэшу в стратегиях поведения для многошаговых игр с полной информацией.
В 2.2 показано, что любая ситуация абсолютного равновесия по Нэшу в многошаговых играх с полной информацией принадлежит описанному в 2.1 классу абсолютных равновесии по Нэшу в стратегиях поведения.
В 2.3 среди всего класса абсолютных равновесий по Нэшу выделено единственное равновесие, определенное в диссертационной работе как "индифферентное" равновесие. Приведен пример построения индифферентного равновесия.
В третьей главе рассмотрена модифицированная игра с переменным коалиционным разбиением. На основе индифферентного равновесия выделено единственное решение для модифицированной игры с переменным коалиционным разбиением.
В 3.1 определена модифицированная игра с переменным коалиционным разбиением, в которой в начальной позиции не обязательно ходит случай.
В 3.2 для модифицированной игры с переменным коалиционным разбиением предложен принцип оптимальности, названный PMS вектором, приводящий к единственному решению. Выведены основные функциональные уравнения для построения этого единственного решения с использованием индифферентного равновесия.
В четвертой главе изучается индивидуальная рациональность полученного решения, и исследуется, может ли быть данное решение стратегически обеспечено. С этой целью проводится так называемый процесс регуляризации задачи и, одновременно, исследуется позиционная состоятельность решения с одной стороны, а с другой предлагается некоторая процедура стратегического обеспечения результата.
В 4.1 приведена схема распространения решений на все позиции оптимального пучка, которые не обязательно принадлежат множеству позиций случайного хода, а могут являться и личными позициями игроков.
В 4.2 исследована позиционная состоятельность решений. Предложена процедура распределения дележа между игроками, с помощью которой обеспечивается позиционная состоятельность решений. Полученные в 4.2 результаты проиллюстрированы на конкретном примере.
В 4.3 введено понятие усеченной подыгры позиционной игры с переменным коалиционным разбиением. С использованием усеченных подыгр определено понятие индивидуальной секвециальной рациональности и показана индивидуальная секвинциальная рациональсть решений.
В 4.4 определено квазипоследовательное равновесие и показано, что PMS вектор реализуем в некоторой ситуации квазипоследовательного равновесия в регуляризованнои игре с полной информацией и переменным коалиционным разбиением. Определяется ситуация коррелированного квазипоследовательного равновесия, и показано, что компоненты PMS вектора предствляют собой выигрыши в некотором квазипоследовательном коррелированном равновесии в регуляризованнои игре с полной информацией и переменным коалиционным разбиением.
Построение характеристических функций вспомогательных кооперативных игр
В настоящем разделе мы укажем способ построения х.ф. v(y,R), Rc=Sk(y) игры T(y,Sk(y)). При построении оптимального "пучка" развития игры Т(х0) в параграфе 2 было определено поведение игроков /єіУ в каждой личной позиции уеР(, ieN принятия решения. Обозначим через U (-) = (U i( ),...,U\(-)) набор стратегий игроков, определенных в параграфе 2, приводящих к реализации оптимального пучка в игре Т(х0). Кооперативная игра G(y,Sk(y)) строится с использованием этих стратегий. Введем понятие следа ситуации игры. След ситуации в подыгре есть сужение этой ситуации на множество позиций данной подыгры. Рассмотрим след U y(-) = (U iy(-),...,U\( )) набора U в подыгре Т(у) и рассмотрим вспомогательную подыгру Т(у) игры Г(х0), в которой выборы игроков i Sk(y) в их личных позициях зафиксированы в соответствии со стратегиями с/ , / є N. Так же как и оптимальный пучок, мы будем строить х.ф. v(y,R), RczSk(y) методом математической индукции для уёРп+1 (т.к. для уєР„+1 наш алгоритм не требует построения вектора Шепли). Рассмотрим множество позиций Х0. Так как длина игры равна Т + 1, то X0czPn+2 и v(y,R), RczSk(y) в этом случае просто равна v(y.R) = Ih(y). ieR Шаг 1. Перейдем от позиций уеХ0 к предшествующим. Пусть у1еХ1 и у Рп+п и рассмотрим след Uyi(-) = (U iyi(-),...,U\yt(-)) набора Uy () в подыгре Т(у,). И пусть Т(у,) - подыгра игры T(yj), в которой выборы игроков iSk(yj) в их личных позициях зафиксированы в соответствии со стратегиями иу () Таким образом, игра Т(у оказывается игрой между игроками, входящими в коалицию Sk(y,). Для каждой подкоалиции RaSk(yj) рассмотрим ассоциированную с Т(у,) игру с нулевой суммой T(y,,Sk(yj)) между двумя игроками: коалицией R, являющуюся максимизирующим игроком (выигрыш коалиции R равен сумме выигрышей игроков R), и коалицией Sk(yj)\R, являющейся минимизирующим игроком (выигрыш коалиции Sk(yj)\R равен выигрышу коалиции R с обратным знаком). Можно показать, что выигрыш каждой коалиции R, определенный таким образом, не может превысить величины v(yl,Sk(y1))= Sr/(y;) (см. (1.4)), поскольку по построению коалиция SJyj) получает выигрыш v(yj,Sk(yj)), используя наилучший ответ против стратегий Ufy () игроков iSk(yt). Пусть v(y,,R) будет значением игры r(yItSk(y,)). С помощью х.ф. v(yj,R), RdSk(y,) вектор Шепли строится в игре Т(у,) обычным способом. Шаг t. Рассмотрим некоторую позицию yteXt, ytPn+I. sfc sic Рассмотрим след U (-) = (U iyt(-),...,U nyt(-)) набора Uy () в подыгре T(yt). И рассмотрим вспомогательную подыгру T(yt) игры Г(х0), в которой выборы игроков ieSk(yt) в их личных позициях определены в соответствии со стратегиями Uy (). Таким образом, игра T(yt) оказывается игрой между игроками, входящими в коалицию Sk(yt). Для каждой подкоалиции RczSk(yt) рассмотрим ассоциированную с T(yt) игру с нулевой суммой T(yt,Sk(yt)) между двумя игроками: коалицией R, являющуюся максимизирующим игроком (выигрыш коалиции R равен сумме выигрышей игроков R), и коалицией Sk(y,)\R, являющейся минимизирующим игроком (выигрыш коалиции Sk(yt)\R равен выигрышу коалиции R с обратным знаком). Можно показать, что выигрыш каждой коалиции R, определенный таким образом, не может превысить величины v(y, Sk(y,))= Иг!(Уі) поскольку по построению коалиция Sk(yt) ieSk(x,) получает выигрыш v(y,,Sk(yl)), используя наилучший ответ против стратегий Ufy () игроков iSk(yt). Пусть v(yt,R) будет значением игры f(yt,Sk(yt)). С помощью х.ф. v(yt,R), RcSk(yt) вектор Шепли строится в игре T(yt) обычным способом. Продолжая далее, можем построить v(y,R), RaSk(y) для всех уеРп+, и соответствующий вектор Шепли. Заметим, что построенная х.ф. v(y,R), RczSk(y), yeXt требует знания набора U (), однако последний также использует знание о v(y,R), но уже при уеХп l t. Поэтому наше построение вполне корректно. Рассмотрим позиционную игру Т(х0) с переменным коалиционным разбиением и деревом игры К(х0), изображенном на рис. 1.1. Здесь N = {1,2,3}. Множество очередности игрока 1 состоит из Р1={х1,х2,х3,х23,х24,х25}. Множество очередности игрока 2 состоит из Р2 = {х7,х8,х1],х27,х29,х31}. Множество очередности игрока 3 состоит из Р3 = {х5,х13,х33,х35,х37}. Множество ПОЗИЦИЙ случая Предположим, что ht=0, i = 1,2,3 для всех вершин хеР{[]Р4, т.е мгновенные выигрыши отличны от нуля только в окончательных позициях. Выигрыши записаны в окончательных позициях, причем в каждом столбце верхнее число есть выигрыш игрока 1 и т.д. Предположим, что множество допустимых разбиений игроков N = {1,2,3} на коалиции имеет вид А = {А„А2,Ь3}, А,={1},{3,2}; А2 ={1,2,3}; А3 = {1,3},{2}. Пусть в вершинах XGZ(X0) заданы переходные вероятности р(х1),р(х2),р(х3), p(Xj) + p(x2) + p(x3) = 1, р(х1) = р(х3) = ; р(х2) = -. Пусть А(х1) = {1},{3,2}; А(х2) = {1,2,3}; О J А(х3) = {1,3},{2}. Аналогично в вершинах xeZ(x]4) заданы 1 2 переходные вероятности р(х20) = р(х22) = — \ р(х21) = — , 6 3 А(х20) = {1},{3,2}\ А(х21) = {1,2,3}\ А(х22) = {1,3},{2}. В вершинах xeZ(xJ9) заданы переходные вероятности р(х23 ) = р(х25) = — \ р(х24) = -з, А(х23) = {1},{3,2}\ А(х24) = {1,2,3}; А(х25) = {1,3},{2}. Построим оптимальный "пучок" в игре Т(х0). Процедура построения оптимального "пучка" начинается в окончательных позициях х381 х39, х40, х4П х42, х43. Рассмотрим подыгры на деревьях К(х33), К(х35), К(х37).А(х33) = А(х38) = А(х39). В позиции х33 ходит игрок 3. З є {3,2} с А(х33).
Индифферентное равновесие в позиционных играх с полной информацией
Хорошо известна теорема о существовании ситуации абсолютного равновесия по Нэшу в конечной игре с полной информацией в чистых стратегиях ([14,15,22]). Однако, в позиционных играх ситуация абсолютного равновесия по Нэшу может не являться единственной и зависит от "доброжелательности" игроков в том смысле, что один из игроков, будучи в равной степени заинтересован в выборе последующих альтернатив, может выбрать любую из таких вершин, руководствуясь своими личными соображениями. Например, в случае "доброжелательности", игрок во множестве своих личных позиций, в которых выбор последующих альтернатив принесет ему одинаковый максимальный выигрыш, выбирает из них ту, которая более благоприятна для другого игрока, или же ту, которая является неблагоприятной для какого-либо из игроков (см. [15]). В настоящем параграфе мы предложим другой подход выделения абсолютного равновесия по Нэшу, которое может быть получено только при использовании смешанных стратегий. Проиллюстрируем построение доброжелательного и недоброжелательного равновесия на конкретном примере. На рисунке 2.1. представлена позиционная игра двух лиц с полной информацией на древовидном графе. Выигрыши игроков записаны в окончательных позициях. Причем, выигрыш первого игрока соответствует верхнему числу компоненте, второго - нижнему. Множество очередности игрока 1 - Р} = {х0,х3,хб}, второго игрока - P2 = {xltx2}% множество окончательных позиций В позиции х3 ходит игрок 1. Так как максимум max hj(x) достигается в 2-х точках, построим множество Предположим, что игрок 1 настроен доброжелательно по отношению к игроку 2. Это означает, что в позиции х3 выбирает позицию x8eZ,(x3), которая является более благоприятной для игрока 2, чем позиция х7 eZj(x3). Тогда выигрыши игроков в позиции в подыгре Т(х3) составят Н(х3)=(3,б/. В позиции х6 ходит игрок 1. Так как максимум max h,{x)= 1 xeZ{x6) достигается в хр, следовательно, в позиции хб игрок 1 выберет альтернативу х9. Тогда в подыгре г(хб) выигрыши игроков составят Н{х6)=(1,1)\ В позиции х; ходит игрок 2. Так как максимум max КІХ)=6 xeZ{x,) достигается в х .следовательно, в позиции х7 игрок 2 выберет альтернативу х3. Тогда в подыгре Г(х;) выигрыши игроков составят Н(х ,)=(3,2/. В позиции х2 ходит игрок 2. Максимум выигрыша второго игрока max h2{x)=2 достигается в х5. А значит, в позиции х2 игрок 2 xeZ(x2) выберет альтернативу х5. Тогда в подыгре Г(х2) выигрыши игроков составят Н(х1)=(1,2/. Рассмотрим позицию х0. В позиции х„ ходит игрок / и выбирает альтернативу x;eZ(x0) из условия max h,{x) = 3. Тогда выигрыш xeZ(x0) игроков во всей игре Г(х0) составит Н(х0)=(3,б/. Заметим, что в позиции х3 множество Zj(x3) состоит более чем из одного элемента, что порождает неоднозначность выбора альтернативы в позиции х3. Выше мы строили абсолютное равновесие по Нэшу в предположении "доброжелательности" первого игрока. Рассмотрим случай, когда игрок / настроен "недоброжелательно" по отношению к игроку 2. Это означает, что в позиции х3 игрок 1 выбирает позицию x7eZj(x3), Z](x3)=argmaxhJ(x)={x7,x8}, которая является менее xeZ(x3) благоприятной для игрока 2, чем позиция х8є2,(х3). Тогда выигрыши игроков в позиции х3 в подыгре Г(х3) составят Н{х3)=(3,6)\ В позиции хб ходит игрок 1. Так как максимум тах h,{x)=l достигается в хд, следовательно, в позиции х6 игрок 1 выберет альтернативу хд. Тогда в подыгре Т(хб) выигрыши игроков составят Н(х6)= (1,1)\ В позиции Xj ходит игрок 2. Так как максимум тах h2(x)=4 достигается в х4, следовательно, в позиции х{ игрок 2 выберет альтернативу х4. Тогда в подыгре Г(х7) выигрыши игроков составят H(Xl)=(4,3)\ В позиции х2 ходит игрок 2. Максимум выигрыша второго игрока max h2(x)=2 достигается в х5. А значит, в позиции х2 игрок 2 выберет альтернативу х5. Тогда в подыгре Г(х2) выигрыши игроков составят Н(х,) = (1,2) . Рассмотрим позицию х0. В позиции х0 ходит игрок / и выбирает альтернативу xleZ(x0) из условия та% hl(x)=4. Тогда выигрыш игроков во всей игре Г(х0) составит н(х0) = (4,3) . Как видно из рассмотренного примера, при различном настрое одного из игроков (доброжелательном и недоброжелательном) абсолютные равновесия в игре Т(х0) и соответствующие им выигрыши различны. Как было упомянуто ранее, в силу того, что при построении абсолютного равновесия по Нэшу методом обратной индукции, в некоторой подыгре может случиться, что один из игроков обнаруживает, что его выигрыш (при условии продолжения игры в соответствии с данным равновесием по Нэшу в подыграх) не зависит от того, какую альтернативу он выберет. Для устранения проблемы многозначности абсолютных равновесии по Нэшу введем понятие "индифферентного" равновесия, отражающее "безразличие" при выборе альтернативы в указанных позициях. В позициях хєК(х0), в которых принимающему решение игроку i(x) безразлично, какую из альтернатив yeZ fe ) выбрать, предпишем игроку i(x) выбрать вершины у є Z x Дх ) с равными вероятностями, т.е. вероятность выбора каждой из альтернатив yk єї х), k = 1,..., Z (xi в позиции хеК(х0) равна.
Основные функциональные уравнения для построения единственного решения с использованием индифферентного равновесия
В первой главе настоящей работы нами был предложен принцип оптимальности для позиционных игр с переменным коалиционным разбиением. Однако, как это было там же показано, этот принцип оптимальности не приводит к единственному решению. В настоящей главе, построено решение для игры с переменной коалиционной структурой более общего вида, т.е. игры, в которой не обязательно в начальной позиции ходит случай, и для этой игры с использованием индифферентного равновесия, определенного во второй главе, выделено единственное решение.
Пусть, как и ранее, N = {1,...,п} множество игроков. Ак ={SJ}J ,, таких что SjdS O ; ІФ]\ \JSJ=N- разбиение множества игроков N. Множество всех допустимых разбиений множества N обозначим через А. Обозначим через 2$ множество вершин (позиций), непосредственно следующих за у. Игрока, принимающего решение в вершине у (выбирающего следующую альтернативную позицию в вершине y)f будем обозначать через i(y). Выбор игрока і(у) в позиции у -через yeZ(y). Рассмотрим позиционную игру п лиц с переменным коалиционным разбиением, определенную в главе 1 1.1 определение 1.3. Под видоизмененной игрой с переменным коалиционным разбиением будем понимать игру, отличающуюся от игры с переменным коалиционным разбиением, определенной в 1.1 (см. определение 1.3 1.1), лишь тем, что в начальной позиции х0 не обязательно ходит случай. То есть в видоизмененной игре х0 может принадлежать множеству позиций случайного хода Рп+1, а может и нет. Ниже мы будем рассматривать видоизмененную игру с переменным коалиционным разбиением. Как и ранее, будем предполагать, что игрок i =N в позиции хєР( (где Pt - множество очередности игрока і) играет в интересах коалиции его содержащей (iGSJ,Sj A{xJ)), то есть стремится максимизировать суммарный выигрыш игроков из коалиции S;. Пусть игроки выбрали свои стратегии U1,...,Un и образовалась ситуация U() = (fJ,(-),...,U„()) Тогда видоизмененная игра развивается следующим образом. Игра начинается в позиции х0, в которой задано некоторое коалиционной разбиение А(х0)еА. Если х0 єР„+п то есть в начальной позиции х0 ходит случай, то в позиции х0 альтернатива x,eZ{x0) выбирается в соответствии с вероятностями, определенными условием (III) определения 1.3 главы 1 1.1. Если х0єРіМ, т.е. в позиции х0 ходит игрок і(х0), то і(х0) выбирает альтернативу xI=Ui (x0)eZ(x0), действуя в интересах коалиции его содержащей. Выбранной таким образом позиции x,eZ(x0) соответствует коалиционное разбиение Д(Зс,)єД, которое может совпадать с коалиционным разбиением в х0, а может и нет. Если на шаге к, xkPn+I{JPn+2, то в позиции хк ходит игрок i(xk) и выбирает альтернативу xk+1 = Ui{-ki)(xk)eZ(xk), действуя в интересах коалиции его содержащей. Если на к -ом шаге игра попадает в позицию случайного хода, т.е. хк є Рп+1, то в позиции хк альтернатива хи1 выбирается в соответствии с вероятностями, определенными условием (III) определения 1.3 главы 1 1.1. Выбранной таким образом позиции xMeZ(xk) соответствует коалиционное разбиение А(хк+1)еА, которое может совпадать с коалиционным разбиением в хк, а может и нет. Игра продолжается до достижения некоторой позиции wsPn+2. В силу конечности дерева К, это происходит за конечное число шагов. В позициях игры х, согласно условию (IV) определения 1.3 главы 1 1.1, заданы выигрыши hj(x),...,hn(x) игроков. Поэтому каждый набор стратегий U(-)=z(U]( ),...,Un(-)) или ситуация определяют некоторое вероятностное распределение на партиях игры (из-за случайных выборов в позициях уеРп+/), а следовательно выигрыш z -го игрока (суммарный выигрыш вдоль реализовавшейся партии) оказывается случайной величиной. Поэтому каждой ситуации U(-) = (U,(),...,UJ-)) однозначно соответствует математическое ожидание выигрышей игроков E U{-),...,1]п(-)) = Е[ К(хк)] I eJV, где / - число вершин (позиций) в реализовавшейся партии х0,...,х,, приводящей в окончательную позицию х,. Как и ранее, в данной постановке мы предполагаем, что игрок ieN в позиции у є Pt (где Pt - множество очередности игрока /) играет в интересах коалиции его содержащей {i Sj,Sj єА( .)), т.е. стремится максимизировать суммарный выигрыш игроков из коалиции Sj. Как и ранее, под длиной игры г(у0) будем понимать длину наибольшего пути на дереве К(у0) (число вершин входящих в максимальный путь). Предположим, что длина игры Г(у0) равна Т + 1. Рассмотрим разбиение множества всех позиций дерева игры К(у0) на Т + 1 множество Y0Y1,...,YT:YT={y0}, где множество Yt состоит из позиций, достигаемых из начальной позиции в точности за T ходов. Элементы множества Y, обозначим через уп t = 0,l,...,T. Рассмотрим множество позиций Y0. Так как длина игры равна Т + 1, то Y0aPn+2, и выигрыши игроков уже определены и равны соответственно ht(w), weY0, і = 1,...,п.
Индивидуальная секвенциальная рациональность решений
В главе 3 PMS вектор определен в вершинах у Рп+1 дерева игры, a SPMS - в вершинах у дерева игры, таких что y eZ(y), где уеРп+1. Пусть оптимальный пучок определен. Для дальнейшего исследования нам необходимо распространить определение PMS вектора на все вершины этого пучка. Пусть zt - некоторая вершина оптимального пучка Z \л zT Рп+1. Пусть в z, задано коалиционное разбиение A(zt)= /( ),...,5 ( ),...,5 -)1()}. Выделим выигрыши игроков из коалиционных выигрышей, то есть определим также, как это делалось в главе 3, для вершин /, таких что y eZ(y), уеРп+], некоторый дележ суммарного выигрыша для каждой из коалиций Выберем произвольно коалицию Sk(zt)eA(zt). Рассмотрим кооперативную игру \Sk(ztJ лиц G{zt,Sk{z$) с характеристической функцией v(z,,#(SA(z,))), RczSk(zt). Выигрыш максимальной {Sk(zt)) коалиции в кооперативной игре G(zt,Sk(zt)) полагаем равным: где A;.(Z,), / eSt(z,) - функции, определенные в главе 3 (см. (3.15)). Вычислим в G(zt,Sk(zt)) вектор Шепли с компонентами Я&(У,-/)). ОО.где При этом для определения компонент вектора Шепли ShXStfa)), ieSk(zt) пользуемся характеристическими функциями v(y,R(Sk(zt)), RcSk(zt), Sk(zt)eA(zt), алгоритм построения которых приведен в 1.3 главы 1. Формула для вычисления вектора Шепли для игроков ieSk(zt)ek(zt) с использованием характеристических функций v(y,R(Sk(zt)), RaSk(zt), Sk(zt)eA(zt) имеет вид: где SPMSXz -ShXs t)) i Sk(zt) c помощью которого определяются выигрыши игроков 1,...,п в случае, если z, Р„+/. Полагаем Таким образом, мы распространили определение PMS вектора на все вершины оптимального пучка Z. Заметим, что аналогичным образом можно распространить определение PMS вектора, определенного в главе 1 на все вершины соответствующего этому вектору оптимального пучка. Рассмотрим динамическую игру Г с переменным коалиционным разбиением с полной информацией на конечном древовидном графе, определенной в главе 1. Предположим, что в результате реализации алгоритма 3.2 главы 3 мы построили оптимальный пучок путей в игре Г. В каждой вершине z этого оптимального пучка однозначно определен PMS вектор, определяющий выигрыш каждого из игроков. Под принципом оптимальности в рассматриваемой нами игре Г с переменным коалиционным разбиением будем считать PMS вектор. Предположим, что в начале игры игроки соглашаются использовать PMS вектор как основу для выбора оптимального дележа. Обозначим через Z оптимальный пучок, соответствующий данному PMS вектору. Предположим, что игра развивается в ситуации й" = (М,,...,Й;,...Й"И) (см. 3.2 главы 3) из позиции x0eZ. Тогда на втором шаге игра переходит в позицию z eZ, где z может быть результатом случайного хода в позиции х0 = zT или результатом детерминированного выбора. Соглашение об использовании PMS вектора как основы для выбора оптимального дележа означает, что игроки, выбирая стратегии Й = (Й;,...,Й;,...М„), определенные при построении алгоритма 3.2 главы 3 и порождающие оптимальный пучок Z, ожидают, что в «среднем» каждый из них получит доход, равный соответствующей компоненте PMS вектора после окончания игры. В позиции zT_,, фактически, игроки играют в новую игру гг , которая является подыгрой игры Г-т. Предположим, что в игре Гг мы, вновь используя алгоритм нахождения оптимального пучка применительно к данной подыгре, находим соответствующий PMS вектор. Рассмотрим два возможных случая: 1. Пусть zTePt, ІФП + 1, п + 2. Возникает естественный вопрос, будет ли PMS вектор, вычисленный для подыгры Г2 , равен PMS вектору, вычисленному для подыгры Тїт; плюс мгновенные выигрыши / ,( г) игроков, полученных ими в вершине zT, если переход в zT_} осуществляется детерминировано, в соответствии с ситуацией u = fa,...,uit...uH), или будет ли PMS вектор, вычисленный для подыгры Гг , равен математическому ожиданию вновь вычисленных PMS векторов для подыгры Г-г/ плюс мгновенные выигрыши ht(zT) игроков, полученных ими в вершине zT, если переход в zT_l происходит случайно, в соответствии с вероятностями, порожденными индифферентным равновесием. 2. Пусть zTePn i = n + l, то есть в вершине zT ходит случай. Возникает вопрос, будет ли PMS вектор, вычисленный для подыгры Г1г, равен математическому ожиданию PMS векторов, вычисленному для подыгр Гг ; (вершины zT_, реализуются в результате случайного выбора, в соответствии с вероятностями, заданными для данной игры) плюс мгновенные выигрыши ht(zr) игроков, полученных ими в вершине ZT. Если это не имеет место, то игроки в подыгре Г-г; не будут ориентироваться на тот же принцип оптимальности, что и в игре rf , что может побудить их к изменению выбора стратегий «;.(), i = l,...,n, и, следовательно, привести к изменению оптимального пучка путей в подыгре.
