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

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

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

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

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

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

численные методы и комплексы программ

Автореферат

диссертации на соискание учёной степени

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

Москва – 2013

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

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

МЕНЬШИКОВ Иван Станиславович, кандидат физико-математических наук, ведущий научный сотрудник отдела математического моделирования экономических систем, Федеральное государственное бюджетное учреждение науки Вычислительный центр им. А.А. Дородницына Российской академии наук

Официальные оппоненты:

ПОДИНОВСКИЙ Владислав Владимирович, доктор технических наук, профессор кафедры высшей математики на факультете экономики, Федеральное государственное автономное образовательное учреждение высшего профессионального образования "Национальный исследовательский университет "Высшая школа экономики" МОРОЗОВ Владимир Викторович, кандидат физико-математических наук, доцент кафедры исследования операций факультета вычислительной математики и кибернетики, Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Московский государственный университет имени М.В.Ломоносова"

Ведущая организация:

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

Защита состоится «» 20 года в _ час. на заседании диссертационного совета «Д 002.017.04» в Федеральном государственном бюджетном учреждении науки Вычислительном центре им. А.А. Дородницына Российской академии наук по адресу: 119333, Москва, Вавилова, дом 40, конференц-зал.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

';

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

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

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

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

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

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

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

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

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

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

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

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

• VI-я, VII-я научные конференции по исследованию операций (ORM-2010, ORM-2013);

• Семинар отдела «Математическое моделирование экономических систем»

ВЦ РАН (Москва, 2013).

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

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

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

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

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

D = {1,..., d }, проектов M = {1,..., m}, игроков N = {1,..., n} и агентов A = {1,..., a} – основные структурные единицы проектной игры. Связи между элементами задаются матрицей инцидентности {eij }iD операций и проектов и двумя отображеjM ниями множества агентов во множества операций {dl }lA и игроков {nl }lA. Числовые параметры игры задаются векторами доходов проектов ( h j ) Проектную игру можно интерпретировать как начальные условия для некоторой динамической игры, причем возможные исходы этой динамической игры можно описать на основании заданной проектной игры. Сделкой () в проектной игре называется набор агентов B( ) A, реализующих некоторый проект j ( ) M и распределение дохода данного проекта между этими агентами. При этом сумма доходов агентов, реализующих проект, должна равняться доходу проекта:

Дележом () в проектной игре будем называть любую совокупность сделок, с непересекающимися множествами агентов. Прибыль агентов, участвующих в дележе, равна доход минус затраты: ul = pl cl, l B, прибыли остальных агентов нулевые. Выигрыш игрока в дележе ( ) – сумма прибылей всех Понятно, что динамическую проектную игру можно построить разными способами. Естественное условие для построения динамической игры заключается в том, чтобы исходы построенной игры были дележами заданной проектной игры. Целью данной работы является построение динамической проектной игры с помощью аукциона с наведенными заявками. Под аукционом в данном случае понимается механизм взаимодействия агентов, управляемых игроками.

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

Наведенной заявкой для агента l от некоторой сделки будем называть заявку с номиналом ql ( ) = h j ( ) px. Данная заявка означает остаток, который может получить агент за выполнение операции i от реализации проекта j при условии, что контрагенты получат свой заявленный доход. Наведенной заявкой ql* (t ) для агента является наилучшая заявка из всех возможных, т.е. заявка с наибольшим номиналом.

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

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

Под простой заявкой будем понимать пару l = ( pl, l ), l A – номинал и время последнего изменения номинала. Тогда наведенной заявкой от потенциальной доченные по убыванию времена простых заявок контрагентов.

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

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

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

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

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

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

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

Рассмотрим сетевой аукцион на двухполюсном графе G = (V, E ). На каждом ребре данного графа находятся три типа агентов A = AS AT AB : продавцы, транспортировщики и покупатели. Каждый продавец и транспортировщик l AS AT может произвести или транспортировать одну единицу товара с затратами cl > 0, а выкупная стоимость покупателя l AB равна vl > 0. Также есть заданное множество собственников N и отображение множества агентов во множество собственников. По заданному сетевому аукциону проектная игра строится следующим образом. Множество операций – это множество дуг в двухполюсном графе, множество проектов – это всевозможные пути графа, не содержащие циклов, из источника в сток. Матрица инцидентности операций и проектов соответствует принадлежности дуг к маршрутам. Множество игроков – это множество собственников, множество агентов проектной игры совпадает с множеством атомарных агентов сетевого аукциона. Распределение агентов по операциям совпадает с расположением агентов на ребрах, а распределение агентов по игрока совпадает с распределением по собственникам. Затраты продавцов и транспортировщиков остаются неизменными, а в качестве затрат покупателей берутся их выкупные стоимости со знаком минус. Доходы проектов полагаются равными нулю. Получаемая проектная игра характеризуется тем, что в каждом проекте есть одна особая прибыльная операция: все агенты, выполняющие эту операцию, имеют отрицательные затраты.

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

Во второй главе рассматриваются динамические кооперативные игры с G coop = { N,V }, где N = {1,..., n} – множество игроков, V : 2 N + – супераддитивная Одним из ключевых понятий в кооперативной теории является дележ. Дележ – исход игры, при котором реализуется максимальная коалиция ( N ) и все игроки получают неотрицательные выигрыши. Пусть x = ( x1,..., xn ) – это вектор выигрышей игроков.

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

( S )V (S ) V ( N ). По теореме Бондаревой–Шепли ядро игры не пусто тогда и только тогда, когда она сбалансирована.

странстве удовлетворяющее условиям:

странстве удовлетворяющее условиям:

Определение. Кооперативная игра называется строго сбалансированной, выполнено условие ( S )V (S ) < V ( N ).

валентны:

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

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

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

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

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

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

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

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

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

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

гой заявки:

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

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

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

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

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

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

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

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

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

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

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

Обозначим выигрыши ненулевых коалиций и сумму выигрышей всех собVi.

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

Теорема 2.5. Игра с нулевыми выигрышами малых коалиций строго сбалансирована тогда и только тогда, когда выполнено условие = min( 0, i ) > 0, где Теорема 2.6. Для строго сбалансированных игр с нулевыми выигрышами малых коалиций большое предъядро является усеченным параллелепипедом:

e ( x, S ) = x ( S ) V ( S ). Для каждого дележа x возьмем упорядоченный по возрастанию вектор эксцессов {e( x, S )}S N. Дележ, доставляющий лексикографический максимум упорядоченному вектору эксцессов, называется N-ядром.

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

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

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

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

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

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

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

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

Для анализа влияния дополнительной информации о значениях N-ядер были выбраны все коалиционные исходы из второй и третьей серии. Гипотеза о том, что дополнительная информация не влияет на проведение участников, была проанализирована с помощью критерия согласия Смирнова для непрерывной случайной величины = max ui Nucli – расстояния от реализованного дележа до N-ядра в смысле заданной метрики. При большом размере ядра наличие дополнительной информации об N-ядре радикально влияет на результаты экспериментов. Гипотеза однородности выборок должна быть отвергнута при уровне значимости = 0.01 (а в некоторых случаях даже при = 0.001 ). При малом ядре экспериментальные данные не противоречат гипотезе о том, что дополнительная информация не влияет на поведение участников. Это согласуется с ожиданиями, потому что в случае малого ядра разброс вокруг его центра (N-ядра) невелик.

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

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

Целью третьей группы экспериментов было получение опыта моделирования рынка программного обеспечения в лаборатории. Для исследования был выбран следующий рынок. Есть фирма – производитель программного обеспечения, и два банка – пользователя ПО. Фирма может сделать три программы:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

конф. по исследованию операций, 2010. – С. 33-35.

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

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

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

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

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

Скиндерев С.А. Блокирующие стратегии в лабораторных кооперативных 11.

играх с наведенными заявками // Труды МФТИ. – 2012. Т. 4, № 4. – С. 155Skinderev S.A. The study of the behavior of participants in laboratory games 12.

with changes in experimental conditions // VII Moscow International Conference on Operation Research: Moscow, 2013: Proceedings. V. I – P. 28-30.

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

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

Скиндерев С.А. Об опыте моделирования рынка программного обеспечения 15.

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

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

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

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