Автор работы: Пользователь скрыл имя, 22 Февраля 2011 в 12:15, курсовая работа
Цель курсовой работы изучить некоторые методы приближённого решения матричных игр, обосновать их алгоритмы, и, по возможности, реализовать на языке программирования.
Введение 2
Теория игр. 3
КЛАССИФИКАЦИЯ ИГР. 3
ГЛАВА 1. МАТРИЧНЫЕ ИГРЫ. 4
§ 1. РЕШЕНИЕ МАТРИЧНЫХ ИГР В ЧИСТЫХ СТРАТЕГИЯХ. 4
§ 2. СМЕШАННОЕ РАСШИРЕНИЕ МАТРИЧНОЙ ИГРЫ. 7
§ 3. СВОЙСТВА РЕШЕНИЙ МАТРИЧНЫХ ИГР. 8
§ 4. ИГРЫ ПОРЯДКА 2 х 2. 12
§5. СВЕДЕНИЕ МАТРИЧНОЙ ИГРЫ К ЗАДАЧЕ 13
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 13
Глава 2. КООПЕРАТИВНЫЕ ИГРЫ 16
§ 1. ПЕРЕЧИСЛЕНИЕ ХАРАКТЕРИСТИЧЕСКИХ ФУНКЦИЙ 20
С МАЛЫМ ЧИСЛОМ ИГРОКОВ. 20
Заключение 33
Список использованной литературы 34
т.е. ради “справедливости” необходимо считать, что при участии игроков в двух играх их выигрыши в отдельных играх должны складываться.
Определение. Вектором цен (вектором Шепли) игры с характеристической функцией u называется n-мерный вектор
j (u) = (j1(u), j2(u), ..., jn(u)),
удовлетворяющий аксиомам Шепли.
Существование вектора Шепли вытекает из следующей теоремы
Теорема. Существует единственная функция j, определённая для всех игр и удовлетворяющая аксиомам Шепли.
Определение. Характеристическая функция wS(T), определённая для любой коалиции S, называется простейшей, если
wS(T) =
Содержательно простейшая характеристическая функция описывает такое положение дел, при котором множество игроков S выигрывает единицу тогда и только тогда, когда оно содержит некоторую основную минимальную выигрывающую коалицию S.
Можно доказать, что компоненты вектора Шепли в явном виде запишутся следующим образом
где t – число элементов в T.
Вектор
Шепли содержательно можно
u(T) - u(T \{i})
и считается выигрышем i-го игрока; gi (T) – это вероятность того, что i-й игрок вступит в коалицию T \{i}; ji (u) – средний выигрыш i-го игрока в такой схеме интерпретации. В том случае, когда u – простейшая,
Следовательно
где суммирование
по T распространяется на все такие
выигрывающие коалиции T, что коалиция
T \{i}не является выигрывающей.
Пример. Рассматривается корпорация из четырёх акционеров, имеющих акции соответственно в следующих размерах
a1 = 10, a2 = 20, a3 = 30, a4 = 40.
Любое решение утверждается акционерами, имеющими в сумме большинство акций. Это решение считается выигрышем, равным 1. Поэтому данная ситуация может рассматриваться как простая игра четырёх игроков, в которой выигрывающими коалициями являются следующие:
{2; 4}, {3; 4},
{1; 2; 3}, {1; 2; 4}, {2; 3; 4}, {1; 3; 4},
{1; 2; 3; 4}.
Найдём вектор Шепли для этой игры.
При нахождении j1 необходимо учитывать, что имеется только одна коалиция T = {1; 2; 3}, которая выигрывает, а коалиция T \{1} = {2; 3} не выигрывает. В коалиции T имеется t = 3 игрока, поэтому
Далее, определяем все выигрывающие коалиции, но не выигрывающие без 2-го игрока: {2; 4}, {1; 2; 3}, {2; 3; 4}. Поэтому
Аналогично получаем, что , .
В результате получаем, что вектор Шепли равен . При этом, если считать, что вес голоса акционера пропорционален количеству имеющихся у него акций, то получим следующий вектор голосования
который, очевидно, отличается от вектора Шепли.
Анализ
игры показывает, что компоненты 2-го
и 3-го игроков равны, хотя третий игрок
имеет больше акций. Это получается вследствие
того, что возможности образования коалиций
у 2-го и 3-го игрока одинаковые. Для 1-го
и 4-го игрока ситуация естественная, отвечающая
силе их капитала.
Итак,
подводя итоги проведенной
В
процессе сбора данных об изучаемом
явлении, анализа этих данных и введения
при построении модели различных предположений
накапливаются ошибки. Они же могут выражаться
числами в матрице выигрышей. Поэтому
точность в определении значения игры
и оптимальных стратегий игроков оправдана
не всегда. А также, следует заметить, что
погрешность в оценке игроком своего выигрыша
не может привести к практически серьёзным
последствиям и небольшое отклонение
игрока от оптимальной стратегии не влечёт
за собой существенного изменения в его
выигрыше. Ввиду этих причин в курсовой
работе были приведены примеры решения
матричных игр, а так же предоставлен код
программы.