Матричные игры

ГОУ СПО  «Слободской государственный колледж  педагогики и социальных отношений» 
 
 
 
 
 
 
 

Дисциплина  «Математические методы» 
 
 
 
 

Курсовая  работа

Матричные игры 
 
 
 
 
 
 
 
 

Выполнил

Студент очного отделения 

специальности 230105

Программное обеспечение

вычислительной техники и

автоматизированных  систем

Курс 3 группа А - 31

Лапихина  С. А.

Преподаватель

Шеренцова О. М. 
 
 
 
 
 
 
 
 
 

Слободской 2009г.

 

План.

1. Введение.
2. Матричные игры и методы их решения.
1. Основные понятия теории игр.
2. Постановка матричной игры и построение модели задачи.
3. Оптимальные стратегии. Седловая точка.
4. Смешанные стратегии.
5. Геометрический метод решения задач 2 х 2, 2 х n, 2 x m.
6. Нахождение решения на примере задачи.
3. Биматричные игры.
1. Примеры биматричных игр. Смешанные стратегии.
2. 2 х 2 – биматричные игры. Ситуации равновесия.
3. Нахождение решений на примере задачи.
4. Заключение.
5. Список литературы.

 

      1. Введение.

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

 

      2. Матричные игры  и методы их  решения.

     Основные  понятия теории игр.

     Термин  «игра» применяется для обозначения  совокупности правил и соглашений, которыми руководствуются субъекты, поведение которых здесь рассматривается. Игра – упрощенная модель конфликта. Для решения конфликтных ситуаций разработан специальный аппарат – теория игр. Стороны, участвующие в игре – игроки. Исход игры называется выигрышем. Правила – система условий определяющая: 1) варианты действия игроков, 2) объем информации каждого игрока о поведении партнеров, 3) выигрыш к которому приводит каждая совокупность действий. Как правило, выигрыш (или проигрыш) может быть задан количественно; например, можно оценить проигрыш нулем, выигрыш единицей, а ничью в ½. Игра парная, если в ней два игрока и множественной если больше. Игра, в которой выигрыш одного игрока – проигрыш второго – игра с нулевой суммой или антагонистической. Ход игрока – выбор и осуществление одного из предусмотренных правилами действий. Ходы могут быть личными и случайными. Личный ход – это сознательный выбор игроком одного из возможных действий (например, ход в шахматной партии). Случайный ход – это случайно выбранное действие (выбор карты из перетасованной колоды). Стратегией игрока называется совокупность правил, определяющих выбор его действия при каждом личном ходе в зависимости от сложившейся ситуации. Игра называется конечной, если у каждого игрока имеется конечное число стратегий, и бесконечной – в противном случае. Для того чтобы найти решение игры, следует для каждого игрока найти стратегию, которая удовлетворяет условию оптимальности, т.е. один игрок должен получить максимальный выигрыш, в то же время второй игрок должен иметь минимальный проигрыш. Такие стратегии называют оптимальными, оптимальные стратегии должны удовлетворять условию устойчивости, т.е. любому игроку было невыгодно отклонятся от выбранной стратегии.

 

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

     Пусть у игрока А есть m возможных ходов (стратегий) А₁, А₂, .., А_m, а у игрока В есть n возможных ходов (стратегий) В₁, В₂, .., В_n. Если игрок А сделает ход А_i, а игрок В сделает ход В_j, то эти ходы A_i и B_j однозначно определяют исход игры aij для игрока А и bij для игока В. Для удобства эти числа записывают в виде платежных матриц размера m x n (как всегда первый индекс – номер строки, второй – номер столбца, т.е. стратегии А указаны по строкам, стратегии В – по столбцам):

      a₁₁  a₁₂  … a_1n                        b₁₁  b₁₂  … b_1n

     a₂₁  a₂₂  … a_2n     = A   b₂₁  b₂₂  … b_2n        = B

       …   …    …   …     …   ….   … ….

     a_m1 a_m2 … a_mn       b_m1 b_m2 … b_mn 

     У каждого игрока получается своя матрица. Это так называемая биматричная  игра. Но сначала мы ограничимся  случаем, когда интересы сторон А и В противоположны (частный случай биматричной игры, о которой будет говорится далее), т.е. выигрыш игрока А это проигрыш игрока В (А + В = 0, А= - В, a_ij = - b_ij), в этом случае можно ограничится только одной матрицей – матрицей игрока А. Такие игры называют матричные.

     Пример: Игроки А и В играют в следующую игру. Игрок А записывает одно из трех чисел 1, 2, 3, игрок В записывает одно из двух чисел 1, 2, если сумма чисел четная, то выигрыш игрока А, иначе выигрыш игрока В.

     Нетрудно заметить, что a₁+b₁=2 – выигрыш игрока А, a₁+b₂=3 – проигрыш игрока А, далее заполняем по аналогии, при этом судим, что если получившееся число положительное, то и выигрыш игрока А положительный, иначе выгоднее считать выигрыш игрока А отрицательным.

       

 

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

     С матрицей игры А связано несколько  понятий.

     Нижняя  цена игры a = max(i) min(j) a_ij (сначала находим минимум в каждой строке, затем из минимумов находим максимум). Это станет гарантированным выигрышем игрока А при любой стратегии игрока В.

     Верхняя цена игры b = min(j) max(i) a_ij (сначала находиммаксимум в каждом столбце, а потом из полученных максимумов находим минимум). Это станет гарантированным проигрышем игрока В при любой стратегии игрока А. Очевидно, что a ≤ b. Случай, когда a=b рассматривается отдельно, о цене игры говорят, что v=a=b. Соответственно стратегии являются оптимальными, а саму игру именуют игрой с седловой точкой. Где v и есть седловая точка. 

     Исходя  из того, что верхняя и нижняя стоимость игры равны «4» делаем вывод, что оптимальными стратегиями в данном примере станут стратегии А₂ и В₃, при этом цена игры и седловая точка будет равна «4»

 

      Смешанные стратегии.

     Если  игра не имеет Седловой точки, то применение чистых стратегий не приводит к оптимальному решению задачи. В таком случае получить решение задачи можно случайным  образом чередуя чистые стратегии. Смешанной стратегией игрока А считается применение чистых стратегий А₁, А₂, .., А_i, .., А_m с вероятностями p₁, p₂, .., p_i, .., p_m, причем сумма вероятностей равна одному: ∑p_i = 1. Смешанные стратегии игрока А записываются в виде матрицы:

          А₁, А₂, .., А_i, .., А_m   

     S_a =     или строки S_a = (p₁, p₂, .., p_i, .., p_m)

                 p₁,  p₂,  .., p_i,  .., p_m

     Аналогично  смешанные стратегии игрока В  обозначаются

              B₁, B₂, .., B_i, .., B_m   

     S_b =     или строки S_b = (q₁, q₂, .., q_i, .., q_m)

              p₁, p₂,  .., p_i, .., p_m

     где сумма вероятностей стратегий равна: ∑q_i = 1

     На  основании принципа минимакса определяется оптимальное решение игры: это  пара оптимальных стратегий S_a*, S_b* в общем случаи смешанных, обладающих следующим свойством: если один из игроков придерживается своей оптимальной стратегии, то второму не выгодно отклонятся от своей. Выигрыш соответствует оптимальному решению, называется ценой игры v. При этом выполняется неравенство: α ≤ v ≤ β, где α и β нижняя и верхняя стоимость игры.

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

 

      Геометрический метод  решения задач 2 x 2, 2 x n, m x 2.

      Решение игры 2 х 2 допускает геометрическую интерпретацию. Пусть игра задана платежной матрицей P = a(_ij), i,j = 1,2 по оси абсцисс отложим единичный отрезок А₁, А₂; точка А₁(х = 0) отображает стратегию А₁, а все промежуточные точки этого отрезка – смешанные стратегии SA первого игрока, причем расстояние от S_A до правого конца отрезка – это вероятность p₁ стратегии A₁,растояние до левого конца – вероятность p₂ стратегии А₂. На перпендикулярных осях откладываем выигрыши при стратегии А₁ и А₂ соответственно. Если второй игрок примет стратегию В₁, то она дает выигрыши а₁₁ и а₂₁ на осях соответствующим стратегиям А₁ и А₂. Обозначим эти точки на осях буквой В₁. Средний выигрыш v₁ равен ординате точки M₁, которая лежит на отрезке В₁В₁ и имеет абсциссу S_a. Аналогично строим отрезок В₂В₂ соответствующий применению вторым игроком стратегии В₂, при этом средний выигрыш v₂ равен ординате точки М₂. В соответствии с принципом минимакса оптимальная стратегия S*_a такова, что минимальный выигрыш игрока А (при наихудшем поведении игрока В) обращается в максимум. Ординаты точек, лежащих на ломаной показывают минимальный выигрыш игрока А при использовании любой смешанной стратегии игрока В. Следственно нижняя огибающая ломаная и является оптимальным решением для игрока А. Графический метод применяется для решения игр 2 х 2, 2 x n, m x 2, так как это можно выразить через две оси: для ситуации 2 х 2 это рассмотрение от лица любого игрока, при этом решением будет нижняя огибающая для игрока А и верхняя огибающая для игрока В,