Автор: Пользователь скрыл имя, 29 Октября 2011 в 22:20, курсовая работа
Классификацию игр можно проводить: по количеству игроков, количеству стратегий, характеру взаимодействия игроков, характеру выигрыша, количеству ходов, состоянию информации и т.д.
1. Введение: классификация игр 3
2. Матричные игры. Решение матричных игр в чистых стратегиях 4
3. Смешанное расширение матричной игры 6
4. Свойства решений матричных игр 7
5. Игры порядка 2 х 2 10
6. Графический метод решения игр 2 х n И m х 2 11
7. Сведение матричной игры к задаче линейного программирования 13
8. Теория Нэша
Федеральное агентство по образованию
ГОУ ВПО
филиал Ростовского государственного экономического университета «РИНХ»
в
п. Матвеев-Курган
Курсовая
работа
по дисциплине: «Математические методы»
тема: «Элементы теории игр»
Выполнил студент_____ курса №_____ группы___ __________________________
Руководитель__________________
К защите
«____»___________2007г.
Матвеев-Курган
2007г.
Содержание:
1. Введение: классификация
игр
2. Матричные игры.
Решение матричных игр в чистых стратегиях
3. Смешанное расширение
матричной игры
4. Свойства решений
матричных игр
5. Игры порядка
2 х 2
6. Графический метод
решения игр 2 х n И m х
2
7. Сведение матричной
игры к задаче линейного программирования
8. Теория Нэша
Введение:
классификация игр
Классификацию игр можно
В зависимости от количества игроков различают игры двух и n игроков. Первые из них наиболее изучены. Игры трёх и более игроков менее исследованы из-за возникающих принципиальных трудностей и технических возможностей получения решения. Чем больше игроков - тем больше проблем.
По количеству стратегий игры
делятся на конечные и
По характеру взаимодействия игры делятся на:
бескоалиционные: игроки не имеют права вступать в соглашения, образовывать коалиции;
коалиционные (кооперативные) – могут вступать в коалиции.
В кооперативных играх
По характеру выигрышей игры делятся на: игры с нулевой суммой (общий капитал всех игроков не меняется, а перераспределяется между игроками; сумма выигрышей всех игроков равна нулю) и игры с ненулевой суммой.
По виду функций выигрыша игры делятся на: матричные, биматричные, непрерывные, выпуклые, сепарабельные, типа дуэлей и др.
Матричная игра – это конечная игра двух игроков с нулевой суммой, в которой задаётся выигрыш игрока 1 в виде матрицы (строка матрицы соответствует номеру применяемой стратегии игрока 2, столбец – номеру применяемой стратегии игрока 2; на пересечении строки и столбца матрицы находится выигрыш игрока 1, соответствующий применяемым стратегиям).
Для матричных игр доказано, что
любая из них имеет решение
и оно может быть легко
Биматричная игра – это конечная игра двух игроков с ненулевой суммой, в которой выигрыши каждого игрока задаются матрицами отдельно для соответствующего игрока (в каждой матрице строка соответствует стратегии игрока 1, столбец – стратегии игрока 2, на пересечении строки и столбца в первой матрице находится выигрыш игрока 1, во второй матрице – выигрыш игрока 2.)
Для биматричных игр также
разработана теория
Непрерывной считается игра, в которой функция выигрышей каждого игрока является непрерывной в зависимости от стратегий. Доказано, что игры этого класса имеют решения, однако не разработано практически приемлемых методов их нахождения.
Если функция выигрышей
Матричные игры.
Решение
матричных игр
в чистых стратегиях.
Матричная игра
двух игроков с нулевой суммой
может рассматриваться как
Первый игрок имеет m стратегий i = 1,2,...,m, второй имеет n стратегий j = 1,2,...,n. Каждой паре стратегий (i,j) поставлено в соответствие число аij, выражающее выигрыш игрока 1 за счёт игрока 2, если первый игрок примет свою i-ю стратегию, а 2 – свою j-ю стратегию.
Каждый из игроков делает один ход: игрок 1 выбирает свою i-ю стратегию (i= ), 2 – свою j-ю стратегию (j= ), после чего игрок 1 получает выигрыш аij за счёт игрока 2 (если аij< 0, то это значит, что игрок 1 платит второму сумму | аij | ). На этом игра заканчивается.
Каждая стратегия игрока i= ; j = часто называется чистой стратегией.
Если рассмотреть
матрицу
А =
то проведение каждой партии матричной игры с матрицей А сводится к выбору игроком 1 i-й строки, а игроком 2 j-го столбца и получения игроком 1 (за счёт игрока 2) выигрыша аij.
Главным в исследовании игр является понятие оптимальных стратегий игроков. В это понятие интуитивно вкладывается такой смысл: стратегия игрока является оптимальной, если применение этой стратегии обеспечивает ему наибольший гарантированный выигрыш при всевозможных стратегиях другого игрока. Исходя из этих позиций, игрок 1 исследует матрицу выигрышей А следующим образом: для каждого значения i (i = ) определяется минимальное значение выигрыша в зависимости от применяемых стратегий игрока 2
аij (i = )
т.е. определяется минимальный выигрыш для игрока 1 при условии, что он примет свою i-ю чистую стратегию, затем из этих минимальных выигрышей отыскивается такая стратегия i = iо, при которой этот минимальный выигрыш будет максимальным, т.е. находится
аij = = (1).
Определение. Число , определённое по формуле (1) называется нижней чистой ценой игры и показывает, какой минимальный выигрыш может гарантировать себе игрок 1, применяя свои чистые стратегии при всевозможных действиях игрока 2.
Игрок 2 при оптимальном своём поведении должен стремится по возможности за счёт своих стратегий максимально уменьшить выигрыш игрока 1. Поэтому для игрока 2 отыскивается
аij
т.е. определяется max выигрыш игрока 1, при условии, что игрок 2 применит свою j-ю чистую стратегию, затем игрок 2 отыскивает такую свою j = j1 стратегию, при которой игрок 1 получит min выигрыш, т.е. находит
aij = = (2).
Определение. Число , определяемое по формуле (2), называется чистой верхней ценой игры и показывает, какой максимальный выигрыш за счёт своих стратегий может себе гарантировать игрок 1.
Другими словами, применяя свои чистые стратегии игрок 1 может обеспечить себе выигрыш не меньше , а игрок 2 за счёт применения своих чистых стратегий может не допустить выигрыш игрока 1 больше, чем .
Определение. Если в игре с матрицей А = , то говорят, что эта игра имеет седловую точку в чистых стратегиях и чистую цену игры
u = = .
Седловая точка – это пара чистых стратегий (iо,jо) соответственно игроков 1 и 2, при которых достигается равенство = . В это понятие вложен следующий смысл: если один из игроков придерживается стратегии, соответствующей седловой точке, то другой игрок не сможет поступить лучше, чем придерживаться стратегии, соответствующей седловой точке. Математически это можно записать и иначе:
где i, j – любые чистые стратегии соответственно игроков 1 и 2; (iо,jо) – стратегии, образующие седловую точку.
Таким образом,
исходя из (3), седловой элемент
является минимальным в iо-й
строке и максимальным в jо-м столбце
в матрице А. Отыскание седловой точки
матрицы А происходит следующим образом:
в матрице А последовательно в каждой
строке находят минимальный элемент
и проверяют, является ли этот элемент
максимальным в своём столбце. Если
да, то он и есть седловой элемент, а пара
стратегий, ему соответствующая, образует
седловую точку. Пара чистых стратегий
(iо,jо) игроков
1 и 2, образующая седловую точку и седловой
элемент
, называется решением
игры. При этом iо и
jо называются оптимальными
чистыми стратегиями
соответственно игроков 1 и 2.
Пример 1
Седловой точкой является пара (iо = 3; jо = 1), при которой u = = = 2.
Заметим, что хотя
выигрыш в ситуации (3;3) также равен 2 =
=
, она не является седловой точкой,
т.к. этот выигрыш не является максимальным
среди выигрышей третьего столбца.
Пример 2
Из анализа матрицы выигрышей видно,
что
, т.е. данная матрица не имеет седловой
точки. Если игрок 1 выбирает свою чистую
максиминную стратегию i
= 2, то игрок 2, выбрав свою минимаксную
j = 2, проиграет только 20. В этом случае
игроку 1 выгодно выбрать стратегию i =
1, т.е. отклониться от своей чистой максиминной
стратегии и выиграть 30. Тогда игроку 2
будет выгодно выбрать стратегию j = 1, т.е.
отклониться от своей чистой минимаксной
стратегии и проиграть 10. В свою очередь
игрок 1 должен выбрать свою 2-ю стратегию,
чтобы выиграть 40, а игрок 2 ответит выбором
2-й стратегии и т.д.