Нестеренко М.Ю., Голубенко И.В. Кооперативные игры
Подождите немного. Документ загружается.
находим А({I,II,III})
Вычислим значение характеристической функции, для этого составим
дополнительные функции:
- функция maxmin находит максимум из минимумов по строкам.
- функция minmax находит минимум из максимумов по столбцам
11
- функция v(A) проверяет существование решения в чистых стратегиях,
т.е. наличие седловой точки. Если такое решение есть, то функция
возвращает цену игры.
Вычислим значение характеристической функции для первой
коалиции.
Применяя описанную выше функцию v к матрице выигрышей A1
получим, что верхняя и нижняя цены игры не совпадают и для того, чтобы
вычислить цену игры требуется ее сведение к задаче линейного
программирования.
Как известно из раздела стратегических игр, игра, задаваемая матрицей
А1, сводится к задаче линейного программирования с ограничениями,
заданными системой:
30t
1
67 .5t
2
69t
3
≥1
87.5t
1
27.5t
2
69t
3
≥1
87.5t
1
67.5t
2
48t
3
≥1
67.5t
1
35t
2
69t
3
≥1
125t
1
−5t
2
69 t
3
≥1
125t
1
35t
2
48t
3
≥1
67.5t
1
67.5t
2
42t
3
≥1
125t
1
27 .5t
2
42t
3
≥1
125t
1
67 .5t
2
21t
3
≥1
{}{}{}{}{}{}{}{}
и целевой функцией f :
f=t
1
+t
2
+t
3
min
.
12
Для решения задачи линейного программирования в среде MathCAD,
опишем целевую функцию f следующим образом:
.
Параметр функции х – вектор, элементами которого являются значения
переменных t
1
, t
2
и t
3
. Размерность вектора х – число строк в матрице
выигрышей (которое равно числу стратегий игрока) или число столбцов в
транспонированной матрице выигрышей.
Далее необходимо указать начальное значение параметра,
относительно которого будет решаться задача минимизации. Это значение
должно попадать в допустимую область, заданную системой ограничений.
Система ограничений в матричном виде запишется следующим
образом: А1
Т
∙t1 ≥ 1, в таком виде и будем ее использовать для решения ЗЛП.
Для решения оптимизационных задач (к которым относится и задача
линейного программирования) в программном комплексе MathCAD имеются
встроенные функции Maximize и Minimize для вычисления точек максимума и
минимума соответственно. Для того, чтобы задать ограничения на
допустимую область значений параметров оптимизации, их нужно поместить
в блок решения Given до вызова функций Maximize или Minimize.
Таким образом, получим решение t, зная которое найдем цену игры:
Подробнее о сведении игры к задаче линейного программирования в
[3]. Узнать больше о решении задач оптимизации в MathCAD можно из
встроенной справочной системы или из любого справочного или учебного
пособия по MathCAD.
13
Применяя функцию v ко второй матрице выигрышей получим, что
верхняя и нижняя цены игры совпадают и сведение к задаче линейного
программирования не требуется. Функция v в данном случае возвращает
цену игры.
Третья матрица требует построение задачи линейного
программирования:
Для этого, как и ранее, опишем целевую функцию, укажем допустимое
начальное значение параметра минимизации, запишем систему ограничений
для данной задачи в матричном виде и решим задачу минимизации с
помощью функции Minimize, указав в блоке Given систему ограничений в
матричном виде:
Далее найдем цену игры. Она будет значением характеристической
функции для третьей коалиции.
Для оставшихся коалиций верхняя и нижняя цены игры совпадают,
поэтому значения характеристической функции для каждой коалиций могут
быть вычислены с помощью функции v:
14
На основе вычислений сделаем вывод, что наибольший выигрыш дает
коалиция {I, II, III} – он равен 310500.
3 Проверка существенности игры
Кооперативные игры называются существенными, если для любых
коалиций K и L выполняется неравенство:
v(K) + v(L) < v(KUL).
В существенной игре игрокам выгодно объединяться, так как в
коалиции вследствие формирования множества стратегий выигрыш ее k-го
игрока возрастает сравнительно с его индивидуальным выигрышем в
некооперативной игре.
Проверка существенности данной кооперативной игры имеет вид:
v ({I}) + v ({II}) < v ({I, II})
v ({I}) + v ({III}) < v ({I, III})
v ({II}) + v ({II}) < v ({II, II})
v ({I}) + v ({II}) + v ({III}) < v ({I, II, III})
Если все неравенства справедливы, то игра существенна:
4 Оптимальные коалиции и оптимальное распределение выигрыша
внутри коалиции на основе подхода Шепли
15
Вектор Шепли - это распределение выигрыша между игроками в
задачах теории кооперативных игр. Строится с учетом среднего вклада в
выигрыш коалиции каждого игрока – участника коалиции.
Общий вид компонентов вектора Шепли имеет вид:
i∈T
T ⊂ N
∑
где n - количество игроков, T – любая коалиция, содержащая i-го
игрока, t - количество участников коалиции,
v T
- характеристическая
функция игры.
Рассчитаем элементы вектора Шепли.
Первый игрок, входя в коалиции {I}, {I,II}, {I,III}, {I,II,III} увеличивает
общий выигрыш этих коалиций, поэтому
Для второго и третьего игроков соответственно
Таким образом, получаем вектор
Получаем, что выигрыш следует разделить между игроками
следующим образом:
первый игрок получит 78379, второй игрок – 102493, третий – 129628.
5 Оптимальные коалиции и оптимальное распределение выигрыша
внутри коалиции на основе стратегии угроз
Для начала рассмотрим двух игроков: 1 и 2. Найдем максимальную
общую полезность для двух данных игроков:
16
где k -максимальная общая полезность.
Можем рассмотреть игру А12-А21
Решая ЗЛП получим:
Решая ЗЛП получим:
Рассчитаем арбитражные значения u и w, в результате чего получим
Следовательно, возможность угрозы со стороны второго игрока
наиболее сильная.
Рассматривая 1 и 3 игроков, найдем максимальную общую полезность
для двух данных игроков:
Можем рассмотреть игру А13-А31
Решая ЗЛП получим:
17
Решая ЗЛП получим:
Рассчитаем арбитражные значения u и w, в результате чего получим
Следовательно, возможность угрозы со стороны второго игрока
наиболее сильные.
Рассматривая 2 и 3 игроков, найдем максимальную общую полезность
для двух данных игроков:
Далее можем рассмотреть игру А23-А32
Решая ЗЛП получим:
Рассчитаем арбитражные значения u и w, в результате чего получим
Следовательно, возможность угрозы со стороны обоих игроков
равновероятны.
18
4 Содержание письменного отчета
1. Постановка задачи.
2. Краткое изложение теоретического материала по теме "Кооперативные
игры".
3. Результаты моделирования в виде кооперативной игры.
4. Решение игры с помощью MathCad.
5. Анализ полученных результатов и выводы.
5 Вопросы к защите лабораторной работы
1. Каковы цели кооперативной игры?
2. Что такое коалиция в кооперативной игре?
3. По какой формуле считается всевозможное число коалиций?
4. Дайте определение характеристической функции кооперативной игры.
5. Перечислите и охарактеризуйте свойства характеристической функции.
6. Что означает стратегически эквивалентная игра?
7. Что такое 0 — 1 редуцированная форма кооперативной игры?
8. Какие кооперативные игры считаются существенными и несущественными?
9. Дайте определение дележа и что такое доминирование дележей в коопера-
тивных играх?
10.Перечислите основные аксиомы Шепли.
19
Список использованных источников
1 Моделирование рисковых ситуаций в экономике и
бизнесе: учеб. пособие для вузов / А.М. Дубров, Б.А.
Лагоша, Е.Ю. Хрусталев, Т.П. Барановская; под ред. Б.А.
Лагоши.-2-е изд., перераб. и доп. - М.: Финансы и
статистика, 2003. - 224 с.
2 Протасов И.Д. Теория игр и исследование операций: учеб.
пособие / И.Д. Протасов. - М.: Гелиос АРВ, 2003. – 368 с.
3 Крушевский А.В. Теория игр. – Киев: Издательское
объединение «Вища школа», 1997. - 216 с.
4 Г. Оуэн. Теория игр: перевод с английского И. Н.
Врублевской, Г. Н. Дюбина и А. Н. Ляпунова; под редакцией
А. А. Корбута с вступительной статьей Н. Н. Воробьева. –
М.: Издательство «Мир», 1971. – 468 с.
20