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

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

00

60

о

372

ОГАНЯН ЛЕВ СЕРГЕЕВИЧ

АЛГОРИТМЫ И ПРОГРАММНЫЙ КОМПЛЕКС РЕШЕНИЯ ЗАДАЧ ТЕОРИИ КООПЕРАТИВНЫХ ИГР. ЯДЕРНЫЕ РЕШЕНИЯ ДИСКРЕТНЫХ КООПЕРАТИВНЫХ ИГР

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

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

Ростов-на-Дону - 2010

004601372

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

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

Мермелыптейн Геннадий Гавриилович

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

Лябах Николай Николаевич кандидат физико-математических наук, профессор ЕрусалимскиЙ Яков Михайлович

Ведущая организация: Южно-Российский государственный технический

университет (ЮРГТУ-НПИ)

Защита диссертации состоится 14 мая 2010 г. в 13:00 часов на заседании диссертационного совета Д 218.010.03 при Ростовском государственном университете путей сообщения по адресу: 344038, г. Ростов-на-Дону, пл. Ростовского Стрелкового Полка Народного Ополчения, 2.

С диссертацией можно ознакомиться в научной библиотеке РГУПС по адресу: 344038, г. Ростов-на-Дону, пл. Ростовского Стрелкового Полка Народного Ополчения, 2.

Автореферат разослан « апреля 2010 г. Ученый секретарь

диссертационного совета Д 218.010.03 доктор технических наук, профессор

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

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

Большой вклад в развитие теории кооперативных игр внесли Фон Нейман Дж., Моргенштерн О., Наш Дж., Шепли Л.С., Воробьев Н.Н., Бондарева О.Н., Мулен Э., Петросян Л.А., Яновская Е.Б. и др.

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

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

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

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

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

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

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

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

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

Для достижения этих целей в работе решены следующие задачи:

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

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

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

4. Выведены достаточные условия непустоты С-ядра дискретной игры.

5. Разработанные алгоритмы реализованы в виде блоков комплекса проблемно-ориентированных программ, позволяющих вычислять минимальные сбалансированные покрытия, существенные минимальные сбалансированные покрытия, проверять супераддитивность, сбалансированность, двойственную сбалансированность игр, вычислять вектор Шепли, Л^ядро, обобщенное 7У-ядро, вершины С-ядра и двойственного С-ядра и другие множества, связанные с кооперативной игрой.

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

Методы диссертационного исследования основываются на применении аппаратов теории игр и исследования операций, теории многогранников, теории графов.

Научная новизна работы состоит в следующих результатах:

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

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

3. Разработаны и исследованы дополнительные свойства таких математических объектов как множество дележей, множество двойственных дележей, множество Вебера и СС-ядро целочисленной игры.

4. Получены достаточные условия непустоты С-ядра дискретной игры.

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

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

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

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

Апробация работы. Основные положения диссертации докладывались на второй международной конференции «Математическое моделирование социальной и экономической динамики» (г. Москва, 2007 г.); на всероссийском симпозиуме «Математические модели и информационные технологии в экономике» (г. Кисловодск, 2007 г.); на конференции «Современные информационные технологии в образовании: Южный Федеральный Округ» (г. Ростов-на-Дону, 2007 г.); на XVI международной конференции «Математика. Экономика. Образование» (г. Ростов-на-Дону, 2008 г.); на всероссийской конференции «Современные проблемы прикладной математики и математического моделирования» (г. Воронеж, 2007 г.),; на всероссийской научно-практической конференции «Современная математика и проблемы математического образования» (г. Орел, 2009 г.); на третьей международной конференции «Теория игр и менеджмент» (г. Санкт-Петербург, 2009 г.); на X всероссийском симпозиуме по прикладной и промышленной математике (г.Сочи, 2009 г.).

Публикации. По материалам диссертации опубликовано 11 печатных работ общим объемом 2.5 пл., из них 3 - в изданиях, рекомендованных ВАК.

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, двух приложений и списка литературы. Объем диссертационной работы 146 страниц. Библиографический список содержит 99 наименований.

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

В первой главе рассмотрены супераддитивные кооперативные игры С =<Лг,у>, N={1,...,«} - множество игроков, у.2к -»Л1 - характеристическая функция, у^УН^г) 5 у(5,1и52), 51П52=0 с трансферабельной полезностью. Возможная пустота С-ядра кооперативной игры является главным ограничением этого понятия, поэтому важной проблемой кооперативной теории игр является вывод условий его существования. Каждая существенная игра с трансферабельной полезностью стратегически эквивалентна своей (0-1)-редуцированной форме у(0=0, /е/У; у(Лг)=1; 0<у(5}<1, БаИ.

Игра С7 имеет непустое С-ядро тогда и только тогда,

когда она сбалансирована, т.е. £ 1, 1 = 1,/, где

5сЛГ

А' = (А1 (1),..., А'(п), Л'(1,2),..., Л'(п-1,п),...,Л'(2,..., п)), /=й, - вершины многогранника М„аКт, т = 2"-2, заданного условиями Ц$)х(Б) = %(Щ, ¿(5) > 0, 5 с Л^, (%{8) - характеристический вектор

Sc.ll

коалиции 5).

Из ^ < 1, ¡ = 1,1, следует, что проблема аналитического

описания множества сбалансированных, супераддитивных, (0-1)-редуцированных игр В„ сводится к задаче нахождения всех вершин вспомогательного многогранника М„. Размерность многогранника М„ экспоненциально растет при увеличении числа игроков, но количество

ненулевых компонент его вершин Л' не больше п. Поэтому, Л' е Мп задают в виде пары (Р',а'), где Р'^ЗсЛГ: А'(5)>0} - семейство коалиций, соответствующих положительным компонентам вершины X (минимальное сбалансированное покрытие), а1=(Л'(8)еЛ''.Л'(!1)>0) - вектор

положительных компонент вершины Л' (вектор коэффициентов). Минимальное сбалансированное покрытие называется несущественным,

если соответствующее ему неравенство системы X < 1, / = 1,/,

является следствием остальных неравенств этой системы и условий супераддитивности. В противном случае минимальное сбалансированное покрытие называется существенным(СМСП). 1) СМСП игры трех лиц:

№ Существенное минимальное Количество Коэффициенты

сбалансированное покрытие покрытий покрытия

1 {1>2},{1,3},{2,3} 1 (1/2,1/2,1/2)

2) СМСП игры четырех лиц:

№ Существенное минимальное Количество Коэффициенты

сбалансированное покрытие покрытий покрытия

1 {1,2}>{1»3},{1,4},{2>3,4} 4 (1/3,1/3,1/3,2/3)

2 {1ДЗ}({1А4},{3,4} 6 (1/2,1/2,1/2)

3 {1 АЗ},{1,2,4},{1,3,4},{2,3,4} 1 (1/3, 1/3, 1/3, 1/3)

3) СМСП игры пяти лиц:

№ Существенное минимальное сбалансированное покрытие Количество покрытий Коэффициенты покрытия

1 {1>2}.{1>3,4,5},{2,3,4,5} 10 (1/2,1/2,1/2)

2 {1,2,4},{2,3,5),{1,3,4,5} 15 (1/2,1/2,1/2)

3 {{1,2},{1,3},{2,3},{4,5} 10 (1/2,1/2,1/2,1)

4 {1.2.3}, {1,4,5},{2,4,5},{3,4,5} 10 (2/3,1/3,1/3,1/3)

5 {2,4},{3,4},{ 1,4,5), {1,2,3,5} 30 (1/3,1/3,1/3,2/3)

6 {1,5},{2,5},{3,5},{4,5},{1,2,3,4} 5 (1/4,1/4,1/4,1/4,3/4)

7 {4,5},{1,2,5),{1,3,5},{2,3,5},{1,2,3,4} 20 (2/5,1/5,1/5,1/5,3/5)

8 {1,4,5},{2,4,5},{3,4,5},{1,2,3,4},{1,2,3,5} 10 (1/5,1/5,1/5,2/5,2/5)

9 {1,2,3,4},{1,2,3,5),{1,2,4,5),{1,3,4,5},{2,3,4,5} 1 (1/4,1/4,1/4,1/4,1/4)

10 {1,2},{1,3,4},{2,3,4},{2,3,5},{1,4,5} 60 (1/4,1/4,1/4,1/2,1/2)

И {1,2,4}, {2,3,4), {1,3,5}, {2,3,5}, {1,4,5} 12 (1/3,1/3,1/3,1/3,1/3)

12 {2,4},{3,4},{1,2,3},{2,3,5},{1,4,5} 30 (1/5,1/5,2/5,2/5,3/5)

Утверждение 1. Множество Вл супераддитивных, сбалансированных, (0-1)-реАудированных игр четырех лиц определяется условиями:

v(U,3) + v(2,3,4) + v(l,4)<2; (1)

v(U) + v(3,4)<l; (2)

2v(l,2,3) + v(l,4) + v(2,4) + v(3,4) < 3; (3)

v(l ДЗ) + v(l,2,4) + v(l,3,4) + v(2,3,4) < 3; v(l) = v(2) = v(3) = v(4) = 0;

v(S) > 0,1 S\ = 2; \(S) й 1, ISÍ= 3; v(5,) < v(S2), Ul = 2, Ы = 3, а также аналогичными (1), (2), (3) неравенствами, получающимися перестановкой игроков.

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

Утверждение 2. Пусть ^-коалиция, IS I =2,3,...,и-1, (7},..,,Tt) -разбиение S, тогда множество P={S,Tl и (N \ S),...,T, u(N\S)} есть минимальное сбалансированное покрытие с коэффициентами

a = (l-l/f,l/í,...,l/í)-

Утверждение 3. Пусть ^-коалиция, 15 I =2,3,...,«-], (7,1,...,Г() -разбиение 5, тогда множество Р={5,ЛГ\7"1,...,ЛГ\7"(} есть минимальное сбалансированное покрытие с коэффициентами а = (1 //,..., 1 /7).

Во второй главе рассмотрены два подкласса классических кооперативных игр: дискретные кооперативные шры и целочисленные кооперативные игры.

Кооперативная игра С/ = (М,у2)> с целочисленной характеристической

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

Обозначим 0,, 02, бгг - соответственно множества классических, целочисленных и дискретных игр; = 2 хг; = {дс е Я"|х(ЛГ) = -

определим как множество преддележей игры в, /(С?) = еX,- >16А^} - множество дележей игры С?; М| -

множество целочисленных многогранников пространства Я";

у (5) = - \ 5) - характеристическая функция двойственной игры;

- множество двойственных дележей игры (7; СС(<Э) = /(С) п I (С7) -СС-ядроигры С7; - множество перестановок ^ = - определенная я* коалиция; «*((?) е Л" -

соответствующий я" маргинальный вектор, т.е. (С) = ) - К^м); множество Вебера игры С? обозначим через

Щв) = соот({|ия'(0)| к е Я(ЛГ)}).

Любую дискретную игру можно привести к О-редуцированной форме, когда у(г) = 0, ¡еЫ;

Формула перехода к О-редуцированной игре имеет вид: v'(S) = v(S) - ЕКО' SçzN.

feS

Если х' = (х,х'„) - дележ игры < N, v'>, то х- (*]5..., хп), где Xj = xj + y(i), ieN, является дележом исходной игры < N, v>.

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

Утверждение 4. Пусть Gz е Qz, тогда:

(a) W{Gz)*0,W(Gz)eMnz;

(b) если выполняется условие

ieN

то I(Gz)*0; I{Gz)eMÎ;

(c) если выполняется условие

5>z(0*vz(JV)t (5)

ieN

то I*(GZ) * 0 ; /*(Gz) G Mz ;

(d) если выполняются условия (4)-(5) и условие vz(i)£vz(i), ieN, (6) то CC(GZ ) * 0, CC(GZ ) в Ml.

Дискретную игру Gzz формально можно записать в виде кооперативной игры с нетрансферабельной полезностью (НТП-игры) GZZ=(N,VZ), где

Vz(S) = {xeZs\x(S)<vz(S)}, SçN, s = |5|, т.е. Vz - многозначная характеристическая функция, ставящая в соответствие каждой коалиции SçzN (S#0), непустое множество Vz(S)eRs, содержащее s-мерные векторы выигрышей, допустимые для коалиции S. Результаты, полученные для НТП-игр, не применимы к дискретной игре Gzz из-за требований, налагаемых на характеристическую функцию. Например, из условий, что

хеУ2(£■), уеЯ" и у^х должно следовать уеУ2(5), которое не выполняется для дискретных множеств. С другой стороны, возможность количественного сравнения предпочтений агентов в игре позволила

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

Множества дележей, двойственных дележей, СС-ядро и множество

Вебера дискретной игры ^72 есть пересечения соответствующих множеств игры и целочисленной решетки Zn: /(<?гг)= )п »

1\ог2)=1\о2)глг\ сс(022)=сс(в2)г,гп, щсг2)=щог)п2я.

С-ядро дискретной игры (как и С-ядро классической игры) определяется в литературе неоднозначно. С-ядро дискретной игры ^гг это пересечение С-ядра игры и целочисленной решетки: С(С22) = С(С2)Г[1",

множество недоминируемых дележей ЩОг2) = 1(Сг)\дотЦ02) - будем

называть .О-ядром игры •

Следующие утверждения характеризуют множества, связанные с игрой ^22, и соотношения между ними.

Утверждение 5. Пусть Ощ е (¿т, тогда:

(a) 1Г{ва)*0-,

(b) /(622 ) * 0 тогда и только тогда, когда выполняется условие (4);

(c) I* {Сг^ ) ^ 0 тогда и только тогда, когда выполняется условие (5);

(с1) СС(Оп ) -ф- 0 тогда и только тогда, когда выполняются условия (4)-(6); Утверждение б. Пусть Сн е Чтг. тогда:

(a) С^д^ОДг);

(b) требование супераддитивности функции у2 не достаточно для равенства

(c) если C(Gzz) * D(Gzz )»то возможно C(GZZ ) * 0;

(d) существуют игры , для которых CC(GZZ ) с D{GZZ );

(e) D(Gz)nZnaD(Gzz).

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

SaN S:ieS v '

Из C(G2Z)qC(G2) следует, что условие (7) для v = vz является

необходимым условием существования С-ядра дискретной игры . Доказано, что необходимым условием непустоты £>-ядра дискретной игры является сбалансированность вспомогательной игры (N, vz), где = vrz(s,) = vz('s,)--'s + 1. S<zN. Приведем достаточные

условия непустоты С-ядра дискретной игры.

Утверждение 7. Если выполняется одно из условий:

(a) существует такое ieN, что vz(S) + если ieS, и W J J keN\S

, если iíS:

keS

(b) существует такое ieN, что vz(s)+^X/^zW-vz, если ieS, и

, если i Й o ;

keS

(c) существует такая перестановка я, что vz (£) - Z Щ (yz), S * Sf, ieN;

ieS

(d) игра G'z=(N,v'z), где v;(5) = max{vz(5),0z(S)}, <oz(S) = vz(N)~ I¿i(vz)( SqN, b¡(vz) = vz(N)-vz(N\i),выпукла;

ieN\S

то игра сбалансирована, следовательно, она имеет непустое С-ядро.

Рассмотрены некоторые специальные классы целочисленных игр. В Г-симплексных играх С-ядро является С^-!)-мерным симплексом

С^г) = сопу{/' {в 2 )| г е Т), Г с N, Т Ф 0. В двойственно Г-симплексных

играх . Игра является игрой

большого босса с игроком и в качестве большого босса, если выполняются условия (4)-(6) и

для таких 5 с N, что п «£ Б,

для таких 5сN, что пеБ. Обозначим через

множества игр, удовлетворяющих соответственно условиям (а)-(Ф утверждения 7. Нетрудно проверить, что 5Нв содержит класс целочисленных Г-симплексных игр и игр большого босса, — класс целочисленных

двойственно Г-симплексных игр. Множество содержит, в частности,

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

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

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

«Интерфейс преподавателя», в котором присутствуют административные функции, а также модули для проверки результатов тестирования и оценки работ студентов;

- «Интерфейс студента», в котором студент самостоятельно выбирает режим работы, он может заниматься изучением материалов, подготовкой к

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

- «Интерфейс решения задач кооперативной теории», в котором можно создавать и решать задания из кооперативной теории игр.

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

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

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

Комплекс создан в среде Delphi 7, выбор данной среды программирования обусловлен как гибкостью и широкими возможностями языка, так и удобством разработки интерфейса приложения. Программная реализация комплекса содержит 27 модулей, общий объем текста модулей превышает 9000 строк. Многие блоки комплекса являются ресурсоемкими, и скорость выполнения заданий зависит от мощности процессора и объема

оперативной памяти компьютера. Комплекс работает на ЮМ PC - совместимом компьютере, с процессором Pentium П и выше, 128 Мб и более оперативной памяти.

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

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

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

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

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

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

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

6. Разработаны и исследованы дополнительные свойства таких математических объектов как: множество дележей, множество двойственных дележей, множество Вебера и СС-ядро целочисленной игры.

7. Установлено, что при использовании множества Си между дискретными и классическими играми устанавливаются соотношения,

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

8. Получены достаточные условия непустоты С-ядра дискретной игры.

Результаты исследований отражены в следующих публикациях:

Издания, рекомендованные ВАК:

1. Зинченко А.Б., Оганян JI.C. О структуре многогранников использующихся в кооперативной теории // Известия высших учебных заведений. Северо-Кавказский регион. Естественные науки, 2007. - № 1, -С. 21-23.

2. Оганян J1.C., Зинченко А.Б., Мермельштейн Г.Г. Ядерные решения дискретной кооперативной игры // Известия высших учебных заведений. Северо-Кавказский регион. Технические науки, 2009. -№ 5. - С. 6-9.

3. Оганян JI.C., Зинченко А.Б., Мермельштейн Г.Г. Кооперативные игры с условиями дискретности / Обозрение прикладной и промышленной математики. Десятый всероссийский симпозиум по прикладной и промышленной математике. - Москва, 2009. - Т. 16. - Вып. 4. - С. 687

Другие издания:

4. Зинченко А.Б., Оганян Л.С., Теншцев И.Е. Графы пересечений и нецелочисленные вершины релаксированного многогранника разбиений. ДЕП., № 216-В2006, от 09.10.2006.

5. Оганян Л.С., Зинченко А.Б., Мермельштейн Г.Г. О сбалансированности экономических конфликтов, моделируемых дискретными играми / Сборник научных трудов всероссийского симпозиума «Математические модели и информационные технологии в экономике». Т.2. - Кисловодск, 2007. - С. 7-10.

6. Оганян Л.С., Зинченко А.Б., Мермельштейн Г.Г. Компьютерная поддержка спецкурса по кооперативным играм / Научно-методическая конференция «Современные информационные технологии в образовании: Южный Федеральный округ» - Ростов н/Д, 2007-С. 196-197.

7. L. S. Oganyan, A.B. Zinchenko, G.G. Mermelshtein The concept of a core of cooperative game with integer imputations / Proceedings of the second international conference "Mathematical modeling of social and economical dynamics". - Moscow, 2007. - P. 199-201.

8. Оганян JI.C. Свойства ядра кооперативной игры с целочисленными дележами / Материалы П международной научной конференции «Современные проблемы прикладной математики и математического моделирования». -Воронеж, 2007. - С. 145-146.

9. Оганян Л.С., Мермелынтейн Г.Г. Обучающий программный комплекс «Кооперативные игры» / XVI международная конференция «Математика. Экономика. Образование». -Ростов н/Д, 2008. - С. 187-188.

10. Оганян Л.С., Зинченко А.Б., Мермелыптейн Г.Г. Решения дискретной кооперативной игры и условия их существования / Материалы всероссийской заочной научно-практической конференции «Современная математика и проблемы математического образования». - Орел, 2009.-С. 310-315.

11. Lev S. Oganyan, Alexandra В. Zinchenko and Gennady G. Mermelshtejn Core like solution concepts for discrete cooperative games / The third international conference "Game theory and management". - St. Petersburg, 2009. - P. 189-191.

Личный вклад автора в работах, выполненных в соавторстве

/1/ - вывод условий определяющих множество супераддитивных, сбалансированных, (0-1 )-редуцированных игр четырех лиц; /2,3/ -доказательство новых свойств множеств, связанных с целочисленными и дискретными играми; /4/ - получение типов покрытий игр малой размерности; /5/ - постановка задачи; /6,9/ - постановка задачи, разработка структуры комплекса; 111 - вывод условий существования ядра дискретной игры; /10/ -доказательство свойств множества дележей дискретной игры; /11/ -доказательство утверждений, связанных с множеством недоминируемых дележей.

/ у

ОГАНЯН ЛЕВ СЕРГЕЕВИЧ

АЛГОРИТМЫ И ПРОГРАММНЫЙ КОМПЛЕКС РЕШЕНИЯ ЗАДАЧ ТЕОРИИ КООПЕРАТИВНЫХ ИГР. ЯДЕРНЫЕ РЕШЕНИЯ ДИСКРЕТНЫХ КООПЕРАТИВНЫХ ИГР.

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

Подписано к печати 30.03. № .Формат 60x84/16 Бумага офсетная. Печать офсетная. Усл.печ.л. 1.4 Уч.-изд.Л.1 Тираж 100 Заказ № 4969.

Ростовский государственный университет путей сообщения. Ризография РГУПС.

Адрес университета: 344038, г. Ростов-на-Дону, пл. Ростовского Стрелкового Полка Народного Ополчения, 2.

Введение.

Глава 1. Сбалансированные игры с трансферабельными полезностями.

1.1 Основные понятия кооперативной теории игр.

1.2 С-ядро и условия его существования

1.3 Значения кооперативных игр. Цена Шепли и И-ядро

1.4 Минимальные сбалансированные покрытия.

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

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

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

1.8 Основные результаты, полученные в первой главе.

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

2.1. Применение стандартного отношения доминирования для определения сбалансированности дискретных игр.

2.2. С-ядро, Э-ядро, СС-ядро и соотношения между

2.3. Основные результаты, полученные во второй главе.

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

3.1. Описание работы комплекса в режиме администрирования.

3.2. Описание работы комплекса в режиме тестирования и обучения.

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

3.4. Выводы по третьей главе.

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

Большой вклад в развитие теории кооперативных игр внесли Фон Нейман Дж., Моргенштерн О., Нэш Дж., Шепли JI.C., Воробьев H.H., Бондарева О.Н., Мулен Э., Петросян JI.A., Яновская Е.Б. и др.

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

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

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

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

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

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

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

Для достижения этих целей в работе решены следующие задачи:

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

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

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

4. Выведены достаточные условия непустоты С-ядра дискретной игры.

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

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

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

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

1. Сбалансированные игры с трансферабельными полезностями

3.4. Выводы по третьей главе

Описанные и исследованные в первой и второй главах диссертации математические объекты позволили реализовать эффективные алгоритмы в виде комплекса проблемно-ориентированных программ.

Разработанный комплекс состоит из трех основных функциональных блоков. Блок решения задач кооперативной теории позволяет решать широкий круг вопросов, связанных с кооперативной теорией игр. Вычисление минимальных сбалансированных покрытий и существенных минимальных сбалансированных покрытий, делает возможным генерирование сбалансированных игр. Также есть возможность проверки суперадцитивности, сбалансированности, двойственной сбалансированности игр; вычисления цены Шепли, тУ-ядра, обобщенного УУ-ядра; вычисления вершин С-ядра, двойственного С-ядра. Блок администрирования позволяет преподавателю устанавливать основные настройки комплекса, редактировать и создавать новые тестовые задания. Блок тестирования и обучения помогает студентам подготовиться к проверочным работам, а также дает возможность преподавателю проводить контрольные работы для студентов в виде тестов.

108

Заключение

Основные научные и практические результаты работы:

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

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

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

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

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

6. Разработаны и исследованы дополнительные свойства таких математических объектов как: множество дележей, множество двойственных дележей, множество Вебера и СС-ядро целочисленной игры.

7. Установлено, что при использовании множества ^zz между дискретными и классическими играми устанавливаются соотношения, аналогичные соотношениям между дискретными и непрерывными задачами математического программирования.

8. Получены достаточные условия непустоты С-ядра дискретной игры.

Библиографический

1. Аъзамхужаев М.Х., Морозов В.В. О решении дискретных кооперативных игр трех лиц // Математические методы оптимизации и управления в сложных системах. Межвузовский тематический сборник научных трудов. Калинин. 1986. С.84-88.

2. Аъзамхуясаев М.Х. Условия непустоты ядер дискретных кооперативных игр // Программное оборудование и вопросы принятия решений. М. 1989. С.210-219.

3. Бондарева О.Н., Некоторые приложения методов линейного программирования к теории кооперативных игр // Проблемы кибернетики. 1963. Вып. 10

4. Бондарева О.Н., О теоретико-игровых моделях в экономике. Л.: ЛГУ,1974.

5. Воробьев H.H., Основы теории игр: бескоалиционные игры, М.: Наука. 1984

6. Гермейер Ю.Б., Игры с непротивоположными интересами. М.: Наука, 1976.

7. Губко М.В. Управление организационными системами с коалиционным взаимодействием участников. М., 2003. 140 с.

8. Гусаков С.В., Землянухина Л.Н., Зинченко А.Б., Сантылова Л.И. Методические указания по курсу: Методы оптимизации, части 5 и 7. — Ростов-надону, 2000.

9. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич P.M. Лекции по теории графов. М., 1990.

10. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. М., 1981.

11. Жак C.B., Зинченко А.Б. Согласование внутренних цен предприятий как кооперативная игра с побочными платежами // Изв. вузов. Сев.-Кавк. регион. Естеств. науки, №4, 2001.

12. Зинченко А.Б. Об одном способе вывода достаточных условий существования с-ядра кооперативной игры // Тез. докл. 23 междунар. школы-семинара им. академика С.С.Шаталина "Системное моделирование социально-экономических процессов", Воронеж, 2000.

13. Зинченко А.Б. С-ядро дискретной кооперативной игры. Деп. 3.03.2004. №390-В2004.

14. Зинченко А.Б. Аналитическое описание игр, моделирующих сбалансированные конфликты // Теория конфликта и ее приложения. Материалы IV Всероссийской научно-технической конференции, Воронеж, 2006, с. 183-186.

15. Зинченко А.Б., Оганян U.C., Тенищее И.Е. Графы пересечений и нецелочисленные вершины релаксированного многогранника разбиений ДЕП., №1216-В2006, от 9.10.2006.

16. Зинченко А.Б., Тенищее И.Е. Устойчивость экономических ситуаций, моделируемых ТП-играми // Управление устойчивым развитием экономических систем. Межвузовский сборник научных трудов, Санкт-Петербург, 2006, с.627-629.

17. Зинченко А.Б., Мермелъштейн Г.Г. Сбалансированные и двойственно сбалансированные дискретные кооперативные игры // Экономический вестник РГУ. 2007. Т. 5. №1. Ч. 2. С. 109-115.

18. Зинченко А.Б., Оганян U.C. О структуре многогранников, использующихся в кооперативной теории // Известия вузов. СевероКавказский регион. Естественные науки, 2007. №1. С.21-23.

19. Зыков A.A. Основы теории графов. М., 2004.

20. Кофман А. Введение в прикладную комбинаторику. М., 1975.

21. Кукушкин H.С., Морозов B.B. Теория неантагонистических игр. М., 1984.

22. Майника Алгоритмы теории графов. — М., 1981.

23. Морозов В.В., Аъзамхуэ/саев М.Х. О поиске дележей дискретной кооперативной игры //Применение вычислительных средств в научных исследованиях и учебном процессе. М., 1991. С.49-62.

24. Мулен Э. Теория игр с примерами из математической экономики. — М., 1985.

25. Мулен Э. Кооперативное принятие решений: аксиомы и модели. — М., 1991.

26. Оганян Л.С., Зинченко А.Б., Мермелъштейн Г. Г. Компьютерная поддержка спецкурса по кооперативным играм, Современные информационные технологии в образовании: Южный Федеральный округ, Ростов-на-Дону, 2007, 196-197.

27. Оганян JI.C. Свойства ядра кооперативной игры с целочисленными дележами, Материалы II международной научной конференции «Современные проблемы прикладной математики и математического моделирования», Воронеж, 2007, 145-146.

28. Оганян Л.С., Мермелъштейн Г. Г. Обучающий программный комплекс «Кооперативные игры»,XVI Международная конференция «Математика. Экономика. Образование», Ростов-на-Дону, 2008.

29. Оганян Л.С., Зинченко А.Б., Мермелъштейн Г.Г. Кооперативные игры с условиями дискретности, Обозрение прикладной и промышленной математики. Десятый всероссийский симпозиум по прикладной и промышленной математике, Москва, 2009. Т. 16. — Вып. 4. — С. 687

30. Оганян Л.С., Зинченко А.Б., Мермелъштейн Г.Г. Ядерные решения дискретной кооперативной игры, Известия высших учебных заведений, Северо-Кавказский регион, Технические науки, № 5, 2009, 6-9.

31. Печерский СЛ., Функции эксцесса для кооперативных игр без побочных платежей: аксиоматический подход. //Экономико-математические исследования: математические модели и информационные технологии. СПб:. Наука 65-82.

32. Печерский СЛ., Яновская Е.Б., Трансферабельные значения для игр с нетрансферабельными полезностями //Экономические исследования: теория и приложения. СПб:. Европейский университет в СПб. 2000. 310-349.

33. ЪЪ.Петросян Л.А., Зенкевич H.A., Семина Е.А., Теория игр. М.: Высшая школа, Книжный дом «Университет». 1998.

34. Роберте Ф.С. Дискретные математические модели с приложениями к социологическим, биологическим и экологическим задачам. М., 1986.

35. Розенмюллер И. Кооперативные игры и рынки. М., 1974.

36. Трубин В.А. О методе решения задач целочисленного линейного программирования специального вида. // Докл. АН СССР, 1969, 189, №5.

37. Черников С.Н. Линейные неравенства. М., 1968.

38. Фон Нейман Дж. Моргенштерн О. Теория игр и экономическое поведение. М.: Наука, 1970.41 .Aumann R.J., The core of a cooperative game without side payments, Transactions of the American Mathematical Society 98, 1961. P. 539-552.

39. Aumann, R.J. and Dreze J.H., Cooperative games with coalition structure, International Journal of Game Theory, 3, 1974. P. 217-237.

40. Azamkhuzhaev M.Kh., Nonemptiness conditions for cores of discrete cooperative games // Computational Mathematics and Modeling, 1991. V.2. N.4. P.406-411.

41. Billera L.J., Some theorems on the core of an n-person game without side payments, SIAM Journal on Applied Mathematics 18, 1970. P. 567-579.

42. Bonnisseau J. M., Iehle V. Payoff-dependent balancedness and cores // Games and Economic Behavior. 2007. Vol. 61. No. 1. P. 1-26.

43. Branzei R., D. Dimitrov and S. Tijs S. Models in cooperative game theory: crisp, fuzzy and multichoice games. //Lecture notes in economics and mathematical systems, Springer-Verlag, Berlin, 2005, P. 17-19.

44. Bruyneel Guido. Computation of the nucleolus of a game by means of minimal balanced sets. "Oper. Res. " Verfahren, 1978, 34.

45. Calvo E. and Santos J.C., A value for multichoice games, Mathematical Social Sciences 40, 2000. P. 341-354.

46. Calvo E. and Santos J.C., A value for mixed action-set games, International Journal of Game Theory 30, 2001. P. 61-78.

47. Curiell. J., Maschler M., Tijs S. Bankruptcy games // Math. Meth. Oper. Res. 1987. Vol. 34. No. 5. P. 143-159.

48. Davis, M. and Maschler M., The kernel of a cooperative game, Naval Research Logistics Quarterly, 12, 1965. P. 223-259.

49. Dimand Mary-Ann, Dimand Robert W. The History Of Game Theory, Routledge, 1996.

50. Driessen T.S.H., Cooperative Games, Solutions and Applications, Kluwer Academic Publishers.1988.

51. Driessen T.S.H. and H. Sun, A potential approach to solutions for set games, Memorandum No. 1571, Faculty of Mathematical Sciences, University of Twente, Enschede, The Netherlands. 2001.

52. Francisco S., Balanced contributions axiom in the solution of cooperative games, Games and Economic Behavior, 20, 1997. P. 161-168.

53. Funaki Y. Dual Axiomatizations of Solutions of Cooperative Games. Working Paper. 13. Toyo University. Japan. 1994.

54. Funaki Y., Yamato T. The core and consistency properties: a general characterizations // International Game Theory Review. 2001. 3. P.175-187.

55. Gibbins R., Game theory for applied economists. Princeton University Press, Princeton, 1992.

56. Hwang Y.A., Sudholter P. An Axiomatization of the Core on the Universal Domain and other Natural Domains // International Journal of Game Theory. 2001.29. P.597-623.

57. Keiding H. and L. Thorlund-Petersen, The core of a cooperative game without side payments, Journal of Optimization Theory and Applications 54, 1987. P. 273-288.

58. Kuipers J. On the core of information graph games // Int. J. Game Theory.1993. Vol. 21. P. 339-350.

59. Llerena F., Rafels C. Convex decomposition of games and axiomatizations of the core and D-core // International Journal of Game Theory. 2007. V.35. N.4. P.603-615.

60. Lucas, W. F., Game theory and its application, Proceedings of Symposia in Applied Mathematics, 24, American Mathematical Society. 1981.

61. Monderer D., Samet D. and L.S. Shapley, Weight values and the core, International Journal of Game Theory, 21, 1992. P. 27-39.

62. Moulin H., Cores and large cores when population varies, International Journal of Game Theory, 19, 1990. P. 219-232.

63. Moulin H., Cooperative Microeconomics: a Game Theoretic Introduction. Princeton University Press; Prentice-Hall. 1995.

64. Myerson R.B., Game Theory: analysis of conflict. Harvard University Press, Cambridge. 1991.

65. Nash J., Two-person cooperative games, Econometrica 21, 1953. P. 128-140.

66. Nouweland H., Borm P.E.H., Brouwers M., Bruinderink R. and Tijs S.H., A game theoretic approach to problems in telecommunication, Management Science, 42, 1996. P. 294-303.

67. Nowak A.S. and T. Radzik, The Shapley value for n-person games in generalized characteristic function form, Games and Economic Behavior 6,1994. P. 150-161.

68. Oganyan L.S., Zinchenko A.B., Mermelshtejn G.G. The concept of a core ofcooperative game with integer imputations, Proceedings of the second international conference "Mathematical modeling of social and economical dynamics", Moscow, 2007. P. 199-201.

69. Oganyan L.S., Zinchenko A.B. and Mermelshtejn G. G. Core like solution concepts for discrete cooperative games, //Game theory and management: proceedings of the third international conference , St. Petersburg, 2009, 189-191.

70. Osbourne M.J., Rubinstein A. A Course in Game Theory, MIT Press, 1994.

71. Owen G., Game Theory, 3rd ed., Academic Press. 1995.

72. Predtetchinski A. and Hering P.J.J., A necessary and sufficient condition for the non-emptiness of the core of a non-transferable utility game, METEOR Research Memorandum 02/19, Universiteit Maastricht, 2002.

73. Peleg B. and SudhAolter P. Introduction to the Theory of Cooperative Games. Boston: Kluwer Academic Publishers. 2003.

74. Peters H, Cooperative Game Theory. University of Maastricht. 1997.

75. Potters J., Poos R., Tijs S., MutoS. Clane games // Games and Economic Behavior. 1989. No. 1. P. 275-293.

76. Rafels, C. and S. Tijs, On cores of cooperative games and the stability of the Weber set, International Journal of Game Theory 26, 1997. P. 491-499.

77. Roth, A., The Shapley Value: Essays in Honor of Lloyd S. Shapley, Cambridge University Press. 1988.

78. Rosenthal E.G., Monotonicity of the core and value in dynamic cooperative games, International Journal of Game Theory, 19, 45-57. Scarf H., The core of an N person game, Econometrica 35. 1990. P. 50-69.

79. Shapley, L.S., A value for n-person games, in: Contributions to the Theory of Games II, Annals of Mathematics Studies No, 28, (Kuhn H. and A.W. Tucher, eds.) Princeton University Press, Princeton, 1953. P. 307-317.

80. Shapley L.S. and ShubikM., On market games, Journal of Economic Theory 1, 1969. P. 9-25.

81. Shapley L.S., On balanced games without side payments, in: Mathematical Programming, eds. T.C. Hu and S.M. Robinson (Academic Press, New York, 1973. P. 261-290.

82. Shapley L.S., Measurement of power in political systems, Proceedings of symposia in applied mathematics, 24, 1981. P. 69-81.

83. Shubik M., Game theory in the social sciences: concepts and solutions. Massachusetts: MIT Press, 1991.

84. Tijs S., MecaA., LorezM.A. Benefit sharing in holding situations // Eur. J. Oper. Res. 2005. Vol. 162. No. 1. P. 251-269.

85. Tijs, S. Introduction to Game Theory, Hindustan Book Agency. 2003.

86. Tijs, S., Branzei R., Ishihara S. and S. Muto, On cores and stable sets for fuzzy games, Fuzzy Sets and Systems 146,2004. P. 285-296.

87. Voorneveld M., Grahn S. A minimal test for convex games and the Shapley value // Working Paper Series 2001:2, Department of Economics, Uppsala University. 2001.

88. Weber R.J., Probabilistic values for games. In The Shapley Value: Essays in Honor of Lloyd S. Shapley. Cambridge: Cambridge University Press, 1988. P. 101-119.

89. Yanovskaya E. Consistency Properties of the Nontransferable Cooperative Game Solution // Game Theoretical Applications to Economics and Operation Research /T.Parthasarathy at al. (eds.). Kluwer Academic Publishers. 1997. P. 67- 84.

90. Yanovskaya E. Set-Valued Analogues of the Prenucleolus // Game Theory and Applications. 3 / L.Petrosjan, V. Mazalov (eds.). N.Y.: Nova Science Publishers. 1997a. 161-175.

91. Young, H.P., Monotonic Solutions of Cooperative Games, International Journal of Game Theory 14, 1985. P. 65-72.118