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

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

СКИНДЕРЕВ Сергей Александрович

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

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

Автореферат

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

13 ФЕВ 2014

Москва'-2013 005545190

005545190

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

Научный руководитель:

МЕНЬШИКОВ Иван Станиславович,

кандидат физико-математических наук,

ведущий научный сотрудник отдела математического моделирования экономических систем,

Федеральное государственное бюджетное учреждение науки Вычислительный центр им. A.A. Дородницына Российской академии наук Официальные оппоненты:

ПОДИНОВСКИЙ Владислав Владимирович, доктор технических наук,

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

МОРОЗОВ Владимир Викторович,

кандидат физико-математических наук,

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

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Московский государственный университет имени М.В.Ломоносова" Ведущая организация:

Федеральное государственное автономное образовательное учреждение высшего профессионального образования "Московский физико-технический институт (государственный университет)"

Защита состоится « 3» (I M(dt 20 j года в ■{ V час. на заседании

бюджетном учреждении науки Вычислительном центре им. A.A. Дородницына Российской академии наук по адресу: 119333, Москва, Вавилова, дом 40, конференц-зал.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН.

диссертационного совета «Д 002.017.04» в Федеральном государственном

г.

/

Ученый секретарь диссертационного совета, д.ф.-м.н.

Новикова Н.М.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы

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

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

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

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

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

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

Цель работы

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

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

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

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

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

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

Методы исследования

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

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

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

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

Научная новизна

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

4

ектов, как кооперативные игры, сетевые аукционы и рынки товаров коллективного пользования.

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

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

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

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

Практическая ценность работы

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

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

Апробация и публикации

По теме диссертации опубликовано 15 работ, в том числе одна работа [11]-в журнале из списка изданий, рекомендованных ВАК РФ. Результаты диссертационного исследования докладывались, обсуждались и получили одобрение специалистов на научных конференциях и семинарах:

• 50-я, 51-я, 53-я, 54-я, 55-я, 56-я научные конференции МФТИ (2007, 2008, 2010, 2011,2012,2013 года);

• У1-я, УП-я научные конференции по исследованию операций (СЖМ-2010, 011М-2013);

• Семинар отдела «Математическое моделирование экономических систем» ВЦ РАН (Москва, 2013).

Структура диссертации

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

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

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

Формально проектной игрой будем называть следующий объект Т = где множества операций

£> = {1,...,</}, проектов М-{\,...,т], игроков N={1.....п} и агентов А = {1.....а] - основные структурные единицы проектной игры. Связи между элементами задаются матрицей инцидентности {е/}^" операций и проектов и двумя отображениями множества агентов во множества операций {¿,}1еА и игроков {п,}1ел. Чи-

! . ч М

еловые параметры игры задаются векторами доходов проектов (Л') еК" и затрат агентов (с, )!еЛ е К".

Проектную игру можно интерпретировать как начальные условия для некоторой динамической игры, причем возможные исходы этой динамической игры можно описать на основании заданной проектной игры. Сделкой <р(Г) в проектной игре Г называется набор агентов В(<р) с А, реализующих некоторый проект Л<р)еМ и распределение дохода данного проекта между этими агентами. При этом сумма доходов агентов, реализующих проект, должна равняться доходу проекта: £ Л = > а Д°Х°Д агента должен быть не меньше его затрат

р, >с, У/е Я.

Дележом Ф(Г) в проектной игре Г будем называть любую совокупность сделок, с непересекающимися множествами агентов. Прибыль агентов, участвующих в дележе, равна доход минус затраты: и, = р, -с,,/е В, прибыли остальных агентов нулевые. Выигрыш игрока в дележе Ф(Г) - сумма прибылей всех агентов, управляемых игроком: ик = £ N.

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

Игра проходит в заданном промежутке времени /е [О.г], в течение которого каждый агент /е А варьирует свою заявку р:(1) на получение дохода. Эта заявка означает готовность агента выполнить свою операцию (без уточнения, в рамках какого проекта она будет выполнена) и получить за это доход не меньше р,(0. В качестве информации о текущем состоянии игры каждый агент получает встречную (наведенную) заявку ?,*('), которая означает предложение поучаствовать в наиболее выгодном для данного агента проекте. Встречная заявка для агента составляется и вычисляется на основе заявок остальных агентов. В мо-

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

Наведенной заявкой для агента I от некоторой сделки <р будем называть заявку с номиналом q,(<p) = h'"]- J] р,. Данная заявка означает остаток, который

леВ(<Р}\/

может получить агент за выполнение операции /' от реализации проекта j при условии, что контрагенты получат свой заявленный доход. Наведенной заявкой q'(t) для агента является наилучшая заявка из всех возможных, т.е. заявка с наибольшим номиналом.

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

Алгоритм определения номинала наилучшей заявки описан. Если агент соглашается с наведенной заявкой, то он вступает в сделку, а также в сделку вступают все контрагенты, которые образовали для него эту наилучшую заявку. Но возникает проблема однозначного выбора набора контрагентов, в случае, если несколько наведенных заявок имеют одинаковый номинал. Для решения этой задачи используется лексикографическое правило сравнения наведенных заявок. Под простой заявкой будем понимать пару р, =(р,,т,),1е А — номинал и время последнего изменения номинала. Тогда наведенной заявкой от потенциальной сделки <р будем понимать £№) = (?,(?>),r(O<H),...,V0)> где тс,о'ы,>->то> - упорядоченные по убыванию времена простых заявок контрагентов.

Формально аукцион можно описать следующим клиринговым механизмом. Если при подаче агентом I очередной заявки р = (р,т) на рынок i = d, в момент времени т выполняется условие: р < q], то происходит сделка, и заявка агента /

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

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

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

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

Рассмотрим кооперативную игру С""р ={Ы,У], где ЛГ = {1,...,п} - множество игроков, ¥:2Ы ->К+ - характеристическая функция, задающая выигрыши коалиций. Идея построения проектной игры по кооперативной заключается в следующем. Множество игроков, агентов и операций отождествляются с множеством игроков в кооперативной игре. Множеством проектов становится множество коалиций. Матрица инцидентности операций и проектов соответствует участию игроков кооперативной игры в коалициях. Доходы проектов соответствуют значениям характеристической функции - выигрышам коалиций. Затраты агентов полагаются нулевыми.

Рассмотрим сетевой аукцион на двухполюсном графе С = (У,Е). На каждом ребре данного графа находятся три типа агентов А = и А„: продавцы, транспортировщики и покупатели. Каждый продавец и транспортировщик 1е ЛЕ и АТ может произвести или транспортировать одну единицу товара с затратами с, >0, а выкупная стоимость покупателя 1е Ав равна V, >0. Также есть заданное множество собственников N и отображение множества агентов во множество собственников. По заданному сетевому аукциону проектная игра строит-

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

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

Во второй главе рассматриваются динамические кооперативные игры с наведенными заявками. Кооперативная игра представляет собой пару Ос""р ={И,У), где N = {1,...,«} - множество игроков, У:2"-»М, - супераддитивная характеристичгская функция, К = {Г(5)>0}11_)<, У(0) = О,

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

игроки получают неотрицательные выигрыши. Пусть х = (х,,...,х„) - это вектор выигрышей игроков.

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

Г Г(Ю = Х(Ы)

< с N

Кооперативная игра называется сбалансированной, если для любого сбалансированного покрытия а:2" ->[0;1], £ «(5) = 1,\//е N, выполнено условие

£ а(Х)К(5) < Н(Л<). По теореме Бондаревой-Шепли ядро игры не пусто тогда и

только тогда, когда она сбалансирована.

Определение. Малое предъядро для игры С={л',1/} - это множество в пространстве Ж", удовлетворяющее условиям: Гк(Л0 < х(Ы)

< х(5)

[ < Ут-УШ\Б)

VScN.

Определение. Большое предъядро для игры С={М,У) - множество в пространстве К", удовлетворяющее условиям: У(ЛГ) < х(Щ

VSclV

0.

Определение. Кооперативная игра называется строго сбалансированной, если для любого сбалансированного покрытия а-.2ы ->[0;1], £ а(5) = 1,У/е лг,

£с№Е£

выполнено условие £ < .

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

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

• Ядро игры имеет размерность я -1.

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

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

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

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

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

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

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

Лемма 2.6. Для динамической кооперативной игры с наведенными заявками справедливо следующее утверждение. Чтобы наведенная заявка р" от макси-

12

мольной коалиции была лучше наведенной заявки р от другой коалиции необходимо и достаточно, чтобы ее номинал р(ры) был строго больше номинала другой заявки: р(/>") > р(р).

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

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

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

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

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

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

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

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

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

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

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

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

Обозначим выигрыши ненулевых коалиций и сумму выигрышей всех собственных коалиций следующим образом: у(аг\о = учУ1 еМ; у^) = гы; е_„ = £ ^.

Без ограничения общности будем считать, что выполняется условие 0<У.„<...<У_1<У!/.

Теорема 2.5. Игра с нулевыми выигрышами малых коалиций строго сбалансирована тогда и только тогда, когда выполнено условие к-=пнп(*<,,*;):>0, где

п-1

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

уы < х(Ы) О < х,

У/еЛГ

х,

N

Эксцессом вектора х относительно коалиции 5 называется число е(х,5) = .х(5)-К(5). Для каждого дележа х возьмем упорядоченный по возрастанию вектор эксцессов {е^З)}5^. Дележ, доставляющий лексикографический максимум упорядоченному вектору эксцессов, называется Ы-ядром.

Теорема 2.7 (о вычислении ГЧ-ядра). Для игр л>3 лиц с нулевыми выигрышами малых коалиций Ы-ядро вычисляется как функция параметров {К,} - Причем пространство значений делится на (2л-1) областей, в каждой из которых все компоненты И-ядра вычисляются линейными функциями параметров {К.,} • Каждая область д" ' задается в виде условий: =[у<=м\/\у)> о},

Ма ={ке Л/|/тМ(К)^0,/",(К)>0},ш = 2,...,п-1,

М" ={КеЛ/|/"-1(К)<0,/"(К)>о},

м2п-т _ |к 6 м | (К) < 0, /2"~т (Р') > о}, т = 2,..., П -1,

М2"-1 = {У е М | /2"~2 {У) < О},

где {/т(К)}т '.....2" 2 набор из (2л-2) функций, удовлетворяющий условиям:

Обозначим хтшс, = {х".....х"},т = 1.....2п-1 значения Ы-ядер в каждой из облас-

ти

Г (Г) = 2£_д , - £ - (я - т)Ц„ - (« - 2у„, /я =!,...,« -1 /

У2"-1 (К) = £ + (и - т)К_т - (" - 2)К„ ,т = 1,..., и -1.

й {лг}'

. Тогда значения задаются следующими формулами:

теи

х" = ±(Уц-У_1),т = 2.....2п-2,1 = 1.....т-1;

- Е^-У~г-1> т=1.....' = т.....

У-1

т-1

Ы

В третьей главе приводится описание программного комплекса для проведения лабораторных экспериментов. Данная глава носит описательный характер, а главной ценностью ее является программный комплекс, переданный в лабораторию экспериментальной экономики МФТИ и ВЦ РАН. Предпосылками к созданию нового программного комплекса стало отсутствие в лаборатории инструментальных средств для проведения экспериментов с использованием аукциона с наведенными заявками. Программный комплекс «г-Тгее» (Цюрихский Университет, Швейцария) позволяет моделировать широкий спектр экспериментов в дискретном времени, а симулятор непрерывных финансовых рынков «БТБ» (Университет Карнеги Меллон, США) не предоставляет возможности централизованного сбора заявок.

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

Для создания программного комплекса было выбрано инструментальное средство «Генератор проектов», разработанное в ВЦ РАН. Основными преимуществами данного средства для разработки комплекса стали клиент-серверная архитектура, сетевая модель данных, встроенный лексический анализатор, под-

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

В четвертой главе рассматриваются проведенные эксперименты. В лаборатории экспериментальной экономики МФТИ и ВЦ РАН было проведено достаточно большое количество лабораторных экспериментов с использованием динамических проектных игр с наведенными заявками. Все эксперименты проводились в рамках курса «Экспериментальная экономика», читаемого студентам старших курсов ФУПМ МФТИ. Во всех экспериментах использовался программный комплекс, описанный в главе 3. Для анализа были выбраны только несколько самых значимых экспериментов.

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

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

В первой группе экспериментов было выбрано пять экземпляров приведенных игр трех лиц. Каждая игра характеризуется тремя числовыми параметрами - выигрышами парных коалиций. Выбор делался таким образом, чтобы каждый набор параметров попал в одну из пяти областей вычисления N-ядра. Также каждому набору соответствует разный размер С-ядра, характеризуемый параметром к. Эксперимент состоял из трех последовательных серий. В каждой серии последовательно разыгрывались игры трех лиц (наборы параметров менялись каждые пять попыток). Участниками были студенты 6 курса ФУПМ МФТИ, в качестве мотивации использовались учебные очки. Отличие между тремя сериями заключалось только в информированности участников, влияние которой

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

Результаты влияния дополнительной информации о блокирующих стратегиях можно кратко охарактеризовать следующим образом. Гипотеза о том, что информация не влияет на проведение участников, была проанализирована с помощью критерия согласия х2 Для дискретной случайной величины 4=щ+ы2+ щ - суммарного выигрыша игроков. При малом размере ядра наличие дополнительной информации о блокирующих стратегиях радикально влияет на результаты экспериментов. Гипотеза однородности выборок должна быть отвергнута при уровне значимости а=0.05 (а в некоторых случаях даже при а=0.001). При большом ядре экспериментальные данные не противоречат гипотезе о том, что дополнительная информация не влияет на поведение участников. Это согласуется с ожиданиями, потому что в случае большого ядра парные коалиции слабы и практически любая стратегия будет блокирующей.

Для анализа влияния дополнительной информации о значениях И-ядер были выбраны все коалиционные исходы из второй и третьей серии. Гипотеза о том, что дополнительная информация не влияет на проведение участников, была проанализирована с помощью критерия согласия Смирнова для непрерывной случайной величины £= тахЦ-льс/,! - расстояния от реализованного дележа до

И-ядра в смысле заданной метрики. При большом размере ядра наличие дополнительной информации об И-ядре радикально влияет на результаты экспериментов. Гипотеза однородности выборок должна быть отвергнута при уровне значимости а=0.01 (а в некоторых случаях даже при от=0.001). При малом ядре экспериментальные данные не противоречат гипотезе о том, что дополнительная информация не влияет на поведение участников. Это согласуется с ожиданиями, потому что в случае малого ядра разброс вокруг его центра (Ы-ядра) невелик.

Во второй группе экспериментов объектом исследования был сетевой газовый аукцион «TRUE» - модельный сетевой рынок, изучаемый в лаборатории экспериментальной экономики МФТИ и ВЦ РАН. В этой игре 4 игрока - собственника (Turk, Rus, Ukr, Eur), управляющие 7-ю экономическими агентами (по два продавца и покупателя и три транспортировщика). Также необходимо отметить, что в данной игре агенты могут совершить 28 атомарных действий (покупка, продажа или транспортировка неделимой единицы товара). Многочисленные попытки предсказания поведения игроков с помощью кооперативной теории игр терпят неудачу. Проблема заключается в том, что характеристическая функция данной игры симметрична относительно игроков «Rus» и «Ukr», а в экспериментах средний выигрыш игрока «Rus» в 1.5-2.5 раза больше выигрыша игрока «Ukr».

Для экспериментов было выбрано четыре различных проектных представления данного сетевого рынка. Первое - простое проектное представление игры «TRUE». В качестве второй модели предлагается изоморфное представление рынка - «Проектная игра TRUE-28», где в качестве участников проекта выступают атомарные действия агентов. Следующее представление - это «Проектная игра TRUE-7». В этом случае участниками проектов будут не элементарные действия экономических агентов, а сами агенты. И, наконец, четвертое представление - это «Проектная игра TRUE-4» или просто кооперативная игра «TRUE». В этом случае вообще нет никакого разбиения на агентов, т.е. каждый игрок играет только за себя. Гипотеза о том, что различные проектные представления не влияют на проведение участников, была проанализирована с помощью критерия согласия Смирнова для непрерывной случайной величины ¡¡ = и""' -иЛг - разница выигрышей игроков «Rus» и «Ukr». Оказалось, что экспериментальные данные не противоречат гипотезе однородности для любой пары различных многоагентных представления игры «TRUE». А вот поведение участников в кооперативной игре «TRUE-4» существенно отличается от поведения в любом многоагентном представлении, т.е. гипотеза однородности выборок должна быть отвергнута при уровне значимости a=o.oooi.

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

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

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

В заключении перечислены основные результаты работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

20

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

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

• Выделен и детально проанализирован класс кооперативных игр с нулевыми выигрышами малых коалиций. В частности, для этого класса кооперативных игр получена аналитическая формула для вычисления N-ядра.

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

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

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

о различные проектные представления одного и того же сетевого рынка существенно влияют на результаты эксперимента

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

СПИСОК ПУБЛИКАЦИЙ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1. Меньшикова O.P., Скиндерев С. А. Применение кооперативной теории игр к исследованию сетевых энергетических рынков в лаборатории // Труды 50 науч. конф. МФТИ, М.-Долгопрудный, 2007. - С. 144-146.

2. Меньшиков И.С., Платонов В.В., Скиндерев С.А., Чабан А.Н. Сравнительный анализ эффективности лабораторных сетевых аукционов. - М.: ВЦ РАН, 2007.-45 с.

3. Скиндерев С.А., Меньшиков И.С. Аукцион с наведенными заявками для лабораторных кооперативных игр // Труды 51 научной конференции МФТИ, М.-Долгопрудный, 2008. - С. 64-67.

4. Скиндерев С.А., Меньшиков И.С. Аукцион с наведенными заявками для лабораторных кооперативных игр // Труды VI научной конференции по исследованию операций, 2010. - С. 35-37.

5. Скиндерев С.А., Меньшиков И.С. Использование технологии Генератор Проектов для создания лабораторных сетевых аукционов // Труды VI науч. конф. по исследованию операций, 2010. - С. 33-35.

6. Скиндерев С.А., Меньшиков И.С. Исследование предъядра в лабораторных кооперативный играх // Труды 53 научной конференции МФТИ, М. -Долгопрудный, 2010. - С. 124-125.

7. Скиндерев С.А. Использование технологии Генератор Проектов для создания лабораторных сетевых аукционов И Автоматизация проектирования инженерных и финансовых информационных систем средствами генератора проектов. М.: ВЦ РАН, 2010. - С. 80-88.

8. Скиндерев С.А., Меньшиков И.С. Влияние информированности участников на распределение выигрышей в лабораторных кооперативных играх // Труды 54 научной конференции МФТИ, М,-Долгопрудный, 2011. - С. 71-72.

9. Скиндерев С.А., Меньшиков И.С. Проектные игры как инструмент моделирования экономических ситуаций // Труды 55-й научной конференции МФТИ. М.: МФТИ, 2012. - С. 70-71.

10. Скиндерев С.А. Анализ различных проектных представлений сетевого газового аукциона «TRUE» Н Труды 55 научной конференции МФТИ, М.Долгопрудный, 2012 - С. 72-73.

11. СкиндереБ С.А. Блокирующие стратегии в лабораторных кооперативных играх с наведенными заявками // Труды МФТИ. - 2012. Т. 4, № 4. - С. 155168.

12. Skinderev S.A. The study of the behavior of participants in laboratory games with changes in experimental conditions // VII Moscow International Conference on Operation Research: Moscow, 2013: Proceedings. V. I - P. 28-30.

13. Скиндерев С.А. Исследование особенностей поведения участников лабораторных игр при изменениях условий проведения экспериментов // Труды VII науч. конф. по исследованию операций, 2013. Т. II - С. 17-18.

14. Скиндерев С.А., Меньшиков И.С. N-ядро для кооперативных игр с нулевыми выигрышами малых коалиций // Труды 56 научной конференции МФТИ, УПМ, М.-Долгопрудный, 2013. Т. 1. - С. 71-72.

15. Скиндерев С.А. Об опыте моделирования рынка программного обеспечения в лаборатории // Труды 56 научной конференции МФТИ, УПМ, М.Долгопрудный, 2013. Т. 1. - С. 72-73.

В работе [1] Скиндереву С.А. принадлежит расчет различных решений кооперативной теории игр для выбранных сетевых энергетических рынков и сравнение полученных решений с результатами экспериментов.

В работе [2] Скиндереву С.А. принадлежит постановка, проведение и анализ результатов экспериментов, использующих аукцион с наведенными заявками.

В совместных работах с научным руководителем [3-6, 8-9, 14] Скиндереву С.А. принадлежат основные результаты, а Меньшикову И.С. принадлежат постановки задач и проверка полученных результатов.

Подписано в печать: 26.12.2013 Объем: 1,6усл.п.л. Тираж 100 экз. Заказ № 940 Отпечатано в типографии «Реглет» 107031, г.Москва, ул. Рождественка , д.5/7, стр. 1 (495) 623 93 06 www.reglet.ru

Федеральное государственное бюджетное учреждение науки Вычислительный центр им. A.A. Дородницына Российской академии наук

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

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

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

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

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

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

Москва 2013

Оглавление

Введение.........................................................................................................5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4.2 Динамическая игра для кооперативной игры трех лиц.........55

2.4.3 Аукцион с наведенными заявками для игры трех лиц...........55

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

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

2.5.1 Вычисление >1-ядра....................................................................62

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

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

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

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

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

3.1 Предпосылки создания программного комплекса.....................73

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

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

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

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

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

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

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

3.9 Выходные данные..........................................................................86

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

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

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

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

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

4.1.2 Описание серии игр (сценарий последовательности)............88

4.1.3 Мотивация участников..............................................................89

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

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

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

4.2 Сравнительный анализ кооперативных игр трех лиц................91

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

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

4.2.3 Анализ влияния информации о блокирующих стратегиях....94

4.2.4 Анализ влияния информации о значениях N-ядер.................97

4.2.5 Интерпретация результатов....................................................102

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

4.3.1 Построение проектных игр.....................................................103

4.3.2 Планирование и проведение серий экспериментов..............104

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

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

4.3.5 Сворачивание случайного вектора в случайную величину. 105

4.3.6 Применение критерия согласия Смирнова для проверки гипотезы однородности................................................................................106

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

4.4 Моделирование рынка программного обеспечения в лаборатории......................................................................................................108

4.4.1 Рынок банковского программного обеспечения...................108

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

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

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

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

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

Заключение.................................................................................................116

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

Введение

Актуальность темы

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

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

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

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

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

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

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

Обзор литературы

Основоположником экспериментально экономического подхода считается Верной Смит. Его методология проведения экспериментов и моделирования аукционов опубликованы в работах [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].

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

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

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

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

Цель работы

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

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

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

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

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

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

Методы исследования

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

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

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

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

Научная новизна

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

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

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

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

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

Практическая ценность работы

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

Разработанный программный комплекс передан в Лабораторию экспериментальной экономики МФТИ и используется для проведения лаборатор-

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

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

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

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

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