«Математическое моделирование аукциона с наведенными заявками для лабораторных проектных игр ...»

Федеральное государственное бюджетное учреждение наук

и

Вычислительный центр им. А.А. Дородницына

Российской академии наук

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

Скиндерев Сергей Александрович

Математическое моделирование

аукциона с наведенными заявками

для лабораторных проектных игр

Специальность 05.13.18 - математическое моделирование,

численные методы и комплексы программ Диссертация на соискание учёной степени кандидата физико-математических наук

Научный руководитель к.ф.-м.н. Меньшиков И.С.

Москва 2013 2 Оглавление Введение

Глава 1 Проектные игры

Определение проектной игры

1. Динамическая проектная игра

1. Пример аукциона

1.2. Аукцион с наведенными заявками

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

Кооперативная игра

1.3. Сетевой аукцион

1.3. Рынок товаров коллективного пользования

1.3. Основные результаты главы 1

1. Глава 2 Динамические кооперативные игры

Общие сведения о кооперативных играх

2. Динамическая кооперативная игра

2. Дополнительные определения и утверждения

2. Критерии существования предъядер

2.3. Блокирующие состояния

2.3. Условия согласованности

2.3. Примеры для игры трех лиц

2. Общие сведения об игре трех лиц

2.4. Динамическая игра для кооперативной игры трех лиц......... 2.4. Аукцион с наведенными заявками для игры трех лиц.......... 2.4. Блокирующие состояния

2.4. Игры с нулевыми выигрышами малых коалиций

2. Вычисление N-ядра

2.5. Алгоритм вычисления N-ядра для игр с нулевыми 2.5. выигрышами малых коалиций

Дополнительные исследования игр с нулевыми играми 2.5. малых коалиций

Метрика в пространстве дележей

Основные результаты главы 2

Глава 3 Программный комплекс для проведения экспериментов..... Предпосылки создания программного комплекса

Требования к реализации

Технология Генератор Проектов

Сетевая модель данных

Расширение модели для динамической игры

Серия из последовательных игр

Кратное количество участников

Язык описания проектных игр

Выходные данные

3.10 Производительность и надежность

3.11 Основные результаты главы 3

Глава 4 Анализ экспериментов

Общий подход к анализу

Описание одной игры (элементарная игра)

Описание серии игр (сценарий последовательности)........... Мотивация участников

Постановка эксперимента

Извлечение данных для анализа

Проблема повторяемости и стационарности

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

Описание экспериментов

Анализ влияния информации о блокирующих стратегиях... Анализ влияния информации о значениях N-ядер................. Интерпретация результатов

Сравнительный анализ игр по сетевому газовому аукциону. Построение проектных игр

Планирование и проведение серий экспериментов............. Извлечение данных для анализа

Построение гипотезы для пары серий

Сворачивание случайного вектора в случайную величину гипотезы однородности

Интерпретация результата

лаборатории

Рынок банковского программного обеспечения.................. Аукцион с наведенными заявками

Особенности игры «BNK»

Пробный эксперимент

Основные эксперименты

Основные результаты главы 4

Заключение

Список литературы

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

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

Развитие экспериментальной экономики упирается в необходимость разработки новых математических методов. Потребности экспериментальной экономики порождают неисследованные ранее вопросы и задачи, которые относятся к области теории игр. Такие математические задачи необходимо решать при анализе результатов экспериментов.

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

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

Эффективность предложенного подхода подтверждается совокупностью лабораторных экспериментов, проведенных в Лаборатории экспериментальной экономики МФТИ и ВЦ РАН.

Обзор литературы Основоположником экспериментально экономического подхода считается Вернон Смит. Его методология проведения экспериментов и моделирования аукционов опубликованы в работах [14, 17-20]. Другими яркими представителями экспериментально-экономического подхода является группа исследователей под руководством одного из ведущих современных экономистов Чарльза Плотта [2-4].

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

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

Одним из подходов к выбору эффективного торгового механизма для какого-либо экономического рынка является теоретико-игровой. Основным инструментом анализа сетевых рынков являет построение различных аукционов. Такой подход применяется, например, в работах [8, 21, 23]. Эти работы посвящены моделированию рынков однородного товара, в частности, исследуются проблемы расчета конкурентного равновесия для сетевого рынка по заданным функциям спроса и предложения.

Другие работы посвящены исследованию сетевых рынков в лаборатории. В работе [10] в качестве исследуемого в лаборатории метода предлагается закрытый аукцион подачи заявок с диспетчером.

Еще один объект, активно исследуемый в настоящее время – это рынки товаров коллективного пользования. Одной из классических работ в этой области считается работ Элионор Остром [12]. Там рассматривается объект, называемый в зарубежной литературе «public goods», т.е. общественное благо.

Основной проблемой на рынках такого рода товаров (мосты, дороги и пр.) является так называемая проблема безбилетника. Это означает, что у пользователей товаров коллективного пользования нет рыночных стимулов тратить ресурсы на производство таких товаров. Так же есть и более современные исследования рынков общественных благ, в том числе и в лабораториях [7, 13].

Альтернативный способ исследования рынков и аукционов является подход кооперативной теории игр [36, 39, 40]. В таком подходе экономическая ситуация представляется в виде характеристической функции. Такой подход достаточно популярен. В работе [33] исследуются характеристические функции, построенные по сетевым рынкам. В работе [25] приводится учет кооперативных взаимодействий в рыночных механизмах.

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

Основная масса экспериментально-экономических лабораторий находится в США. В России к подобным лабораториям можно отнести таковые в Московском физико-техническом институте, Высшей школе экономики и Российской экономической школе.

Лаборатория экспериментальной экономики МФТИ и ВЦ РАН (ЛЭЭ) была создана в 2003 году. Она продолжает традиции Лаборатории экспериментальной экономики академии народного хозяйства при Правительстве РФ (с 1991 года). В ЛЭЭ проводится широкий спектр экспериментов: от моделирования рынка электроэнергии РФ до различных международных проектов.

Также на базе лаборатории проводится курс «Экспериментальная экономика» для студентов старших курсов ФУПМ МФТИ.

В 2004-2009 гг. в ЛЭЭ проводилась серия экспериментов по моделированию сетевых рынков. Первый исследуемый аукцион использует механизм централизованного сбора заявок участников диспетчером, обладающим заданным функционалом совокупного выигрыша [10]. Второй – торговый механизм, являющийся обобщением непрерывного двойного аукциона на случай сетевой торговли, основанный на использовании производных контрактов. Такой подход основан на модели финансовых рынков [30, 37]. Третий аукцион – это другой вариант сетевого двойного аукциона, основанный на так называемых наведенных заявках [26, 27].

Для первого аукциона использовался программный комплекс «Z-Tree»

(Цюрихский Университет, Швейцария). Для второго – программный комплекс «FTS» (Университет Карнеги Меллон, США). «Z-Tree» [5, 6] идеально подходит для моделирования и постановки различных экономических экспериментов в дискретном времени. «FTS» [54] является симулятором финансовой торговой системы, принцип ее работы основан на непрерывном двойном аукционе.

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

Впервые аукцион с наведенными заявками был предложен как разновидность аукционов для сетевых рынков [26, 27]. Целью данной работы был детальный анализ описанного аукциона, а также обобщение его применимости на другие классы экономических ситуаций, таких как кооперативные игры и рынки товаров коллективного пользования.

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

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

• Построение универсального механизма переговоров между участниками о возможном исходе игры.

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

• Планирование и проведение серии лабораторных экспериментов с использованием универсального механизма переговоров.

• Исследование особенностей поведения участников лабораторных экспериментов при изменении внешних условий.

Методы исследования В работе применялись методы теории игр и экспериментальной экономики.

Для разработки программного комплекса использовался инструментальный комплекс «Генератор проектов».

Для проведения экспериментов были использованы методики, разработанные в Лаборатории экспериментальной экономики МФТИ и ВЦ РАН.

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

Научная новизна • Разработана новая математическая модель проектных игр для описания взаимодействия нескольких участников, имеющих возможность вступать в кооперацию. Модель является обобщением таких классов теоретико-игровых объектов, как кооперативные игры, сетевые аукционы и рынки товаров коллективного пользования.

• Создан язык описания проектных игр.

• Аукцион с наведенными заявками для сетевых рынков обобщен на случай произвольной проектной игры.

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

Эти игры удалось исследовать как теоретически, так и на основе проведения серий лабораторных экспериментов.

• Для определенного в диссертации класса кооперативных игр получена аналитическая формула для вычисления N-ядра.

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

Разработанный программный комплекс передан в Лабораторию экспериментальной экономики МФТИ и используется для проведения лабораторных работ по курсу «Экспериментальная экономика», который читается студентам факультета управления и прикладной математики МФТИ.

Глава 1 Проектные игры Проектная игра – это математическая модель описания широкого класса экономических ситуаций, в которых участники имеют возможность кооперировать. В качестве примеров моделей, описываемых с помощью проектной игры, можно привести кооперативную игру, сетевой аукцион и рынок товаров коллективного пользования [47].

Проектная игра – каркас (макет) для построения лабораторной (динамической) игры.

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

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

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

M = {1,..., m} – множество допустимых проектов;

{dl }lA – разбиение множества агентов по операциям, {nl }lA – разбиение множества агентов по игрокам, которому принадлежит агент l.

( cl )lA a – вектор затрат агентов на проведение операций;

Определение 1.1 (окончание) Фактически множества D, M, N, A содержат индексы соответствующих сущностей. Для обозначения элементов будем использовать следующие индексы: i D, j M, k N, l A. Матрица {eij }iD задает структуру допустимых проектов:

[ D, M ] = {(i, j ) ( D, M ) | eij = 1} – множество связных пар «операцияпроект»;

• Dji = D j \ i, (i, j ) [ D, M ] – множество операций, дополняющих операцию i до проекта j.

Разбиение множества агентов по операциям {dl }lA означает, что каждый агент может выполнить только одну операцию, причем одну и ту же операцию могут выполнять разные агенты. Разбиение множества агентов по игрокам {nl }lA означает, что каждым агентом управляет один игрок, причем один игрок может управлять несколькими агентами.

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

Пусть доход проекта равен 1, а затраты на выполнение операций – нулевые.

Формальное определение будет выглядеть так.

D = {1, 2,3} – множество операций;

e = 1 – матрица принадлежности операций к проектам;

(1,1, 2, 2,3,3) – разбиение множества агентов по операциям.

(1,1, 2, 2,3,3) – разбиение множества агентов по игрокам.

h = (100 ) – вектор доходов от реализации проектов.

Пример 1.1 (Окончание) Определение 1. Дележом в проектной игре назовем следующую совокупность объектов ( ) = { R, {ms }sR, B, {rl }lB, ( pl )lB }, где {ms }sR – типы реализованных проектов: каждый реализованный • B A – множество оперирующих агентов, т.е. агентов, участвующих в дележе;

{rl }lB – распределение оперирующих агентов по реализованным проектам, rl R – проект, в котором участвует агент l ;

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

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

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

Объединение дележей с непересекающимися множествами оперирующих агентов также будет дележом.

Для агентов, не участвующих в проекте положим rl = 0, l A \ B, а их прибыли будут нулевым: ul = 0, l A : rl = 0. Выигрыш игрока при дележе ( ) – Один из возможных дележей для игры из примера 1 – это когда реализовались два (одинаковых) проекта:

R = {1, 2} – множество реализованных проектов, Выигрыши игроков при таком дележе, соответственно U = ( 40 65 95).

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

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

Проектной игрой с различными агентами будем называть игру раций тождественны D A ; dl = l, l A.

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

Замечание Произвольную проектную игру можно представить в виде проектной игры с различными агентами.

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

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

1.2.2 Аукцион с наведенными заявками Основой построения аукциона с наведенными заявками [26, 27] служит принцип открытого непрерывного двойного аукциона. Игра проходит в заданном промежутке времени t ( 0; T ), в течение которого каждый агент l A варьирует свою заявку pl (t ) на получение дохода. Эта заявка означает готовность агента выполнить свою операцию (без уточнения, в рамках какого проекта будет выполнена операция) и получить за это доход не меньше pl (t ). В качестве информации о текущем состоянии игры каждый агент получает встречную (наведенную) заявку ql (t ), которая означает предложение поучаствовать в наиболее выгодном для данного агента проекте. Встречная заявка для агента составляется и вычисляется на основе заявок остальных агентов. В момент, когда заявка некоторого агента l станет равной наведенной, реализуется проект, включающий агента l и всех тех агентов, которые образовали для него наилучшую наведенную заявку. При этом агенты, вступившие в проект, выходят из игры и получают доход, согласно своим заявкам (рис. 1.1).

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

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

Теперь о правиле формирования наведенной заявки. Для каждой операции создается рынок, состоящий из двух очередей заявок: простых и наведенных. Каждый агент l A варьирует заявку на рынок своей операции. Отсутствие заявки (в т.ч. в начале игры) можно интерпретировать как заявку с очень большим номиналом: P > (| h j |,| cl |). Под простой заявкой (от агенjM,l A та) в каждый момент 0 < t < T будем понимать пару l = ( pl, l ), где cl < pl P – номинал заявки, 0 l < t – время последнего изменения номинала. Нетрудно заметить, что функции pl (t ) получаются кусочно-постоянными.

Для определения наведенной заявки необходимо ввести дополнительные понятия. Фиксируем операцию i D и один из проектов, содержащих эту операцию j M i. Возьмем по одному агенту, выполняющему операции, дополняющие операцию i до проекта j. Полученное множество назовем множеством контрагентов Aji A, т.е. множеством, удовлетворяющим условиям:

Совокупность множеств контрагентов для каждой связной пары (i, j ) [ D, M ] обозначим ji. Можно заметить, что количество множеств контрагентов ji может быть достаточно большим. Но для проектной игры с различными агентами, когда каждую операцию может выполнить только один агент (см. опр. 1.3), все множества ji состоят из одного элемента.

Построим множество контрагентов для проектной игры из примера 1.1.

Фиксируем операцию i = 1, и единственный допустимый проект j = 1. Тогда множествами контрагентов будут всевозможные комбинации агентов, выполняющих операции i = 2,3 : 1 = {{3;5}, {3; 6}, {4;5}, {4;6}}. Для остальных операций аналогично: 2 = {{1;5}, {1; 6}, {2;5}, {2;6}}, 3 = {{1;3}, {1; 4}, {2;3}, {2; 4}}.

Определение 1. Наведенной заявкой от множества контрагентов Aji ji будем называть заявку с номиналом Определение 1.4 (окончание) Данная заявка означает остаток, который может получить агент за выполнение операции i от реализации допустимого проекта j при условии, что контрагенты получат свой заявленный доход.

Как уже было сказано, наилучшая наведенная заявка для операции i D – это наибольшая из всех наведенных. Очевидно, что она должна состоять из простых заявок с минимальным номиналом. Таким образом, номинал наилучшей простой заявки для каждой операции i будет вычислен по формуле:

pi* = min pl. Далее для каждой операции номинал наилучшей наведенной с каждого проекта j M i (содержащего эту операцию) заявки вычисляется по каждой операции i будет вычислен по формуле: qi* = max qij *. И, наконец, ноjM i минал наилучшей наведенной заявки для каждого агента l A будет:

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

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

При изменении номинала одной простой заявки может измениться номинал сразу нескольких наведенных. Из-за этого указанный алгоритм сравнения заявок не справляется с задачей детерминированного упорядочивания заявок. Под наведенной заявкой от множества контрагентов Aji A будем понимать ( Aji ) = ( q( Aji ), (|D |1),..., (1), 0 ), где (|D |1) >... > (1) – упорядоченные по убыванию времена простых заявок контрагентов, а q( Aji ) вычисляется по формуле (1.1). Простые заявки, из которых состоит наведенная, будем называть базой наведенной заявки. Тогда сравнение наведенных заявок будет осуществляться по следующему лексикографическому правилу. Наведенная заявка с бльшим номиналом лучше. При равенстве номиналов сравниваем первую пару времен: лучше та, у которой это время меньше. При равенстве очередной пары времен сравниваем следующую и т.д. Если база одной заявки является подмножеством базы другой, то лучшей считает, та, у которой база меньше (при условии равенства номиналов, конечно). Таким образом, на множестве наведенных заявок построено отношение порядка.

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

Утверждение 1. Любая пара наведенных заявок сравнима относительно построенного порядка (построенный порядок является полным).

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

Утверждение 1. Если базы двух наведенных заявок отличаются только парой простых заявок, то наведенная заявка, имеющая в своем составе лучшую простую, – лучше.

Утверждение 1. Наилучшая наведенная заявка состоит из наилучших простых.

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

В процессе торгов важным понятием является сделка. Сделка в проектной игре – это дележ (), состоящий из одного реализованного проекта (см. опр. 1.2). Фактически образование сделки означает, что агенты договорились о реализации одного проекта и распределении дохода этого проекта.

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

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

Еще одним важным понятием будет сделка, согласованная с заявками.

Сделка () называется согласованной с вектором заявок { pl }lA, если доход каждого оперирующего агента не меньше его заявки: pl ( ) pl, l B ( ), где B ( ) – множество оперирующих агентов, а pl ( ) – их доходы.

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

Описание клирингового механизма Если при подаче агентом l очередной заявки = ( p, ) на рынок i = dl во время такта выполняется условие:

где qi* вычисляется по формуле (1.2), тогда происходит сделка, и заявка агента l удовлетворяется по номиналу наведенной заявки, а все те простые, из которых состоит наведенная, удовлетворяются по своим номиналам. При этом удовлетворенные заявки исключаются из очередей, а агенты переходят из множества активных во множество оперирующих.

Иначе (если (1.3) не выполняется) новая заявка добавляется в соответствующую очередь.

В обоих случаях происходит перерасчет наведенных заявок (достаточно посчитать только наилучшие наведенные заявки).

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

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

Теорема 1.1 (окончание) Первое утверждение эквивалентно утверждению: на каждом такте сделки, согласованные с заявками, существуют тогда и только тогда, когда выполняется неравенство (5). Первая часть второго утверждения говорит, что агент, подавший замыкающую заявку, получает максимальный доход. Фактически это означает, что замыкающий агент соглашается с встречной заявкой, которая по определению является наилучшим предложением для данного агента. Вторая часть второго утверждения является обобщением наиболее распространенного правила, что среди заявок с одинаковым номиналом лучшей считается та, которая была подана раньше. Обобщение необходимо, так как подача одной простой заявки может привести к появлению нескольких наведенных. Для пояснения обратимся к проектной игре из примера 1.

Пусть агенты последовательно подают следующие заявки: 1 = (20,1), 2 = (20, 2), 3 = (30,3), 4 = (35, 4), 5 = (50,5), 6 = (40, 6). Тогда во время третьего такта появляются две заявки на рынок i = 3 : ( 1, 3 ) = (100 20 30 = 50;3,1) и ( 2, 3 ) = (100 20 30 = 50;3, 2). И первая наведенная заявка будет лучше второй: (50;3,1) (50;3, 2). В данном случае номиналы наведенных заявок и времена их появления совпадают, и применяется лексикографическое правило сравнения. Это лексикографическое правило формализует тот факт, что первый агент раньше второго подготовил третьему агенту возможность сделать наведенную заявку, поэтому наведенная заявка, включающая первого агента лучше. На четвертом такте появляются еще две наведенные заявки на рынок заявок будет следующей: (50;3,1) (50;3, 2) (45; 4,1) (45; 4, 2). На пятом такте, очевидно, выполняется условие клиринга и должна произойти сделка, но возможны две сделки (согласованные с заявками) с тройками агентов (1, 3,5) или (2,3, 5). Клиринговый механизм выбирает первую: реализуется единственный допустимый проект и в нем участвуют агенты (1, 3,5), а их доходы:

x1 = 20, x3 = 30, x5 = 50. При этом в очереди наведенных заявок для рынка i = остается всего одна заявка: ( 2, 4 ) = (45; 4, 2). И, наконец, на шестом такте подается заявка шестым агентом, но опять возникает целое множество сделок, согласованных с заявками. Это всевозможные сделки агентов 2, 4 и 6, удовлетворяющие условиям: x2 20, x4 35, x6 40, x2 + x4 + x6 = 100, но клиринговый механизм выбирает ту, в которой замыкающий (шестой) агент получает максимальный доход: x2 = 20, x4 = 35, x6 = 45.

Доказательство теоремы 1. Если клиринговый механизм совершает сделку, то эта сделка, по построению, будет согласована с заявками.

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

Ну и наконец, второе утверждение теоремы является прямым следствием основного правила клирингового механизма (сделка происходит по цене наведенной заявки) и лексикографического правила упорядочивания заявкок.

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

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

1.3.1 Кооперативная игра Рассмотрим кооперативную игру (с трансферабельной полезностью зом. В качестве множеств игроков, агентов и операций берется множество игроков в кооперативной игре: N * = A* = D* = N. Множество проектов – это eS =, i N *, S M *. Как уже было сказано, множества игроков, агентов и операций совпадают: dl = nl = l, l A*. Затраты на выполнения операций нулевые: cl = 0, l A*. Доходы проектов – выигрыши коалиций: h S = v( S ), S M *.

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

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

Введем некоторые обозначения. Пусть j = 1,..., m – произвольным образом пронумерованные агенты – продавцы, покупатели и транспортировщики.

Обозначим через S множество всех продавцов, T – всех транспортировщиков, B – покупателей. Соответственно, | S | + | T | + | B |= m. Все агенты заданным способом разделены по собственникам.

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

Предположим, что затраты поставщика или транспортировщика j на единицу k составляют c kj > 0, а выкупная стоимость покупателя j от единицы k равна v kj > 0. Можно считать, по выкупной стоимости покупатель реализует товар конечным потребителям. Прибылью продавца (транспортировщика) j в результате заключения сделки по единице k на сетевом рынке мы будем называть разницу p kj c kj между ценой продажи p kj и затратами на производство (транспортировку) данной единицы. Прибылью покупателя от покупки единицы k назовем разницу v kj p kj между стоимостью реализации товара конечным потребителями v kj и ценой покупки p kj. Общий выигрыш является суммой прибылей по всем сделкам. В случае если агент не заключил ни одной сделки, его выигрыш полагается равным нулю.

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

Итак, рассмотрим сетевой аукцион на двухполюсном графе G = (V, E ). На каждом ребре данного графа находятся три типа агентов A = AS AT AB : продавцы, транспортировщики и покупатели. Причем продавцы находятся на ребрах, исходящих из источника, а покупатели – на ребрах, ведущих в сток:

расположение агентов задано в виде отображения множества агентов во множество ребер {e(l ) E}lA. Каждый продавец и транспортировщик l AS AT может произвести или транспортировать одну единицу товара с затратами cl > 0, а выкупная стоимость покупателя l AB равна vl > 0. И, наконец, есть заданное множество собственников N и отображение множества агентов во множество собственников {n(l ) N }lA.

зом. Множество операций – это множество дуг в двухполюсном графе:

D* = E, множество проектов – это всевозможные пути графа, не содержащие циклов, из источника s V в сток t V : M * = Path( s, t ). Матрица принадлежности операций к проектам соответствует принадлежности дуг к маршрутам:

eij =, i E, j Path( s, t ). Множество игроков – это множество собственниi j ков: N * = N. Множество агентов проектной игры совпадает с множеством d l * = e(l ), l A, а распределение агентов по игрока совпадает с распределением по собственникам: nl * = n(l ), l A. Затраты продавцов и транспортировщиков остаются неизменными: cl * = cl > 0, l AS AT, а в качестве затрат покупателей берутся их выкупные стоимости со знаком минус: cl * = vl < 0, l AB.

Доходы проектов полагаются равными нулю: h j = 0, j M *.

Как видно, в описанном построении есть два неэквивалентных преобразования: это множество проектов и затраты покупателей. Проверим, что такое преобразование сохраняет свойства сетевого аукциона. В сетевом аукционе проект это добыча единицы продукта в некоторой вершине, транспортировка по одному или нескольким ребрам в вершину с покупателем и, наконец, потребление этой единицы в конечной вершине. Но это как раз и есть полный маршрут из источника в сток в двухполюсном графе. Теперь разберемся с ценами и доходами. Возьмем произвольный маршрут j Path( s, t ), и выберем одного продавца, одного покупателя и по одному транспортировщику из каждой дуги маршрута: ls lb {lt }. Понятно, что для заключения такой сделки необходимо, чтобы цена покупки была равна цене продажи плюс сумме цен за транспортировку: pb = ps + pt. При этом прибыль продавца и транспортировщиков будет разница их цен и затрат, прибыль покупателя – его выкупная стоимость минус цена покупки ub = vb pb. Если в дележе в проектной игре доход покупателя интерпретировать как минус цену покупки pb* = pb, то тогда правило дележа (сделки) в проектной игре совпадет с правилом сделки в сетевом аукционе. Условие дележа: ps + pt + pb* = h j = 0, прибыль агента-покупателя ub* = pb* cb* = pb (vb ) = ub. Что и требовалось подтвердить.

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

1.3.3 Рынок товаров коллективного пользования Товары коллективного пользования характеризуются тем, что при производстве единицы такого товара прибыль от его реализации могут получить сразу несколько экономически агентов (примерами таких товаров могут служить дороги, мосты, или даже программное обеспечение для компьютеров).

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

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

В качестве примера рассмотрим один из проектов с товаром коллективного пользования. Пусть для производства товара требуется несколько операций Ds, а также пусть найдутся агенты As, способные выполнить эти операции с заданными затратами: {cl }lA. А также пусть есть некоторое множестs во агентов Ab, которые могут получить заданные выкупные стоимости {vl }lA b в случае производства единицы данного товара. Ну и естественное условие для осуществления сделки по производству единицы товара – суммарная цена покупки должна быть равна суммарной цене на производство:

Идея построения проектной игры по приведенному примеру аналогична той идее в сетевых аукционах, где некоторые величины умножались на коэффициент 1 для покупателя. Множество операций D* = Ds Db, где Db – это операции потребления готового продукта агентами из множества Ab. Множество агентов: A* = As Ab, и их затраты: cl * = cl, l As, cl * = vl, l Ab. Доход такого проекта, как и в случае сетевых аукционов нулевой: h = 0. Нетрудно убедиться, что условие дележа и правила вычисления прибылей удовлетворяют естественным соотношениям.

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

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

Глава 2 Динамические кооперативные игры Кооперативная теория игр рассматривает экономические ситуации с помощью построения характеристических функций. Обычно теория дает множества справедливых в определенном смысле дележей, а также предлагает конкретные селекторы указанных множеств. В данной главе рассматривается обратная задача, т.е. по заданной характеристической функции строится динамическая игра. Пример исследования такой задачи можно найти в работах [1, 11]. В данной же работе в качестве механизма предлагается непрерывный двойной аукцион с наведенными заявками (см. [41, 43]).

2.1 Общие сведения о кооперативных играх Рассмотрим кооперативную игру G coop = { N,V }, где N = {1,..., n} – множество игроков, V : 2 N + – супераддитивная характеристическая функция, Для удобства будем различать обозначение произвольной коалиции S N, включающей максимальную коалицию, и обозначение собственной коалиции S N.

Одним из ключевых понятий в кооперативной теории является дележ.

Дележ – исход игры, при котором реализуется максимальная коалиция и все игроки получают неотрицательные выигрыши. Пусть x = ( x1,..., xn ) – это вектор выигрышей игроков, тогда множество дележей можно записать так (см.

рис 2.1):

Рис. 2.1 Множество дележей Подмножество дележей, в которых каждая коалиция получает выигрыш, не меньший, чем она могла бы получить, отделившись от максимальной коалиции, называется ядром или C-ядром (см. рис 2.2):

Кооперативная игра называется сбалансированной, если для любого сбалансированного покрытия : 2 N ( S ) = 1, i N, выполнено условие ( S )V (S ) V ( N ). По теореме Бондаревой–Шепли [15, 22] ядро игры не пусто тогда и только тогда, когда она сбалансирована.

2.2 Динамическая кооперативная игра Под динамической кооперативной игрой мы будем понимать динамическую проектную игру, которая построена по кооперативной. Подробно будет рассмотрена динамическая кооперативная игра с наведенными заявками.

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

Как и прежде, каждый игрок i формирует заявку на получение некоторого выигрыша pi (t ), i N ; t (0, T ). При этом он получает множество наведенных заявок – остатки от выигрышей коалиций после вычета заявок партнеров по соответствующим коалициям. Как и для произвольной проектной игры, в качестве предложения вступить в одну из коалиций выбирается максимальная из заявок всех коалиций S, в которые входит игрок i :

И, наконец, вспомним о лексикографическом правиле сравнения заявок.

Сначала сравниваются номиналы заявок (чем больше, тем лучше), затем максимальные времена простых (чем меньше, тем лучше), и так далее. В таком случае может оказаться, что если база некоторой заявки является подмножеством другой, то более «короткая» будет лучшей (конечно при условии равенства номиналов). Приведем пример такой пары векторов времен: (3; 2;1) и (3;1). Но в таком случае надо в любой паре «вложенных» заявок «лучшей»

считать «короткую», например (3; 2;1) и (3; 2). Это условие эквивалентно приписыванию к вектору времен (справа) нулевого времени.

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

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

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

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

Определение 2.1(окончание) Определение 2. Очищенной динамической кооперативной игрой с наведенными заявками будем называть динамическую кооперативную игру с наведенными заявками, в которой проекты построены для тех и только тех коалиций S N, у которых выигрыш положителен V ( S ) > 0.

Определение 2.2 (окончание) 2.3 Дополнительные определения и утверждения Для анализа динамической кооперативной игры с наведенными заявками потребуется ввести дополнительные понятия, а также сформулировать и доказать некоторые утверждения.

Как и раньше вектор, составленный из заявок всех игроков x = { xi }iN, будем называть состоянием игры. В тексте под состоянием игры понимать не только сами состояния, но и произвольные вектора из множества n. Данное множество будем называть обобщенным пространством состояний. Также будем считать, что все известные множества (например, дележи, ядро и другие) лежат в этом пространстве. Суммы заявок игроков коалиций в состоянии x обозначим следующим образом: i Для дальнейшего анализа потребуется ввести дополнительные определения [42].

Определение 2. удовлетворяющее условиям:

Определение 2.3 (окончание) Неравенства второй строки (2.4) являются следствием остальных, поэтому определение малого предъядра можно записать так:

Определение 2. удовлетворяющее условиям:

Определение 2.4 (окончание) Часть неравенств второй строки (2.5) являются следствием остальных, поэтому определение большого предъядра можно записать так:

Изображения большого и малого предъядер в трехмерном пространстве приведены на рис. 2.3 и 2.4.

Рис. 2.3 Малое предъядро Рис. 2.4 Большое предъядро 2.3.1 Критерии существования предъядер Мы определили два множества: большое и малое предъядра. В данном разделе будет сформулирована и доказана теорема о непустоте указанных множеств в обобщенном пространстве состояний. Формулы, описывающие множества для предъядер, очень похожи на формулы определения ядра, поэтому критерии их существования будем искать схожими с условиями теоремы Бондаревой–Шепли.

условие Определение 2.5 (окончание) Строго сбалансированные игры отличаются от просто сбалансированных, тем, что здесь строгие неравенства.

Обозначим множества ядра, малого предъядра и большого предъядра в лежности операций к проектам за исключением столбца (строки) с коалицией всех игроков. Тогда определение ядра можно записать через матриxi = V ( N ) тия: : 2 N [0;1] можно записать:

Рассмотрим экстремальную задачу:

и найдем связь ее решения с ядром игры.

Лемма 2. экстремальной задачи (2.8) удовлетворяет условию:

Доказательство ность относительно подпространства xi = V ( N ), а не относительно аффинiN ной оболочки ядра).

Пусть внутренность ядра не пустая, тогда существует такой вектор x, что Лемма 2. Доказательство Зафиксируем произвольное сбалансированное покрытие. Для всех ления сбалансированного покрытия найдется хотя бы одна коалиция, для коS > 0.

лансирована.

вания, двойственную задаче (2.8):

По теореме двойственности – решение экстремальной задачи (2.9), которое удовлетворяет условиям:

* E, g ( * ) = L V ( N ). Таким образом мы нашли сбалансированное покрытие *, не удовлетворяющее условию (2.6), значит, игра не является строго сбалансированной. Лемма доказана.

Лемма 2. В игре малое предъядро не пусто тогда и только тогда, когда игра строго сбалансирована.

Доказательство Пусть малое предъядро не пусто, тогда существует можно уменьшить на величину, и при этом полученная точка будет лежать Обратно. Пусть игра строго сбалансирована, тогда по лемме 2. Это значит, что существует Лемма 2. В игре большое предъядро не пусто тогда и только тогда, когда игра строго сбалансирована.

Доказательство Пусть большое предъядро не пусто, тогда существует Обратно, пусть игра строго сбалансирована, тогда по лемме 2.3 малое предъядро не пусто, а т.к. каждая точка малого предъядра является точкой большого предъядра и большое предъядро не пусто. Доказано.

Теорема 2. Для кооперативной игры лиц следующие утверждения эквивалентны:

• Игра строго сбалансирована.

• Малое предъядро игры не пусто.

• Большое предъядро не пусто.

Теорема 2.1 (окончание) Формально доказательство следует из лемм 2.1 – 2.4.

Доказательство эквивалентности первого и второго пунктов аналогично доказательству теоремы Бондаревой–Шепли. Далее, если внутренность ядра непуста, то можно из любой точки внутренности немного «подняться» вдоль одной из осей и оказаться в малом предъядре. Значит, из непустоты внутренности ядра следует непустота малого предъядра. Малое предъядро содержится в большом, поэтому из непустоты малого следует непустота большого. И, наконец, из любой точки большого предъядра можно «спуститься» вдоль направления к началу координат и попасть во внутреннюю точку ядра. Значит, из непустоты большого предъядра следует непустота внутренности ядра.

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

Утверждение 2. Для строго сбалансированной игры пересечение замыкания малого предъядра с плоскостью дележей ( x( N ) = VN ) совпадает с ядром.

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

Утверждение 2. Для строго сбалансированной игры пересечение замыкания большого предъядра с плоскостью дележей ( x( N ) = VN ) совпадает с ядром.

Доказательство По определению малое предъядро содержится в большом предъядре, значит, пересечение замыкания малого предъядра с плоскостью дележей содержится в исследуемом пересечении. Докажем обратное включение. Не хваx( S ) V ( N ), S : V ( N \ S ) = 0, Доказано.

2.3.2 Блокирующие состояния Напомним, что для динамической проектной игры активный агент – это агент, который еще не вступил в сделку и может управлять своей заявкой. В динамической кооперативной игре с наведенными заявками, как уже было сказано, агентов будем отождествлять с игроками.

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

Состояние, в котором все игроки активны, назовем активным состоянием. Понятно, что если игра находится в активном состоянии, то до этого момента включительно еще не произошло ни одной сделки. Далее определим еще несколько видов активных состояний. Блокирующие состояния были исследованы в работе [49].

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

Определение 2.6 (окончание) Теперь вспомним о дополнительных определениях и сформулируем и докажем теоремы. Для этого необходимо доказать несколько лемм.

В динамической кооперативной игре с наведенными заявками активныx n, Доказательство Неравенства в условии леммы эквивалентны, что в данный момент не возможна ни одна коалиция (не выполняются условия реализации проекта – коалиции). Но сделка не могла произойти и до этого момента, потому что x ( S0 ) = V ( S 0 ). После этого агенты перестали бы быть активными и не смогли изменять свои заявки. Таким образом, неравенства условий леммы эквивалентны активности состояния x.

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

Доказательство Достаточность очевидна: если номинал больше, то по основному правилу сравнения заявка с максимальной коалиции лучше.

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

Доказательство (окончание) Для доказательства очередной леммы необходимо ввести еще одно опx n ределение. Для состояния игры определим эксцесс для каждой коалиции как разницу между суммой заявок участников коалиции и номинальным выигрышем этой коалиции: ( S ) x(S ) V (S ), S N.

заявками следующие утверждения для некоторой собственной коалиции SN эквивалентны.

Доказательство утверждение леммы, использую эквивалентные преобразования.

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

Теорема 2. В полной динамической кооперативной игре с наведенными заявками множество блокирующих состояний совпадает с малым предъядром.

Теорема 2.2 (окончание) Условие теоремы можно переформулировать. В полной динамической кооперативной игре с наведенными заявками состояние является сильно блокирующим в том и только в том случае, если оно принадлежит малому предъядру.

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

По лемме 2.5 первое и набор вторых условий малого предъядра эквивалентно тому, что состояние активно.

Условие блокирования (никакой игрок своим ходом не может реализовать никакую коалицию, кроме коалиции всех игроков) в силу правила аукi N циона эквивалентно тому, что для каждого игрока наилучшей наведенной заявкой является заявка, наведенная с максимальной коалиции iN с ноp( iN ) = qiN является наилучшей тогда и только тогда, когда ее номинал строго больше номиналов других заявок, причем это выполнено для всех игроков и коалиqiN > qiS, i N, S N : i S.

лициям получаем, что последнее условие эквивалентно условию x( N \ S ) < V ( N ) V ( S ), S N. А набор этих условий эквивалентен третьему набору условий малого предъядра (2.4): в этом нетрудно убедиться, сделав замену SN \S. Теорема доказана.

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

Теорема 2.3 (окончание) Вспомним, что в очищенной динамической кооперативной игре с наведенными заявками проекты строятся только коалиций с положительным выV (S ) > 0.

игрышем Также вспомним определение большого предъядра. По опx n выполнение условий (см. 2.5):

По лемме 2.5 первое и набор вторых условий малого предъядра эквивалентно тому, что состояние активно.

Условие блокирования (никакой игрок своим ходом не может реализовать никакую коалицию, кроме коалиции всех игроков) в силу правила аукi N циона эквивалентно тому, что для каждого игрока наилучшей наведенной заявкой является заявка, наведенная с максимальной коалиции iN с ноp( iN ) = qiN что заявка с максимальной коалиции является наилучшей тогда и только тогда, когда ее номинал строго больше номиналов других заявок, причем это qiN > qiS, i N, S N : i S,V ( S ) > 0. Применяя лемму 2.7 ко всем собственным набор этих условий эквивалентен третьему набору условий большого предъSN \S.

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

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

Доказательство – активное состояние. Применяя лемму 2.7 ко всем собственным коалиx них неравенств (2.5) следует, что для всех игроков участвующих в каiS.

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

Утверждение 2. В очищенной динамической кооперативной игре с наведенными заявками любая точка малого предъядра является блокирующим состоянием.

Доказательство Доказательство следует, из теоремы 2.3 и того, что малое предъядро содержится в большом.

2.3.3 Условия согласованности Задача построения динамической кооперативной игры – это обратная задача к рассматриваемой в кооперативной теории. То есть по заданной характеристической функции строится новая динамическая игра. Но к полученной динамической игре можно снова применить кооперативный подход и построить новую характеристическую функцию. При этом сразу возникает вопрос: а совпадает ли новая характеристическая функция с исходной?

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

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

Определение 2. Множество достижимости в динамической кооперативной игре – это подмножество дележей, которое может реализоваться в игре.

Определение 2.7 (окончание) Используя введенное понятие, можем более формально определить слабую согласованность. Назовем динамическую кооперативную игру слабо согласованной, если множество достижимости не пусто.

Теперь исследуем вопрос согласованности для динамических кооперативных игр с наведенными заявками. Основным результатом будет следующая теорема.

Множество достижимости для динамической кооперативной игры наведенными заявками совпадает с множеством внутренних точек ядра.

Доказательство Пусть вектор принадлежит внутренности ядра. Докажем, что точка z = ( x1 +, x2,…, xn ) будет принадлежать малому предъядру (см. доказательство леммы 2.3). По теореме 2.2 состояние – блокирующее состояние, а значит, активно. В активное состояние попасть просто: все игроки последовательно выставляют соответствующие заявки. При этом ни одна коалиция не заключается, т.к. состояние активно. Далее первый игрок соглашается со своей наведенной заявкой (в блокирующем состоянии наилучшая заявка наводится с максимальной коалиции). По правилу аукциона совершается сделка – максимальная коалиция, причем все получают доход согласно своим заявкам. Таким образом, игра достигнет желаемого состояния x.

состояние было достигнуто, когда один из игроков согласился с наведенx некоторый дележ игры, т.е. это реализованная максимальная коалиция. Итак, игрок замкнул максимальную коалицию, уменьшив свою заявку на некотоi рую величину i > 0, значит, до этого момент все игроки были активными, т.е.

симальной коалиции iN была лучше любой другой наведенной заявки для этого игрока iS, S N : i S. По лемме 2.6 для номиналов указанных заявок ных коалиций, содержащих игрока i :

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

Доказательство (окончание) Теперь можно подытожить все полученные результаты и сформулировать критерии согласованности для динамических кооперативных игр с наведенными заявками.

Утверждение 2. Для того чтобы динамическая кооперативная игра с наведенными заявками была слабо согласованна, необходимо и достаточно, чтобы исходная кооперативная игра была строго сбалансирована.

Доказательство Доказательство напрямую следует из теорем 2.1 и 2.4.

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

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

2.4 Примеры для игры трех лиц В этом разделе будем рассматривать кооперативную игру трех лиц.

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

2.4.1 Общие сведения об игре трех лиц В этом разделе будем рассматривать игры, в которых множество игроN = {1, 2,3}.

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

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

В силу супераддитивности характеристической функции без ограничения общности можно положить 0 a b c d = 100.

Одним из ключевых понятий в кооперативной теории является дележ.

Дележ – исход игры, при котором реализуется максимальная коалиция и все игроки получают неотрицательные выигрыши. Пусть x = ( x1, x2, x3 ) – это вектор выигрышей игроков, тогда множество дележей (см. рис. 2.1) можно записать так:

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

По теореме Бондаревой–Шепли [15, 22] ядро не пусто тогда и только тогда, когда она сбалансирована. Для приведенной кооперативной игры трех лиц сбалансированность игры определяется параметром, где Таким образом, ядро не пусто тогда и только тогда, когда 0. Причем, если > 0, то игра строго сбалансирована и ядро не вырождено, т.е. имеет максимальную размерность. Для игр трех лиц невырожденное ядро является плоским многоугольником.

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

Один из примеров построения подобных механизмов можно найти в [1, 11], где для образования коалиции используется последовательное голосование за предложенный одним из игроков дележ.

Далее будет определен и проанализирован механизм наведенных заявок для кооперативных игр.

2.4.3 Аукцион с наведенными заявками для игры трех лиц Теперь опишем механизм для случая произвольной строго сбалансированной кооперативной игры трех лиц в редуцированной форме. Есть четыре выигрывающие коалиции с выигрышами a, b, c, d. Как и в игре двух лиц каждый игрок формирует заявку на получение некоторого выигрыша pi (t ), i = 1, 2, 3; t (0, T ). Каждый игрок может вступить в одну из трех коалиций, соответственно, он получает три наведенные заявки. Например, первый игрок получает заявки – остатки от выигрышей коалиций после вычета заявок партнеров по соответствующим коалициям. Естественно в качестве заявки с предложением первому игроку вступить в коалицию выбрать максимальную из полученных заявок: q1 (t ) = max ( q1a (t ), q1b (t ), q1d (t ) ). Это согласуется с основным правилом непрерывного двойного аукциона, когда наилучшей заявкой типа «спрос» является заявка с максимальным номиналом.

Второе условие: в случае если номиналы заявок равны, приоритет отдается той заявке, которая была подана раньше. В данном случае временем заявки будет максимальное время подачи простых заявок, из которых состоит наведенная. Но даже в случае трех игроков может возникнуть неоднозначность. Предположим, что сначала подал заявку игрок 1 в момент t1, затем игрок 2 в момент t2, тогда в момент t2 образуются сразу две заявки для игрока 3: q3d (t2 ) и q3c (t2 ). И если их номиналы окажутся равны, то заявки будут несравнимы в классическом аукционе. В таком случае предпочтение отдается парным коалициям. Такой приоритет выбран для выполнения условий согласованности, о которых будет написано ниже.

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

Условия согласованности выбираются из следующих соображений. Нетрудно проверить, что если ядро игры пусто, то никакие (с том числе совместные) действия игроков не смогут привести к образованию максимальной коалиции (для замыкающего игрока всегда найдется заявка с парной коалиции, которая будет для него выгоднее, чем максимальная). Значит, одним из необходимых условий возможности дележа является непустота ядра. Также, можно заметить, что если ядро состоит из одной точки, например (100 / 3,100 / 3,100 / 3), когда a = b = c = 200 / 3, то в этом случае реализовать дележ тоже будет невозможно. Это следует из того, что если два игрока подадут свои заявки, то в этот же момент образуется парная коалиция.

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

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

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

2.4.4 Блокирующие состояния Рассмотрим предложенный механизм более детально. Приведем анализ от лица первого игрока. Он не входит только в одну из четырех коалиций с номинальным выигрышем V (2,3) = c. Зададимся вопросом, может ли игрок сделать такую заявку, чтобы образование коалиции (2,3) стало невозможным в рамках аукциона. Запишем условие, при котором второму и третьему игрокам будет выгоднее вступить в максимальную коалицию:

d p2 p1 = q3 > q3 = c p2 ; d p3 p1 = q2 > q2 = c p3. Решая систему неравенств относительно p1 получаем p1 < d c.

Проведя аналогичные рассуждения для остальных игроков, получим блокирующее состояние ( p1, p2, p3 ) :

Назовем полученное множество большим предъядром (см. рис. 2.3). Связь с ядром можно заметить, сравнивая последнюю систему неравенств определением ядра. Можно сформулировать следующее утверждение. Если игра находится в состоянии p = ( p1, p2, p3 ) из большого предъядра, то никакой игрок своим ходом не сможет реализовать никакую коалицию с положительным выигрышем, кроме, быть может, максимальной.

Теперь построим множество состояний игры, в которых блокированными оказываются все коалиции, а не только выигрывающие:

Назовем полученное множество малым предъядром (см. рис. 2.4) Сформулируем еще одно утверждение. Если игра находится в состоянии p = ( p1, p2, p3 ) из малого предъядра, то никакой игрок своим ходом не сможет реализовать никакую коалицию, кроме максимальной.

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

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

Определение 2. Игра с нулевыми выигрышами малых коалиций – это кооперативная игра, характеристическая функция которой удовлетворяет условиям:

Определение 2.8 (окончание) Нетрудно убедиться, что приведенная игра трех лиц принадлежит этому классу. Многие результаты, полученные для игр трех лиц, будут справедливы и для всего класса игра с нулевыми выигрышами малых коалиций [49, 51].

Обозначим выигрыши ненулевых коалиций и сумму выигрышей всех собственных коалиций следующим образом:

Без ограничения общности будем считать, что выполняется условие Игра с нулевыми выигрышами малых коалиций строго сбалансирована тогда и только тогда, когда Доказательство Далее для каждого игрока гой сбалансированности для таких покрытий будут означать, что i > 0, i N.

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

Для строго сбалансированных игр с нулевыми выигрышами малых коалиций большое предъядро является усеченным параллелепипедом:

Доказательство В ограничения параллелепипеда входят все неравенства из определения большого предъядра, значит, большое предъядро содержится в параллелепипеде.

Доказано.

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

2.5.1 Вычисление N-ядра Значение N-ядра вычисляется как распределение выигрыша, на котором степень неудовлетворённости самых неудовлетворенных коалиций, измеряемая величиной их эксцесса, будет наименьшей [36].

Обозначим через e( x) для каждого допустимого распределения выигрышей x в кооперативной игре ( N,V ) вектор эксцессов всех коалиций, с элементами, упорядоченными по возрастанию. Напомним, что эксцесс – это разница между выигрышем коалиции и значением характеристической функции: ( S ) = x( S ) V ( S ), S N.

N-ядром кооперативной игры называется точка x, соответствующая минимуму отношения лексикографического порядка на множестве всевозможных векторов e( x) для x принадлежащих множеству дележей игры.

Вычислить N-ядро можно следующим способом. Основная идея нахождения N-ядра – это максимизация минимального эксцесса: min ( ( S ) ) max.

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

Пусть D0 = D – множество дележей, а 0 = 2 N \ N – множество собственных коалиций. Тогда на первом шаге мы находим подмножество дележей, на ключаем из рассмотрения коалиции, на которых достигает минимум эксцесarg min ( ( S ) ) x D1.

должать до тех пор, пока при некотором значении k множество Dk не станет точкой. Это и будет искомым значением N-ядра. Этот процесс завершится в худшем случае за n 1 шаг, т.к. на каждой итерации размерность множества Dk уменьшается хотя бы на единицу, а размерность множества дележей равна На самом деле исключаемые коалиции (те, на которых достигается минимум эксцессов) являются сбалансированными покрытиями. Напомним, что сбалансированное покрытие – это такое распределение на множестве коаличто выполнено условие ( S )V (S ) V ( N ).

Поэтому поиск минимума эксцессов сводится на каждом шаге к поиску ключевого покрытия.

2.5.2 Алгоритм вычисления N-ядра для игр с нулевыми выигрышами Теперь приступим к вычислению N-ядра для произвольной игры с нулевыми выигрышами малых коалиций. Напомним, что произвольная такая игра Теорема 2.7 (о вычислении N-ядра) Для игр лиц с нулевыми выигрышами малых коалиций N-ядро вычисляется как функция параметров {Vi }. Причем пространство значений {Vi } делится на областей, в каждой из которых все компоненты N-ядра вычисляются линейными функциями параметров {Vi }.

таблицу 2).

Теорема 2.7 (окончание) Доказательство теоремы 2. Для N-ядра минимум эксцессов всегда достигается на некотором сбалансированном покрытии [34]. Для игр с нулевыми играми малых коалиций множество возможных сбалансированных покрытий уменьшается всего до (n + 2) возможных вариантах. Первое – покрытие состоит из индивидуальных такой коалиции мажорируется эксцессом индивидуальной коалицией.

Достаточно легко убедиться, что верны соотношения Обозначим через ( ) максимально возможный эксцесс некоторого покрытия Рассмотрим первый шаг вычисления N-ядра. Посчитаем максимально возможные эксцессы всех покрытий. Вспомним, что эксцессы индивидуальных коалиций равны значениям выигрышей: (i) = x i, i = 1,..., n, а эксцессы дополняющих коалиций определяются по формулам:

( N \ i) = (VN xi ) Vi, i = 1,..., n. Максимально возможные эксцессы определяются из условий равенства эксцессов всех коалиций покрытия:

Можно заметить, что минимальным эксцессом второй строчки (2.12) является эксцесс 1 (1 ). Сравнивая полученные эксцессы между собой, получаем соотношения:

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

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

покрытия):

Теперь сравним полученные эксцессы и найдем минимальный из них во всех возможных случаях:

Итак, по индукции мы доказали корректность заполнения всей таблицы, кроме одной последней ячейки в центральной строке. Но эта компонента Nn

VN VN VN VN

2.5.2.1 Три игрока Любую игру 3 лиц можно привести к игре с нулевыми выигрышами малых коалиций, при условии, что выигрыши парных коалиций будут меньше Полученный результат с точностью до обозначений совпадает с результатом, полученным в работе [34].

2.5.2.2 Четыре игрока Обозначим ненулевые выигрыши коалиций для игры 4 лиц:

Таблица 2.5. Области для игры четырех лиц Таблица 2.6. Значения векторов для игры четырех лиц 2.5.3 Дополнительные исследования игр с нулевыми играми малых В этом разделе будут представлены результаты для некоторых частных случаях игр с нулевыми выигрышами малых коалиций.

Утверждение 2.7 (без доказательства) (VN V1,…,VN V n ) на плоскость дележей ( x( N ) = VN ), вычисляется по формуле Утверждение 2.8 (без доказательства) Для строго сбалансированных игр с нулевыми выигрышами малых коалиций большое предъядро является симплексом в том и только в том случае, когда Утверждение 2.9 (без доказательства) Для строго сбалансированных игр с нулевыми выигрышами малых коалиций в случае, когда большое предъядро является симплексом, проекция вершины симплекса на плоскость дележей совпадает с N-ядром.

2.6 Метрика в пространстве дележей Обозначим множество дележей для игры n лиц:

Введем метрику на D n.

Возможно ввести и другую метрику на D n, используя индекс Лузмора – Хэндби [9].

Основным преимуществом данных метрик является тот факт, что на множестве дележей расстояние между любой парой точек принимает значения на отрезке [ 0;V ( N ) ], причем значение V ( N ) достигается. Далее приведем два несложных утверждения.

В трехмерных играх метрики L и M совпадают:

Vi = VN, i = 1,..., n, то C-ядро игры представимо в следующем виде:

Core = x : M ( x, Nucl ) Последнее утверждение можно использовать как сигнал к использованию именно метрику M xy в качестве основной в пространстве дележей. Метризация пространства дележей понадобится в главе 4 для анализа результатов экспериментов. Второй плюс такой метрики заключается в том, что N-ядро всегда принадлежит центру C-ядра в смысле данной метрики. Это следует из первого шага вычисления N-ядра.

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

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

На основе введенных понятий описываются множества достижимости в динамической кооперативной игре и блокирующих состояния.

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

Глава 3 Программный комплекс для проведения экспериментов Существует несколько подходов к изучению рыночных механизмов.

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

Другим способом исследования эффективности рыночных механизмов является подход экспериментальной экономики, основной идеей которого является создание лабораторных рынков. Такой подход активно применяется в лаборатории экспериментальной экономики МФТИ и ВЦ РАН. Основная идея такого подхода состоит в построении модельной ситуации в лаборатории, оборудованной компьютерным классом с последующим анализом поведения мотивированных участников экспериментов.

3.1 Предпосылки создания программного комплекса Существую несколько программных оболочек для эффективного создания различных классов лабораторных экономических ситуаций на сети компьютеров (локальной или Интернете). В лаборатории экспериментальной экономики МФТИ и ВЦ РАН наиболее популярными оболочками для проведения экспериментов являются «z-Tree» и «FTS».

Программная оболочка «z-Tree» [5, 6] разработана в Цюрихском Университете (Швейцария). Она является средой программирования практически любых дискретных экономических ситуаций. Под дискретной экономической ситуацией понимается игра, где игроки одновременной и независимо делают свои ходы, а затем программа диспетчер собирает действия-ходы игроков и на их основе выдает решение и начисляются выигрыши игрокам. Такие игры могут быть как одношаговыми, так и многошаговыми.

Программная оболочка «FTS» [54] разработана в Университете Карнеги Меллон (США). Она является симулятором финансовой торговой системы [30, 37] и предназначена для проведения лабораторных экспериментов, использующих открытый непрерывный двойной аукцион. Основная идея проведения аукциона – создание множества независимых рынков отдельных ценных бумаг.

В 2006-2007 гг. в лаборатории экспериментальной экономики МФТИ и ВЦ РАН проводились серии экспериментов по изучению модельного сетевого рынка. Данный лабораторный рынок получил название «сетевой газовый рынок TRUE» [31, 32]. Основной целью экспериментов было экспериментальное сравнение трех различных аукционных механизмов: сетевого аукционного механизма с диспетчером, двойного сетевого аукциона с производными контрактами и сетевого аукциона с наведенными заявкам.

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

Пример использования такого аукциона можно найти, например, в работе [10]. Программная оболочка «z-Tree» удовлетворяет всем необходимым требованиям для создания подобного рода лабораторных аукционов.

Второй механизм – непрерывный двойной аукцион. Основные требование этого аукциона – обеспечить работу системы в реальном времени, чтобы без задержек отображать состояние торговой сессии, и удобный пользовательский интерфейс, чтобы минимизировать не вынужденные ошибки участников аукциона. Пример использования финансового рынка для моделирования сетевого можно найти, например, в работе [29]. Как уже было сказано, идеальной оболочкой для проведения лабораторных игр с использованием финансовых рынков является «FTS».

Третий механизм – аукцион с наведенными заявками [41, 43]. Сетевой аукционный механизм с наведенными заявками по отношению к предыдущим можно назвать компромиссным вариантом, сочетающим в себе прозрачность ценообразования и организованность взаимодействия участников аукциона. Основная идея аукциона с наведенными заявками состоит в том, что для каждого агента совокупность заявок всех остальных агентов порождает для него встречную заявку. В основе работы данного торгового механизма лежит составление для каждого агента наведенных заявок по совокупности заявок остальных со своей заявкой. Это позволяет каждому агенту работать только на одном рынке. Прозрачность ценообразования сохраняется, поскольку всегда можно либо согласиться с наведенной заявкой, либо изменить свою, продолжая торг с виртуальным партнером. Роль диспетчера в данном механизме сводиться к корректному распространению наведенных заявок.

Обе вышеупомянутые оболочки оказываются непригодными для создания лабораторных игр с наведенными заявками. Программа «z-Tree» неприспособленна для игр в непрерывном времени. Программа «FTS» не позволяет создавать приватные рынки с непрерывными двойными аукционами, а также в ней не предусмотрено возможности централизованного сбора заявок, т.е.

все созданные им финансовые рынки являются независимыми.

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

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

Как видно из главы 1 аукцион с наведенными заявками применим не только к сетевым рынкам, но и к более широкому классу экономических ситуаций – проектным играм.

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

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

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

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

Также в системе должна быть предусмотрена возможность проведения серии последовательных экспериментов – т.е. последовательность единичных экспериментов с заданным правилом изменения параметров.

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

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

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

Описание Рисунок 3.1. Общая схема программного комплекса 3.3 Технология Генератор Проектов В качестве инструментария для создания программного комплекса была выбрана технология «Генератор проектов» [44, 45]. Слово проект в данном случае никак не связано с понятием проектной игры, и совпадение чисто случайно. Кратко опишем основные преимущества Генератора проектов (ГП), описание которого можно найти, например, в работах [24, 53]. Данная технология предназначена для автоматизации разработки программных комплексов, использующих следующие информационные технологии. Многоуровневая клиент-серверная архитектура, удаленный пользовательские рабочие места, режим реального времени выполнения бизнес-процедур, использование реляционных и сетевых структур данных, оконный интерфейс пользовательских приложений, защита информации от несанкционированного доступа – вот основные концепции ГП. Основным механизмом автоматизации является автоматическая генерация текстов программ по формальному описанию проекта разрабатываемой системы.

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

Сетевое взаимодействие между модулями в ГП реализовано таким образом, что прикладная логика работы бизнес сервера осуществляется в одном потоке, что позволяет обрабатывать запросы строго последовательно. Это согласуется с одним из главных постулатов механизма: все заявки участников должны поступать на обработку строго последовательно.

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

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

Сложная модель проектной игры может быть описана в рамках технологии ГП посредством сетевой модели данных – базового механизма программирования на Генераторе.

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

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

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

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

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